1 // -*- C++ -*-
2 
3 // Copyright (C) 2005, 2006, 2009 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 ov_tree_map_/traits.hpp
38  * Contains an implementation class for ov_tree_.
39  */
40 
41 #ifndef PB_DS_OV_TREE_NODE_AND_IT_TRAITS_HPP
42 #define PB_DS_OV_TREE_NODE_AND_IT_TRAITS_HPP
43 
44 #include <ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp>
45 
46 namespace __gnu_pbds
47 {
48   namespace detail
49   {
50     /// Tree traits.
51     /// @ingroup traits
52     template<typename Key,
53 	     typename Mapped,
54 	     class Cmp_Fn,
55 	     template<typename Node_CItr,
56 		      class Node_Itr,
57 		      class Cmp_Fn_,
58 		      typename _Alloc_>
59     class Node_Update,
60 	     typename _Alloc>
61     struct tree_traits<
62       Key,
63       Mapped,
64       Cmp_Fn,
65       Node_Update,
66       ov_tree_tag,
67       _Alloc>
68     {
69     private:
70       typedef
71       typename types_traits<
72       Key,
73       Mapped,
74       _Alloc,
75       false>::value_type
76       value_type;
77 
78     public:
79       typedef
80       typename tree_node_metadata_dispatch<
81       Key,
82       Mapped,
83       Cmp_Fn,
84       Node_Update,
85       _Alloc>::type
86       metadata_type;
87 
88       /// This is an iterator to an iterator: it iterates over nodes,
89       /// and de-referencing it returns one of the tree's iterators.
90       typedef
91       ov_tree_node_const_it_<
92 	value_type,
93 	metadata_type,
94 	_Alloc>
95       node_const_iterator;
96 
97       typedef
98       ov_tree_node_it_<
99 	value_type,
100 	metadata_type,
101 	_Alloc>
102       node_iterator;
103 
104       typedef
105       Node_Update<
106 	node_const_iterator,
107 	node_iterator,
108 	Cmp_Fn,
109 	_Alloc>
110       node_update;
111 
112       typedef
113       __gnu_pbds::null_node_update<
114 	node_const_iterator,
115 	node_iterator,
116 	Cmp_Fn,
117 	_Alloc>*
118       null_node_update_pointer;
119     };
120 
121 
122     /// Specialization.
123     /// @ingroup traits
124     template<typename Key,
125 	     class Cmp_Fn,
126 	     template<typename Node_CItr,
127 		      class Node_Itr,
128 		      class Cmp_Fn_,
129 		      typename _Alloc_>
130     class Node_Update,
131 	     typename _Alloc>
132     struct tree_traits<
133       Key,
134       null_type,
135       Cmp_Fn,
136       Node_Update,
137       ov_tree_tag,
138       _Alloc>
139     {
140     private:
141       typedef
142       typename types_traits<
143       Key,
144       null_type,
145       _Alloc,
146       false>::value_type
147       value_type;
148 
149     public:
150       typedef
151       typename tree_node_metadata_dispatch<
152       Key,
153       null_type,
154       Cmp_Fn,
155       Node_Update,
156       _Alloc>::type
157       metadata_type;
158 
159       /// This is an iterator to an iterator: it iterates over nodes,
160       /// and de-referencing it returns one of the tree's iterators.
161       typedef
162       ov_tree_node_const_it_<
163 	value_type,
164 	metadata_type,
165 	_Alloc>
166       node_const_iterator;
167 
168       typedef node_const_iterator node_iterator;
169 
170       typedef
171       Node_Update<
172 	node_const_iterator,
173 	node_const_iterator,
174 	Cmp_Fn,
175 	_Alloc>
176       node_update;
177 
178       typedef
179       __gnu_pbds::null_node_update<
180 	node_const_iterator,
181 	node_iterator,
182 	Cmp_Fn,
183 	_Alloc>*
184       null_node_update_pointer;
185     };
186   } // namespace detail
187 } // namespace __gnu_pbds
188 
189 #endif // #ifndef PB_DS_OV_TREE_NODE_AND_IT_TRAITS_HPP
190 
191