Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // -*- C++ -*-
  2.  
  3. // Copyright (C) 2005-2015 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 pairing_heap_/pairing_heap_.hpp
  38.  * Contains an implementation class for a pairing heap.
  39.  */
  40.  
  41. /*
  42.  * Pairing heap:
  43.  * Michael L. Fredman, Robert Sedgewick, Daniel Dominic Sleator,
  44.  *    and Robert Endre Tarjan, The Pairing Heap:
  45.  *    A New Form of Self-Adjusting Heap, Algorithmica, 1(1):111-129, 1986.
  46.  */
  47.  
  48. #include <ext/pb_ds/detail/cond_dealtor.hpp>
  49. #include <ext/pb_ds/detail/type_utils.hpp>
  50. #include <ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp>
  51. #include <debug/debug.h>
  52.  
  53. namespace __gnu_pbds
  54. {
  55.   namespace detail
  56.   {
  57. #define PB_DS_CLASS_T_DEC \
  58.   template<typename Value_Type, typename Cmp_Fn, typename _Alloc>
  59.  
  60. #define PB_DS_CLASS_C_DEC \
  61.   pairing_heap<Value_Type, Cmp_Fn, _Alloc>
  62.  
  63. #ifdef _GLIBCXX_DEBUG
  64. #define PB_DS_P_HEAP_BASE \
  65.   left_child_next_sibling_heap<Value_Type, Cmp_Fn, null_type, _Alloc, false>
  66. #else
  67. #define PB_DS_P_HEAP_BASE \
  68.   left_child_next_sibling_heap<Value_Type, Cmp_Fn, null_type, _Alloc>
  69. #endif
  70.  
  71.     /**
  72.      *  Pairing heap.
  73.      *
  74.      *  @ingroup heap-detail
  75.      */
  76.     template<typename Value_Type, typename Cmp_Fn, typename _Alloc>
  77.     class pairing_heap : public PB_DS_P_HEAP_BASE
  78.     {
  79.     private:
  80.       typedef PB_DS_P_HEAP_BASE                         base_type;
  81.       typedef typename base_type::node_pointer          node_pointer;
  82.  
  83.       typedef typename _Alloc::template rebind<Value_Type>::other __rebind_a;
  84.  
  85.     public:
  86.       typedef Value_Type                                value_type;
  87.       typedef Cmp_Fn                                    cmp_fn;
  88.       typedef _Alloc                                    allocator_type;
  89.       typedef typename _Alloc::size_type                size_type;
  90.       typedef typename _Alloc::difference_type          difference_type;
  91.  
  92.       typedef typename __rebind_a::pointer              pointer;
  93.       typedef typename __rebind_a::const_pointer        const_pointer;
  94.       typedef typename __rebind_a::reference            reference;
  95.       typedef typename __rebind_a::const_reference      const_reference;
  96.  
  97.       typedef typename base_type::point_const_iterator  point_const_iterator;
  98.       typedef typename base_type::point_iterator        point_iterator;
  99.       typedef typename base_type::const_iterator        const_iterator;
  100.       typedef typename base_type::iterator              iterator;
  101.  
  102.       pairing_heap();
  103.  
  104.       pairing_heap(const Cmp_Fn&);
  105.  
  106.       pairing_heap(const pairing_heap&);
  107.  
  108.       void
  109.       swap(pairing_heap&);
  110.  
  111.       ~pairing_heap();
  112.  
  113.       inline point_iterator
  114.       push(const_reference);
  115.  
  116.       void
  117.       modify(point_iterator, const_reference);
  118.  
  119.       inline const_reference
  120.       top() const;
  121.  
  122.       void
  123.       pop();
  124.  
  125.       void
  126.       erase(point_iterator);
  127.  
  128.       template<typename Pred>
  129.       size_type
  130.       erase_if(Pred);
  131.  
  132.       template<typename Pred>
  133.       void
  134.       split(Pred, pairing_heap&);
  135.  
  136.       void
  137.       join(pairing_heap&);
  138.  
  139.     protected:
  140.  
  141.       template<typename It>
  142.       void
  143.       copy_from_range(It, It);
  144.  
  145. #ifdef _GLIBCXX_DEBUG
  146.       void
  147.       assert_valid(const char*, int) const;
  148. #endif
  149.  
  150.     private:
  151.  
  152.       inline void
  153.       push_imp(node_pointer);
  154.  
  155.       node_pointer
  156.       join_node_children(node_pointer);
  157.  
  158.       node_pointer
  159.       forward_join(node_pointer, node_pointer);
  160.  
  161.       node_pointer
  162.       back_join(node_pointer, node_pointer);
  163.  
  164.       void
  165.       remove_node(node_pointer);
  166.     };
  167.  
  168. #define PB_DS_ASSERT_NODE_CONSISTENT(_Node, _Bool) \
  169.  _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(_Node, _Bool,    \
  170.                                                        __FILE__, __LINE__);)
  171.  
  172. #include <ext/pb_ds/detail/pairing_heap_/constructors_destructor_fn_imps.hpp>
  173. #include <ext/pb_ds/detail/pairing_heap_/debug_fn_imps.hpp>
  174. #include <ext/pb_ds/detail/pairing_heap_/find_fn_imps.hpp>
  175. #include <ext/pb_ds/detail/pairing_heap_/insert_fn_imps.hpp>
  176. #include <ext/pb_ds/detail/pairing_heap_/erase_fn_imps.hpp>
  177. #include <ext/pb_ds/detail/pairing_heap_/split_join_fn_imps.hpp>
  178.  
  179. #undef PB_DS_ASSERT_NODE_CONSISTENT
  180. #undef PB_DS_CLASS_C_DEC
  181. #undef PB_DS_CLASS_T_DEC
  182. #undef PB_DS_P_HEAP_BASE
  183.  
  184.   } // namespace detail
  185. } // namespace __gnu_pbds
  186.