l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.6/include/ext/pb_ds/detail/thin_heap_/thin_heap_.hpp

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