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