1// -*- C++ -*-
2
3// Copyright (C) 2005, 2006 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 2, 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// You should have received a copy of the GNU General Public License
17// along with this library; see the file COPYING.  If not, write to
18// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19// MA 02111-1307, USA.
20
21// As a special exception, you may use this file as part of a free
22// software library without restriction.  Specifically, if other files
23// instantiate templates or use macros or inline functions from this
24// file, or you compile this file and link it with other files to
25// produce an executable, this file does not by itself cause the
26// resulting executable to be covered by the GNU General Public
27// License.  This exception does not however invalidate any other
28// reasons why the executable file might be covered by the GNU General
29// Public License.
30
31// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
32
33// Permission to use, copy, modify, sell, and distribute this software
34// is hereby granted without fee, provided that the above copyright
35// notice appears in all copies, and that both that copyright notice
36// and this permission notice appear in supporting documentation. None
37// of the above authors, nor IBM Haifa Research Laboratories, make any
38// representation about the suitability of this software for any
39// purpose. It is provided "as is" without express or implied
40// warranty.
41
42/**
43 * @file bin_search_tree_.hpp
44 * Contains an implementation class for bin_search_tree_.
45 */
46/*
47 * This implementation uses an idea from the SGI STL (using a "header" node
48 *    which is needed for efficient iteration).
49 */
50
51#include <ext/pb_ds/exception.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/detail/map_debug_base.hpp>
55#include <ext/pb_ds/tree_policy.hpp>
56#include <ext/pb_ds/detail/cond_dealtor.hpp>
57#include <ext/pb_ds/detail/type_utils.hpp>
58#include <ext/pb_ds/detail/tree_trace_base.hpp>
59#include <utility>
60#include <functional>
61#include <debug/debug.h>
62
63namespace pb_ds
64{
65  namespace detail
66  {
67
68#define PB_DS_CLASS_T_DEC						\
69    template<typename Key, typename Mapped, class Cmp_Fn,		\
70	     class Node_And_It_Traits, class Allocator>
71
72#ifdef PB_DS_DATA_TRUE_INDICATOR
73#define PB_DS_CLASS_NAME			\
74    bin_search_tree_data_
75#endif
76
77#ifdef PB_DS_DATA_FALSE_INDICATOR
78#define PB_DS_CLASS_NAME			\
79    bin_search_tree_no_data_
80#endif
81
82#define PB_DS_CLASS_C_DEC						\
83    PB_DS_CLASS_NAME<							\
84						Key,			\
85						Mapped,			\
86						Cmp_Fn,			\
87						Node_And_It_Traits,	\
88						Allocator>
89
90#define PB_DS_TYPES_TRAITS_C_DEC				\
91    types_traits<				\
92						Key,		\
93						Mapped,		\
94						Allocator,	\
95						false>
96
97#ifdef _GLIBCXX_DEBUG
98#define PB_DS_MAP_DEBUG_BASE_C_DEC					\
99    map_debug_base<Key,	eq_by_less<Key, Cmp_Fn>, \
100	      typename Allocator::template rebind<Key>::other::const_reference>
101#endif
102
103#ifdef PB_DS_DATA_TRUE_INDICATOR
104#define PB_DS_V2F(X) (X).first
105#define PB_DS_V2S(X) (X).second
106#define PB_DS_EP2VP(X)& ((X)->m_value)
107#endif
108
109#ifdef PB_DS_DATA_FALSE_INDICATOR
110#define PB_DS_V2F(X) (X)
111#define PB_DS_V2S(X) Mapped_Data()
112#define PB_DS_EP2VP(X)& ((X)->m_value.first)
113#endif
114
115#ifdef PB_DS_TREE_TRACE
116#define PB_DS_TREE_TRACE_BASE_C_DEC					\
117    tree_trace_base<							\
118									typename Node_And_It_Traits::const_node_iterator, \
119									typename Node_And_It_Traits::node_iterator, \
120									Cmp_Fn,	\
121									true, \
122									Allocator>
123#endif
124
125    /**
126     * class description = "8i|\|4ree $34rc|-| 7r33 74813.">
127     **/
128    template<typename Key,
129	     typename Mapped,
130	     class Cmp_Fn,
131	     class Node_And_It_Traits,
132	     class Allocator>
133    class PB_DS_CLASS_NAME :
134#ifdef _GLIBCXX_DEBUG
135      public PB_DS_MAP_DEBUG_BASE_C_DEC,
136#endif
137#ifdef PB_DS_TREE_TRACE
138      public PB_DS_TREE_TRACE_BASE_C_DEC,
139#endif
140      public Cmp_Fn,
141      public PB_DS_TYPES_TRAITS_C_DEC,
142      public Node_And_It_Traits::node_update
143    {
144
145    protected:
146      typedef
147      typename Allocator::template rebind<
148      typename Node_And_It_Traits::node>::other
149      node_allocator;
150
151      typedef typename node_allocator::value_type node;
152
153      typedef typename node_allocator::pointer node_pointer;
154
155      typedef PB_DS_TYPES_TRAITS_C_DEC traits_base;
156
157      typedef
158      typename Node_And_It_Traits::null_node_update_pointer
159      null_node_update_pointer;
160
161    private:
162      typedef cond_dealtor< node, Allocator> cond_dealtor_t;
163
164#ifdef _GLIBCXX_DEBUG
165      typedef PB_DS_MAP_DEBUG_BASE_C_DEC map_debug_base;
166#endif
167
168    public:
169
170      typedef typename Allocator::size_type size_type;
171
172      typedef typename Allocator::difference_type difference_type;
173
174      typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_type key_type;
175
176      typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_pointer key_pointer;
177
178      typedef
179      typename PB_DS_TYPES_TRAITS_C_DEC::const_key_pointer
180      const_key_pointer;
181
182      typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_reference key_reference;
183
184      typedef
185      typename PB_DS_TYPES_TRAITS_C_DEC::const_key_reference
186      const_key_reference;
187
188#ifdef PB_DS_DATA_TRUE_INDICATOR
189      typedef typename PB_DS_TYPES_TRAITS_C_DEC::mapped_type mapped_type;
190
191      typedef
192      typename PB_DS_TYPES_TRAITS_C_DEC::mapped_pointer
193      mapped_pointer;
194
195      typedef
196      typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_pointer
197      const_mapped_pointer;
198
199      typedef
200      typename PB_DS_TYPES_TRAITS_C_DEC::mapped_reference
201      mapped_reference;
202
203      typedef
204      typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_reference
205      const_mapped_reference;
206#endif
207
208      typedef typename PB_DS_TYPES_TRAITS_C_DEC::value_type value_type;
209
210      typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer pointer;
211
212      typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer const_pointer;
213
214      typedef typename PB_DS_TYPES_TRAITS_C_DEC::reference reference;
215
216      typedef
217      typename PB_DS_TYPES_TRAITS_C_DEC::const_reference
218      const_reference;
219
220      typedef
221      typename Node_And_It_Traits::const_point_iterator
222      const_point_iterator;
223
224      typedef const_point_iterator const_iterator;
225
226      typedef typename Node_And_It_Traits::point_iterator point_iterator;
227
228      typedef point_iterator iterator;
229
230      typedef
231      typename Node_And_It_Traits::const_reverse_iterator
232      const_reverse_iterator;
233
234      typedef typename Node_And_It_Traits::reverse_iterator reverse_iterator;
235
236      typedef
237      typename Node_And_It_Traits::const_node_iterator
238      const_node_iterator;
239
240      typedef typename Node_And_It_Traits::node_iterator node_iterator;
241
242      typedef Cmp_Fn cmp_fn;
243
244      typedef Allocator allocator;
245
246      typedef typename Node_And_It_Traits::node_update node_update;
247
248    public:
249
250      PB_DS_CLASS_NAME();
251
252      PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn);
253
254      PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_update);
255
256      PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other);
257
258      void
259      swap(PB_DS_CLASS_C_DEC& other);
260
261      ~PB_DS_CLASS_NAME();
262
263      inline bool
264      empty() const;
265
266      inline size_type
267      size() const;
268
269      inline size_type
270      max_size() const;
271
272      Cmp_Fn&
273      get_cmp_fn();
274
275      const Cmp_Fn&
276      get_cmp_fn() const;
277
278      inline point_iterator
279      lower_bound(const_key_reference r_key);
280
281      inline const_point_iterator
282      lower_bound(const_key_reference r_key) const;
283
284      inline point_iterator
285      upper_bound(const_key_reference r_key);
286
287      inline const_point_iterator
288      upper_bound(const_key_reference r_key) const;
289
290      inline point_iterator
291      find(const_key_reference r_key);
292
293      inline const_point_iterator
294      find(const_key_reference r_key) const;
295
296      inline iterator
297      begin();
298
299      inline const_iterator
300      begin() const;
301
302      inline iterator
303      end();
304
305      inline const_iterator
306      end() const;
307
308      inline reverse_iterator
309      rbegin();
310
311      inline const_reverse_iterator
312      rbegin() const;
313
314      inline reverse_iterator
315      rend();
316
317      inline const_reverse_iterator
318      rend() const;
319
320      inline const_node_iterator
321      node_begin() const;
322
323      inline node_iterator
324      node_begin();
325
326      inline const_node_iterator
327      node_end() const;
328
329      inline node_iterator
330      node_end();
331
332      void
333      clear();
334
335    protected:
336
337      void
338      value_swap(PB_DS_CLASS_C_DEC& other);
339
340      void
341      initialize_min_max();
342
343      inline iterator
344      insert_imp_empty(const_reference r_value);
345
346      inline iterator
347      insert_leaf_new(const_reference r_value, node_pointer p_nd, bool left_nd);
348
349      inline node_pointer
350      get_new_node_for_leaf_insert(const_reference r_val, false_type);
351
352      inline node_pointer
353      get_new_node_for_leaf_insert(const_reference r_val, true_type);
354
355      inline void
356      actual_erase_node(node_pointer p_nd);
357
358      inline std::pair<node_pointer, bool>
359      erase(node_pointer p_nd);
360
361      inline void
362      update_min_max_for_erased_node(node_pointer p_nd);
363
364      static void
365      clear_imp(node_pointer p_nd);
366
367      inline std::pair<
368	point_iterator,
369	bool>
370      insert_leaf(const_reference r_value);
371
372      inline void
373      rotate_left(node_pointer p_x);
374
375      inline void
376      rotate_right(node_pointer p_y);
377
378      inline void
379      rotate_parent(node_pointer p_nd);
380
381      inline void
382      apply_update(node_pointer p_nd, null_node_update_pointer);
383
384      template<typename Node_Update_>
385      inline void
386      apply_update(node_pointer p_nd, Node_Update_* p_update);
387
388      inline void
389      update_to_top(node_pointer p_nd, null_node_update_pointer);
390
391      template<typename Node_Update_>
392      inline void
393      update_to_top(node_pointer p_nd, Node_Update_* p_update);
394
395      bool
396      join_prep(PB_DS_CLASS_C_DEC& other);
397
398      void
399      join_finish(PB_DS_CLASS_C_DEC& other);
400
401      bool
402      split_prep(const_key_reference r_key, PB_DS_CLASS_C_DEC& other);
403
404      void
405      split_finish(PB_DS_CLASS_C_DEC& other);
406
407      size_type
408      recursive_count(node_pointer p_nd) const;
409
410#ifdef _GLIBCXX_DEBUG
411      void
412      assert_valid() const;
413
414      void
415      structure_only_assert_valid() const;
416
417      void
418      assert_node_consistent(const node_pointer p_nd) const;
419#endif
420
421    private:
422#ifdef _GLIBCXX_DEBUG
423      void
424      assert_iterators() const;
425
426      void
427      assert_consistent_with_debug_base() const;
428
429      void
430      assert_node_consistent_with_left(const node_pointer p_nd) const;
431
432      void
433      assert_node_consistent_with_right(const node_pointer p_nd) const;
434
435      void
436      assert_consistent_with_debug_base(const node_pointer p_nd) const;
437
438      void
439      assert_min() const;
440
441      void
442      assert_min_imp(const node_pointer p_nd) const;
443
444      void
445      assert_max() const;
446
447      void
448      assert_max_imp(const node_pointer p_nd) const;
449
450      void
451      assert_size() const;
452
453      typedef std::pair< const_pointer, const_pointer> node_consistent_t;
454
455      node_consistent_t
456      assert_node_consistent_(const node_pointer p_nd) const;
457#endif
458
459      void
460      initialize();
461
462      node_pointer
463      recursive_copy_node(const node_pointer p_nd);
464
465    protected:
466      node_pointer m_p_head;
467
468      size_type m_size;
469
470      static node_allocator s_node_allocator;
471    };
472
473#include <ext/pb_ds/detail/bin_search_tree_/constructors_destructor_fn_imps.hpp>
474#include <ext/pb_ds/detail/bin_search_tree_/iterators_fn_imps.hpp>
475#include <ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp>
476#include <ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp>
477#include <ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp>
478#include <ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp>
479#include <ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp>
480#include <ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp>
481#include <ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp>
482#include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp>
483
484#undef PB_DS_CLASS_C_DEC
485
486#undef PB_DS_CLASS_T_DEC
487
488#undef PB_DS_CLASS_NAME
489
490#undef PB_DS_TYPES_TRAITS_C_DEC
491
492#undef PB_DS_MAP_DEBUG_BASE_C_DEC
493
494#ifdef PB_DS_TREE_TRACE
495#undef PB_DS_TREE_TRACE_BASE_C_DEC
496#endif
497
498#undef PB_DS_V2F
499#undef PB_DS_EP2VP
500#undef PB_DS_V2S
501
502  } // namespace detail
503} // namespace pb_ds
504