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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006 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 2, 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 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  32
  33 // Permission to use, copy, modify, sell, and distribute this software
  34 // is hereby granted without fee, provided that the above copyright
  35 // notice appears in all copies, and that both that copyright notice
  36 // and this permission notice appear in supporting documentation. None
  37 // of the above authors, nor IBM Haifa Research Laboratories, make any
  38 // representation about the suitability of this software for any
  39 // purpose. It is provided "as is" without express or implied
  40 // warranty.
  41
  42 /**
  43  * @file thin_heap_.hpp
  44  * Contains an implementation class for a thin heap.
  45  */
  46
  47 #ifndef PB_DS_THIN_HEAP_HPP
  48 #define PB_DS_THIN_HEAP_HPP
  49
  50 /*
  51  * Thin heaps.
  52  * Tarjan and Kaplan.
  53  */
  54
  55 #include <algorithm>
  56 #include <ext/pb_ds/detail/cond_dealtor.hpp>
  57 #include <ext/pb_ds/detail/type_utils.hpp>
  58 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp>
  59 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/null_metadata.hpp>
  60 #include <debug/debug.h>
  61
  62 namespace __gnu_pbds
  63 {
  64   namespace detail
  65   {
  66
  67 #define PB_DS_CLASS_T_DEC \
  68     template<typename Value_Type, class Cmp_Fn, class Allocator>
  69
  70 #define PB_DS_CLASS_C_DEC \
  71     thin_heap_<Value_Type, Cmp_Fn, Allocator>
  72
  73 #ifdef _GLIBCXX_DEBUG
  74 #define PB_DS_BASE_C_DEC \
  75     left_child_next_sibling_heap_<Value_Type, Cmp_Fn,   \
  76                                 typename Allocator::size_type, Allocator, true>
  77 #else
  78 #define PB_DS_BASE_C_DEC                                                \
  79     left_child_next_sibling_heap_<Value_Type, Cmp_Fn, \
  80                                   typename Allocator::size_type, Allocator>
  81 #endif
  82
  83     /**
  84      * class description = "t|-|i|\| h34p">
  85      **/
  86     template<typename Value_Type, class Cmp_Fn, class Allocator>
  87     class thin_heap_ : public PB_DS_BASE_C_DEC
  88     {
  89
  90     private:
  91       typedef PB_DS_BASE_C_DEC base_type;
  92
  93     protected:
  94       typedef typename base_type::node node;
  95
  96       typedef typename base_type::node_pointer node_pointer;
  97
  98       typedef typename base_type::const_node_pointer const_node_pointer;
  99
 100     public:
 101
 102       typedef typename Allocator::size_type size_type;
 103
 104       typedef typename Allocator::difference_type difference_type;
 105
 106       typedef Value_Type value_type;
 107
 108       typedef
 109       typename Allocator::template rebind<
 110         value_type>::other::pointer
 111       pointer;
 112
 113       typedef
 114       typename Allocator::template rebind<
 115         value_type>::other::const_pointer
 116       const_pointer;
 117
 118       typedef
 119       typename Allocator::template rebind<
 120         value_type>::other::reference
 121       reference;
 122
 123       typedef
 124       typename Allocator::template rebind<
 125         value_type>::other::const_reference
 126       const_reference;
 127
 128       typedef
 129       typename PB_DS_BASE_C_DEC::const_point_iterator
 130       const_point_iterator;
 131
 132       typedef typename PB_DS_BASE_C_DEC::point_iterator point_iterator;
 133
 134       typedef typename PB_DS_BASE_C_DEC::const_iterator const_iterator;
 135
 136       typedef typename PB_DS_BASE_C_DEC::iterator iterator;
 137
 138       typedef Cmp_Fn cmp_fn;
 139
 140       typedef Allocator allocator_type;
 141
 142     public:
 143
 144       inline point_iterator
 145       push(const_reference r_val);
 146
 147       void
 148       modify(point_iterator it, const_reference r_new_val);
 149
 150       inline const_reference
 151       top() const;
 152
 153       void
 154       pop();
 155
 156       void
 157       erase(point_iterator it);
 158
 159       inline void
 160       clear();
 161
 162       template<typename Pred>
 163       size_type
 164       erase_if(Pred pred);
 165
 166       template<typename Pred>
 167       void
 168       split(Pred pred, PB_DS_CLASS_C_DEC& other);
 169
 170       void
 171       join(PB_DS_CLASS_C_DEC& other);
 172
 173     protected:
 174
 175       thin_heap_();
 176
 177       thin_heap_(const Cmp_Fn& r_cmp_fn);
 178
 179       thin_heap_(const PB_DS_CLASS_C_DEC& other);
 180
 181       void
 182       swap(PB_DS_CLASS_C_DEC& other);
 183
 184       ~thin_heap_();
 185
 186       template<typename It>
 187       void
 188       copy_from_range(It first_it, It last_it);
 189
 190 #ifdef _GLIBCXX_DEBUG
 191       void
 192       assert_valid() const;
 193
 194       void
 195       assert_max() const;
 196 #endif
 197
 198 #ifdef PB_DS_THIN_HEAP_TRACE_
 199       void
 200       trace() const;
 201 #endif
 202
 203     private:
 204       enum
 205         {
 206           max_rank = (sizeof(size_type) << 4) + 2
 207         };
 208
 209     private:
 210
 211       void
 212       initialize();
 213
 214       inline void
 215       update_max(node_pointer p_nd);
 216
 217       inline void
 218       fix(node_pointer p_nd);
 219
 220       inline void
 221       fix_root(node_pointer p_y);
 222
 223       inline void
 224       fix_sibling_rank_1_unmarked(node_pointer p_y);
 225
 226       inline void
 227       fix_sibling_rank_1_marked(node_pointer p_y);
 228
 229       inline void
 230       fix_sibling_general_unmarked(node_pointer p_y);
 231
 232       inline void
 233       fix_sibling_general_marked(node_pointer p_y);
 234
 235       inline void
 236       fix_child(node_pointer p_y);
 237
 238       inline static void
 239       make_root(node_pointer p_nd);
 240
 241       inline void
 242       make_root_and_link(node_pointer p_nd);
 243
 244       inline void
 245       remove_max_node();
 246
 247       void
 248       to_aux_except_max();
 249
 250       inline void
 251       add_to_aux(node_pointer p_nd);
 252
 253       inline void
 254       make_from_aux();
 255
 256       inline size_type
 257       rank_bound();
 258
 259       inline void
 260       make_child_of(node_pointer p_nd, node_pointer p_new_parent);
 261
 262       inline void
 263       remove_node(node_pointer p_nd);
 264
 265       inline node_pointer
 266       join(node_pointer p_lhs, node_pointer p_rhs) const;
 267
 268 #ifdef _GLIBCXX_DEBUG
 269       void
 270       assert_node_consistent(const_node_pointer p_nd, bool root) const;
 271
 272       void
 273       assert_aux_null() const;
 274 #endif
 275
 276     private:
 277       node_pointer m_p_max;
 278
 279       node_pointer m_a_aux[max_rank];
 280     };
 281
 282     enum
 283       {
 284         num_distinct_rank_bounds = 48
 285       };
 286
 287     // Taken from the SGI implementation; acknowledged in the docs.
 288     static const std::size_t g_a_rank_bounds[num_distinct_rank_bounds] =
 289       {
 290         /* Dealing cards... */
 291         /* 0     */ 0ul,
 292         /* 1     */ 1ul,
 293         /* 2     */ 1ul,
 294         /* 3     */ 2ul,
 295         /* 4     */ 4ul,
 296         /* 5     */ 6ul,
 297         /* 6     */ 11ul,
 298         /* 7     */ 17ul,
 299         /* 8     */ 29ul,
 300         /* 9     */ 46ul,
 301         /* 10    */ 76ul,
 302         /* 11    */ 122ul,
 303         /* 12    */ 199ul,
 304         /* 13    */ 321ul,
 305         /* 14    */ 521ul,
 306         /* 15    */ 842ul,
 307         /* 16    */ 1364ul,
 308         /* 17    */ 2206ul,
 309         /* 18    */ 3571ul,
 310         /* 19    */ 5777ul,
 311         /* 20    */ 9349ul,
 312         /* 21    */ 15126ul,
 313         /* 22    */ 24476ul,
 314         /* 23    */ 39602ul,
 315         /* 24    */ 64079ul,
 316         /* 25    */ 103681ul,
 317         /* 26    */ 167761ul,
 318         /* 27    */ 271442ul,
 319         /* 28    */ 439204ul,
 320         /* 29    */ 710646ul,
 321         /* 30    */ 1149851ul,
 322         /* 31    */ 1860497ul,
 323         /* 32    */ 3010349ul,
 324         /* 33    */ 4870846ul,
 325         /* 34    */ 7881196ul,
 326         /* 35    */ 12752042ul,
 327         /* 36    */ 20633239ul,
 328         /* 37    */ 33385282ul,
 329         /* 38    */ 54018521ul,
 330         /* 39    */ 87403803ul,
 331         /* 40    */ 141422324ul,
 332         /* 41    */ 228826127ul,
 333         /* 42    */ 370248451ul,
 334         /* 43    */ 599074578ul,
 335         /* 44    */ 969323029ul,
 336         /* 45    */ 1568397607ul,
 337         /* 46    */ 2537720636ul,
 338         /* 47    */ 4106118243ul
 339         /* Pot's good, let's play */
 340       };
 341
 342 #include <ext/pb_ds/detail/thin_heap_/constructors_destructor_fn_imps.hpp>
 343 #include <ext/pb_ds/detail/thin_heap_/debug_fn_imps.hpp>
 344 #include <ext/pb_ds/detail/thin_heap_/trace_fn_imps.hpp>
 345 #include <ext/pb_ds/detail/thin_heap_/find_fn_imps.hpp>
 346 #include <ext/pb_ds/detail/thin_heap_/insert_fn_imps.hpp>
 347 #include <ext/pb_ds/detail/thin_heap_/erase_fn_imps.hpp>
 348 #include <ext/pb_ds/detail/thin_heap_/split_join_fn_imps.hpp>
 349
 350 #undef PB_DS_CLASS_C_DEC
 351 #undef PB_DS_CLASS_T_DEC
 352 #undef PB_DS_BASE_C_DEC
 353
 354   } // namespace detail
 355 } // namespace __gnu_pbds
 356
 357 #endif