libstdc++
binary_heap_.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2009, 2011 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
00026 
00027 // Permission to use, copy, modify, sell, and distribute this software
00028 // is hereby granted without fee, provided that the above copyright
00029 // notice appears in all copies, and that both that copyright notice
00030 // and this permission notice appear in supporting documentation. None
00031 // of the above authors, nor IBM Haifa Research Laboratories, make any
00032 // representation about the suitability of this software for any
00033 // purpose. It is provided "as is" without express or implied
00034 // warranty.
00035 
00036 /**
00037  * @file binary_heap_/binary_heap_.hpp
00038  * Contains an implementation class for a binary heap.
00039  */
00040 
00041 #ifndef PB_DS_BINARY_HEAP_HPP
00042 #define PB_DS_BINARY_HEAP_HPP
00043 
00044 #include <queue>
00045 #include <algorithm>
00046 #include <ext/pb_ds/detail/cond_dealtor.hpp>
00047 #include <ext/pb_ds/detail/cond_dealtor.hpp>
00048 #include <ext/pb_ds/detail/type_utils.hpp>
00049 #include <ext/pb_ds/detail/binary_heap_/entry_cmp.hpp>
00050 #include <ext/pb_ds/detail/binary_heap_/entry_pred.hpp>
00051 #include <ext/pb_ds/detail/binary_heap_/resize_policy.hpp>
00052 #include <ext/pb_ds/detail/binary_heap_/point_const_iterator.hpp>
00053 #include <ext/pb_ds/detail/binary_heap_/const_iterator.hpp>
00054 #ifdef PB_DS_BINARY_HEAP_TRACE_
00055 #include <iostream>
00056 #endif
00057 #include <ext/pb_ds/detail/type_utils.hpp>
00058 #include <debug/debug.h>
00059 
00060 namespace __gnu_pbds
00061 {
00062   namespace detail
00063   {
00064 #define PB_DS_CLASS_T_DEC \
00065     template<typename Value_Type, typename Cmp_Fn, typename _Alloc>
00066 
00067 #define PB_DS_CLASS_C_DEC \
00068     binary_heap<Value_Type, Cmp_Fn, _Alloc>
00069 
00070 #define PB_DS_ENTRY_CMP_DEC \
00071     entry_cmp<Value_Type, Cmp_Fn, _Alloc, is_simple<Value_Type>::value>::type
00072 
00073 #define PB_DS_RESIZE_POLICY_DEC \
00074     __gnu_pbds::detail::resize_policy<typename _Alloc::size_type>
00075 
00076     /**
00077      *  Binary heaps composed of resize and compare policies.
00078      *
00079      *  @ingroup heap-detail
00080      *
00081      *  Based on CLRS.
00082      */
00083     template<typename Value_Type, typename Cmp_Fn, typename _Alloc>
00084     class binary_heap
00085     : public PB_DS_ENTRY_CMP_DEC, public PB_DS_RESIZE_POLICY_DEC
00086     {
00087     public:
00088       typedef Value_Type                value_type;
00089       typedef Cmp_Fn                    cmp_fn;
00090       typedef _Alloc                    allocator_type;
00091       typedef typename _Alloc::size_type        size_type;
00092       typedef typename _Alloc::difference_type      difference_type;
00093       typedef typename PB_DS_ENTRY_CMP_DEC      entry_cmp;
00094       typedef PB_DS_RESIZE_POLICY_DEC           resize_policy;
00095       typedef cond_dealtor<value_type, _Alloc>      cond_dealtor_t;
00096 
00097     private:
00098       enum
00099     {
00100       simple_value = is_simple<value_type>::value
00101     };
00102 
00103       typedef integral_constant<int, simple_value>  no_throw_copies_t;
00104 
00105       typedef typename _Alloc::template rebind<value_type>  __rebind_v;
00106       typedef typename __rebind_v::other        value_allocator;
00107 
00108     public:
00109       typedef typename value_allocator::pointer     pointer;
00110       typedef typename value_allocator::const_pointer   const_pointer;
00111       typedef typename value_allocator::reference   reference;
00112       typedef typename value_allocator::const_reference const_reference;
00113 
00114       typedef typename __conditional_type<simple_value,
00115                       value_type, pointer>::__type
00116                                 entry;
00117 
00118       typedef typename _Alloc::template rebind<entry>::other
00119                                 entry_allocator;
00120 
00121       typedef typename entry_allocator::pointer     entry_pointer;
00122 
00123       typedef binary_heap_point_const_iterator_<value_type, entry,
00124                         simple_value, _Alloc>
00125                                 point_const_iterator;
00126 
00127       typedef point_const_iterator          point_iterator;
00128 
00129       typedef binary_heap_const_iterator_<value_type, entry,
00130                       simple_value, _Alloc>
00131                                 const_iterator;
00132 
00133       typedef const_iterator                iterator;
00134 
00135 
00136       binary_heap();
00137 
00138       binary_heap(const cmp_fn&);
00139 
00140       binary_heap(const binary_heap&);
00141 
00142       void
00143       swap(binary_heap&);
00144 
00145       ~binary_heap();
00146 
00147       inline bool
00148       empty() const;
00149 
00150       inline size_type
00151       size() const;
00152 
00153       inline size_type
00154       max_size() const;
00155 
00156       Cmp_Fn&
00157       get_cmp_fn();
00158 
00159       const Cmp_Fn&
00160       get_cmp_fn() const;
00161 
00162       inline point_iterator
00163       push(const_reference);
00164 
00165       void
00166       modify(point_iterator, const_reference);
00167 
00168       inline const_reference
00169       top() const;
00170 
00171       inline void
00172       pop();
00173 
00174       inline void
00175       erase(point_iterator);
00176 
00177       template<typename Pred>
00178     size_type
00179     erase_if(Pred);
00180 
00181       inline void
00182       erase_at(entry_pointer, size_type, false_type);
00183 
00184       inline void
00185       erase_at(entry_pointer, size_type, true_type);
00186 
00187       inline iterator
00188       begin();
00189 
00190       inline const_iterator
00191       begin() const;
00192 
00193       inline iterator
00194       end();
00195 
00196       inline const_iterator
00197       end() const;
00198 
00199       void
00200       clear();
00201 
00202       template<typename Pred>
00203     void
00204     split(Pred, binary_heap&);
00205 
00206       void
00207       join(binary_heap&);
00208 
00209 #ifdef PB_DS_BINARY_HEAP_TRACE_
00210       void
00211       trace() const;
00212 #endif
00213 
00214     protected:
00215       template<typename It>
00216     void
00217     copy_from_range(It, It);
00218 
00219     private:
00220       void
00221       value_swap(binary_heap&);
00222 
00223       inline void
00224       insert_value(const_reference, false_type);
00225 
00226       inline void
00227       insert_value(value_type, true_type);
00228 
00229       inline void
00230       resize_for_insert_if_needed();
00231 
00232       inline void
00233       swap_value_imp(entry_pointer, value_type, true_type);
00234 
00235       inline void
00236       swap_value_imp(entry_pointer, const_reference, false_type);
00237 
00238       void
00239       fix(entry_pointer);
00240 
00241       inline const_reference
00242       top_imp(true_type) const;
00243 
00244       inline const_reference
00245       top_imp(false_type) const;
00246 
00247       inline static size_type
00248       left_child(size_type);
00249 
00250       inline static size_type
00251       right_child(size_type);
00252 
00253       inline static size_type
00254       parent(size_type);
00255 
00256       inline void
00257       resize_for_erase_if_needed();
00258 
00259       template<typename Pred>
00260       size_type
00261       partition(Pred);
00262 
00263       void
00264       make_heap()
00265       {
00266     const entry_cmp& m_cmp = static_cast<entry_cmp&>(*this);
00267     entry_pointer end = m_a_entries + m_size;
00268     std::make_heap(m_a_entries, end, m_cmp);
00269     _GLIBCXX_DEBUG_ASSERT(is_heap());
00270       }
00271 
00272       void
00273       push_heap()
00274       {
00275     if (!is_heap())
00276       make_heap();
00277     else
00278       {
00279         const entry_cmp& m_cmp = static_cast<entry_cmp&>(*this);
00280         entry_pointer end = m_a_entries + m_size;
00281         std::push_heap(m_a_entries, end, m_cmp);
00282       }
00283       }
00284 
00285       void
00286       pop_heap()
00287       {
00288     const entry_cmp& m_cmp = static_cast<entry_cmp&>(*this);
00289     entry_pointer end = m_a_entries + m_size;
00290     std::pop_heap(m_a_entries, end, m_cmp);
00291       }
00292 
00293       bool
00294       is_heap()
00295       {
00296     const entry_cmp& m_cmp = static_cast<entry_cmp&>(*this);
00297     entry_pointer end = m_a_entries + m_size;
00298     bool p = std::__is_heap(m_a_entries, end, m_cmp);
00299     return p;
00300       }
00301 
00302 #ifdef _GLIBCXX_DEBUG
00303       void
00304       assert_valid(const char*, int) const;
00305 #endif
00306 
00307 #ifdef PB_DS_BINARY_HEAP_TRACE_
00308       void
00309       trace_entry(const entry&, false_type) const;
00310 
00311       void
00312       trace_entry(const entry&, true_type) const;
00313 #endif
00314 
00315       static entry_allocator    s_entry_allocator;
00316       static value_allocator    s_value_allocator;
00317       static no_throw_copies_t  s_no_throw_copies_ind;
00318 
00319       size_type         m_size;
00320       size_type         m_actual_size;
00321       entry_pointer         m_a_entries;
00322     };
00323 
00324 #define PB_DS_ASSERT_VALID(X) \
00325   _GLIBCXX_DEBUG_ONLY(X.assert_valid(__FILE__, __LINE__);)
00326 
00327 #define PB_DS_DEBUG_VERIFY(_Cond)                   \
00328   _GLIBCXX_DEBUG_VERIFY_AT(_Cond,                   \
00329                _M_message(#_Cond" assertion from %1;:%2;")  \
00330                ._M_string(__FILE__)._M_integer(__LINE__)    \
00331                ,__file,__line)
00332 
00333 #include <ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp>
00334 #include <ext/pb_ds/detail/binary_heap_/constructors_destructor_fn_imps.hpp>
00335 #include <ext/pb_ds/detail/binary_heap_/iterators_fn_imps.hpp>
00336 #include <ext/pb_ds/detail/binary_heap_/debug_fn_imps.hpp>
00337 #include <ext/pb_ds/detail/binary_heap_/trace_fn_imps.hpp>
00338 #include <ext/pb_ds/detail/binary_heap_/erase_fn_imps.hpp>
00339 #include <ext/pb_ds/detail/binary_heap_/info_fn_imps.hpp>
00340 #include <ext/pb_ds/detail/binary_heap_/find_fn_imps.hpp>
00341 #include <ext/pb_ds/detail/binary_heap_/split_join_fn_imps.hpp>
00342 #include <ext/pb_ds/detail/binary_heap_/policy_access_fn_imps.hpp>
00343 
00344 #undef PB_DS_CLASS_C_DEC
00345 #undef PB_DS_CLASS_T_DEC
00346 #undef PB_DS_ENTRY_CMP_DEC
00347 #undef PB_DS_RESIZE_POLICY_DEC
00348 
00349   } // namespace detail
00350 } // namespace __gnu_pbds
00351 
00352 #endif