traits.hpp revision 1.1.1.4 
1// -*- C++ -*-
2
3// Copyright (C) 2005-2015 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library.  This library is free
6// software; you can redistribute it and/or modify it under the terms
7// of the GNU General Public License as published by the Free Software
8// Foundation; either version 3, or (at your option) any later
9// version.
10
11// This library is distributed in the hope that it will be useful, but
12// WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14// General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23// <http://www.gnu.org/licenses/>.
24
25// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
26
27// Permission to use, copy, modify, sell, and distribute this software
28// is hereby granted without fee, provided that the above copyright
29// notice appears in all copies, and that both that copyright notice
30// and this permission notice appear in supporting documentation. None
31// of the above authors, nor IBM Haifa Research Laboratories, make any
32// representation about the suitability of this software for any
33// purpose. It is provided "as is" without express or implied
34// warranty.
35
36/**
37 * @file bin_search_tree_/traits.hpp
38 * Contains an implementation for bin_search_tree_.
39 */
40
41#ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
42#define PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
43
44#include <ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp>
45#include <ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp>
46
47namespace __gnu_pbds
48{
49  namespace detail
50  {
51    /// Binary search tree traits, primary template
52    /// @ingroup traits
53    template<typename Key,
54	     typename Mapped,
55	     class Cmp_Fn,
56	     template<typename Node_CItr,
57		      class Node_Itr,
58		      class _Cmp_Fn,
59		      typename _Alloc>
60	     class Node_Update,
61	     class Node,
62	     typename _Alloc>
63    struct bin_search_tree_traits
64    {
65    private:
66      typedef types_traits<Key, Mapped, _Alloc, false> type_traits;
67
68    public:
69      typedef Node node;
70
71      typedef
72      bin_search_tree_const_it_<
73	typename _Alloc::template rebind<
74	node>::other::pointer,
75	typename type_traits::value_type,
76	typename type_traits::pointer,
77	typename type_traits::const_pointer,
78	typename type_traits::reference,
79	typename type_traits::const_reference,
80	true,
81	_Alloc>
82      point_const_iterator;
83
84      typedef
85      bin_search_tree_it_<
86	typename _Alloc::template rebind<
87	node>::other::pointer,
88	typename type_traits::value_type,
89	typename type_traits::pointer,
90	typename type_traits::const_pointer,
91	typename type_traits::reference,
92	typename type_traits::const_reference,
93	true,
94	_Alloc>
95      point_iterator;
96
97      typedef
98      bin_search_tree_const_it_<
99	typename _Alloc::template rebind<
100	node>::other::pointer,
101	typename type_traits::value_type,
102	typename type_traits::pointer,
103	typename type_traits::const_pointer,
104	typename type_traits::reference,
105	typename type_traits::const_reference,
106	false,
107	_Alloc>
108      const_reverse_iterator;
109
110      typedef
111      bin_search_tree_it_<
112	typename _Alloc::template rebind<
113	node>::other::pointer,
114	typename type_traits::value_type,
115	typename type_traits::pointer,
116	typename type_traits::const_pointer,
117	typename type_traits::reference,
118	typename type_traits::const_reference,
119	false,
120	_Alloc>
121      reverse_iterator;
122
123      /// This is an iterator to an iterator: it iterates over nodes,
124      /// and de-referencing it returns one of the tree's iterators.
125      typedef
126      bin_search_tree_const_node_it_<
127	Node,
128	point_const_iterator,
129	point_iterator,
130	_Alloc>
131      node_const_iterator;
132
133      typedef
134      bin_search_tree_node_it_<
135	Node,
136	point_const_iterator,
137	point_iterator,
138	_Alloc>
139      node_iterator;
140
141      typedef
142      Node_Update<
143	node_const_iterator,
144	node_iterator,
145	Cmp_Fn,
146	_Alloc>
147      node_update;
148
149      typedef
150      __gnu_pbds::null_node_update<
151	node_const_iterator,
152	node_iterator,
153	Cmp_Fn,
154	_Alloc>*
155      null_node_update_pointer;
156    };
157
158    /// Specialization.
159    /// @ingroup traits
160    template<typename Key,
161	     class Cmp_Fn,
162	     template<typename Node_CItr,
163		      class Node_Itr,
164		      class _Cmp_Fn,
165		      typename _Alloc>
166	     class Node_Update,
167	     class Node,
168	     typename _Alloc>
169    struct
170    bin_search_tree_traits<Key, null_type, Cmp_Fn, Node_Update, Node, _Alloc>
171    {
172    private:
173      typedef types_traits<Key, null_type, _Alloc, false> type_traits;
174
175    public:
176      typedef Node node;
177
178      typedef
179      bin_search_tree_const_it_<
180	typename _Alloc::template rebind<
181	node>::other::pointer,
182	typename type_traits::value_type,
183	typename type_traits::pointer,
184	typename type_traits::const_pointer,
185	typename type_traits::reference,
186	typename type_traits::const_reference,
187	true,
188	_Alloc>
189      point_const_iterator;
190
191      typedef point_const_iterator point_iterator;
192
193      typedef
194      bin_search_tree_const_it_<
195	typename _Alloc::template rebind<
196	node>::other::pointer,
197	typename type_traits::value_type,
198	typename type_traits::pointer,
199	typename type_traits::const_pointer,
200	typename type_traits::reference,
201	typename type_traits::const_reference,
202	false,
203	_Alloc>
204      const_reverse_iterator;
205
206      typedef const_reverse_iterator reverse_iterator;
207
208      /// This is an iterator to an iterator: it iterates over nodes,
209      /// and de-referencing it returns one of the tree's iterators.
210      typedef
211      bin_search_tree_const_node_it_<
212	Node,
213	point_const_iterator,
214	point_iterator,
215	_Alloc>
216      node_const_iterator;
217
218      typedef node_const_iterator node_iterator;
219
220      typedef
221      Node_Update<node_const_iterator, node_iterator, Cmp_Fn, _Alloc>
222      node_update;
223
224      typedef
225      __gnu_pbds::null_node_update<
226	node_const_iterator,
227	node_iterator,
228	Cmp_Fn,
229	_Alloc>*
230      null_node_update_pointer;
231    };
232
233  } // namespace detail
234} // namespace __gnu_pbds
235
236#endif // #ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
237