libstdc++
ov_tree_map_/traits.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005-2021 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 
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,
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
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
92  value_type,
93  metadata_type,
94  _Alloc>
96 
97  typedef
99  value_type,
100  metadata_type,
101  _Alloc>
103 
104  typedef
105  Node_Update<
108  Cmp_Fn,
109  _Alloc>
110  node_update;
111 
112  typedef
116  Cmp_Fn,
117  _Alloc>*
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
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
163  value_type,
164  metadata_type,
165  _Alloc>
167 
169 
170  typedef
171  Node_Update<
174  Cmp_Fn,
175  _Alloc>
176  node_update;
177 
178  typedef
182  Cmp_Fn,
183  _Alloc>*
185  };
186  } // namespace detail
187 } // namespace __gnu_pbds
188 
189 #endif // #ifndef PB_DS_OV_TREE_NODE_AND_IT_TRAITS_HPP
190 
A null node updator, indicating that no node updates are required.
Ordered-vector tree.
ov_tree_node_const_it_< value_type, metadata_type, _Alloc > node_const_iterator
This is an iterator to an iterator: it iterates over nodes, and de-referencing it returns one of the ...
Tree traits class, primary template.
Traits for abstract types.
Represents no type, or absence of type, for template tricks.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:211
ov_tree_node_const_it_< value_type, metadata_type, _Alloc > node_const_iterator
This is an iterator to an iterator: it iterates over nodes, and de-referencing it returns one of the ...
GNU extensions for policy-based data structures for public use.