libstdc++
ov_tree_map_.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_/ov_tree_map_.hpp
38 * Contains an implementation class for ov_tree.
39 */
40
41#include <map>
42#include <set>
43#include <ext/pb_ds/exception.hpp>
44#include <ext/pb_ds/tree_policy.hpp>
45#include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp>
46#include <ext/pb_ds/detail/types_traits.hpp>
47#include <ext/pb_ds/detail/type_utils.hpp>
48#include <ext/pb_ds/detail/tree_trace_base.hpp>
49#ifdef _GLIBCXX_DEBUG
50#include <ext/pb_ds/detail/debug_map_base.hpp>
51#endif
52#include <utility>
53#include <functional>
54#include <algorithm>
55#include <vector>
56#include <assert.h>
57#include <debug/debug.h>
58
59namespace __gnu_pbds
60{
61 namespace detail
62 {
63#ifdef PB_DS_DATA_TRUE_INDICATOR
64#define PB_DS_OV_TREE_NAME ov_tree_map
65#define PB_DS_CONST_NODE_ITERATOR_NAME ov_tree_node_const_iterator_map
66#endif
67
68#ifdef PB_DS_DATA_FALSE_INDICATOR
69#define PB_DS_OV_TREE_NAME ov_tree_set
70#define PB_DS_CONST_NODE_ITERATOR_NAME ov_tree_node_const_iterator_set
71#endif
72
73#define PB_DS_CLASS_T_DEC \
74 template<typename Key, typename Mapped, typename Cmp_Fn, \
75 typename Node_And_It_Traits, typename _Alloc>
76
77#define PB_DS_CLASS_C_DEC \
78 PB_DS_OV_TREE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc>
79
80#define PB_DS_OV_TREE_TRAITS_BASE \
81 types_traits<Key, Mapped, _Alloc, false>
82
83#ifdef _GLIBCXX_DEBUG
84#define PB_DS_DEBUG_MAP_BASE_C_DEC \
85 debug_map_base<Key, eq_by_less<Key, Cmp_Fn>, \
86 typename rebind_traits<_Alloc, Key>::const_reference>
87#endif
88
89#ifdef PB_DS_TREE_TRACE
90#define PB_DS_TREE_TRACE_BASE_C_DEC \
91 tree_trace_base<typename Node_And_It_Traits::node_const_iterator, \
92 typename Node_And_It_Traits::node_iterator, \
93 Cmp_Fn, false, _Alloc>
94#endif
95
96#ifndef PB_DS_CHECK_KEY_EXISTS
97# error Missing definition
98#endif
99
100 /**
101 * @brief Ordered-vector tree associative-container.
102 * @ingroup branch-detail
103 */
104 template<typename Key, typename Mapped, typename Cmp_Fn,
105 typename Node_And_It_Traits, typename _Alloc>
106 class PB_DS_OV_TREE_NAME :
107#ifdef _GLIBCXX_DEBUG
108 protected PB_DS_DEBUG_MAP_BASE_C_DEC,
109#endif
110#ifdef PB_DS_TREE_TRACE
111 public PB_DS_TREE_TRACE_BASE_C_DEC,
112#endif
113 public Cmp_Fn,
114 public Node_And_It_Traits::node_update,
115 public PB_DS_OV_TREE_TRAITS_BASE
116 {
117 private:
118 typedef PB_DS_OV_TREE_TRAITS_BASE traits_base;
119 typedef Node_And_It_Traits traits_type;
120
121 typedef typename remove_const<typename traits_base::value_type>::type non_const_value_type;
122
123 typedef rebind_traits<_Alloc, non_const_value_type> value_alloc_traits;
124 typedef typename value_alloc_traits::allocator_type value_allocator;
125 typedef typename value_alloc_traits::pointer value_vector;
126
127#ifdef _GLIBCXX_DEBUG
128 typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base;
129#endif
130
131#ifdef PB_DS_TREE_TRACE
132 typedef PB_DS_TREE_TRACE_BASE_C_DEC trace_base;
133#endif
134
135 typedef typename traits_base::pointer mapped_pointer_;
136 typedef typename traits_base::const_pointer mapped_const_pointer_;
137
138 typedef typename traits_type::metadata_type metadata_type;
139
140 typedef rebind_traits<_Alloc, metadata_type> metadata_alloc_traits;
141 typedef typename metadata_alloc_traits::allocator_type metadata_allocator;
142 typedef typename metadata_alloc_traits::pointer metadata_pointer;
143 typedef typename metadata_alloc_traits::const_reference metadata_const_reference;
144 typedef typename metadata_alloc_traits::reference metadata_reference;
145
146 typedef typename traits_type::null_node_update_pointer
147 null_node_update_pointer;
148
149 public:
150 typedef ov_tree_tag container_category;
151 typedef _Alloc allocator_type;
152 typedef typename _Alloc::size_type size_type;
153 typedef typename _Alloc::difference_type difference_type;
154 typedef Cmp_Fn cmp_fn;
155
156 typedef typename traits_base::key_type key_type;
157 typedef typename traits_base::key_pointer key_pointer;
158 typedef typename traits_base::key_const_pointer key_const_pointer;
159 typedef typename traits_base::key_reference key_reference;
160 typedef typename traits_base::key_const_reference key_const_reference;
161 typedef typename traits_base::mapped_type mapped_type;
162 typedef typename traits_base::mapped_pointer mapped_pointer;
163 typedef typename traits_base::mapped_const_pointer mapped_const_pointer;
164 typedef typename traits_base::mapped_reference mapped_reference;
165 typedef typename traits_base::mapped_const_reference mapped_const_reference;
166 typedef typename traits_base::value_type value_type;
167 typedef typename traits_base::pointer pointer;
168 typedef typename traits_base::const_pointer const_pointer;
169 typedef typename traits_base::reference reference;
170 typedef typename traits_base::const_reference const_reference;
171
172 typedef const_pointer point_const_iterator;
173#ifdef PB_DS_DATA_TRUE_INDICATOR
174 typedef pointer point_iterator;
175#else
176 typedef point_const_iterator point_iterator;
177#endif
178
179 typedef point_iterator iterator;
180 typedef point_const_iterator const_iterator;
181
182 /// Conditional destructor.
183 template<typename Size_Type>
184 class cond_dtor
185 {
186 public:
187 cond_dtor(value_vector a_vec, iterator& r_last_it,
188 Size_Type total_size)
189 : m_a_vec(a_vec), m_r_last_it(r_last_it), m_max_size(total_size),
190 m_no_action(false)
191 { }
192
193 ~cond_dtor()
194 {
195 if (m_no_action)
196 return;
197 iterator it = m_a_vec;
198 while (it != m_r_last_it)
199 {
200 it->~value_type();
201 ++it;
202 }
203
204 if (m_max_size > 0)
205 value_allocator().deallocate(m_a_vec, m_max_size);
206 }
207
208 inline void
209 set_no_action()
210 { m_no_action = true; }
211
212 protected:
213 value_vector m_a_vec;
214 iterator& m_r_last_it;
215 const Size_Type m_max_size;
216 bool m_no_action;
217 };
218
219 typedef typename traits_type::node_update node_update;
220 typedef typename traits_type::node_iterator node_iterator;
221 typedef typename traits_type::node_const_iterator node_const_iterator;
222
223
224 PB_DS_OV_TREE_NAME();
225
226 PB_DS_OV_TREE_NAME(const Cmp_Fn&);
227
228 PB_DS_OV_TREE_NAME(const Cmp_Fn&, const node_update&);
229
230 PB_DS_OV_TREE_NAME(const PB_DS_CLASS_C_DEC&);
231
232 ~PB_DS_OV_TREE_NAME();
233
234 void
235 swap(PB_DS_CLASS_C_DEC&);
236
237 template<typename It>
238 void
239 copy_from_range(It, It);
240
241 inline size_type
242 max_size() const;
243
244 _GLIBCXX_NODISCARD inline bool
245 empty() const;
246
247 inline size_type
248 size() const;
249
250 Cmp_Fn&
251 get_cmp_fn();
252
253 const Cmp_Fn&
254 get_cmp_fn() const;
255
256 inline mapped_reference
257 operator[](key_const_reference r_key)
258 {
259#ifdef PB_DS_DATA_TRUE_INDICATOR
260 PB_DS_ASSERT_VALID((*this))
261 point_iterator it = lower_bound(r_key);
262 if (it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*it)))
263 {
264 PB_DS_CHECK_KEY_EXISTS(r_key)
265 PB_DS_ASSERT_VALID((*this))
266 return it->second;
267 }
268 return insert_new_val(it, std::make_pair(r_key, mapped_type()))->second;
269#else
270 insert(r_key);
271 return traits_base::s_null_type;
272#endif
273 }
274
275 inline std::pair<point_iterator, bool>
276 insert(const_reference r_value)
277 {
278 PB_DS_ASSERT_VALID((*this))
279 key_const_reference r_key = PB_DS_V2F(r_value);
280 point_iterator it = lower_bound(r_key);
281
282 if (it != end()&& !Cmp_Fn::operator()(r_key, PB_DS_V2F(*it)))
283 {
284 PB_DS_ASSERT_VALID((*this))
285 PB_DS_CHECK_KEY_EXISTS(r_key)
286 return std::make_pair(it, false);
287 }
288
289 return std::make_pair(insert_new_val(it, r_value), true);
290 }
291
292 inline point_iterator
293 lower_bound(key_const_reference r_key)
294 {
295 pointer it = m_a_values;
296 pointer e_it = m_a_values + m_size;
297 while (it != e_it)
298 {
299 pointer mid_it = it + ((e_it - it) >> 1);
300 if (cmp_fn::operator()(PB_DS_V2F(*mid_it), r_key))
301 it = ++mid_it;
302 else
303 e_it = mid_it;
304 }
305 return it;
306 }
307
308 inline point_const_iterator
309 lower_bound(key_const_reference r_key) const
310 { return const_cast<PB_DS_CLASS_C_DEC& >(*this).lower_bound(r_key); }
311
312 inline point_iterator
313 upper_bound(key_const_reference r_key)
314 {
315 iterator pot_it = lower_bound(r_key);
316 if (pot_it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*pot_it)))
317 {
318 PB_DS_CHECK_KEY_EXISTS(r_key)
319 return ++pot_it;
320 }
321
322 PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key)
323 return pot_it;
324 }
325
326 inline point_const_iterator
327 upper_bound(key_const_reference r_key) const
328 { return const_cast<PB_DS_CLASS_C_DEC&>(*this).upper_bound(r_key); }
329
330 inline point_iterator
331 find(key_const_reference r_key)
332 {
333 PB_DS_ASSERT_VALID((*this))
334 iterator pot_it = lower_bound(r_key);
335 if (pot_it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*pot_it)))
336 {
337 PB_DS_CHECK_KEY_EXISTS(r_key)
338 return pot_it;
339 }
340
341 PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key)
342 return end();
343 }
344
345 inline point_const_iterator
346 find(key_const_reference r_key) const
347 { return (const_cast<PB_DS_CLASS_C_DEC&>(*this).find(r_key)); }
348
349 bool
350 erase(key_const_reference);
351
352 template<typename Pred>
353 inline size_type
354 erase_if(Pred);
355
356 inline iterator
357 erase(iterator it)
358 { return erase_imp<iterator>(it); }
359
360 void
361 clear();
362
363 void
364 join(PB_DS_CLASS_C_DEC&);
365
366 void
367 split(key_const_reference, PB_DS_CLASS_C_DEC&);
368
369 inline iterator
370 begin()
371 { return m_a_values; }
372
373 inline const_iterator
374 begin() const
375 { return m_a_values; }
376
377 inline iterator
378 end()
379 { return m_end_it; }
380
381 inline const_iterator
382 end() const
383 { return m_end_it; }
384
385 /// Returns a const node_iterator corresponding to the node at the
386 /// root of the tree.
387 inline node_const_iterator
388 node_begin() const;
389
390 /// Returns a node_iterator corresponding to the node at the
391 /// root of the tree.
392 inline node_iterator
393 node_begin();
394
395 /// Returns a const node_iterator corresponding to a node just
396 /// after a leaf of the tree.
397 inline node_const_iterator
398 node_end() const;
399
400 /// Returns a node_iterator corresponding to a node just
401 /// after a leaf of the tree.
402 inline node_iterator
403 node_end();
404
405 private:
406
407 inline void
408 update(node_iterator, null_node_update_pointer);
409
410 template<typename Node_Update>
411 void
412 update(node_iterator, Node_Update*);
413
414 void
415 reallocate_metadata(null_node_update_pointer, size_type);
416
417 template<typename Node_Update_>
418 void
419 reallocate_metadata(Node_Update_*, size_type);
420
421 template<typename It>
422 void
423 copy_from_ordered_range(It, It);
424
425 void
426 value_swap(PB_DS_CLASS_C_DEC&);
427
428 template<typename It>
429 void
430 copy_from_ordered_range(It, It, It, It);
431
432 template<typename Ptr>
433 inline static Ptr
434 mid_pointer(Ptr p_begin, Ptr p_end)
435 {
436 _GLIBCXX_DEBUG_ASSERT(p_end >= p_begin);
437 return (p_begin + (p_end - p_begin) / 2);
438 }
439
440 inline iterator
441 insert_new_val(iterator it, const_reference r_value)
442 {
443#ifdef PB_DS_REGRESSION
444 typename _Alloc::group_adjustor adjust(m_size);
445#endif
446
447 PB_DS_CHECK_KEY_DOES_NOT_EXIST(PB_DS_V2F(r_value))
448
449 value_vector a_values = s_value_alloc.allocate(m_size + 1);
450
451 iterator source_it = begin();
452 iterator source_end_it = end();
453 iterator target_it = a_values;
454 iterator ret_it;
455
456 cond_dtor<size_type> cd(a_values, target_it, m_size + 1);
457 while (source_it != it)
458 {
459 new (const_cast<void*>(static_cast<const void*>(target_it)))
460 value_type(*source_it++);
461 ++target_it;
462 }
463
464 new (const_cast<void*>(static_cast<const void*>(ret_it = target_it)))
465 value_type(r_value);
466 ++target_it;
467
468 while (source_it != source_end_it)
469 {
470 new (const_cast<void*>(static_cast<const void*>(target_it)))
471 value_type(*source_it++);
472 ++target_it;
473 }
474
475 reallocate_metadata((node_update*)this, m_size + 1);
476 cd.set_no_action();
477 if (m_size != 0)
478 {
479 cond_dtor<size_type> cd1(m_a_values, m_end_it, m_size);
480 }
481
482 ++m_size;
483 m_a_values = a_values;
484 m_end_it = m_a_values + m_size;
485 _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_value)));
486 update(node_begin(), (node_update* )this);
487 PB_DS_ASSERT_VALID((*this))
488 return ret_it;
489 }
490
491#ifdef _GLIBCXX_DEBUG
492 void
493 assert_valid(const char*, int) const;
494
495 void
496 assert_iterators(const char*, int) const;
497#endif
498
499 template<typename It>
500 It
501 erase_imp(It);
502
503 inline node_const_iterator
504 PB_DS_node_begin_imp() const;
505
506 inline node_const_iterator
507 PB_DS_node_end_imp() const;
508
509 inline node_iterator
510 PB_DS_node_begin_imp();
511
512 inline node_iterator
513 PB_DS_node_end_imp();
514
515 private:
516 static value_allocator s_value_alloc;
517 static metadata_allocator s_metadata_alloc;
518
519 value_vector m_a_values;
520 metadata_pointer m_a_metadata;
521 iterator m_end_it;
522 size_type m_size;
523 };
524
525#include <ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp>
526#include <ext/pb_ds/detail/ov_tree_map_/iterators_fn_imps.hpp>
527#include <ext/pb_ds/detail/ov_tree_map_/debug_fn_imps.hpp>
528#include <ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp>
529#include <ext/pb_ds/detail/ov_tree_map_/insert_fn_imps.hpp>
530#include <ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp>
531#include <ext/pb_ds/detail/ov_tree_map_/split_join_fn_imps.hpp>
532#include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp>
533
534#undef PB_DS_CLASS_C_DEC
535#undef PB_DS_CLASS_T_DEC
536#undef PB_DS_OV_TREE_NAME
537#undef PB_DS_OV_TREE_TRAITS_BASE
538#undef PB_DS_DEBUG_MAP_BASE_C_DEC
539#ifdef PB_DS_TREE_TRACE
540#undef PB_DS_TREE_TRACE_BASE_C_DEC
541#endif
542#undef PB_DS_CONST_NODE_ITERATOR_NAME
543 } // namespace detail
544} // namespace __gnu_pbds
std::end
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1239
std::begin
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1217
std
ISO C++ entities toplevel namespace is std.
__gnu_pbds
GNU extensions for policy-based data structures for public use.
Definition: assoc_container.hpp:52
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:213
__gnu_pbds::ov_tree_tag
Ordered-vector tree.
Definition: tag_and_trait.hpp:159
__gnu_pbds::detail::rebind_traits
Consistent API for accessing allocator-related types.
Definition: types_traits.hpp:140
__gnu_pbds::detail::ov_tree_map::node_begin
node_const_iterator node_begin() const
Returns a const node_iterator corresponding to the node at the root of the tree.
__gnu_pbds::detail::ov_tree_map::node_end
node_const_iterator node_end() const
Returns a const node_iterator corresponding to a node just after a leaf of the tree.
__gnu_pbds::detail::ov_tree_map::node_end
node_iterator node_end()
Returns a node_iterator corresponding to a node just after a leaf of the tree.
__gnu_pbds::detail::ov_tree_map::node_begin
node_iterator node_begin()
Returns a node_iterator corresponding to the node at the root of the tree.