libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2015 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_/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_/point_const_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
  59 namespace __gnu_pbds
  60 {
  61   namespace detail
  62   {
  63 #ifdef _GLIBCXX_DEBUG
  64 #define PB_DS_CLASS_T_DEC \
  65     template<typename Value_Type, typename Cmp_Fn, typename Node_Metadata, \
  66              typename _Alloc, bool Single_Link_Roots>
  67
  68 #define PB_DS_CLASS_C_DEC \
  69     left_child_next_sibling_heap<Value_Type, Cmp_Fn, Node_Metadata,     \
  70                                   _Alloc, Single_Link_Roots>
  71 #else
  72 #define PB_DS_CLASS_T_DEC \
  73     template<typename Value_Type, typename Cmp_Fn, typename Node_Metadata, \
  74              typename _Alloc>
  75
  76 #define PB_DS_CLASS_C_DEC \
  77     left_child_next_sibling_heap<Value_Type, Cmp_Fn, Node_Metadata, _Alloc>
  78 #endif
  79
  80     /// Base class for a basic heap.
  81     template<typename Value_Type,
  82              typename Cmp_Fn,
  83              typename Node_Metadata,
  84              typename _Alloc
  85 #ifdef _GLIBCXX_DEBUG
  86              ,bool Single_Link_Roots>
  87 #else
  88              >
  89 #endif
  90     class left_child_next_sibling_heap : public Cmp_Fn
  91     {
  92     protected:
  93       typedef
  94       typename _Alloc::template rebind<
  95       left_child_next_sibling_heap_node_<Value_Type, Node_Metadata,
  96                                          _Alloc> >::other
  97       node_allocator;
  98
  99       typedef typename node_allocator::value_type       node;
 100       typedef typename node_allocator::pointer          node_pointer;
 101       typedef typename node_allocator::const_pointer    node_const_pointer;
 102       typedef Node_Metadata node_metadata;
 103       typedef std::pair< node_pointer, node_pointer>    node_pointer_pair;
 104
 105     private:
 106       typedef cond_dealtor< node, _Alloc>               cond_dealtor_t;
 107
 108       enum
 109         {
 110           simple_value = is_simple<Value_Type>::value
 111         };
 112
 113       typedef integral_constant<int, simple_value>      no_throw_copies_t;
 114       typedef typename _Alloc::template rebind<Value_Type>      __rebind_v;
 115
 116     public:
 117       typedef typename _Alloc::size_type                size_type;
 118       typedef typename _Alloc::difference_type  difference_type;
 119       typedef Value_Type                                value_type;
 120
 121       typedef typename __rebind_v::other::pointer       pointer;
 122       typedef typename __rebind_v::other::const_pointer const_pointer;
 123       typedef typename __rebind_v::other::reference     reference;
 124       typedef typename __rebind_v::other::const_reference const_reference;
 125
 126       typedef left_child_next_sibling_heap_node_point_const_iterator_<node, _Alloc>
 127       point_const_iterator;
 128
 129       typedef point_const_iterator                      point_iterator;
 130
 131       typedef left_child_next_sibling_heap_const_iterator_<node, _Alloc>
 132       const_iterator;
 133
 134       typedef const_iterator                            iterator;
 135       typedef Cmp_Fn                                    cmp_fn;
 136       typedef _Alloc                                    allocator_type;
 137
 138       left_child_next_sibling_heap();
 139       left_child_next_sibling_heap(const Cmp_Fn&);
 140       left_child_next_sibling_heap(const left_child_next_sibling_heap&);
 141
 142       void
 143       swap(PB_DS_CLASS_C_DEC&);
 144
 145       ~left_child_next_sibling_heap();
 146
 147       inline bool
 148       empty() const;
 149
 150       inline size_type
 151       size() const;
 152
 153       inline size_type
 154       max_size() const;
 155
 156       Cmp_Fn&
 157       get_cmp_fn();
 158
 159       const Cmp_Fn&
 160       get_cmp_fn() const;
 161
 162       inline iterator
 163       begin();
 164
 165       inline const_iterator
 166       begin() const;
 167
 168       inline iterator
 169       end();
 170
 171       inline const_iterator
 172       end() const;
 173
 174       void
 175       clear();
 176
 177 #ifdef PB_DS_LC_NS_HEAP_TRACE_
 178       void
 179       trace() const;
 180 #endif
 181
 182     protected:
 183       inline node_pointer
 184       get_new_node_for_insert(const_reference);
 185
 186       inline static void
 187       make_child_of(node_pointer, node_pointer);
 188
 189       void
 190       value_swap(left_child_next_sibling_heap&);
 191
 192       inline static node_pointer
 193       parent(node_pointer);
 194
 195       inline void
 196       swap_with_parent(node_pointer, node_pointer);
 197
 198       void
 199       bubble_to_top(node_pointer);
 200
 201       inline void
 202       actual_erase_node(node_pointer);
 203
 204       void
 205       clear_imp(node_pointer);
 206
 207       void
 208       to_linked_list();
 209
 210       template<typename Pred>
 211       node_pointer
 212       prune(Pred);
 213
 214 #ifdef _GLIBCXX_DEBUG
 215       void
 216       assert_valid(const char*, int) const;
 217
 218       void
 219       assert_node_consistent(node_const_pointer, bool, const char*, int) const;
 220
 221       static size_type
 222       size_under_node(node_const_pointer);
 223
 224       static size_type
 225       degree(node_const_pointer);
 226 #endif
 227
 228 #ifdef PB_DS_LC_NS_HEAP_TRACE_
 229       static void
 230       trace_node(node_const_pointer, size_type);
 231 #endif
 232
 233     private:
 234 #ifdef _GLIBCXX_DEBUG
 235       void
 236       assert_iterators(const char*, int) const;
 237
 238       void
 239       assert_size(const char*, int) const;
 240
 241       static size_type
 242       size_from_node(node_const_pointer);
 243 #endif
 244
 245       node_pointer
 246       recursive_copy_node(node_const_pointer);
 247
 248       inline node_pointer
 249       get_new_node_for_insert(const_reference, false_type);
 250
 251       inline node_pointer
 252       get_new_node_for_insert(const_reference, true_type);
 253
 254 #ifdef PB_DS_LC_NS_HEAP_TRACE_
 255       template<typename Metadata_>
 256       static void
 257       trace_node_metadata(node_const_pointer, type_to_type<Metadata_>);
 258
 259       static void
 260       trace_node_metadata(node_const_pointer, type_to_type<null_type>);
 261 #endif
 262
 263       static node_allocator     s_node_allocator;
 264       static no_throw_copies_t  s_no_throw_copies_ind;
 265
 266     protected:
 267       node_pointer              m_p_root;
 268       size_type                 m_size;
 269     };
 270
 271 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/constructors_destructor_fn_imps.hpp>
 272 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/iterators_fn_imps.hpp>
 273 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/debug_fn_imps.hpp>
 274 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/trace_fn_imps.hpp>
 275 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/insert_fn_imps.hpp>
 276 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/erase_fn_imps.hpp>
 277 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/info_fn_imps.hpp>
 278 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/policy_access_fn_imps.hpp>
 279
 280 #undef PB_DS_CLASS_C_DEC
 281 #undef PB_DS_CLASS_T_DEC
 282
 283   } // namespace detail
 284 } // namespace __gnu_pbds
 285
 286 #endif