1169691Skan// -*- C++ -*-
2169691Skan
3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
4169691Skan//
5169691Skan// This file is part of the GNU ISO C++ Library.  This library is free
6169691Skan// software; you can redistribute it and/or modify it under the terms
7169691Skan// of the GNU General Public License as published by the Free Software
8169691Skan// Foundation; either version 2, or (at your option) any later
9169691Skan// version.
10169691Skan
11169691Skan// This library is distributed in the hope that it will be useful, but
12169691Skan// WITHOUT ANY WARRANTY; without even the implied warranty of
13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14169691Skan// General Public License for more details.
15169691Skan
16169691Skan// You should have received a copy of the GNU General Public License
17169691Skan// along with this library; see the file COPYING.  If not, write to
18169691Skan// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19169691Skan// MA 02111-1307, USA.
20169691Skan
21169691Skan// As a special exception, you may use this file as part of a free
22169691Skan// software library without restriction.  Specifically, if other files
23169691Skan// instantiate templates or use macros or inline functions from this
24169691Skan// file, or you compile this file and link it with other files to
25169691Skan// produce an executable, this file does not by itself cause the
26169691Skan// resulting executable to be covered by the GNU General Public
27169691Skan// License.  This exception does not however invalidate any other
28169691Skan// reasons why the executable file might be covered by the GNU General
29169691Skan// Public License.
30169691Skan
31169691Skan// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
32169691Skan
33169691Skan// Permission to use, copy, modify, sell, and distribute this software
34169691Skan// is hereby granted without fee, provided that the above copyright
35169691Skan// notice appears in all copies, and that both that copyright notice
36169691Skan// and this permission notice appear in supporting documentation. None
37169691Skan// of the above authors, nor IBM Haifa Research Laboratories, make any
38169691Skan// representation about the suitability of this software for any
39169691Skan// purpose. It is provided "as is" without express or implied
40169691Skan// warranty.
41169691Skan
42169691Skan/**
43169691Skan * @file traits.hpp
44169691Skan * Contains an implementation for bin_search_tree_.
45169691Skan */
46169691Skan
47169691Skan#ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
48169691Skan#define PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
49169691Skan
50169691Skan#include <ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp>
51169691Skan#include <ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp>
52169691Skan
53169691Skannamespace pb_ds
54169691Skan{
55169691Skan  namespace detail
56169691Skan  {
57169691Skan
58169691Skan    template<typename Key,
59169691Skan	     typename Mapped,
60169691Skan	     class Cmp_Fn,
61169691Skan	     template<typename Const_Node_Iterator,
62169691Skan		      class Node_Iterator,
63169691Skan		      class Cmp_Fn,
64169691Skan		      class Allocator>
65169691Skan    class Node_Update,
66169691Skan	     class Node,
67169691Skan	     class Allocator>
68169691Skan    struct bin_search_tree_traits
69169691Skan    {
70169691Skan    private:
71169691Skan      typedef
72169691Skan      types_traits<
73169691Skan      Key,
74169691Skan      Mapped,
75169691Skan      Allocator,
76169691Skan      false>
77169691Skan      type_traits;
78169691Skan
79169691Skan    public:
80169691Skan      typedef Node node;
81169691Skan
82169691Skan      typedef
83169691Skan      bin_search_tree_const_it_<
84169691Skan	typename Allocator::template rebind<
85169691Skan	node>::other::pointer,
86169691Skan	typename type_traits::value_type,
87169691Skan	typename type_traits::pointer,
88169691Skan	typename type_traits::const_pointer,
89169691Skan	typename type_traits::reference,
90169691Skan	typename type_traits::const_reference,
91169691Skan	true,
92169691Skan	Allocator>
93169691Skan      const_point_iterator;
94169691Skan
95169691Skan      typedef
96169691Skan      bin_search_tree_it_<
97169691Skan	typename Allocator::template rebind<
98169691Skan	node>::other::pointer,
99169691Skan	typename type_traits::value_type,
100169691Skan	typename type_traits::pointer,
101169691Skan	typename type_traits::const_pointer,
102169691Skan	typename type_traits::reference,
103169691Skan	typename type_traits::const_reference,
104169691Skan	true,
105169691Skan	Allocator>
106169691Skan      point_iterator;
107169691Skan
108169691Skan      typedef
109169691Skan      bin_search_tree_const_it_<
110169691Skan	typename Allocator::template rebind<
111169691Skan	node>::other::pointer,
112169691Skan	typename type_traits::value_type,
113169691Skan	typename type_traits::pointer,
114169691Skan	typename type_traits::const_pointer,
115169691Skan	typename type_traits::reference,
116169691Skan	typename type_traits::const_reference,
117169691Skan	false,
118169691Skan	Allocator>
119169691Skan      const_reverse_iterator;
120169691Skan
121169691Skan      typedef
122169691Skan      bin_search_tree_it_<
123169691Skan	typename Allocator::template rebind<
124169691Skan	node>::other::pointer,
125169691Skan	typename type_traits::value_type,
126169691Skan	typename type_traits::pointer,
127169691Skan	typename type_traits::const_pointer,
128169691Skan	typename type_traits::reference,
129169691Skan	typename type_traits::const_reference,
130169691Skan	false,
131169691Skan	Allocator>
132169691Skan      reverse_iterator;
133169691Skan
134169691Skan      typedef
135169691Skan      bin_search_tree_const_node_it_<
136169691Skan	Node,
137169691Skan	const_point_iterator,
138169691Skan	point_iterator,
139169691Skan	Allocator>
140169691Skan      const_node_iterator;
141169691Skan
142169691Skan      typedef
143169691Skan      bin_search_tree_node_it_<
144169691Skan	Node,
145169691Skan	const_point_iterator,
146169691Skan	point_iterator,
147169691Skan	Allocator>
148169691Skan      node_iterator;
149169691Skan
150169691Skan      typedef
151169691Skan      Node_Update<
152169691Skan	const_node_iterator,
153169691Skan	node_iterator,
154169691Skan	Cmp_Fn,
155169691Skan	Allocator>
156169691Skan      node_update;
157169691Skan
158169691Skan      typedef
159169691Skan      pb_ds::null_tree_node_update<
160169691Skan	const_node_iterator,
161169691Skan	node_iterator,
162169691Skan	Cmp_Fn,
163169691Skan	Allocator>*
164169691Skan      null_node_update_pointer;
165169691Skan    };
166169691Skan
167169691Skan    template<typename Key,
168169691Skan	     class Cmp_Fn,
169169691Skan	     template<typename Const_Node_Iterator,
170169691Skan		      class Node_Iterator,
171169691Skan		      class Cmp_Fn,
172169691Skan		      class Allocator>
173169691Skan    class Node_Update,
174169691Skan	     class Node,
175169691Skan	     class Allocator>
176169691Skan    struct bin_search_tree_traits<
177169691Skan      Key,
178169691Skan      null_mapped_type,
179169691Skan      Cmp_Fn,
180169691Skan      Node_Update,
181169691Skan      Node,
182169691Skan      Allocator>
183169691Skan    {
184169691Skan    private:
185169691Skan      typedef
186169691Skan      types_traits<
187169691Skan      Key,
188169691Skan      null_mapped_type,
189169691Skan      Allocator,
190169691Skan      false>
191169691Skan      type_traits;
192169691Skan
193169691Skan    public:
194169691Skan      typedef Node node;
195169691Skan
196169691Skan      typedef
197169691Skan      bin_search_tree_const_it_<
198169691Skan	typename Allocator::template rebind<
199169691Skan	node>::other::pointer,
200169691Skan	typename type_traits::value_type,
201169691Skan	typename type_traits::pointer,
202169691Skan	typename type_traits::const_pointer,
203169691Skan	typename type_traits::reference,
204169691Skan	typename type_traits::const_reference,
205169691Skan	true,
206169691Skan	Allocator>
207169691Skan      const_point_iterator;
208169691Skan
209169691Skan      typedef const_point_iterator point_iterator;
210169691Skan
211169691Skan      typedef
212169691Skan      bin_search_tree_const_it_<
213169691Skan	typename Allocator::template rebind<
214169691Skan	node>::other::pointer,
215169691Skan	typename type_traits::value_type,
216169691Skan	typename type_traits::pointer,
217169691Skan	typename type_traits::const_pointer,
218169691Skan	typename type_traits::reference,
219169691Skan	typename type_traits::const_reference,
220169691Skan	false,
221169691Skan	Allocator>
222169691Skan      const_reverse_iterator;
223169691Skan
224169691Skan      typedef const_reverse_iterator reverse_iterator;
225169691Skan
226169691Skan      typedef
227169691Skan      bin_search_tree_const_node_it_<
228169691Skan	Node,
229169691Skan	const_point_iterator,
230169691Skan	point_iterator,
231169691Skan	Allocator>
232169691Skan      const_node_iterator;
233169691Skan
234169691Skan      typedef const_node_iterator node_iterator;
235169691Skan
236169691Skan      typedef
237169691Skan      Node_Update<
238169691Skan	const_node_iterator,
239169691Skan	node_iterator,
240169691Skan	Cmp_Fn,
241169691Skan	Allocator>
242169691Skan      node_update;
243169691Skan
244169691Skan      typedef
245169691Skan      pb_ds::null_tree_node_update<
246169691Skan	const_node_iterator,
247169691Skan	node_iterator,
248169691Skan	Cmp_Fn,
249169691Skan	Allocator>*
250169691Skan      null_node_update_pointer;
251169691Skan    };
252169691Skan
253169691Skan  } // namespace detail
254169691Skan} // namespace pb_ds
255169691Skan
256169691Skan#endif // #ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
257