1// -*- C++ -*-
2
3// Copyright (C) 2005, 2006, 2007, 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 pat_trie_.hpp
38 * Contains an implementation class for a patricia tree.
39 */
40
41/**
42 * This implementation loosely borrows ideas from:
43 * 1) Fast Mergeable Integer Maps, Okasaki, Gill 1998
44 * 2) Ptset: Sets of integers implemented as Patricia trees,
45 *    Jean-Christophe Filliatr, 2000
46 **/
47
48#include <ext/pb_ds/detail/pat_trie_/synth_e_access_traits.hpp>
49#include <ext/pb_ds/detail/pat_trie_/node_base.hpp>
50#include <ext/pb_ds/exception.hpp>
51#include <ext/pb_ds/tag_and_trait.hpp>
52#include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp>
53#include <ext/pb_ds/detail/types_traits.hpp>
54#include <ext/pb_ds/tree_policy.hpp>
55#include <ext/pb_ds/detail/cond_dealtor.hpp>
56#include <ext/pb_ds/detail/type_utils.hpp>
57#include <iterator>
58#include <utility>
59#include <algorithm>
60#include <functional>
61#include <assert.h>
62#include <list>
63#ifdef _GLIBCXX_DEBUG
64#include <ext/pb_ds/detail/debug_map_base.hpp>
65#endif
66#include <debug/debug.h>
67
68namespace __gnu_pbds
69{
70  namespace detail
71  {
72#define PB_DS_CLASS_T_DEC \
73    template<typename Key, typename Mapped, typename Node_And_It_Traits, \
74	     typename Allocator>
75
76#ifdef PB_DS_DATA_TRUE_INDICATOR
77#define PB_DS_CLASS_NAME pat_trie_data_
78#endif
79
80#ifdef PB_DS_DATA_FALSE_INDICATOR
81#define PB_DS_CLASS_NAME pat_trie_no_data_
82#endif
83
84#define PB_DS_CLASS_C_DEC \
85    PB_DS_CLASS_NAME<Key, Mapped, Node_And_It_Traits, Allocator>
86
87#define PB_DS_TYPES_TRAITS_C_DEC \
88    types_traits<Key, Mapped, Allocator, false>
89
90#ifdef _GLIBCXX_DEBUG
91#define PB_DS_DEBUG_MAP_BASE_C_DEC \
92    debug_map_base<Key,	eq_by_less<Key, \
93			std::less<Key> >, typename Allocator::template rebind<Key>::other::const_reference>
94#endif
95
96#ifdef PB_DS_DATA_TRUE_INDICATOR
97#define PB_DS_V2F(X) (X).first
98#define PB_DS_V2S(X) (X).second
99#define PB_DS_EP2VP(X)& ((X)->m_value)
100#endif
101
102#ifdef PB_DS_DATA_FALSE_INDICATOR
103#define PB_DS_V2F(X) (X)
104#define PB_DS_V2S(X) Mapped_Data()
105#define PB_DS_EP2VP(X)& ((X)->m_value.first)
106#endif
107
108    /**
109     * class description = PATRICIA trie implementation.">
110     **/
111    template<typename Key,
112	     typename Mapped,
113	     typename Node_And_It_Traits,
114	     typename Allocator>
115    class PB_DS_CLASS_NAME :
116#ifdef _GLIBCXX_DEBUG
117      public PB_DS_DEBUG_MAP_BASE_C_DEC,
118#endif
119      public Node_And_It_Traits::synth_e_access_traits,
120      public Node_And_It_Traits::node_update,
121      public PB_DS_TYPES_TRAITS_C_DEC
122    {
123    private:
124      typedef PB_DS_TYPES_TRAITS_C_DEC traits_base;
125
126      typedef typename Node_And_It_Traits::synth_e_access_traits synth_e_access_traits;
127      typedef typename Allocator::template rebind<synth_e_access_traits>::other::const_pointer const_e_access_traits_pointer;
128      typedef typename synth_e_access_traits::const_iterator const_e_iterator;
129
130      typedef typename Node_And_It_Traits::node node;
131      typedef typename Allocator::template rebind<node>::other::const_pointer const_node_pointer;
132
133      typedef typename Allocator::template rebind<node>::other::pointer node_pointer;
134
135      typedef typename Node_And_It_Traits::head head;
136      typedef typename Allocator::template rebind<head>::other head_allocator;
137      typedef typename head_allocator::pointer head_pointer;
138
139      typedef typename Node_And_It_Traits::leaf leaf;
140      typedef typename Allocator::template rebind<leaf>::other leaf_allocator;
141      typedef typename leaf_allocator::const_pointer const_leaf_pointer;
142      typedef typename leaf_allocator::pointer leaf_pointer;
143
144      typedef typename Node_And_It_Traits::internal_node internal_node;
145      typedef typename Allocator::template rebind<internal_node>::other internal_node_allocator;
146      typedef typename internal_node_allocator::const_pointer const_internal_node_pointer;
147      typedef typename internal_node_allocator::pointer internal_node_pointer;
148
149#include <ext/pb_ds/detail/pat_trie_/cond_dtor_entry_dealtor.hpp>
150
151#ifdef _GLIBCXX_DEBUG
152      typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base;
153#endif
154
155#include <ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp>
156
157      typedef typename Node_And_It_Traits::null_node_update_pointer null_node_update_pointer;
158
159    public:
160      typedef pat_trie_tag container_category;
161      typedef Allocator allocator_type;
162      typedef typename Allocator::size_type size_type;
163      typedef typename Allocator::difference_type difference_type;
164
165      typedef typename traits_base::key_type key_type;
166      typedef typename traits_base::key_pointer key_pointer;
167      typedef typename traits_base::const_key_pointer const_key_pointer;
168      typedef typename traits_base::key_reference key_reference;
169      typedef typename traits_base::const_key_reference const_key_reference;
170      typedef typename traits_base::mapped_type mapped_type;
171      typedef typename traits_base::mapped_pointer mapped_pointer;
172      typedef typename traits_base::const_mapped_pointer const_mapped_pointer;
173      typedef typename traits_base::mapped_reference mapped_reference;
174      typedef typename traits_base::const_mapped_reference const_mapped_reference;
175      typedef typename traits_base::value_type value_type;
176      typedef typename traits_base::pointer pointer;
177      typedef typename traits_base::const_pointer const_pointer;
178      typedef typename traits_base::reference reference;
179      typedef typename traits_base::const_reference const_reference;
180
181      typedef typename Node_And_It_Traits::const_iterator const_point_iterator;
182      typedef typename Node_And_It_Traits::iterator point_iterator;
183      typedef const_point_iterator const_iterator;
184      typedef point_iterator iterator;
185
186      typedef typename Node_And_It_Traits::const_reverse_iterator const_reverse_iterator;
187      typedef typename Node_And_It_Traits::reverse_iterator reverse_iterator;
188      typedef typename Node_And_It_Traits::const_node_iterator const_node_iterator;
189      typedef typename Node_And_It_Traits::node_iterator node_iterator;
190      typedef typename Node_And_It_Traits::e_access_traits e_access_traits;
191      typedef typename Node_And_It_Traits::node_update node_update;
192
193      PB_DS_CLASS_NAME();
194
195      PB_DS_CLASS_NAME(const e_access_traits&);
196
197      PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&);
198
199      void
200      swap(PB_DS_CLASS_C_DEC&);
201
202      ~PB_DS_CLASS_NAME();
203
204      inline bool
205      empty() const;
206
207      inline size_type
208      size() const;
209
210      inline size_type
211      max_size() const;
212
213      e_access_traits&
214      get_e_access_traits();
215
216      const e_access_traits&
217      get_e_access_traits() const;
218
219      node_update&
220      get_node_update();
221
222      const node_update&
223      get_node_update() const;
224
225      inline std::pair<point_iterator, bool>
226      insert(const_reference);
227
228      inline mapped_reference
229      operator[](const_key_reference r_key)
230      {
231#ifdef PB_DS_DATA_TRUE_INDICATOR
232	return insert(std::make_pair(r_key, mapped_type())).first->second;
233#else
234	insert(r_key);
235	return traits_base::s_null_mapped;
236#endif
237      }
238
239      inline point_iterator
240      find(const_key_reference);
241
242      inline const_point_iterator
243      find(const_key_reference) const;
244
245      inline point_iterator
246      lower_bound(const_key_reference);
247
248      inline const_point_iterator
249      lower_bound(const_key_reference) const;
250
251      inline point_iterator
252      upper_bound(const_key_reference);
253
254      inline const_point_iterator
255      upper_bound(const_key_reference) const;
256
257      void
258      clear();
259
260      inline bool
261      erase(const_key_reference);
262
263      inline const_iterator
264      erase(const_iterator);
265
266#ifdef PB_DS_DATA_TRUE_INDICATOR
267      inline iterator
268      erase(iterator);
269#endif
270
271      inline const_reverse_iterator
272      erase(const_reverse_iterator);
273
274#ifdef PB_DS_DATA_TRUE_INDICATOR
275      inline reverse_iterator
276      erase(reverse_iterator);
277#endif
278
279      template<typename Pred>
280      inline size_type
281      erase_if(Pred);
282
283      void
284      join(PB_DS_CLASS_C_DEC&);
285
286      void
287      split(const_key_reference, PB_DS_CLASS_C_DEC&);
288
289      inline iterator
290      begin();
291
292      inline const_iterator
293      begin() const;
294
295      inline iterator
296      end();
297
298      inline const_iterator
299      end() const;
300
301      inline reverse_iterator
302      rbegin();
303
304      inline const_reverse_iterator
305      rbegin() const;
306
307      inline reverse_iterator
308      rend();
309
310      inline const_reverse_iterator
311      rend() const;
312
313      inline const_node_iterator
314      node_begin() const;
315
316      inline node_iterator
317      node_begin();
318
319      inline const_node_iterator
320      node_end() const;
321
322      inline node_iterator
323      node_end();
324
325#ifdef PB_DS_PAT_TRIE_TRACE_
326      void
327      trace() const;
328#endif
329
330    protected:
331
332      template<typename It>
333      void
334      copy_from_range(It, It);
335
336      void
337      value_swap(PB_DS_CLASS_C_DEC&);
338
339      node_pointer
340      recursive_copy_node(const_node_pointer);
341
342    private:
343
344      void
345      initialize();
346
347      inline void
348      apply_update(node_pointer, null_node_update_pointer);
349
350      template<typename Node_Update_>
351      inline void
352      apply_update(node_pointer, Node_Update_*);
353
354      bool
355      join_prep(PB_DS_CLASS_C_DEC&, split_join_branch_bag&);
356
357      void
358      rec_join_prep(const_node_pointer, const_node_pointer,
359		    split_join_branch_bag&);
360
361      void
362      rec_join_prep(const_leaf_pointer, const_leaf_pointer,
363		    split_join_branch_bag&);
364
365      void
366      rec_join_prep(const_leaf_pointer, const_internal_node_pointer,
367		    split_join_branch_bag&);
368
369      void
370      rec_join_prep(const_internal_node_pointer, const_leaf_pointer,
371		    split_join_branch_bag&);
372
373      void
374      rec_join_prep(const_internal_node_pointer, const_internal_node_pointer,
375		    split_join_branch_bag&);
376
377      node_pointer
378      rec_join(node_pointer, node_pointer, size_type, split_join_branch_bag&);
379
380      node_pointer
381      rec_join(leaf_pointer, leaf_pointer, split_join_branch_bag&);
382
383      node_pointer
384      rec_join(leaf_pointer, internal_node_pointer, size_type,
385	       split_join_branch_bag&);
386
387      node_pointer
388      rec_join(internal_node_pointer, leaf_pointer, size_type,
389	       split_join_branch_bag&);
390
391      node_pointer
392      rec_join(internal_node_pointer, internal_node_pointer,
393	       split_join_branch_bag&);
394
395      size_type
396      keys_diff_ind(typename e_access_traits::const_iterator, typename e_access_traits::const_iterator, typename e_access_traits::const_iterator, typename e_access_traits::const_iterator);
397
398      internal_node_pointer
399      insert_branch(node_pointer, node_pointer, split_join_branch_bag&);
400
401      void
402      update_min_max_for_inserted_leaf(leaf_pointer);
403
404      void
405      erase_leaf(leaf_pointer);
406
407      inline void
408      actual_erase_leaf(leaf_pointer);
409
410      void
411      clear_imp(node_pointer);
412
413      void
414      erase_fixup(internal_node_pointer);
415
416      void
417      update_min_max_for_erased_leaf(leaf_pointer);
418
419      static inline const_e_iterator
420      pref_begin(const_node_pointer);
421
422      static inline const_e_iterator
423      pref_end(const_node_pointer);
424
425      inline node_pointer
426      find_imp(const_key_reference);
427
428      inline node_pointer
429      lower_bound_imp(const_key_reference);
430
431      inline node_pointer
432      upper_bound_imp(const_key_reference);
433
434      inline static const_leaf_pointer
435      leftmost_descendant(const_node_pointer);
436
437      inline static leaf_pointer
438      leftmost_descendant(node_pointer);
439
440      inline static const_leaf_pointer
441      rightmost_descendant(const_node_pointer);
442
443      inline static leaf_pointer
444      rightmost_descendant(node_pointer);
445
446#ifdef _GLIBCXX_DEBUG
447      void
448      assert_valid() const;
449
450      void
451      assert_iterators() const;
452
453      void
454      assert_reverse_iterators() const;
455
456      static size_type
457      recursive_count_leafs(const_node_pointer);
458#endif
459
460#ifdef PB_DS_PAT_TRIE_TRACE_
461      static void
462      trace_node(const_node_pointer, size_type);
463
464      template<typename Metadata_>
465      static void
466      trace_node_metadata(const_node_pointer, type_to_type<Metadata_>);
467
468      static void
469      trace_node_metadata(const_node_pointer, type_to_type<null_node_metadata>);
470#endif
471
472      leaf_pointer
473      split_prep(const_key_reference, PB_DS_CLASS_C_DEC&,
474		 split_join_branch_bag&);
475
476      node_pointer
477      rec_split(node_pointer, const_e_iterator, const_e_iterator,
478		PB_DS_CLASS_C_DEC&, split_join_branch_bag&);
479
480      void
481      split_insert_branch(size_type, const_e_iterator,
482			  typename internal_node::iterator,
483			  size_type, split_join_branch_bag&);
484
485      static head_allocator s_head_allocator;
486      static internal_node_allocator s_internal_node_allocator;
487      static leaf_allocator s_leaf_allocator;
488
489      head_pointer m_p_head;
490      size_type m_size;
491    };
492
493#include <ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp>
494#include <ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp>
495#include <ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp>
496#include <ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp>
497#include <ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp>
498#include <ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp>
499#include <ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp>
500#include <ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp>
501#include <ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp>
502#include <ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp>
503#include <ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp>
504
505#undef PB_DS_CLASS_C_DEC
506#undef PB_DS_CLASS_T_DEC
507#undef PB_DS_CLASS_NAME
508#undef PB_DS_TYPES_TRAITS_C_DEC
509#undef PB_DS_DEBUG_MAP_BASE_C_DEC
510#undef PB_DS_V2F
511#undef PB_DS_EP2VP
512#undef PB_DS_V2S
513
514  } // namespace detail
515} // namespace __gnu_pbds
516