Subversion Repositories Kolibri OS

Rev

Go to most recent revision | 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 rb_tree_map_/rb_tree_.hpp
  38.  * Contains an implementation for Red Black trees.
  39.  */
  40.  
  41. #include <ext/pb_ds/detail/standard_policies.hpp>
  42. #include <utility>
  43. #include <vector>
  44. #include <assert.h>
  45. #include <debug/debug.h>
  46.  
  47. namespace __gnu_pbds
  48. {
  49.   namespace detail
  50.   {
  51. #define PB_DS_CLASS_T_DEC \
  52.     template<typename Key, typename Mapped, typename Cmp_Fn, \
  53.              typename Node_And_It_Traits, typename _Alloc>
  54.  
  55. #ifdef PB_DS_DATA_TRUE_INDICATOR
  56. # define PB_DS_RB_TREE_NAME rb_tree_map
  57. # define PB_DS_RB_TREE_BASE_NAME bin_search_tree_map
  58. #endif
  59.  
  60. #ifdef PB_DS_DATA_FALSE_INDICATOR
  61. # define PB_DS_RB_TREE_NAME rb_tree_set
  62. # define PB_DS_RB_TREE_BASE_NAME bin_search_tree_set
  63. #endif
  64.  
  65. #define PB_DS_CLASS_C_DEC \
  66.     PB_DS_RB_TREE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc>
  67.  
  68. #define PB_DS_RB_TREE_BASE \
  69.     PB_DS_RB_TREE_BASE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc>
  70.  
  71.  
  72.     /**
  73.      *  @brief Red-Black tree.
  74.      *  @ingroup branch-detail
  75.      *
  76.      *  This implementation uses an idea from the SGI STL (using a
  77.      *  @a header node which is needed for efficient iteration).
  78.      */
  79.     template<typename Key,
  80.              typename Mapped,
  81.              typename Cmp_Fn,
  82.              typename Node_And_It_Traits,
  83.              typename _Alloc>
  84.     class PB_DS_RB_TREE_NAME : public PB_DS_RB_TREE_BASE
  85.     {
  86.     private:
  87.       typedef PB_DS_RB_TREE_BASE                         base_type;
  88.       typedef typename base_type::node_pointer           node_pointer;
  89.  
  90.     public:
  91.       typedef rb_tree_tag                                container_category;
  92.       typedef Cmp_Fn                                     cmp_fn;
  93.       typedef _Alloc                                     allocator_type;
  94.       typedef typename _Alloc::size_type                 size_type;
  95.       typedef typename _Alloc::difference_type           difference_type;
  96.       typedef typename base_type::key_type               key_type;
  97.       typedef typename base_type::key_pointer            key_pointer;
  98.       typedef typename base_type::key_const_pointer      key_const_pointer;
  99.       typedef typename base_type::key_reference          key_reference;
  100.       typedef typename base_type::key_const_reference    key_const_reference;
  101.       typedef typename base_type::mapped_type            mapped_type;
  102.       typedef typename base_type::mapped_pointer         mapped_pointer;
  103.       typedef typename base_type::mapped_const_pointer   mapped_const_pointer;
  104.       typedef typename base_type::mapped_reference       mapped_reference;
  105.       typedef typename base_type::mapped_const_reference mapped_const_reference;
  106.       typedef typename base_type::value_type             value_type;
  107.       typedef typename base_type::pointer                pointer;
  108.       typedef typename base_type::const_pointer          const_pointer;
  109.       typedef typename base_type::reference              reference;
  110.       typedef typename base_type::const_reference        const_reference;
  111.       typedef typename base_type::point_iterator         point_iterator;
  112.       typedef typename base_type::const_iterator         point_const_iterator;
  113.       typedef typename base_type::iterator               iterator;
  114.       typedef typename base_type::const_iterator         const_iterator;
  115.       typedef typename base_type::reverse_iterator       reverse_iterator;
  116.       typedef typename base_type::const_reverse_iterator const_reverse_iterator;
  117.       typedef typename base_type::node_update            node_update;
  118.  
  119.       PB_DS_RB_TREE_NAME();
  120.  
  121.       PB_DS_RB_TREE_NAME(const Cmp_Fn&);
  122.  
  123.       PB_DS_RB_TREE_NAME(const Cmp_Fn&, const node_update&);
  124.  
  125.       PB_DS_RB_TREE_NAME(const PB_DS_CLASS_C_DEC&);
  126.  
  127.       void
  128.       swap(PB_DS_CLASS_C_DEC&);
  129.  
  130.       template<typename It>
  131.       void
  132.       copy_from_range(It, It);
  133.  
  134.       inline std::pair<point_iterator, bool>
  135.       insert(const_reference);
  136.  
  137.       inline mapped_reference
  138.       operator[](key_const_reference r_key)
  139.       {
  140. #ifdef PB_DS_DATA_TRUE_INDICATOR
  141.         _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
  142.         std::pair<point_iterator, bool> ins_pair =
  143.         base_type::insert_leaf(value_type(r_key, mapped_type()));
  144.  
  145.         if (ins_pair.second == true)
  146.           {
  147.             ins_pair.first.m_p_nd->m_red = true;
  148.             _GLIBCXX_DEBUG_ONLY(this->structure_only_assert_valid(__FILE__, __LINE__);)
  149.             insert_fixup(ins_pair.first.m_p_nd);
  150.           }
  151.         _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
  152.         return ins_pair.first.m_p_nd->m_value.second;
  153. #else
  154.         insert(r_key);
  155.         return base_type::s_null_type;
  156. #endif
  157.       }
  158.  
  159.       inline bool
  160.       erase(key_const_reference);
  161.  
  162.       inline iterator
  163.       erase(iterator);
  164.  
  165.       inline reverse_iterator
  166.       erase(reverse_iterator);
  167.  
  168.       template<typename Pred>
  169.       inline size_type
  170.       erase_if(Pred);
  171.  
  172.       void
  173.       join(PB_DS_CLASS_C_DEC&);
  174.  
  175.       void
  176.       split(key_const_reference, PB_DS_CLASS_C_DEC&);
  177.  
  178.     private:
  179.  
  180. #ifdef _GLIBCXX_DEBUG
  181.       void
  182.       assert_valid(const char*, int) const;
  183.  
  184.       size_type
  185.       assert_node_consistent(const node_pointer, const char*, int) const;
  186. #endif
  187.  
  188.       inline static bool
  189.       is_effectively_black(const node_pointer);
  190.  
  191.       void
  192.       initialize();
  193.  
  194.       void
  195.       insert_fixup(node_pointer);
  196.  
  197.       void
  198.       erase_node(node_pointer);
  199.  
  200.       void
  201.       remove_node(node_pointer);
  202.  
  203.       void
  204.       remove_fixup(node_pointer, node_pointer);
  205.  
  206.       void
  207.       split_imp(node_pointer, PB_DS_CLASS_C_DEC&);
  208.  
  209.       inline node_pointer
  210.       split_min();
  211.  
  212.       std::pair<node_pointer, node_pointer>
  213.       split_min_imp();
  214.  
  215.       void
  216.       join_imp(node_pointer, node_pointer);
  217.  
  218.       std::pair<node_pointer, node_pointer>
  219.       find_join_pos_right(node_pointer, size_type, size_type);
  220.  
  221.       std::pair<node_pointer, node_pointer>
  222.       find_join_pos_left(node_pointer, size_type, size_type);
  223.  
  224.       inline size_type
  225.       black_height(node_pointer);
  226.  
  227.       void
  228.       split_at_node(node_pointer, PB_DS_CLASS_C_DEC&);
  229.     };
  230.  
  231. #define PB_DS_STRUCT_ONLY_ASSERT_VALID(X)                               \
  232.   _GLIBCXX_DEBUG_ONLY(X.structure_only_assert_valid(__FILE__, __LINE__);)
  233.  
  234. #include <ext/pb_ds/detail/rb_tree_map_/constructors_destructor_fn_imps.hpp>
  235. #include <ext/pb_ds/detail/rb_tree_map_/insert_fn_imps.hpp>
  236. #include <ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp>
  237. #include <ext/pb_ds/detail/rb_tree_map_/debug_fn_imps.hpp>
  238. #include <ext/pb_ds/detail/rb_tree_map_/split_join_fn_imps.hpp>
  239. #include <ext/pb_ds/detail/rb_tree_map_/info_fn_imps.hpp>
  240.  
  241. #undef PB_DS_STRUCT_ONLY_ASSERT_VALID
  242. #undef PB_DS_CLASS_T_DEC
  243. #undef PB_DS_CLASS_C_DEC
  244. #undef PB_DS_RB_TREE_NAME
  245. #undef PB_DS_RB_TREE_BASE_NAME
  246. #undef PB_DS_RB_TREE_BASE
  247.   } // namespace detail
  248. } // namespace __gnu_pbds
  249.