traits.hpp revision 169691 
1// -*- C++ -*-
2
3// Copyright (C) 2005, 2006 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 2, 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// You should have received a copy of the GNU General Public License
17// along with this library; see the file COPYING.  If not, write to
18// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19// MA 02111-1307, USA.
20
21// As a special exception, you may use this file as part of a free
22// software library without restriction.  Specifically, if other files
23// instantiate templates or use macros or inline functions from this
24// file, or you compile this file and link it with other files to
25// produce an executable, this file does not by itself cause the
26// resulting executable to be covered by the GNU General Public
27// License.  This exception does not however invalidate any other
28// reasons why the executable file might be covered by the GNU General
29// Public License.
30
31// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
32
33// Permission to use, copy, modify, sell, and distribute this software
34// is hereby granted without fee, provided that the above copyright
35// notice appears in all copies, and that both that copyright notice
36// and this permission notice appear in supporting documentation. None
37// of the above authors, nor IBM Haifa Research Laboratories, make any
38// representation about the suitability of this software for any
39// purpose. It is provided "as is" without express or implied
40// warranty.
41
42/**
43 * @file traits.hpp
44 * Contains an implementation for bin_search_tree_.
45 */
46
47#ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
48#define PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
49
50#include <ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp>
51#include <ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp>
52
53namespace pb_ds
54{
55  namespace detail
56  {
57
58    template<typename Key,
59	     typename Mapped,
60	     class Cmp_Fn,
61	     template<typename Const_Node_Iterator,
62		      class Node_Iterator,
63		      class Cmp_Fn,
64		      class Allocator>
65    class Node_Update,
66	     class Node,
67	     class Allocator>
68    struct bin_search_tree_traits
69    {
70    private:
71      typedef
72      types_traits<
73      Key,
74      Mapped,
75      Allocator,
76      false>
77      type_traits;
78
79    public:
80      typedef Node node;
81
82      typedef
83      bin_search_tree_const_it_<
84	typename Allocator::template rebind<
85	node>::other::pointer,
86	typename type_traits::value_type,
87	typename type_traits::pointer,
88	typename type_traits::const_pointer,
89	typename type_traits::reference,
90	typename type_traits::const_reference,
91	true,
92	Allocator>
93      const_point_iterator;
94
95      typedef
96      bin_search_tree_it_<
97	typename Allocator::template rebind<
98	node>::other::pointer,
99	typename type_traits::value_type,
100	typename type_traits::pointer,
101	typename type_traits::const_pointer,
102	typename type_traits::reference,
103	typename type_traits::const_reference,
104	true,
105	Allocator>
106      point_iterator;
107
108      typedef
109      bin_search_tree_const_it_<
110	typename Allocator::template rebind<
111	node>::other::pointer,
112	typename type_traits::value_type,
113	typename type_traits::pointer,
114	typename type_traits::const_pointer,
115	typename type_traits::reference,
116	typename type_traits::const_reference,
117	false,
118	Allocator>
119      const_reverse_iterator;
120
121      typedef
122      bin_search_tree_it_<
123	typename Allocator::template rebind<
124	node>::other::pointer,
125	typename type_traits::value_type,
126	typename type_traits::pointer,
127	typename type_traits::const_pointer,
128	typename type_traits::reference,
129	typename type_traits::const_reference,
130	false,
131	Allocator>
132      reverse_iterator;
133
134      typedef
135      bin_search_tree_const_node_it_<
136	Node,
137	const_point_iterator,
138	point_iterator,
139	Allocator>
140      const_node_iterator;
141
142      typedef
143      bin_search_tree_node_it_<
144	Node,
145	const_point_iterator,
146	point_iterator,
147	Allocator>
148      node_iterator;
149
150      typedef
151      Node_Update<
152	const_node_iterator,
153	node_iterator,
154	Cmp_Fn,
155	Allocator>
156      node_update;
157
158      typedef
159      pb_ds::null_tree_node_update<
160	const_node_iterator,
161	node_iterator,
162	Cmp_Fn,
163	Allocator>*
164      null_node_update_pointer;
165    };
166
167    template<typename Key,
168	     class Cmp_Fn,
169	     template<typename Const_Node_Iterator,
170		      class Node_Iterator,
171		      class Cmp_Fn,
172		      class Allocator>
173    class Node_Update,
174	     class Node,
175	     class Allocator>
176    struct bin_search_tree_traits<
177      Key,
178      null_mapped_type,
179      Cmp_Fn,
180      Node_Update,
181      Node,
182      Allocator>
183    {
184    private:
185      typedef
186      types_traits<
187      Key,
188      null_mapped_type,
189      Allocator,
190      false>
191      type_traits;
192
193    public:
194      typedef Node node;
195
196      typedef
197      bin_search_tree_const_it_<
198	typename Allocator::template rebind<
199	node>::other::pointer,
200	typename type_traits::value_type,
201	typename type_traits::pointer,
202	typename type_traits::const_pointer,
203	typename type_traits::reference,
204	typename type_traits::const_reference,
205	true,
206	Allocator>
207      const_point_iterator;
208
209      typedef const_point_iterator point_iterator;
210
211      typedef
212      bin_search_tree_const_it_<
213	typename Allocator::template rebind<
214	node>::other::pointer,
215	typename type_traits::value_type,
216	typename type_traits::pointer,
217	typename type_traits::const_pointer,
218	typename type_traits::reference,
219	typename type_traits::const_reference,
220	false,
221	Allocator>
222      const_reverse_iterator;
223
224      typedef const_reverse_iterator reverse_iterator;
225
226      typedef
227      bin_search_tree_const_node_it_<
228	Node,
229	const_point_iterator,
230	point_iterator,
231	Allocator>
232      const_node_iterator;
233
234      typedef const_node_iterator node_iterator;
235
236      typedef
237      Node_Update<
238	const_node_iterator,
239	node_iterator,
240	Cmp_Fn,
241	Allocator>
242      node_update;
243
244      typedef
245      pb_ds::null_tree_node_update<
246	const_node_iterator,
247	node_iterator,
248	Cmp_Fn,
249	Allocator>*
250      null_node_update_pointer;
251    };
252
253  } // namespace detail
254} // namespace pb_ds
255
256#endif // #ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
257