left_child_next_sibling_heap_.hpp revision 302408 
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 left_child_next_sibling_heap_.hpp
44 * Contains an implementation class for a basic heap.
45 */
46
47#ifndef PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_HPP
48#define PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_HPP
49
50/*
51 * Based on CLRS.
52 */
53
54#include <iterator>
55#include <ext/pb_ds/detail/cond_dealtor.hpp>
56#include <ext/pb_ds/detail/type_utils.hpp>
57#include <ext/pb_ds/detail/left_child_next_sibling_heap_/node.hpp>
58#include <ext/pb_ds/detail/left_child_next_sibling_heap_/const_point_iterator.hpp>
59#include <ext/pb_ds/detail/left_child_next_sibling_heap_/const_iterator.hpp>
60#ifdef PB_DS_LC_NS_HEAP_TRACE_
61#include <iostream>
62#endif
63#include <debug/debug.h>
64
65namespace pb_ds
66{
67  namespace detail
68  {
69
70#ifdef _GLIBCXX_DEBUG
71#define PB_DS_CLASS_T_DEC						\
72    template<								\
73						typename Value_Type,	\
74						class Cmp_Fn,		\
75						typename Node_Metadata,	\
76						class Allocator,	\
77						bool Single_Link_Roots>
78#else
79#define PB_DS_CLASS_T_DEC						\
80    template<								\
81						typename Value_Type,	\
82						class Cmp_Fn,		\
83						typename Node_Metadata,	\
84						class Allocator>
85#endif
86
87#ifdef _GLIBCXX_DEBUG
88#define PB_DS_CLASS_C_DEC						\
89    left_child_next_sibling_heap_<					\
90							Value_Type,	\
91							Cmp_Fn,		\
92							Node_Metadata,	\
93							Allocator,	\
94							Single_Link_Roots>
95#else
96#define PB_DS_CLASS_C_DEC						\
97    left_child_next_sibling_heap_<					\
98							Value_Type,	\
99							Cmp_Fn,		\
100							Node_Metadata,	\
101							Allocator>
102#endif
103
104    /**
105     * class description = "Base class for some types of h3ap$">
106     **/
107#ifdef _GLIBCXX_DEBUG
108    template<typename Value_Type,
109	     class Cmp_Fn,
110	     typename Node_Metadata,
111	     class Allocator,
112	     bool Single_Link_Roots>
113#else
114    template<typename Value_Type,
115	     class Cmp_Fn,
116	     typename Node_Metadata,
117	     class Allocator>
118#endif
119    class left_child_next_sibling_heap_ : public Cmp_Fn
120    {
121
122    protected:
123      typedef
124      typename Allocator::template rebind<
125      left_child_next_sibling_heap_node_<
126      Value_Type,
127      Node_Metadata,
128      Allocator> >::other
129      node_allocator;
130
131      typedef typename node_allocator::value_type node;
132
133      typedef typename node_allocator::pointer node_pointer;
134
135      typedef typename node_allocator::const_pointer const_node_pointer;
136
137      typedef Node_Metadata node_metadata;
138
139      typedef std::pair< node_pointer, node_pointer> node_pointer_pair;
140
141    private:
142      typedef cond_dealtor< node, Allocator> cond_dealtor_t;
143
144      enum
145	{
146	  simple_value = is_simple<Value_Type>::value
147	};
148
149      typedef integral_constant<int, simple_value> no_throw_copies_t;
150
151    public:
152
153      typedef typename Allocator::size_type size_type;
154
155      typedef typename Allocator::difference_type difference_type;
156
157      typedef Value_Type value_type;
158
159      typedef
160      typename Allocator::template rebind<
161	value_type>::other::pointer
162      pointer;
163
164      typedef
165      typename Allocator::template rebind<
166	value_type>::other::const_pointer
167      const_pointer;
168
169      typedef
170      typename Allocator::template rebind<
171	value_type>::other::reference
172      reference;
173
174      typedef
175      typename Allocator::template rebind<
176	value_type>::other::const_reference
177      const_reference;
178
179      typedef
180      left_child_next_sibling_heap_node_const_point_iterator_<
181	node,
182	Allocator>
183      const_point_iterator;
184
185      typedef const_point_iterator point_iterator;
186
187      typedef
188      left_child_next_sibling_heap_const_iterator_<
189	node,
190	Allocator>
191      const_iterator;
192
193      typedef const_iterator iterator;
194
195      typedef Cmp_Fn cmp_fn;
196
197      typedef Allocator allocator;
198
199    public:
200
201      left_child_next_sibling_heap_();
202
203      left_child_next_sibling_heap_(const Cmp_Fn& r_cmp_fn);
204
205      left_child_next_sibling_heap_(const PB_DS_CLASS_C_DEC& other);
206
207      void
208      swap(PB_DS_CLASS_C_DEC& other);
209
210      ~left_child_next_sibling_heap_();
211
212      inline bool
213      empty() const;
214
215      inline size_type
216      size() const;
217
218      inline size_type
219      max_size() const;
220
221      Cmp_Fn&
222      get_cmp_fn();
223
224      const Cmp_Fn&
225      get_cmp_fn() const;
226
227      inline iterator
228      begin();
229
230      inline const_iterator
231      begin() const;
232
233      inline iterator
234      end();
235
236      inline const_iterator
237      end() const;
238
239      void
240      clear();
241
242#ifdef PB_DS_LC_NS_HEAP_TRACE_
243      void
244      trace() const;
245#endif
246
247    protected:
248
249      inline node_pointer
250      get_new_node_for_insert(const_reference r_val);
251
252      inline static void
253      make_child_of(node_pointer p_nd, node_pointer p_new_parent);
254
255      void
256      value_swap(PB_DS_CLASS_C_DEC& other);
257
258      inline static node_pointer
259      parent(node_pointer p_nd);
260
261      inline void
262      swap_with_parent(node_pointer p_nd, node_pointer p_parent);
263
264      void
265      bubble_to_top(node_pointer p_nd);
266
267      inline void
268      actual_erase_node(node_pointer p_nd);
269
270      void
271      clear_imp(node_pointer p_nd);
272
273      void
274      to_linked_list();
275
276      template<typename Pred>
277      node_pointer
278      prune(Pred pred);
279
280#ifdef _GLIBCXX_DEBUG
281      void
282      assert_valid() const;
283
284      void
285      assert_node_consistent(const_node_pointer p_nd, bool single_link) const;
286
287      static size_type
288      size_under_node(const_node_pointer p_nd);
289
290      static size_type
291      degree(const_node_pointer p_nd);
292#endif
293
294#ifdef PB_DS_LC_NS_HEAP_TRACE_
295      static void
296      trace_node(const_node_pointer, size_type level);
297#endif
298
299    protected:
300      node_pointer m_p_root;
301
302      size_type m_size;
303
304    private:
305#ifdef _GLIBCXX_DEBUG
306      void
307      assert_iterators() const;
308
309      void
310      assert_size() const;
311
312      static size_type
313      size_from_node(const_node_pointer p_nd);
314#endif
315
316      node_pointer
317      recursive_copy_node(const_node_pointer p_nd);
318
319      inline node_pointer
320      get_new_node_for_insert(const_reference r_val, false_type);
321
322      inline node_pointer
323      get_new_node_for_insert(const_reference r_val, true_type);
324
325#ifdef PB_DS_LC_NS_HEAP_TRACE_
326      template<typename Metadata_>
327      static void
328      trace_node_metadata(const_node_pointer p_nd, type_to_type<Metadata_>);
329
330      static void
331      trace_node_metadata(const_node_pointer, type_to_type<null_left_child_next_sibling_heap_node_metadata>);
332#endif
333
334    private:
335      static node_allocator s_node_allocator;
336
337      static no_throw_copies_t s_no_throw_copies_ind;
338    };
339
340#include <ext/pb_ds/detail/left_child_next_sibling_heap_/constructors_destructor_fn_imps.hpp>
341#include <ext/pb_ds/detail/left_child_next_sibling_heap_/iterators_fn_imps.hpp>
342#include <ext/pb_ds/detail/left_child_next_sibling_heap_/debug_fn_imps.hpp>
343#include <ext/pb_ds/detail/left_child_next_sibling_heap_/trace_fn_imps.hpp>
344#include <ext/pb_ds/detail/left_child_next_sibling_heap_/insert_fn_imps.hpp>
345#include <ext/pb_ds/detail/left_child_next_sibling_heap_/erase_fn_imps.hpp>
346#include <ext/pb_ds/detail/left_child_next_sibling_heap_/info_fn_imps.hpp>
347#include <ext/pb_ds/detail/left_child_next_sibling_heap_/policy_access_fn_imps.hpp>
348
349#undef PB_DS_CLASS_C_DEC
350#undef PB_DS_CLASS_T_DEC
351
352  } // namespace detail
353} // namespace pb_ds
354
355#endif
356