git.libre-soc.org Git - gcc.git/blob

   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 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     protected:
  93       typedef
  94       typename _Alloc::template rebind<
  95       left_child_next_sibling_heap_node_<Value_Type, Node_Metadata,
  96                                          _Alloc> >::other
  97       node_allocator;
  98
  99       typedef typename node_allocator::value_type       node;
 100       typedef typename node_allocator::pointer          node_pointer;
 101       typedef typename node_allocator::const_pointer    node_const_pointer;
 102       typedef Node_Metadata node_metadata;
 103       typedef std::pair< node_pointer, node_pointer>    node_pointer_pair;
 104
 105     private:
 106       typedef cond_dealtor< node, _Alloc>               cond_dealtor_t;
 107
 108       enum
 109         {
 110           simple_value = is_simple<Value_Type>::value
 111         };
 112
 113       typedef integral_constant<int, simple_value>      no_throw_copies_t;
 114       typedef typename _Alloc::template rebind<Value_Type>      __rebind_v;
 115
 116     public:
 117       typedef typename _Alloc::size_type                size_type;
 118       typedef typename _Alloc::difference_type  difference_type;
 119       typedef Value_Type                                value_type;
 120
 121       typedef typename __rebind_v::other::pointer       pointer;
 122       typedef typename __rebind_v::other::const_pointer const_pointer;
 123       typedef typename __rebind_v::other::reference     reference;
 124       typedef typename __rebind_v::other::const_reference const_reference;
 125
 126       typedef left_child_next_sibling_heap_node_point_const_iterator_<node, _Alloc>
 127       point_const_iterator;
 128
 129       typedef point_const_iterator                      point_iterator;
 130
 131       typedef left_child_next_sibling_heap_const_iterator_<node, _Alloc>
 132       const_iterator;
 133
 134       typedef const_iterator                            iterator;
 135       typedef Cmp_Fn                                    cmp_fn;
 136       typedef _Alloc                                    allocator_type;
 137
 138     public:
 139
 140       left_child_next_sibling_heap();
 141       left_child_next_sibling_heap(const Cmp_Fn&);
 142       left_child_next_sibling_heap(const left_child_next_sibling_heap&);
 143
 144       void
 145       swap(PB_DS_CLASS_C_DEC&);
 146
 147       ~left_child_next_sibling_heap();
 148
 149       inline bool
 150       empty() const;
 151
 152       inline size_type
 153       size() const;
 154
 155       inline size_type
 156       max_size() const;
 157
 158       Cmp_Fn&
 159       get_cmp_fn();
 160
 161       const Cmp_Fn&
 162       get_cmp_fn() const;
 163
 164       inline iterator
 165       begin();
 166
 167       inline const_iterator
 168       begin() const;
 169
 170       inline iterator
 171       end();
 172
 173       inline const_iterator
 174       end() const;
 175
 176       void
 177       clear();
 178
 179 #ifdef PB_DS_LC_NS_HEAP_TRACE_
 180       void
 181       trace() const;
 182 #endif
 183
 184     protected:
 185
 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,
 264                           type_to_type<null_type>);
 265 #endif
 266     protected:
 267       node_pointer              m_p_root;
 268       size_type                 m_size;
 269
 270     private:
 271       static node_allocator     s_node_allocator;
 272       static no_throw_copies_t  s_no_throw_copies_ind;
 273     };
 274
 275 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/constructors_destructor_fn_imps.hpp>
 276 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/iterators_fn_imps.hpp>
 277 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/debug_fn_imps.hpp>
 278 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/trace_fn_imps.hpp>
 279 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/insert_fn_imps.hpp>
 280 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/erase_fn_imps.hpp>
 281 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/info_fn_imps.hpp>
 282 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/policy_access_fn_imps.hpp>
 283
 284 #undef PB_DS_CLASS_C_DEC
 285 #undef PB_DS_CLASS_T_DEC
 286
 287   } // namespace detail
 288 } // namespace __gnu_pbds
 289
 290 #endif