Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // -*- C++ -*-
  2.  
  3. // Copyright (C) 2005-2013 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 bin_search_tree_/bin_search_tree_.hpp
  38.  *  Contains an implementation class for binary search tree.
  39.  */
  40.  
  41. #include <ext/pb_ds/exception.hpp>
  42. #include <ext/pb_ds/tree_policy.hpp>
  43. #include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp>
  44. #include <ext/pb_ds/detail/types_traits.hpp>
  45. #include <ext/pb_ds/detail/cond_dealtor.hpp>
  46. #include <ext/pb_ds/detail/type_utils.hpp>
  47. #include <ext/pb_ds/detail/tree_trace_base.hpp>
  48. #ifdef _GLIBCXX_DEBUG
  49. #include <ext/pb_ds/detail/debug_map_base.hpp>
  50. #endif
  51. #include <utility>
  52. #include <functional>
  53. #include <debug/debug.h>
  54.  
  55. namespace __gnu_pbds
  56. {
  57.   namespace detail
  58.   {
  59. #ifdef PB_DS_DATA_TRUE_INDICATOR
  60. #define PB_DS_BIN_TREE_NAME bin_search_tree_map
  61. #endif
  62.  
  63. #ifdef PB_DS_DATA_FALSE_INDICATOR
  64. #define PB_DS_BIN_TREE_NAME bin_search_tree_set
  65. #endif
  66.  
  67. #define PB_DS_CLASS_T_DEC \
  68.     template<typename Key, typename Mapped, typename Cmp_Fn, \
  69.              typename Node_And_It_Traits, typename _Alloc>
  70.  
  71. #define PB_DS_CLASS_C_DEC \
  72.     PB_DS_BIN_TREE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc>
  73.  
  74. #define PB_DS_BIN_TREE_TRAITS_BASE \
  75.     types_traits<Key, Mapped, _Alloc, false>
  76.  
  77. #ifdef _GLIBCXX_DEBUG
  78. #define PB_DS_DEBUG_MAP_BASE_C_DEC  \
  79.     debug_map_base<Key, eq_by_less<Key, Cmp_Fn>, \
  80.               typename _Alloc::template rebind<Key>::other::const_reference>
  81. #endif
  82.  
  83. #ifdef PB_DS_TREE_TRACE
  84. #define PB_DS_TREE_TRACE_BASE_C_DEC \
  85.     tree_trace_base<typename Node_And_It_Traits::node_const_iterator, \
  86.                     typename Node_And_It_Traits::node_iterator,       \
  87.                     Cmp_Fn, true, _Alloc>
  88. #endif
  89.  
  90.  
  91.     /*
  92.      *  @brief Binary search tree (BST).
  93.      *
  94.      *  This implementation uses an idea from the SGI STL (using a @a
  95.      *  header node which is needed for efficient iteration).
  96.      */
  97.     template<typename Key, typename Mapped, typename Cmp_Fn,
  98.              typename Node_And_It_Traits, typename _Alloc>
  99.     class PB_DS_BIN_TREE_NAME :
  100. #ifdef _GLIBCXX_DEBUG
  101.       public PB_DS_DEBUG_MAP_BASE_C_DEC,
  102. #endif
  103. #ifdef PB_DS_TREE_TRACE
  104.       public PB_DS_TREE_TRACE_BASE_C_DEC,
  105. #endif
  106.       public Cmp_Fn,
  107.       public PB_DS_BIN_TREE_TRAITS_BASE,
  108.       public Node_And_It_Traits::node_update
  109.     {
  110.       typedef Node_And_It_Traits                        traits_type;
  111.  
  112.     protected:
  113.       typedef PB_DS_BIN_TREE_TRAITS_BASE                traits_base;
  114.  
  115.       typedef
  116.       typename _Alloc::template rebind<typename traits_type::node>::other
  117.       node_allocator;
  118.  
  119.       typedef typename node_allocator::value_type       node;
  120.       typedef typename node_allocator::pointer          node_pointer;
  121.  
  122.       typedef typename traits_type::null_node_update_pointer
  123.       null_node_update_pointer;
  124.  
  125.     private:
  126.       typedef cond_dealtor<node, _Alloc>                cond_dealtor_t;
  127.  
  128. #ifdef _GLIBCXX_DEBUG
  129.       typedef PB_DS_DEBUG_MAP_BASE_C_DEC                debug_base;
  130. #endif
  131.  
  132.     public:
  133.       typedef typename _Alloc::size_type                size_type;
  134.       typedef typename _Alloc::difference_type  difference_type;
  135.       typedef typename traits_base::key_type            key_type;
  136.       typedef typename traits_base::key_pointer         key_pointer;
  137.       typedef typename traits_base::key_const_pointer   key_const_pointer;
  138.       typedef typename traits_base::key_reference       key_reference;
  139.       typedef typename traits_base::key_const_reference key_const_reference;
  140.  
  141. #ifdef PB_DS_DATA_TRUE_INDICATOR
  142.       typedef typename traits_base::mapped_type         mapped_type;
  143.       typedef typename traits_base::mapped_pointer      mapped_pointer;
  144.       typedef typename traits_base::mapped_const_pointer mapped_const_pointer;
  145.       typedef typename traits_base::mapped_reference    mapped_reference;
  146.       typedef typename traits_base::mapped_const_reference mapped_const_reference;
  147. #endif
  148.  
  149.       typedef typename traits_base::value_type          value_type;
  150.       typedef typename traits_base::pointer             pointer;
  151.       typedef typename traits_base::const_pointer       const_pointer;
  152.       typedef typename traits_base::reference           reference;
  153.       typedef typename traits_base::const_reference     const_reference;
  154.       typedef typename traits_type::point_const_iterator point_const_iterator;
  155.  
  156.       typedef point_const_iterator                      const_iterator;
  157.       typedef typename traits_type::point_iterator      point_iterator;
  158.       typedef point_iterator                            iterator;
  159.  
  160.       typedef typename traits_type::const_reverse_iterator const_reverse_iterator;
  161.  
  162.       typedef typename traits_type::reverse_iterator    reverse_iterator;
  163.       typedef typename traits_type::node_const_iterator node_const_iterator;
  164.       typedef typename traits_type::node_iterator       node_iterator;
  165.       typedef typename traits_type::node_update         node_update;
  166.  
  167.       typedef Cmp_Fn                                    cmp_fn;
  168.       typedef _Alloc                                    allocator_type;
  169.  
  170.       PB_DS_BIN_TREE_NAME();
  171.  
  172.       PB_DS_BIN_TREE_NAME(const Cmp_Fn&);
  173.  
  174.       PB_DS_BIN_TREE_NAME(const Cmp_Fn&, const node_update&);
  175.  
  176.       PB_DS_BIN_TREE_NAME(const PB_DS_CLASS_C_DEC&);
  177.  
  178.       void
  179.       swap(PB_DS_CLASS_C_DEC&);
  180.  
  181.       ~PB_DS_BIN_TREE_NAME();
  182.  
  183.       inline bool
  184.       empty() const;
  185.  
  186.       inline size_type
  187.       size() const;
  188.  
  189.       inline size_type
  190.       max_size() const;
  191.  
  192.       Cmp_Fn&
  193.       get_cmp_fn();
  194.  
  195.       const Cmp_Fn&
  196.       get_cmp_fn() const;
  197.  
  198.       inline point_iterator
  199.       lower_bound(key_const_reference);
  200.  
  201.       inline point_const_iterator
  202.       lower_bound(key_const_reference) const;
  203.  
  204.       inline point_iterator
  205.       upper_bound(key_const_reference);
  206.  
  207.       inline point_const_iterator
  208.       upper_bound(key_const_reference) const;
  209.  
  210.       inline point_iterator
  211.       find(key_const_reference);
  212.  
  213.       inline point_const_iterator
  214.       find(key_const_reference) const;
  215.  
  216.       inline iterator
  217.       begin();
  218.  
  219.       inline const_iterator
  220.       begin() const;
  221.  
  222.       inline iterator
  223.       end();
  224.  
  225.       inline const_iterator
  226.       end() const;
  227.  
  228.       inline reverse_iterator
  229.       rbegin();
  230.  
  231.       inline const_reverse_iterator
  232.       rbegin() const;
  233.  
  234.       inline reverse_iterator
  235.       rend();
  236.  
  237.       inline const_reverse_iterator
  238.       rend() const;
  239.  
  240.       /// Returns a const node_iterator corresponding to the node at the
  241.       /// root of the tree.
  242.       inline node_const_iterator
  243.       node_begin() const;
  244.  
  245.       /// Returns a node_iterator corresponding to the node at the
  246.       /// root of the tree.
  247.       inline node_iterator
  248.       node_begin();
  249.  
  250.       /// Returns a const node_iterator corresponding to a node just
  251.       /// after a leaf of the tree.
  252.       inline node_const_iterator
  253.       node_end() const;
  254.  
  255.       /// Returns a node_iterator corresponding to a node just
  256.       /// after a leaf of the tree.
  257.       inline node_iterator
  258.       node_end();
  259.  
  260.       void
  261.       clear();
  262.  
  263.     protected:
  264.       void
  265.       value_swap(PB_DS_CLASS_C_DEC&);
  266.  
  267.       void
  268.       initialize_min_max();
  269.  
  270.       inline iterator
  271.       insert_imp_empty(const_reference);
  272.  
  273.       inline iterator
  274.       insert_leaf_new(const_reference, node_pointer, bool);
  275.  
  276.       inline node_pointer
  277.       get_new_node_for_leaf_insert(const_reference, false_type);
  278.  
  279.       inline node_pointer
  280.       get_new_node_for_leaf_insert(const_reference, true_type);
  281.  
  282.       inline void
  283.       actual_erase_node(node_pointer);
  284.  
  285.       inline std::pair<node_pointer, bool>
  286.       erase(node_pointer);
  287.  
  288.       inline void
  289.       update_min_max_for_erased_node(node_pointer);
  290.  
  291.       static void
  292.       clear_imp(node_pointer);
  293.  
  294.       inline std::pair<point_iterator, bool>
  295.       insert_leaf(const_reference);
  296.  
  297.       inline void
  298.       rotate_left(node_pointer);
  299.  
  300.       inline void
  301.       rotate_right(node_pointer);
  302.  
  303.       inline void
  304.       rotate_parent(node_pointer);
  305.  
  306.       inline void
  307.       apply_update(node_pointer, null_node_update_pointer);
  308.  
  309.       template<typename Node_Update_>
  310.         inline void
  311.         apply_update(node_pointer, Node_Update_*);
  312.  
  313.       inline void
  314.       update_to_top(node_pointer, null_node_update_pointer);
  315.  
  316.       template<typename Node_Update_>
  317.         inline void
  318.         update_to_top(node_pointer, Node_Update_*);
  319.  
  320.       bool
  321.       join_prep(PB_DS_CLASS_C_DEC&);
  322.  
  323.       void
  324.       join_finish(PB_DS_CLASS_C_DEC&);
  325.  
  326.       bool
  327.       split_prep(key_const_reference, PB_DS_CLASS_C_DEC&);
  328.  
  329.       void
  330.       split_finish(PB_DS_CLASS_C_DEC&);
  331.  
  332.       size_type
  333.       recursive_count(node_pointer) const;
  334.  
  335. #ifdef _GLIBCXX_DEBUG
  336.       void
  337.       assert_valid(const char*, int) const;
  338.  
  339.       void
  340.       structure_only_assert_valid(const char*, int) const;
  341.  
  342.       void
  343.       assert_node_consistent(const node_pointer, const char*, int) const;
  344. #endif
  345.  
  346.     private:
  347. #ifdef _GLIBCXX_DEBUG
  348.       void
  349.       assert_iterators(const char*, int) const;
  350.  
  351.       void
  352.       assert_consistent_with_debug_base(const char*, int) const;
  353.  
  354.       void
  355.       assert_node_consistent_with_left(const node_pointer,
  356.                                        const char*, int) const;
  357.  
  358.       void
  359.       assert_node_consistent_with_right(const node_pointer,
  360.                                         const char*, int) const;
  361.  
  362.       void
  363.       assert_consistent_with_debug_base(const node_pointer,
  364.                                         const char*, int) const;
  365.  
  366.       void
  367.       assert_min(const char*, int) const;
  368.  
  369.       void
  370.       assert_min_imp(const node_pointer, const char*, int) const;
  371.  
  372.       void
  373.       assert_max(const char*, int) const;
  374.  
  375.       void
  376.       assert_max_imp(const node_pointer, const char*, int) const;
  377.  
  378.       void
  379.       assert_size(const char*, int) const;
  380.  
  381.       typedef std::pair<const_pointer, const_pointer> node_consistent_t;
  382.  
  383.       node_consistent_t
  384.       assert_node_consistent_(const node_pointer, const char*, int) const;
  385. #endif
  386.  
  387.       void
  388.       initialize();
  389.  
  390.       node_pointer
  391.       recursive_copy_node(const node_pointer);
  392.  
  393.     protected:
  394.       node_pointer              m_p_head;
  395.       size_type                 m_size;
  396.       static node_allocator     s_node_allocator;
  397.     };
  398.  
  399. #define PB_DS_STRUCT_ONLY_ASSERT_VALID(X)                               \
  400.   _GLIBCXX_DEBUG_ONLY(X.structure_only_assert_valid(__FILE__, __LINE__);)
  401.  
  402. #define PB_DS_ASSERT_NODE_CONSISTENT(_Node)                             \
  403.   _GLIBCXX_DEBUG_ONLY(assert_node_consistent(_Node, __FILE__, __LINE__);)
  404.  
  405. #include <ext/pb_ds/detail/bin_search_tree_/constructors_destructor_fn_imps.hpp>
  406. #include <ext/pb_ds/detail/bin_search_tree_/iterators_fn_imps.hpp>
  407. #include <ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp>
  408. #include <ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp>
  409. #include <ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp>
  410. #include <ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp>
  411. #include <ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp>
  412. #include <ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp>
  413. #include <ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp>
  414. #include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp>
  415.  
  416. #undef PB_DS_ASSERT_NODE_CONSISTENT
  417. #undef PB_DS_STRUCT_ONLY_ASSERT_VALID
  418. #undef PB_DS_CLASS_C_DEC
  419. #undef PB_DS_CLASS_T_DEC
  420. #undef PB_DS_BIN_TREE_NAME
  421. #undef PB_DS_BIN_TREE_TRAITS_BASE
  422. #undef PB_DS_DEBUG_MAP_BASE_C_DEC
  423.  
  424. #ifdef PB_DS_TREE_TRACE
  425. #undef PB_DS_TREE_TRACE_BASE_C_DEC
  426. #endif
  427.   } // namespace detail
  428. } // namespace __gnu_pbds
  429.