traits.hpp revision 169692 
138465Smsmith// -*- C++ -*-
238465Smsmith
338465Smsmith// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
438465Smsmith//
538465Smsmith// This file is part of the GNU ISO C++ Library.  This library is free
638465Smsmith// software; you can redistribute it and/or modify it under the terms
738465Smsmith// of the GNU General Public License as published by the Free Software
838465Smsmith// Foundation; either version 2, or (at your option) any later
938465Smsmith// version.
1038465Smsmith
1138465Smsmith// This library is distributed in the hope that it will be useful, but
1238465Smsmith// WITHOUT ANY WARRANTY; without even the implied warranty of
1338465Smsmith// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
1438465Smsmith// General Public License for more details.
1538465Smsmith
1638465Smsmith// You should have received a copy of the GNU General Public License
1738465Smsmith// along with this library; see the file COPYING.  If not, write to
1838465Smsmith// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
1938465Smsmith// MA 02111-1307, USA.
2038465Smsmith
2138465Smsmith// As a special exception, you may use this file as part of a free
2238465Smsmith// software library without restriction.  Specifically, if other files
2338465Smsmith// instantiate templates or use macros or inline functions from this
2438465Smsmith// file, or you compile this file and link it with other files to
2538465Smsmith// produce an executable, this file does not by itself cause the
2639673Sdfr// resulting executable to be covered by the GNU General Public
2738465Smsmith// License.  This exception does not however invalidate any other
2838465Smsmith// reasons why the executable file might be covered by the GNU General
2938465Smsmith// Public License.
3038465Smsmith
3138764Smsmith// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
3238465Smsmith
3338465Smsmith// Permission to use, copy, modify, sell, and distribute this software
3438465Smsmith// is hereby granted without fee, provided that the above copyright
3538465Smsmith// notice appears in all copies, and that both that copyright notice
3638465Smsmith// and this permission notice appear in supporting documentation. None
3738465Smsmith// of the above authors, nor IBM Haifa Research Laboratories, make any
3838465Smsmith// representation about the suitability of this software for any
3938465Smsmith// purpose. It is provided "as is" without express or implied
4038465Smsmith// warranty.
4138465Smsmith
4238465Smsmith/**
4338465Smsmith * @file traits.hpp
4438465Smsmith * Contains an implementation for bin_search_tree_.
4538465Smsmith */
4638465Smsmith
4738465Smsmith#ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
4838465Smsmith#define PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
4938465Smsmith
5038465Smsmith#include <ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp>
5138465Smsmith#include <ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp>
5238465Smsmith
5338465Smsmithnamespace pb_ds
5438465Smsmith{
5538465Smsmith  namespace detail
5638465Smsmith  {
5738764Smsmith
5838764Smsmith    template<typename Key,
5938764Smsmith	     typename Mapped,
6038764Smsmith	     class Cmp_Fn,
6138764Smsmith	     template<typename Const_Node_Iterator,
6238764Smsmith		      class Node_Iterator,
6338764Smsmith		      class Cmp_Fn,
6438764Smsmith		      class Allocator>
6538764Smsmith    class Node_Update,
6638764Smsmith	     class Node,
6738764Smsmith	     class Allocator>
6838764Smsmith    struct bin_search_tree_traits
6938764Smsmith    {
7038764Smsmith    private:
7138764Smsmith      typedef
7238764Smsmith      types_traits<
7338764Smsmith      Key,
7438764Smsmith      Mapped,
7538764Smsmith      Allocator,
7638764Smsmith      false>
7738764Smsmith      type_traits;
7838764Smsmith
7938764Smsmith    public:
8038764Smsmith      typedef Node node;
8138764Smsmith
8238764Smsmith      typedef
8338764Smsmith      bin_search_tree_const_it_<
8438764Smsmith	typename Allocator::template rebind<
8538764Smsmith	node>::other::pointer,
8638764Smsmith	typename type_traits::value_type,
8738764Smsmith	typename type_traits::pointer,
8838764Smsmith	typename type_traits::const_pointer,
8938764Smsmith	typename type_traits::reference,
9039472Smsmith	typename type_traits::const_reference,
9139472Smsmith	true,
9239472Smsmith	Allocator>
9339472Smsmith      const_point_iterator;
9439472Smsmith
9539472Smsmith      typedef
9639472Smsmith      bin_search_tree_it_<
9739472Smsmith	typename Allocator::template rebind<
9839472Smsmith	node>::other::pointer,
9939472Smsmith	typename type_traits::value_type,
10039472Smsmith	typename type_traits::pointer,
10139472Smsmith	typename type_traits::const_pointer,
10239472Smsmith	typename type_traits::reference,
10339472Smsmith	typename type_traits::const_reference,
10439673Sdfr	true,
10539472Smsmith	Allocator>
10639472Smsmith      point_iterator;
10739472Smsmith
10839472Smsmith      typedef
10939472Smsmith      bin_search_tree_const_it_<
11039472Smsmith	typename Allocator::template rebind<
11139472Smsmith	node>::other::pointer,
11239472Smsmith	typename type_traits::value_type,
11339472Smsmith	typename type_traits::pointer,
11439472Smsmith	typename type_traits::const_pointer,
11539472Smsmith	typename type_traits::reference,
11639472Smsmith	typename type_traits::const_reference,
11739472Smsmith	false,
11839472Smsmith	Allocator>
11939472Smsmith      const_reverse_iterator;
12039472Smsmith
12139472Smsmith      typedef
12239472Smsmith      bin_search_tree_it_<
12339472Smsmith	typename Allocator::template rebind<
12439472Smsmith	node>::other::pointer,
12539472Smsmith	typename type_traits::value_type,
12639472Smsmith	typename type_traits::pointer,
12739472Smsmith	typename type_traits::const_pointer,
12839472Smsmith	typename type_traits::reference,
12939472Smsmith	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