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