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