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 splay_tree_/splay_tree_.hpp
  38.  * Contains an implementation class for splay trees.
  39.  */
  40. /*
  41.  * This implementation uses an idea from the SGI STL (using a @a header node
  42.  *    which is needed for efficient iteration). Following is the SGI STL
  43.  *    copyright.
  44.  *
  45.  * Copyright (c) 1996,1997
  46.  * Silicon Graphics Computer Systems, Inc.
  47.  *
  48.  * Permission to use, copy, modify, distribute and sell this software
  49.  * and its documentation for any purpose is hereby granted without fee,
  50.  * provided that the above copyright notice appear in all copies and
  51.  * that both that copyright notice and this permission notice appear
  52.  * in supporting documentation.    Silicon Graphics makes no
  53.  * representations about the suitability of this software for any
  54.  * purpose.    It is provided "as is" without express or implied warranty.
  55.  *
  56.  *
  57.  * Copyright (c) 1994
  58.  * Hewlett-Packard Company
  59.  *
  60.  * Permission to use, copy, modify, distribute and sell this software
  61.  * and its documentation for any purpose is hereby granted without fee,
  62.  * provided that the above copyright notice appear in all copies and
  63.  * that both that copyright notice and this permission notice appear
  64.  * in supporting documentation.    Hewlett-Packard Company makes no
  65.  * representations about the suitability of this software for any
  66.  * purpose.    It is provided "as is" without express or implied warranty.
  67.  *
  68.  *
  69.  */
  70.  
  71. #include <utility>
  72. #include <vector>
  73. #include <assert.h>
  74. #include <debug/debug.h>
  75.  
  76. namespace __gnu_pbds
  77. {
  78.   namespace detail
  79.   {
  80. #ifdef PB_DS_DATA_TRUE_INDICATOR
  81. # define PB_DS_S_TREE_NAME splay_tree_map
  82. # define PB_DS_S_TREE_BASE_NAME bin_search_tree_map
  83. #endif
  84.  
  85. #ifdef PB_DS_DATA_FALSE_INDICATOR
  86. # define PB_DS_S_TREE_NAME splay_tree_set
  87. # define PB_DS_S_TREE_BASE_NAME bin_search_tree_set
  88. #endif
  89.  
  90. #define PB_DS_CLASS_T_DEC \
  91.     template<typename Key, typename Mapped, typename Cmp_Fn, \
  92.              typename Node_And_It_Traits, typename _Alloc>
  93.  
  94. #define PB_DS_CLASS_C_DEC \
  95.     PB_DS_S_TREE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc>
  96.  
  97. #define PB_DS_S_TREE_BASE \
  98.     PB_DS_S_TREE_BASE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc>
  99.  
  100.  
  101.     /**
  102.      *  @brief Splay tree.
  103.      *  @ingroup branch-detail
  104.      */
  105.     template<typename Key, typename Mapped, typename Cmp_Fn,
  106.              typename Node_And_It_Traits, typename _Alloc>
  107.     class PB_DS_S_TREE_NAME : public PB_DS_S_TREE_BASE
  108.     {
  109.     private:
  110.       typedef PB_DS_S_TREE_BASE                          base_type;
  111. #ifdef _GLIBCXX_DEBUG
  112.       typedef base_type debug_base;
  113. #endif
  114.       typedef typename base_type::node_pointer           node_pointer;
  115.  
  116.     public:
  117.       typedef splay_tree_tag                             container_category;
  118.       typedef _Alloc                                     allocator_type;
  119.       typedef typename _Alloc::size_type                 size_type;
  120.       typedef typename _Alloc::difference_type           difference_type;
  121.       typedef Cmp_Fn                                     cmp_fn;
  122.       typedef typename base_type::key_type               key_type;
  123.       typedef typename base_type::key_pointer            key_pointer;
  124.       typedef typename base_type::key_const_pointer      key_const_pointer;
  125.       typedef typename base_type::key_reference          key_reference;
  126.       typedef typename base_type::key_const_reference    key_const_reference;
  127.       typedef typename base_type::mapped_type            mapped_type;
  128.       typedef typename base_type::mapped_pointer         mapped_pointer;
  129.       typedef typename base_type::mapped_const_pointer   mapped_const_pointer;
  130.       typedef typename base_type::mapped_reference       mapped_reference;
  131.       typedef typename base_type::mapped_const_reference mapped_const_reference;
  132.       typedef typename base_type::value_type             value_type;
  133.       typedef typename base_type::pointer                pointer;
  134.       typedef typename base_type::const_pointer          const_pointer;
  135.       typedef typename base_type::reference              reference;
  136.       typedef typename base_type::const_reference        const_reference;
  137.       typedef typename base_type::point_iterator         point_iterator;
  138.       typedef typename base_type::const_iterator         point_const_iterator;
  139.       typedef typename base_type::iterator               iterator;
  140.       typedef typename base_type::const_iterator         const_iterator;
  141.       typedef typename base_type::reverse_iterator       reverse_iterator;
  142.       typedef typename base_type::const_reverse_iterator const_reverse_iterator;
  143.       typedef typename base_type::node_update            node_update;
  144.  
  145.       PB_DS_S_TREE_NAME();
  146.  
  147.       PB_DS_S_TREE_NAME(const Cmp_Fn&);
  148.  
  149.       PB_DS_S_TREE_NAME(const Cmp_Fn&, const node_update&);
  150.  
  151.       PB_DS_S_TREE_NAME(const PB_DS_CLASS_C_DEC&);
  152.  
  153.       void
  154.       swap(PB_DS_CLASS_C_DEC&);
  155.  
  156.       template<typename It>
  157.       void
  158.       copy_from_range(It, It);
  159.  
  160.       void
  161.       initialize();
  162.  
  163.       inline std::pair<point_iterator, bool>
  164.       insert(const_reference r_value);
  165.  
  166.       inline mapped_reference
  167.       operator[](key_const_reference r_key)
  168.       {
  169. #ifdef PB_DS_DATA_TRUE_INDICATOR
  170.         _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
  171.         std::pair<point_iterator, bool> ins_pair =
  172.           insert_leaf_imp(value_type(r_key, mapped_type()));
  173.  
  174.         ins_pair.first.m_p_nd->m_special = false;
  175.         _GLIBCXX_DEBUG_ONLY(base_type::assert_valid(__FILE__, __LINE__));
  176.         splay(ins_pair.first.m_p_nd);
  177.         _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
  178.         return ins_pair.first.m_p_nd->m_value.second;
  179. #else
  180.         insert(r_key);
  181.         return base_type::s_null_type;
  182. #endif
  183.       }
  184.  
  185.       inline point_iterator
  186.       find(key_const_reference);
  187.  
  188.       inline point_const_iterator
  189.       find(key_const_reference) const;
  190.  
  191.       inline bool
  192.       erase(key_const_reference);
  193.  
  194.       inline iterator
  195.       erase(iterator it);
  196.  
  197.       inline reverse_iterator
  198.       erase(reverse_iterator);
  199.  
  200.       template<typename Pred>
  201.       inline size_type
  202.       erase_if(Pred);
  203.  
  204.       void
  205.       join(PB_DS_CLASS_C_DEC&);
  206.  
  207.       void
  208.       split(key_const_reference, PB_DS_CLASS_C_DEC&);
  209.  
  210.     private:
  211.       inline std::pair<point_iterator, bool>
  212.       insert_leaf_imp(const_reference);
  213.  
  214.       inline node_pointer
  215.       find_imp(key_const_reference);
  216.  
  217.       inline const node_pointer
  218.       find_imp(key_const_reference) const;
  219.  
  220. #ifdef _GLIBCXX_DEBUG
  221.       void
  222.       assert_valid(const char* file, int line) const;
  223.  
  224.       void
  225.       assert_special_imp(const node_pointer, const char* file, int line) const;
  226. #endif
  227.  
  228.       void
  229.       splay(node_pointer);
  230.  
  231.       inline void
  232.       splay_zig_zag_left(node_pointer, node_pointer, node_pointer);
  233.  
  234.       inline void
  235.       splay_zig_zag_right(node_pointer, node_pointer, node_pointer);
  236.  
  237.       inline void
  238.       splay_zig_zig_left(node_pointer, node_pointer, node_pointer);
  239.  
  240.       inline void
  241.       splay_zig_zig_right(node_pointer, node_pointer, node_pointer);
  242.  
  243.       inline void
  244.       splay_zz_start(node_pointer, node_pointer, node_pointer);
  245.  
  246.       inline void
  247.       splay_zz_end(node_pointer, node_pointer, node_pointer);
  248.  
  249.       inline node_pointer
  250.       leftmost(node_pointer);
  251.  
  252.       void
  253.       erase_node(node_pointer);
  254.     };
  255.  
  256. #define PB_DS_ASSERT_BASE_NODE_CONSISTENT(_Node)                        \
  257.   _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(_Node,          \
  258.                                                         __FILE__, __LINE__);)
  259.  
  260. #include <ext/pb_ds/detail/splay_tree_/constructors_destructor_fn_imps.hpp>
  261. #include <ext/pb_ds/detail/splay_tree_/insert_fn_imps.hpp>
  262. #include <ext/pb_ds/detail/splay_tree_/splay_fn_imps.hpp>
  263. #include <ext/pb_ds/detail/splay_tree_/erase_fn_imps.hpp>
  264. #include <ext/pb_ds/detail/splay_tree_/find_fn_imps.hpp>
  265. #include <ext/pb_ds/detail/splay_tree_/debug_fn_imps.hpp>
  266. #include <ext/pb_ds/detail/splay_tree_/split_join_fn_imps.hpp>
  267.  
  268. #undef PB_DS_ASSERT_BASE_NODE_CONSISTENT
  269. #undef PB_DS_CLASS_T_DEC
  270. #undef PB_DS_CLASS_C_DEC
  271. #undef PB_DS_S_TREE_NAME
  272. #undef PB_DS_S_TREE_BASE_NAME
  273. #undef PB_DS_S_TREE_BASE
  274.   } // namespace detail
  275. } // namespace __gnu_pbds
  276.