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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2009, 2011 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 thin_heap_/thin_heap_.hpp
  38  * Contains an implementation class for a thin heap.
  39  */
  40
  41 #ifndef PB_DS_THIN_HEAP_HPP
  42 #define PB_DS_THIN_HEAP_HPP
  43
  44 #include <algorithm>
  45 #include <ext/pb_ds/detail/cond_dealtor.hpp>
  46 #include <ext/pb_ds/detail/type_utils.hpp>
  47 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp>
  48 #include <debug/debug.h>
  49
  50 namespace __gnu_pbds
  51 {
  52   namespace detail
  53   {
  54 #define PB_DS_CLASS_T_DEC \
  55     template<typename Value_Type, typename Cmp_Fn, typename _Alloc>
  56
  57 #define PB_DS_CLASS_C_DEC \
  58     thin_heap<Value_Type, Cmp_Fn, _Alloc>
  59
  60 #ifdef _GLIBCXX_DEBUG
  61 #define PB_DS_BASE_T_P \
  62     <Value_Type, Cmp_Fn, typename _Alloc::size_type, _Alloc, true>
  63 #else
  64 #define PB_DS_BASE_T_P \
  65     <Value_Type, Cmp_Fn, typename _Alloc::size_type, _Alloc>
  66 #endif
  67
  68     /**
  69      *  Thin heap.
  70      *  Base class for @ref priority_queue.
  71      *
  72      *  See Tarjan and Kaplan.
  73      */
  74     template<typename Value_Type, typename Cmp_Fn, typename _Alloc>
  75     class thin_heap
  76     : public left_child_next_sibling_heap PB_DS_BASE_T_P
  77     {
  78     private:
  79       typedef typename _Alloc::template rebind<Value_Type>::other __rebind_a;
  80       typedef left_child_next_sibling_heap PB_DS_BASE_T_P base_type;
  81
  82     protected:
  83       typedef typename base_type::node                  node;
  84       typedef typename base_type::node_pointer          node_pointer;
  85       typedef typename base_type::node_const_pointer    node_const_pointer;
  86
  87     public:
  88       typedef Value_Type                                value_type;
  89       typedef Cmp_Fn                                    cmp_fn;
  90       typedef _Alloc                                    allocator_type;
  91       typedef typename _Alloc::size_type                size_type;
  92       typedef typename _Alloc::difference_type          difference_type;
  93
  94       typedef typename __rebind_a::pointer              pointer;
  95       typedef typename __rebind_a::const_pointer        const_pointer;
  96       typedef typename __rebind_a::reference            reference;
  97       typedef typename __rebind_a::const_reference      const_reference;
  98
  99       typedef typename base_type::point_iterator        point_iterator;
 100       typedef typename base_type::point_const_iterator  point_const_iterator;
 101       typedef typename base_type::iterator              iterator;
 102       typedef typename base_type::const_iterator        const_iterator;
 103
 104
 105       inline point_iterator
 106       push(const_reference);
 107
 108       void
 109       modify(point_iterator, const_reference);
 110
 111       inline const_reference
 112       top() const;
 113
 114       void
 115       pop();
 116
 117       void
 118       erase(point_iterator);
 119
 120       inline void
 121       clear();
 122
 123       template<typename Pred>
 124       size_type
 125       erase_if(Pred);
 126
 127       template<typename Pred>
 128       void
 129       split(Pred, PB_DS_CLASS_C_DEC&);
 130
 131       void
 132       join(PB_DS_CLASS_C_DEC&);
 133
 134     protected:
 135       thin_heap();
 136
 137       thin_heap(const Cmp_Fn&);
 138
 139       thin_heap(const PB_DS_CLASS_C_DEC&);
 140
 141       void
 142       swap(PB_DS_CLASS_C_DEC&);
 143
 144       ~thin_heap();
 145
 146       template<typename It>
 147       void
 148       copy_from_range(It, It);
 149
 150 #ifdef _GLIBCXX_DEBUG
 151       void
 152       assert_valid(const char*, int) const;
 153
 154       void
 155       assert_max(const char*, int) const;
 156 #endif
 157
 158 #ifdef PB_DS_THIN_HEAP_TRACE_
 159       void
 160       trace() const;
 161 #endif
 162
 163     private:
 164       enum
 165         {
 166           max_rank = (sizeof(size_type) << 4) + 2
 167         };
 168
 169       void
 170       initialize();
 171
 172       inline void
 173       update_max(node_pointer);
 174
 175       inline void
 176       fix(node_pointer);
 177
 178       inline void
 179       fix_root(node_pointer);
 180
 181       inline void
 182       fix_sibling_rank_1_unmarked(node_pointer);
 183
 184       inline void
 185       fix_sibling_rank_1_marked(node_pointer);
 186
 187       inline void
 188       fix_sibling_general_unmarked(node_pointer);
 189
 190       inline void
 191       fix_sibling_general_marked(node_pointer);
 192
 193       inline void
 194       fix_child(node_pointer);
 195
 196       inline static void
 197       make_root(node_pointer);
 198
 199       inline void
 200       make_root_and_link(node_pointer);
 201
 202       inline void
 203       remove_max_node();
 204
 205       void
 206       to_aux_except_max();
 207
 208       inline void
 209       add_to_aux(node_pointer);
 210
 211       inline void
 212       make_from_aux();
 213
 214       inline size_type
 215       rank_bound();
 216
 217       inline void
 218       make_child_of(node_pointer, node_pointer);
 219
 220       inline void
 221       remove_node(node_pointer);
 222
 223       inline node_pointer
 224       join(node_pointer, node_pointer) const;
 225
 226 #ifdef _GLIBCXX_DEBUG
 227       void
 228       assert_node_consistent(node_const_pointer, bool, const char*, int) const;
 229
 230       void
 231       assert_aux_null(const char*, int) const;
 232 #endif
 233
 234       node_pointer      m_p_max;
 235       node_pointer      m_a_aux[max_rank];
 236     };
 237
 238     enum
 239       {
 240         num_distinct_rank_bounds = 48
 241       };
 242
 243     // Taken from the SGI implementation; acknowledged in the docs.
 244     static const std::size_t g_a_rank_bounds[num_distinct_rank_bounds] =
 245       {
 246         /* Dealing cards... */
 247         /* 0     */ 0ul,
 248         /* 1     */ 1ul,
 249         /* 2     */ 1ul,
 250         /* 3     */ 2ul,
 251         /* 4     */ 4ul,
 252         /* 5     */ 6ul,
 253         /* 6     */ 11ul,
 254         /* 7     */ 17ul,
 255         /* 8     */ 29ul,
 256         /* 9     */ 46ul,
 257         /* 10    */ 76ul,
 258         /* 11    */ 122ul,
 259         /* 12    */ 199ul,
 260         /* 13    */ 321ul,
 261         /* 14    */ 521ul,
 262         /* 15    */ 842ul,
 263         /* 16    */ 1364ul,
 264         /* 17    */ 2206ul,
 265         /* 18    */ 3571ul,
 266         /* 19    */ 5777ul,
 267         /* 20    */ 9349ul,
 268         /* 21    */ 15126ul,
 269         /* 22    */ 24476ul,
 270         /* 23    */ 39602ul,
 271         /* 24    */ 64079ul,
 272         /* 25    */ 103681ul,
 273         /* 26    */ 167761ul,
 274         /* 27    */ 271442ul,
 275         /* 28    */ 439204ul,
 276         /* 29    */ 710646ul,
 277         /* 30    */ 1149851ul,
 278         /* 31    */ 1860497ul,
 279         /* 32    */ 3010349ul,
 280         /* 33    */ 4870846ul,
 281         /* 34    */ 7881196ul,
 282         /* 35    */ 12752042ul,
 283         /* 36    */ 20633239ul,
 284         /* 37    */ 33385282ul,
 285         /* 38    */ 54018521ul,
 286         /* 39    */ 87403803ul,
 287         /* 40    */ 141422324ul,
 288         /* 41    */ 228826127ul,
 289         /* 42    */ 370248451ul,
 290         /* 43    */ 599074578ul,
 291         /* 44    */ 969323029ul,
 292         /* 45    */ 1568397607ul,
 293         /* 46    */ 2537720636ul,
 294         /* 47    */ 4106118243ul
 295         /* Pot's good, let's play */
 296       };
 297
 298 #define PB_DS_ASSERT_NODE_CONSISTENT(_Node, _Bool)                      \
 299   _GLIBCXX_DEBUG_ONLY(assert_node_consistent(_Node, _Bool,              \
 300                                              __FILE__, __LINE__);)
 301
 302 #define PB_DS_ASSERT_AUX_NULL(X)                                        \
 303   _GLIBCXX_DEBUG_ONLY(X.assert_aux_null(__FILE__, __LINE__);)
 304
 305 #include <ext/pb_ds/detail/thin_heap_/constructors_destructor_fn_imps.hpp>
 306 #include <ext/pb_ds/detail/thin_heap_/debug_fn_imps.hpp>
 307 #include <ext/pb_ds/detail/thin_heap_/trace_fn_imps.hpp>
 308 #include <ext/pb_ds/detail/thin_heap_/find_fn_imps.hpp>
 309 #include <ext/pb_ds/detail/thin_heap_/insert_fn_imps.hpp>
 310 #include <ext/pb_ds/detail/thin_heap_/erase_fn_imps.hpp>
 311 #include <ext/pb_ds/detail/thin_heap_/split_join_fn_imps.hpp>
 312
 313 #undef PB_DS_ASSERT_AUX_NULL
 314 #undef PB_DS_ASSERT_NODE_CONSISTENT
 315 #undef PB_DS_CLASS_C_DEC
 316 #undef PB_DS_CLASS_T_DEC
 317 #undef PB_DS_BASE_T_P
 318
 319   } // namespace detail
 320 } // namespace __gnu_pbds
 321
 322 #endif