libstdc++
pairing_heap_.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005, 2006, 2009, 2011 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 
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 
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 
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