1// -*- C++ -*-
2
3// Copyright (C) 2005, 2006 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 2, 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// You should have received a copy of the GNU General Public License
17// along with this library; see the file COPYING.  If not, write to
18// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19// MA 02111-1307, USA.
20
21// As a special exception, you may use this file as part of a free
22// software library without restriction.  Specifically, if other files
23// instantiate templates or use macros or inline functions from this
24// file, or you compile this file and link it with other files to
25// produce an executable, this file does not by itself cause the
26// resulting executable to be covered by the GNU General Public
27// License.  This exception does not however invalidate any other
28// reasons why the executable file might be covered by the GNU General
29// Public License.
30
31// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
32
33// Permission to use, copy, modify, sell, and distribute this software
34// is hereby granted without fee, provided that the above copyright
35// notice appears in all copies, and that both that copyright notice
36// and this permission notice appear in supporting documentation. None
37// of the above authors, nor IBM Haifa Research Laboratories, make any
38// representation about the suitability of this software for any
39// purpose. It is provided "as is" without express or implied
40// warranty.
41
42/**
43 * @file pairing_heap_.hpp
44 * Contains an implementation class for a pairing heap.
45 */
46
47/*
48 * Pairing heap:
49 * Michael L. Fredman, Robert Sedgewick, Daniel Dominic Sleator,
50 *    and Robert Endre Tarjan, The Pairing Heap:
51 *    A New Form of Self-Adjusting Heap, Algorithmica, 1(1):111-129, 1986.
52 */
53
54#include <ext/pb_ds/detail/cond_dealtor.hpp>
55#include <ext/pb_ds/detail/type_utils.hpp>
56#include <ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp>
57#include <ext/pb_ds/detail/left_child_next_sibling_heap_/null_metadata.hpp>
58#include <debug/debug.h>
59
60namespace pb_ds
61{
62  namespace detail
63  {
64
65#define PB_DS_CLASS_T_DEC \
66    template<typename Value_Type, class Cmp_Fn, class Allocator>
67
68#define PB_DS_CLASS_C_DEC \
69    pairing_heap_<Value_Type, Cmp_Fn, Allocator>
70
71#ifdef _GLIBCXX_DEBUG
72#define PB_DS_BASE_C_DEC \
73    left_child_next_sibling_heap_<			\
74									Value_Type, \
75									Cmp_Fn,	\
76									null_left_child_next_sibling_heap_node_metadata, \
77									Allocator, \
78									false>
79#else
80#define PB_DS_BASE_C_DEC						\
81    left_child_next_sibling_heap_<			\
82									Value_Type, \
83									Cmp_Fn,	\
84									null_left_child_next_sibling_heap_node_metadata, \
85									Allocator>
86#endif
87
88    /**
89     * class description = "P4ri|\|g h3ap$">
90     **/
91    template<typename Value_Type, class Cmp_Fn, class Allocator>
92    class pairing_heap_ : public PB_DS_BASE_C_DEC
93    {
94
95    private:
96      typedef PB_DS_BASE_C_DEC base_type;
97
98      typedef typename base_type::node_pointer node_pointer;
99
100    public:
101
102      typedef typename Allocator::size_type size_type;
103
104      typedef typename Allocator::difference_type difference_type;
105
106      typedef Value_Type value_type;
107
108      typedef
109      typename Allocator::template rebind<
110	value_type>::other::pointer
111      pointer;
112
113      typedef
114      typename Allocator::template rebind<
115	value_type>::other::const_pointer
116      const_pointer;
117
118      typedef
119      typename Allocator::template rebind<
120	value_type>::other::reference
121      reference;
122
123      typedef
124      typename Allocator::template rebind<
125	value_type>::other::const_reference
126      const_reference;
127
128      typedef
129      typename PB_DS_BASE_C_DEC::const_point_iterator
130      const_point_iterator;
131
132      typedef typename PB_DS_BASE_C_DEC::point_iterator point_iterator;
133
134      typedef typename PB_DS_BASE_C_DEC::const_iterator const_iterator;
135
136      typedef typename PB_DS_BASE_C_DEC::iterator iterator;
137
138      typedef Cmp_Fn cmp_fn;
139
140      typedef Allocator allocator;
141
142
143      pairing_heap_();
144
145      pairing_heap_(const Cmp_Fn& r_cmp_fn);
146
147      pairing_heap_(const PB_DS_CLASS_C_DEC& other);
148
149      void
150      swap(PB_DS_CLASS_C_DEC& other);
151
152      ~pairing_heap_();
153
154      inline point_iterator
155      push(const_reference r_val);
156
157      void
158      modify(point_iterator it, const_reference r_new_val);
159
160      inline const_reference
161      top() const;
162
163      void
164      pop();
165
166      void
167      erase(point_iterator it);
168
169      template<typename Pred>
170      size_type
171      erase_if(Pred pred);
172
173      template<typename Pred>
174      void
175      split(Pred pred, PB_DS_CLASS_C_DEC& other);
176
177      void
178      join(PB_DS_CLASS_C_DEC& other);
179
180    protected:
181
182      template<typename It>
183      void
184      copy_from_range(It first_it, It last_it);
185
186#ifdef _GLIBCXX_DEBUG
187      void
188      assert_valid() const;
189#endif
190
191    private:
192
193      inline void
194      push_imp(node_pointer p_nd);
195
196      node_pointer
197      join_node_children(node_pointer p_nd);
198
199      node_pointer
200      forward_join(node_pointer p_nd, node_pointer p_next);
201
202      node_pointer
203      back_join(node_pointer p_nd, node_pointer p_next);
204
205      void
206      remove_node(node_pointer p_nd);
207
208    };
209
210#include <ext/pb_ds/detail/pairing_heap_/constructors_destructor_fn_imps.hpp>
211#include <ext/pb_ds/detail/pairing_heap_/debug_fn_imps.hpp>
212#include <ext/pb_ds/detail/pairing_heap_/find_fn_imps.hpp>
213#include <ext/pb_ds/detail/pairing_heap_/insert_fn_imps.hpp>
214#include <ext/pb_ds/detail/pairing_heap_/erase_fn_imps.hpp>
215#include <ext/pb_ds/detail/pairing_heap_/split_join_fn_imps.hpp>
216
217#undef PB_DS_CLASS_C_DEC
218#undef PB_DS_CLASS_T_DEC
219#undef PB_DS_BASE_C_DEC
220
221  } // namespace detail
222} // namespace pb_ds
223