Main Page Modules Namespace List Class Hierarchy Alphabetical List Compound List File List Namespace Members Compound Members File Members Related Pages

# heap_array.h

Go to the documentation of this file.

    00001 // heap_array.h: interface for the heap_array class.
    00002 //
    00003 //////////////////////////////////////////////////////////////////////
    00004 //
    00005 //  Copyright (C) 2002 Tanguy Fautré.
    00006 //
    00007 //  This software is provided 'as-is', without any express or implied
    00008 //  warranty.  In no event will the authors be held liable for any damages
    00009 //  arising from the use of this software.
    00010 //
    00011 //  Permission is granted to anyone to use this software for any purpose,
    00012 //  including commercial applications, and to alter it and redistribute it
    00013 //  freely, subject to the following restrictions:
    00014 //
    00015 //  1. The origin of this software must not be misrepresented; you must not
    00016 //     claim that you wrote the original software. If you use this software
    00017 //     in a product, an acknowledgment in the product documentation would be
    00018 //     appreciated but is not required.
    00019 //  2. Altered source versions must be plainly marked as such, and must not be
    00020 //     misrepresented as being the original software.
    00021 //  3. This notice may not be removed or altered from any source distribution.
    00022 //
    00023 //  Tanguy Fautré
    00024 //  softdev@pandora.be
    00025 //
    00026 //////////////////////////////////////////////////////////////////////
    00027 //
    00028 //                      Semi-dynamic indexed heap
    00029 //                      *************************
    00030 //
    00031 // Current version: 1.00 BETA 1 (24/10/2002)
    00032 //
    00033 // Comment: heap_array acts like a normal heap, you can push elements
    00034 //          and then get the greatest one.
    00035 //          However you cannot push any more element once an element
    00036 //          has been removed (pop, erase, etc...).
    00037 //          Elements can be modified after they've been pushed into
    00038 //          the heap via their indice.
    00039 //
    00040 // History: -
    00041 //
    00042 //////////////////////////////////////////////////////////////////////
    00043
    00044 #ifndef HEAP_ARRAY_H
    00045 #define HEAP_ARRAY_H
    00046
    00047
    00048
    00049 // namespace common_structures
    00050 namespace common_structures {
    00051
    00052
    00053
    00054
    00055 template <class T, class CmpT = std::less<T> >
    00056 class heap_array
    00057 {
    00058 public:
    00059
    00060     struct heap_is_locked { };
    00061
    00062
    00063     // heap_array main interface. Pre = PreCondition, Post = PostCondition
    00064
    00065     heap_array() : m_Locked(false) { }      // Post: ((size() == 0) && ! locked())
    00066
    00067     void clear();                           // Post: ((size() == 0) && ! locked())
    00068
    00069     void reserve(size_t Size);
    00070     size_t size() const;
    00071
    00072     bool empty() const;
    00073     bool locked() const;
    00074     bool removed(size_t i) const;           // Pre: (valid(i))
    00075     bool valid(size_t i) const;
    00076
    00077     const T & top() const;                  // Pre: (! empty())
    00078     const T & peek(size_t i) const;         // Pre: (valid(i) && ! removed(i))
    00079     const T & operator [] (size_t i) const; // Pre: (valid(i) && ! removed(i))
    00080
    00081     size_t push(const T & Elem);            // Pre: (! locked()) else throw (heap_is_locked)
    00082
    00083     void pop();                             // Pre: (! empty())                  Post: (locked())
    00084     void erase(size_t i);                   // Pre: (valid(i) && ! removed(i))   Post: (locked())
    00085     void update(size_t i, const T & Elem);  // Pre: (valid(i) && ! removed(i))   Post: (locked())
    00086
    00087 protected:
    00088
    00089     struct linker {
    00090         linker(const T & Elem, size_t i) : m_Elem(Elem), m_Indice(i) { }
    00091
    00092         T       m_Elem;
    00093         size_t  m_Indice;
    00094     };
    00095
    00096     typedef typename std::vector<linker> linked_heap;
    00097     typedef typename std::vector<size_t> finder;
    00098
    00099     void Adjust(size_t i);
    00100     void Swap(size_t a, size_t b);
    00101     bool Less(const linker & a, const linker & b) const;
    00102
    00103     linked_heap m_Heap;
    00104     finder      m_Finder;
    00105     CmpT        m_Compare;
    00106     bool        m_Locked;
    00107 };
    00108
    00109
    00110
    00111
    00112 //////////////////////////////////////////////////////////////////////////
    00113 // heap_indexed Inline functions
    00114 //////////////////////////////////////////////////////////////////////////
    00115
    00116 template <class T, class CmpT>
    00117 inline void heap_array<T, CmpT>::clear() {
    00118     m_Heap.clear();
    00119     m_Finder.clear();
    00120     m_Locked = false;
    00121 }
    00122
    00123
    00124 template <class T, class CmpT>
    00125 inline bool heap_array<T, CmpT>::empty() const {
    00126     return m_Heap.empty();
    00127 }
    00128
    00129
    00130 template <class T, class CmpT>
    00131 inline bool heap_array<T, CmpT>::locked() const {
    00132     return m_Locked;
    00133 }
    00134
    00135
    00136 template <class T, class CmpT>
    00137 inline void heap_array<T, CmpT>::reserve(size_t Size) {
    00138     m_Heap.reserve(Size);
    00139     m_Finder.reserve(Size);
    00140 }
    00141
    00142
    00143 template <class T, class CmpT>
    00144 inline size_t heap_array<T, CmpT>::size() const {
    00145     return m_Heap.size();
    00146 }
    00147
    00148
    00149 template <class T, class CmpT>
    00150 inline const T & heap_array<T, CmpT>::top() const {
    00151     // Debug check to ensure heap is not empty
    00152     assert(! empty());
    00153
    00154     return m_Heap.front().m_Elem;
    00155 }
    00156
    00157
    00158 template <class T, class CmpT>
    00159 inline const T & heap_array<T, CmpT>::peek(size_t i) const {
    00160     // Debug check to ensure element is still present
    00161     assert(! removed(i));
    00162
    00163     return (m_Heap[m_Finder[i]].m_Elem);
    00164 }
    00165
    00166
    00167 template <class T, class CmpT>
    00168 inline const T & heap_array<T, CmpT>::operator [] (size_t i) const {
    00169     return peek(i);
    00170 }
    00171
    00172
    00173 template <class T, class CmpT>
    00174 inline void heap_array<T, CmpT>::pop() {
    00175     m_Locked = true;
    00176
    00177     // Debug check to ensure heap is not empty
    00178     assert(! empty());
    00179
    00180     Swap(0, size() - 1);
    00181     m_Heap.pop_back();
    00182     Adjust(0);
    00183 }
    00184
    00185
    00186 template <class T, class CmpT>
    00187 inline size_t heap_array<T, CmpT>::push(const T & Elem) {
    00188     if (m_Locked)
    00189         throw heap_is_locked();
    00190
    00191     size_t Id = size();
    00192     m_Finder.push_back(Id);
    00193     m_Heap.push_back(linker(Elem, Id));
    00194     Adjust(Id);
    00195
    00196     return Id;
    00197 }
    00198
    00199
    00200 template <class T, class CmpT>
    00201 inline void heap_array<T, CmpT>::erase(size_t i) {
    00202     m_Locked = true;
    00203
    00204     // Debug check to ensure element is still present
    00205     assert(! removed(i));
    00206
    00207     size_t j = m_Finder[i];
    00208     Swap(j, size() - 1);
    00209     m_Heap.pop_back();
    00210     Adjust(j);
    00211 }
    00212
    00213
    00214 template <class T, class CmpT>
    00215 inline bool heap_array<T, CmpT>::removed(size_t i) const {
    00216     return (m_Finder[i] >= m_Heap.size());
    00217 }
    00218
    00219
    00220 template <class T, class CmpT>
    00221 inline bool heap_array<T, CmpT>::valid(size_t i) const {
    00222     return (i < m_Finder.size());
    00223 }
    00224
    00225
    00226 template <class T, class CmpT>
    00227 inline void heap_array<T, CmpT>::update(size_t i, const T & Elem) {
    00228     // Debug check to ensure element is still present
    00229     assert(! removed(i));
    00230
    00231     size_t j = m_Finder[i];
    00232     m_Heap[j].m_Elem = Elem;
    00233     Adjust(j);
    00234 }
    00235
    00236
    00237 template <class T, class CmpT>
    00238 inline void heap_array<T, CmpT>::Adjust(size_t i) {
    00239     size_t j;
    00240
    00241     // Check the upper part of the heap
    00242     for (j = i; (j > 0) && (Less(m_Heap[(j - 1) / 2], m_Heap[j])); j = ((j - 1) / 2))
    00243         Swap(j, (j - 1) / 2);
    00244
    00245     // Check the lower part of the heap
    00246     for (i = j; (j = 2 * i + 1) < size(); i = j) {
    00247         if ((j + 1 < size()) && (Less(m_Heap[j], m_Heap[j + 1])))
    00248             ++j;
    00249
    00250         if (Less(m_Heap[j], m_Heap[i]))
    00251             return;
    00252
    00253         Swap(i, j);
    00254     }
    00255 }
    00256
    00257
    00258 template <class T, class CmpT>
    00259 inline void heap_array<T, CmpT>::Swap(size_t a, size_t b) {
    00260     std::swap(m_Heap[a], m_Heap[b]);
    00261
    00262     // use (size_t &) to get rid of a bogus compile warning
    00263     (size_t &) (m_Finder[(m_Heap[a].m_Indice)]) = a;
    00264     (size_t &) (m_Finder[(m_Heap[b].m_Indice)]) = b;
    00265 }
    00266
    00267
    00268 template <class T, class CmpT>
    00269 inline bool heap_array<T, CmpT>::Less(const linker & a, const linker & b) const {
    00270     return m_Compare(a.m_Elem, b.m_Elem);
    00271 }
    00272
    00273
    00274
    00275
    00276 }; // namespace common_structures
    00277
    00278 #endif