root/OpenSceneGraph/trunk/src/osgUtil/TriStrip_heap_array.h @ 4772

Revision 4772, 7.6 kB (checked in by robert, 9 years ago)

Added catch of erase of the last element of heap.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
Line 
1// heap_array.h: interface for the heap_array class.
2//
3//////////////////////////////////////////////////////////////////////
4//
5//  Copyright (C) 2002 Tanguy Fautré.
6//
7//  This software is provided 'as-is', without any express or implied
8//  warranty.  In no event will the authors be held liable for any damages
9//  arising from the use of this software.
10//
11//  Permission is granted to anyone to use this software for any purpose,
12//  including commercial applications, and to alter it and redistribute it
13//  freely, subject to the following restrictions:
14//
15//  1. The origin of this software must not be misrepresented; you must not
16//     claim that you wrote the original software. If you use this software
17//     in a product, an acknowledgment in the product documentation would be
18//     appreciated but is not required.
19//  2. Altered source versions must be plainly marked as such, and must not be
20//     misrepresented as being the original software.
21//  3. This notice may not be removed or altered from any source distribution.
22//
23//  Tanguy Fautré
24//  softdev@pandora.be
25//
26//////////////////////////////////////////////////////////////////////
27//
28//                        Semi-dynamic indexed heap
29//                        *************************
30//
31// Current version: 1.00 BETA 1 (24/10/2002)
32//
33// Comment: heap_array acts like a normal heap, you can push elements
34//          and then get the greatest one.
35//          However you cannot push any more element once an element
36//          has been removed (pop, erase, etc...).
37//          Elements can be modified after they've been pushed into
38//          the heap via their indice.
39//         
40// History: -
41//
42//////////////////////////////////////////////////////////////////////
43
44#ifndef TRISTRIP_HEAP_ARRAY_H
45#define TRISTRIP_HEAP_ARRAY_H
46
47
48// namespace common_structures
49namespace common_structures {
50
51
52
53
54template <class T, class CmpT = std::less<T> >
55class heap_array
56{
57public:
58
59    struct heap_is_locked {    };
60
61
62    // heap_array main interface. Pre = PreCondition, Post = PostCondition
63
64    heap_array() : m_Locked(false) { }        // Post: ((size() == 0) && ! locked())
65
66    void clear();                            // Post: ((size() == 0) && ! locked())
67
68    void reserve(size_t Size);
69    size_t size() const;
70
71    bool empty() const;
72    bool locked() const;
73    bool removed(size_t i) const;            // Pre: (valid(i))
74    bool valid(size_t i) const;
75
76    const T & top() const;                    // Pre: (! empty())
77    const T & peek(size_t i) const;            // Pre: (valid(i) && ! removed(i))
78    const T & operator [] (size_t i) const;    // Pre: (valid(i) && ! removed(i))
79
80    size_t push(const T & Elem);            // Pre: (! locked()) else throw (heap_is_locked)
81
82    void pop();                                // Pre: (! empty())                  Post: (locked())
83    void erase(size_t i);                    // Pre: (valid(i) && ! removed(i))   Post: (locked())
84    void update(size_t i, const T & Elem);    // Pre: (valid(i) && ! removed(i))   Post: (locked())
85
86protected:
87
88    struct linker {
89        linker(const T & Elem, size_t i) : m_Elem(Elem), m_Indice(i) { }
90
91        T        m_Elem;
92        size_t    m_Indice;
93    };
94
95    typedef std::vector<linker> linked_heap;
96    typedef std::vector<size_t> finder;
97
98    void Adjust(size_t i);
99    void Swap(size_t a, size_t b);
100    bool Less(const linker & a, const linker & b) const;
101
102    linked_heap    m_Heap;
103    finder        m_Finder;
104    CmpT        m_Compare;
105    bool        m_Locked;
106};
107
108
109
110
111//////////////////////////////////////////////////////////////////////////
112// heap_indexed Inline functions
113//////////////////////////////////////////////////////////////////////////
114
115template <class T, class CmpT>
116inline void heap_array<T, CmpT>::clear() {
117    m_Heap.clear();
118    m_Finder.clear();
119    m_Locked = false;
120}
121
122
123template <class T, class CmpT>
124inline bool heap_array<T, CmpT>::empty() const {
125    return m_Heap.empty();
126}
127
128
129template <class T, class CmpT>
130inline bool heap_array<T, CmpT>::locked() const {
131    return m_Locked;
132}
133
134
135template <class T, class CmpT>
136inline void heap_array<T, CmpT>::reserve(size_t Size) {
137    m_Heap.reserve(Size);
138    m_Finder.reserve(Size);
139}
140
141
142template <class T, class CmpT>
143inline size_t heap_array<T, CmpT>::size() const {
144    return m_Heap.size();
145}
146
147
148template <class T, class CmpT>
149inline const T & heap_array<T, CmpT>::top() const {
150    // Debug check to ensure heap is not empty
151    //assert(! empty());
152    if (empty()) throw "heap_array<T, CmpT>::top() error, heap empty";
153
154    return m_Heap.front().m_Elem;
155}
156
157
158template <class T, class CmpT>
159inline const T & heap_array<T, CmpT>::peek(size_t i) const {
160    // Debug check to ensure element is still present
161    //assert(! removed(i));
162    if (removed(i)) throw "heap_array<T, CmpT>::peek(size_t i) error";
163
164    return (m_Heap[m_Finder[i]].m_Elem);
165}
166
167
168template <class T, class CmpT>
169inline const T & heap_array<T, CmpT>::operator [] (size_t i) const {
170    return peek(i);
171}
172
173
174template <class T, class CmpT>
175inline void heap_array<T, CmpT>::pop() {
176    m_Locked = true;
177
178    // Debug check to ensure heap is not empty
179    //assert(! empty());
180    if (empty()) throw "heap_array<T, CmpT>::pop() error, heap empty";
181   
182    Swap(0, size() - 1);
183    m_Heap.pop_back();
184    Adjust(0);
185}
186
187
188template <class T, class CmpT>
189inline size_t heap_array<T, CmpT>::push(const T & Elem) {
190    if (m_Locked)
191        throw "heap_is_locked";
192
193    size_t Id = size();
194    m_Finder.push_back(Id);
195    m_Heap.push_back(linker(Elem, Id));
196    Adjust(Id);
197
198    return Id;
199}
200
201
202template <class T, class CmpT>
203inline void heap_array<T, CmpT>::erase(size_t i) {
204    m_Locked = true;
205
206    // Debug check to ensure element is still present
207    if (removed(i)) throw "heap_array<T, CmpT>::erase(size_t i) error";
208
209    size_t j = m_Finder[i];
210
211    if (j==m_Heap.size()-1)
212    {
213        m_Heap.pop_back();
214    }
215    else
216    {
217        Swap(j, size() - 1);
218        m_Heap.pop_back();
219        Adjust(j);
220    }
221
222
223}
224
225
226template <class T, class CmpT>
227inline bool heap_array<T, CmpT>::removed(size_t i) const {
228    return (m_Finder[i] >= m_Heap.size());
229}
230
231
232template <class T, class CmpT>
233inline bool heap_array<T, CmpT>::valid(size_t i) const {
234    return (i < m_Finder.size());
235}
236
237
238template <class T, class CmpT>
239inline void heap_array<T, CmpT>::update(size_t i, const T & Elem) {
240    // Debug check to ensure element is still present
241    // assert(! removed(i));
242    if (removed(i)) throw "heap_array<T, CmpT>::update(size_t i, const T & Elem) error";
243
244    size_t j = m_Finder[i];
245    m_Heap[j].m_Elem = Elem;
246    Adjust(j);
247}
248
249
250template <class T, class CmpT>
251inline void heap_array<T, CmpT>::Adjust(size_t i)
252{
253    if (m_Heap.size()<=1) return; // nothing to swap, so just return.
254
255    size_t j;
256
257    // Check the upper part of the heap
258    for (j = i; (j > 0) && (Less(m_Heap[(j - 1) / 2], m_Heap[j])); j = ((j - 1) / 2))
259        Swap(j, (j - 1) / 2);
260
261    // Check the lower part of the heap
262    for (i = j; (j = 2 * i + 1) < size(); i = j) {
263         if ((j + 1 < size()) && (Less(m_Heap[j], m_Heap[j + 1])))
264            ++j;
265
266        if (Less(m_Heap[j], m_Heap[i]))
267            return;
268
269        Swap(i, j);
270    }
271}
272
273
274template <class T, class CmpT>
275inline void heap_array<T, CmpT>::Swap(size_t a, size_t b) {
276    std::swap(m_Heap[a], m_Heap[b]);
277
278    // use (size_t &) to get rid of a bogus compile warning
279    (size_t &) (m_Finder[(m_Heap[a].m_Indice)]) = a;
280    (size_t &) (m_Finder[(m_Heap[b].m_Indice)]) = b;
281}
282
283
284template <class T, class CmpT>
285inline bool heap_array<T, CmpT>::Less(const linker & a, const linker & b) const {
286    return m_Compare(a.m_Elem, b.m_Elem);
287}
288
289
290
291
292} // namespace common_structures
293
294#endif
Note: See TracBrowser for help on using the browser.