1// -*- C++ -*-
2
3// Copyright (C) 2005, 2006, 2009 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 rc_binomial_heap_.hpp
38 * Contains an implementation for rc_binomial_heap_.
39 */
40
41/*
42 * Redundant-counter binomial heap.
43 */
44
45#include <ext/pb_ds/detail/cond_dealtor.hpp>
46#include <ext/pb_ds/detail/type_utils.hpp>
47#include <ext/pb_ds/detail/binomial_heap_base_/binomial_heap_base_.hpp>
48#include <ext/pb_ds/detail/rc_binomial_heap_/rc.hpp>
49#include <debug/debug.h>
50
51namespace __gnu_pbds
52{
53  namespace detail
54  {
55#define PB_DS_CLASS_T_DEC \
56    template<typename Value_Type, class Cmp_Fn, class Allocator>
57
58#define PB_DS_CLASS_C_DEC \
59    rc_binomial_heap_<Value_Type, Cmp_Fn, Allocator>
60
61#define PB_DS_BASE_C_DEC \
62    binomial_heap_base_<Value_Type, Cmp_Fn, Allocator>
63
64#define PB_DS_RC_C_DEC \
65    rc<typename PB_DS_BASE_C_DEC::node, Allocator>
66
67    /**
68     * class description = "8y|\|0|\/|i41 h34p 74813">
69     **/
70    template<typename Value_Type, class Cmp_Fn, class Allocator>
71    class rc_binomial_heap_ : public PB_DS_BASE_C_DEC
72    {
73
74    private:
75      typedef PB_DS_BASE_C_DEC base_type;
76
77      typedef typename base_type::node_pointer node_pointer;
78
79      typedef typename base_type::const_node_pointer const_node_pointer;
80
81      typedef PB_DS_RC_C_DEC rc_t;
82
83    public:
84
85      typedef typename Allocator::size_type size_type;
86
87      typedef typename Allocator::difference_type difference_type;
88
89      typedef Value_Type value_type;
90
91      typedef typename base_type::pointer pointer;
92
93      typedef typename base_type::const_pointer const_pointer;
94
95      typedef typename base_type::reference reference;
96
97      typedef typename base_type::const_reference const_reference;
98
99      typedef typename base_type::const_point_iterator const_point_iterator;
100
101      typedef typename base_type::point_iterator point_iterator;
102
103      typedef typename base_type::const_iterator const_iterator;
104
105      typedef typename base_type::iterator iterator;
106
107      typedef typename base_type::cmp_fn cmp_fn;
108
109      typedef typename base_type::allocator_type allocator_type;
110
111    public:
112
113      rc_binomial_heap_();
114
115      rc_binomial_heap_(const Cmp_Fn& r_cmp_fn);
116
117      rc_binomial_heap_(const PB_DS_CLASS_C_DEC& other);
118
119      ~rc_binomial_heap_();
120
121      void
122      swap(PB_DS_CLASS_C_DEC& other);
123
124      inline point_iterator
125      push(const_reference r_val);
126
127      void
128      modify(point_iterator it, const_reference r_new_val);
129
130      inline void
131      pop();
132
133      void
134      erase(point_iterator it);
135
136      inline void
137      clear();
138
139      template<typename Pred>
140      size_type
141      erase_if(Pred pred);
142
143      template<typename Pred>
144      void
145      split(Pred pred, PB_DS_CLASS_C_DEC& other);
146
147      void
148      join(PB_DS_CLASS_C_DEC& other);
149
150#ifdef _GLIBCXX_DEBUG
151      void
152      assert_valid() const;
153#endif
154
155#ifdef PB_DS_RC_BINOMIAL_HEAP_TRACE_
156      void
157      trace() const;
158#endif
159
160    private:
161
162      inline node_pointer
163      link_with_next_sibling(node_pointer p_nd);
164
165      void
166      make_0_exposed();
167
168      void
169      make_binomial_heap();
170
171#ifdef _GLIBCXX_DEBUG
172      static const_node_pointer
173      next_2_pointer(const_node_pointer p_nd);
174
175      static const_node_pointer
176      next_after_0_pointer(const_node_pointer p_nd);
177#endif
178
179    private:
180      rc_t m_rc;
181    };
182
183#include <ext/pb_ds/detail/rc_binomial_heap_/constructors_destructor_fn_imps.hpp>
184#include <ext/pb_ds/detail/rc_binomial_heap_/debug_fn_imps.hpp>
185#include <ext/pb_ds/detail/rc_binomial_heap_/erase_fn_imps.hpp>
186#include <ext/pb_ds/detail/rc_binomial_heap_/trace_fn_imps.hpp>
187#include <ext/pb_ds/detail/rc_binomial_heap_/insert_fn_imps.hpp>
188#include <ext/pb_ds/detail/rc_binomial_heap_/split_join_fn_imps.hpp>
189
190#undef PB_DS_CLASS_C_DEC
191
192#undef PB_DS_CLASS_T_DEC
193
194#undef PB_DS_BASE_C_DEC
195
196#undef PB_DS_RC_C_DEC
197  } // namespace detail
198} // namespace __gnu_pbds
199