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 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.  
  59. namespace __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 _Alloc::template rebind<Key>::other::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 typename _Alloc::template rebind<non_const_value_type>::other value_allocator;
  124.       typedef typename value_allocator::pointer         value_vector;
  125.  
  126. #ifdef _GLIBCXX_DEBUG
  127.       typedef PB_DS_DEBUG_MAP_BASE_C_DEC                debug_base;
  128. #endif
  129.  
  130. #ifdef PB_DS_TREE_TRACE
  131.       typedef PB_DS_TREE_TRACE_BASE_C_DEC               trace_base;
  132. #endif
  133.  
  134.       typedef typename traits_base::pointer             mapped_pointer_;
  135.       typedef typename traits_base::const_pointer       mapped_const_pointer_;
  136.  
  137.       typedef typename traits_type::metadata_type       metadata_type;
  138.  
  139.       typedef typename _Alloc::template rebind<metadata_type>::other metadata_allocator;
  140.       typedef typename metadata_allocator::pointer      metadata_pointer;
  141.       typedef typename metadata_allocator::const_reference metadata_const_reference;
  142.       typedef typename metadata_allocator::reference    metadata_reference;
  143.  
  144.       typedef typename traits_type::null_node_update_pointer
  145.       null_node_update_pointer;
  146.  
  147.     public:
  148.       typedef ov_tree_tag                                container_category;
  149.       typedef _Alloc                                    allocator_type;
  150.       typedef typename _Alloc::size_type                size_type;
  151.       typedef typename _Alloc::difference_type          difference_type;
  152.       typedef Cmp_Fn                                    cmp_fn;
  153.  
  154.       typedef typename traits_base::key_type            key_type;
  155.       typedef typename traits_base::key_pointer         key_pointer;
  156.       typedef typename traits_base::key_const_pointer   key_const_pointer;
  157.       typedef typename traits_base::key_reference       key_reference;
  158.       typedef typename traits_base::key_const_reference key_const_reference;
  159.       typedef typename traits_base::mapped_type         mapped_type;
  160.       typedef typename traits_base::mapped_pointer      mapped_pointer;
  161.       typedef typename traits_base::mapped_const_pointer mapped_const_pointer;
  162.       typedef typename traits_base::mapped_reference    mapped_reference;
  163.       typedef typename traits_base::mapped_const_reference mapped_const_reference;
  164.       typedef typename traits_base::value_type          value_type;
  165.       typedef typename traits_base::pointer             pointer;
  166.       typedef typename traits_base::const_pointer       const_pointer;
  167.       typedef typename traits_base::reference           reference;
  168.       typedef typename traits_base::const_reference     const_reference;
  169.  
  170.       typedef const_pointer                             point_const_iterator;
  171. #ifdef PB_DS_DATA_TRUE_INDICATOR
  172.       typedef pointer                                   point_iterator;
  173. #else
  174.       typedef point_const_iterator                      point_iterator;
  175. #endif
  176.  
  177.       typedef point_iterator                            iterator;
  178.       typedef point_const_iterator                      const_iterator;
  179.  
  180.       /// Conditional destructor.
  181.       template<typename Size_Type>
  182.         class cond_dtor
  183.         {
  184.         public:
  185.           cond_dtor(value_vector a_vec, iterator& r_last_it,
  186.                     Size_Type total_size)
  187.           : m_a_vec(a_vec), m_r_last_it(r_last_it), m_max_size(total_size),
  188.             m_no_action(false)
  189.           { }
  190.  
  191.           ~cond_dtor()
  192.           {
  193.             if (m_no_action)
  194.               return;
  195.             iterator it = m_a_vec;
  196.             while (it != m_r_last_it)
  197.               {
  198.                 it->~value_type();
  199.                 ++it;
  200.               }
  201.            
  202.             if (m_max_size > 0)
  203.               value_allocator().deallocate(m_a_vec, m_max_size);
  204.           }
  205.  
  206.           inline void
  207.           set_no_action()
  208.           { m_no_action = true; }
  209.          
  210.         protected:
  211.           value_vector          m_a_vec;
  212.           iterator&             m_r_last_it;
  213.           const Size_Type       m_max_size;
  214.           bool                  m_no_action;
  215.        };
  216.      
  217.       typedef typename traits_type::node_update         node_update;
  218.       typedef typename traits_type::node_iterator       node_iterator;
  219.       typedef typename traits_type::node_const_iterator node_const_iterator;
  220.  
  221.  
  222.       PB_DS_OV_TREE_NAME();
  223.  
  224.       PB_DS_OV_TREE_NAME(const Cmp_Fn&);
  225.  
  226.       PB_DS_OV_TREE_NAME(const Cmp_Fn&, const node_update&);
  227.  
  228.       PB_DS_OV_TREE_NAME(const PB_DS_CLASS_C_DEC&);
  229.  
  230.       ~PB_DS_OV_TREE_NAME();
  231.  
  232.       void
  233.       swap(PB_DS_CLASS_C_DEC&);
  234.  
  235.       template<typename It>
  236.       void
  237.       copy_from_range(It, It);
  238.  
  239.       inline size_type
  240.       max_size() const;
  241.  
  242.       inline bool
  243.       empty() const;
  244.  
  245.       inline size_type
  246.       size() const;
  247.  
  248.       Cmp_Fn&
  249.       get_cmp_fn();
  250.  
  251.       const Cmp_Fn&
  252.       get_cmp_fn() const;
  253.  
  254.       inline mapped_reference
  255.       operator[](key_const_reference r_key)
  256.       {
  257. #ifdef PB_DS_DATA_TRUE_INDICATOR
  258.         PB_DS_ASSERT_VALID((*this))
  259.         point_iterator it = lower_bound(r_key);
  260.         if (it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*it)))
  261.           {
  262.             PB_DS_CHECK_KEY_EXISTS(r_key)
  263.             PB_DS_ASSERT_VALID((*this))
  264.              return it->second;
  265.           }
  266.         return insert_new_val(it, std::make_pair(r_key, mapped_type()))->second;
  267. #else
  268.         insert(r_key);
  269.         return traits_base::s_null_type;
  270. #endif
  271.       }
  272.  
  273.       inline std::pair<point_iterator, bool>
  274.       insert(const_reference r_value)
  275.       {
  276.         PB_DS_ASSERT_VALID((*this))
  277.         key_const_reference r_key = PB_DS_V2F(r_value);
  278.         point_iterator it = lower_bound(r_key);
  279.  
  280.         if (it != end()&&  !Cmp_Fn::operator()(r_key, PB_DS_V2F(*it)))
  281.           {
  282.             PB_DS_ASSERT_VALID((*this))
  283.             PB_DS_CHECK_KEY_EXISTS(r_key)
  284.             return std::make_pair(it, false);
  285.           }
  286.  
  287.         return std::make_pair(insert_new_val(it, r_value), true);
  288.       }
  289.  
  290.       inline point_iterator
  291.       lower_bound(key_const_reference r_key)
  292.       {
  293.         pointer it = m_a_values;
  294.         pointer e_it = m_a_values + m_size;
  295.         while (it != e_it)
  296.           {
  297.             pointer mid_it = it + ((e_it - it) >> 1);
  298.             if (cmp_fn::operator()(PB_DS_V2F(*mid_it), r_key))
  299.               it = ++mid_it;
  300.             else
  301.               e_it = mid_it;
  302.           }
  303.         return it;
  304.       }
  305.  
  306.       inline point_const_iterator
  307.       lower_bound(key_const_reference r_key) const
  308.       { return const_cast<PB_DS_CLASS_C_DEC& >(*this).lower_bound(r_key); }
  309.  
  310.       inline point_iterator
  311.       upper_bound(key_const_reference r_key)
  312.       {
  313.         iterator pot_it = lower_bound(r_key);
  314.         if (pot_it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*pot_it)))
  315.           {
  316.             PB_DS_CHECK_KEY_EXISTS(r_key)
  317.             return ++pot_it;
  318.           }
  319.  
  320.         PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key)
  321.         return pot_it;
  322.       }
  323.  
  324.       inline point_const_iterator
  325.       upper_bound(key_const_reference r_key) const
  326.       { return const_cast<PB_DS_CLASS_C_DEC&>(*this).upper_bound(r_key); }
  327.  
  328.       inline point_iterator
  329.       find(key_const_reference r_key)
  330.       {
  331.         PB_DS_ASSERT_VALID((*this))
  332.         iterator pot_it = lower_bound(r_key);
  333.         if (pot_it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*pot_it)))
  334.           {
  335.             PB_DS_CHECK_KEY_EXISTS(r_key)
  336.             return pot_it;
  337.           }
  338.  
  339.         PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key)
  340.         return end();
  341.       }
  342.  
  343.       inline point_const_iterator
  344.       find(key_const_reference r_key) const
  345.       { return (const_cast<PB_DS_CLASS_C_DEC&>(*this).find(r_key)); }
  346.  
  347.       bool
  348.       erase(key_const_reference);
  349.  
  350.       template<typename Pred>
  351.       inline size_type
  352.       erase_if(Pred);
  353.  
  354.       inline iterator
  355.       erase(iterator it)
  356.       { return erase_imp<iterator>(it); }
  357.  
  358.       void
  359.       clear();
  360.  
  361.       void
  362.       join(PB_DS_CLASS_C_DEC&);
  363.  
  364.       void
  365.       split(key_const_reference, PB_DS_CLASS_C_DEC&);
  366.  
  367.       inline iterator
  368.       begin()
  369.       { return m_a_values; }
  370.  
  371.       inline const_iterator
  372.       begin() const
  373.       { return m_a_values; }
  374.  
  375.       inline iterator
  376.       end()
  377.       { return m_end_it; }
  378.  
  379.       inline const_iterator
  380.       end() const
  381.       { return m_end_it; }
  382.  
  383.       /// Returns a const node_iterator corresponding to the node at the
  384.       /// root of the tree.
  385.       inline node_const_iterator
  386.       node_begin() const;
  387.  
  388.       /// Returns a node_iterator corresponding to the node at the
  389.       /// root of the tree.
  390.       inline node_iterator
  391.       node_begin();
  392.  
  393.       /// Returns a const node_iterator corresponding to a node just
  394.       /// after a leaf of the tree.
  395.       inline node_const_iterator
  396.       node_end() const;
  397.  
  398.       /// Returns a node_iterator corresponding to a node just
  399.       /// after a leaf of the tree.
  400.       inline node_iterator
  401.       node_end();
  402.  
  403.     private:
  404.  
  405.       inline void
  406.       update(node_iterator, null_node_update_pointer);
  407.  
  408.       template<typename Node_Update>
  409.       void
  410.       update(node_iterator, Node_Update*);
  411.  
  412.       void
  413.       reallocate_metadata(null_node_update_pointer, size_type);
  414.  
  415.       template<typename Node_Update_>
  416.       void
  417.       reallocate_metadata(Node_Update_*, size_type);
  418.  
  419.       template<typename It>
  420.       void
  421.       copy_from_ordered_range(It, It);
  422.  
  423.       void
  424.       value_swap(PB_DS_CLASS_C_DEC&);
  425.  
  426.       template<typename It>
  427.       void
  428.       copy_from_ordered_range(It, It, It, It);
  429.  
  430.       template<typename Ptr>
  431.       inline static Ptr
  432.       mid_pointer(Ptr p_begin, Ptr p_end)
  433.       {
  434.         _GLIBCXX_DEBUG_ASSERT(p_end >= p_begin);
  435.         return (p_begin + (p_end - p_begin) / 2);
  436.       }
  437.  
  438.       inline iterator
  439.       insert_new_val(iterator it, const_reference r_value)
  440.       {
  441. #ifdef PB_DS_REGRESSION
  442.         typename _Alloc::group_adjustor adjust(m_size);
  443. #endif
  444.  
  445.         PB_DS_CHECK_KEY_DOES_NOT_EXIST(PB_DS_V2F(r_value))
  446.  
  447.         value_vector a_values = s_value_alloc.allocate(m_size + 1);
  448.  
  449.         iterator source_it = begin();
  450.         iterator source_end_it = end();
  451.         iterator target_it = a_values;
  452.         iterator ret_it;
  453.  
  454.         cond_dtor<size_type> cd(a_values, target_it, m_size + 1);
  455.         while (source_it != it)
  456.           {
  457.             new (const_cast<void*>(static_cast<const void*>(target_it)))
  458.               value_type(*source_it++);
  459.             ++target_it;
  460.           }
  461.  
  462.         new (const_cast<void*>(static_cast<const void*>(ret_it = target_it)))
  463.           value_type(r_value);
  464.         ++target_it;
  465.  
  466.         while (source_it != source_end_it)
  467.           {
  468.             new (const_cast<void*>(static_cast<const void*>(target_it)))
  469.               value_type(*source_it++);
  470.             ++target_it;
  471.           }
  472.  
  473.         reallocate_metadata((node_update*)this, m_size + 1);
  474.         cd.set_no_action();
  475.         if (m_size != 0)
  476.           {
  477.             cond_dtor<size_type> cd1(m_a_values, m_end_it, m_size);
  478.           }
  479.  
  480.         ++m_size;
  481.         m_a_values = a_values;
  482.         m_end_it = m_a_values + m_size;
  483.         _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_value)));
  484.         update(node_begin(), (node_update* )this);
  485.         PB_DS_ASSERT_VALID((*this))
  486.         return ret_it;
  487.       }
  488.  
  489. #ifdef _GLIBCXX_DEBUG
  490.       void
  491.       assert_valid(const char*, int) const;
  492.  
  493.       void
  494.       assert_iterators(const char*, int) const;
  495. #endif
  496.  
  497.       template<typename It>
  498.       It
  499.       erase_imp(It);
  500.  
  501.       inline node_const_iterator
  502.       PB_DS_node_begin_imp() const;
  503.  
  504.       inline node_const_iterator
  505.       PB_DS_node_end_imp() const;
  506.  
  507.       inline node_iterator
  508.       PB_DS_node_begin_imp();
  509.  
  510.       inline node_iterator
  511.       PB_DS_node_end_imp();
  512.  
  513.     private:
  514.       static value_allocator    s_value_alloc;
  515.       static metadata_allocator s_metadata_alloc;
  516.  
  517.       value_vector              m_a_values;
  518.       metadata_pointer          m_a_metadata;
  519.       iterator                  m_end_it;
  520.       size_type                 m_size;
  521.     };
  522.  
  523. #include <ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp>
  524. #include <ext/pb_ds/detail/ov_tree_map_/iterators_fn_imps.hpp>
  525. #include <ext/pb_ds/detail/ov_tree_map_/debug_fn_imps.hpp>
  526. #include <ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp>
  527. #include <ext/pb_ds/detail/ov_tree_map_/insert_fn_imps.hpp>
  528. #include <ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp>
  529. #include <ext/pb_ds/detail/ov_tree_map_/split_join_fn_imps.hpp>
  530. #include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp>
  531.  
  532. #undef PB_DS_CLASS_C_DEC
  533. #undef PB_DS_CLASS_T_DEC
  534. #undef PB_DS_OV_TREE_NAME
  535. #undef PB_DS_OV_TREE_TRAITS_BASE
  536. #undef PB_DS_DEBUG_MAP_BASE_C_DEC
  537. #ifdef PB_DS_TREE_TRACE
  538. #undef PB_DS_TREE_TRACE_BASE_C_DEC
  539. #endif
  540. #undef PB_DS_CONST_NODE_ITERATOR_NAME
  541.   } // namespace detail
  542. } // namespace __gnu_pbds
  543.