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

Revision 10757, 8.0 kB (checked in by robert, 5 years ago)

Removed throw.

  • 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// namespace common_structures
48namespace common_structures {
49
50
51
52
53template <class T, class CmpT = std::less<T> >
54class heap_array
55{
56public:
57
58    struct heap_is_locked {    };
59
60
61    // heap_array main interface. Pre = PreCondition, Post = PostCondition
62
63    heap_array() : m_Locked(false) { }        // Post: ((size() == 0) && ! locked())
64
65    void clear();                            // Post: ((size() == 0) && ! locked())
66
67    void reserve(size_t Size);
68    size_t size() const;
69
70    bool empty() const;
71    bool locked() const;
72    bool removed(size_t i) const;            // Pre: (valid(i))
73    bool valid(size_t i) const;
74
75    const T & top() const;                    // Pre: (! empty())
76    const T & peek(size_t i) const;            // Pre: (valid(i) && ! removed(i))
77    const T & operator [] (size_t i) const;    // Pre: (valid(i) && ! removed(i))
78
79    size_t push(const T & Elem);            // Pre: (! locked()) else throw (heap_is_locked)
80
81    void pop();                                // Pre: (! empty())                  Post: (locked())
82    void erase(size_t i);                    // Pre: (valid(i) && ! removed(i))   Post: (locked())
83    void update(size_t i, const T & Elem);    // Pre: (valid(i) && ! removed(i))   Post: (locked())
84
85protected:
86
87    struct linker {
88        linker(const T & Elem, size_t i) : m_Elem(Elem), m_Indice(i) { }
89
90        T        m_Elem;
91        size_t    m_Indice;
92    };
93
94    typedef std::vector<linker> linked_heap;
95    typedef std::vector<size_t> finder;
96
97    void Adjust(size_t i);
98    void Swap(size_t a, size_t b);
99    bool Less(const linker & a, const linker & b) const;
100
101    linked_heap    m_Heap;
102    finder        m_Finder;
103    CmpT        m_Compare;
104    bool        m_Locked;
105};
106
107
108
109
110//////////////////////////////////////////////////////////////////////////
111// heap_indexed Inline functions
112//////////////////////////////////////////////////////////////////////////
113
114template <class T, class CmpT>
115inline void heap_array<T, CmpT>::clear() {
116    m_Heap.clear();
117    m_Finder.clear();
118    m_Locked = false;
119}
120
121
122template <class T, class CmpT>
123inline bool heap_array<T, CmpT>::empty() const {
124    return m_Heap.empty();
125}
126
127
128template <class T, class CmpT>
129inline bool heap_array<T, CmpT>::locked() const {
130    return m_Locked;
131}
132
133
134template <class T, class CmpT>
135inline void heap_array<T, CmpT>::reserve(size_t Size) {
136    m_Heap.reserve(Size);
137    m_Finder.reserve(Size);
138}
139
140
141template <class T, class CmpT>
142inline size_t heap_array<T, CmpT>::size() const {
143    return m_Heap.size();
144}
145
146
147template <class T, class CmpT>
148inline const T & heap_array<T, CmpT>::top() const {
149    // Debug check to ensure heap is not empty
150    if (empty())
151    {
152        osg::notify(osg::NOTICE)<<"TriStripVisitor:: heap_array<T, CmpT>::top() error, heap empty."<<std::endl;
153    }
154
155    return m_Heap.front().m_Elem;
156}
157
158
159template <class T, class CmpT>
160inline const T & heap_array<T, CmpT>::peek(size_t i) const {
161    // Debug check to ensure element is still present
162    //assert(! removed(i));
163    if (removed(i))
164    {
165        osg::notify(osg::NOTICE)<<"TriStripVisitor:: heap_array<T, CmpT>::peek(size_t i) error."<<std::endl;
166    }
167
168    return (m_Heap[m_Finder[i]].m_Elem);
169}
170
171
172template <class T, class CmpT>
173inline const T & heap_array<T, CmpT>::operator [] (size_t i) const {
174    return peek(i);
175}
176
177
178template <class T, class CmpT>
179inline void heap_array<T, CmpT>::pop() {
180    m_Locked = true;
181
182    // Debug check to ensure heap is not empty
183    if (empty())
184    {
185        osg::notify(osg::NOTICE)<<"TriStripVisitor:: heap_array<T, CmpT>::pop() error, heap empty."<<std::endl;;
186        return;
187    }
188   
189    Swap(0, size() - 1);
190    m_Heap.pop_back();
191    Adjust(0);
192}
193
194
195template <class T, class CmpT>
196inline size_t heap_array<T, CmpT>::push(const T & Elem) {
197    if (m_Locked)
198    {
199        osg::notify(osg::NOTICE)<<"TriStripVisitor:: heap_array<T, CmpT>::push() heap_is_locked."<<std::endl;;
200        return 0;
201    }
202
203    size_t Id = size();
204    m_Finder.push_back(Id);
205    m_Heap.push_back(linker(Elem, Id));
206    Adjust(Id);
207
208    return Id;
209}
210
211
212template <class T, class CmpT>
213inline void heap_array<T, CmpT>::erase(size_t i) {
214    m_Locked = true;
215
216    // Debug check to ensure element is still present
217    if (removed(i))
218    {
219        osg::notify(osg::NOTICE)<<"TriStripVisitor:: heap_array<T, CmpT>::erase(size_t i) error."<<std::endl;;
220        return;
221    }
222   
223    size_t j = m_Finder[i];
224
225    if (j==m_Heap.size()-1)
226    {
227        m_Heap.pop_back();
228    }
229    else
230    {
231        Swap(j, size() - 1);
232        m_Heap.pop_back();
233        Adjust(j);
234    }
235
236
237}
238
239
240template <class T, class CmpT>
241inline bool heap_array<T, CmpT>::removed(size_t i) const {
242    return (m_Finder[i] >= m_Heap.size());
243}
244
245
246template <class T, class CmpT>
247inline bool heap_array<T, CmpT>::valid(size_t i) const {
248    return (i < m_Finder.size());
249}
250
251
252template <class T, class CmpT>
253inline void heap_array<T, CmpT>::update(size_t i, const T & Elem) {
254    // Debug check to ensure element is still present
255    // assert(! removed(i));
256    if (removed(i))
257    {
258        osg::notify(osg::NOTICE)<<"TriStripVisitor:: heap_array<T, CmpT>::update(size_t i, const T & Elem) error."<<std::endl;;
259        return;
260    }
261
262    size_t j = m_Finder[i];
263    m_Heap[j].m_Elem = Elem;
264    Adjust(j);
265}
266
267
268template <class T, class CmpT>
269inline void heap_array<T, CmpT>::Adjust(size_t i)
270{
271    if (m_Heap.size()<=1) return; // nothing to swap, so just return.
272
273    size_t j;
274
275    // Check the upper part of the heap
276    for (j = i; (j > 0) && (Less(m_Heap[(j - 1) / 2], m_Heap[j])); j = ((j - 1) / 2))
277        Swap(j, (j - 1) / 2);
278
279    // Check the lower part of the heap
280    for (i = j; (j = 2 * i + 1) < size(); i = j) {
281         if ((j + 1 < size()) && (Less(m_Heap[j], m_Heap[j + 1])))
282            ++j;
283
284        if (Less(m_Heap[j], m_Heap[i]))
285            return;
286
287        Swap(i, j);
288    }
289}
290
291
292template <class T, class CmpT>
293inline void heap_array<T, CmpT>::Swap(size_t a, size_t b) {
294    std::swap(m_Heap[a], m_Heap[b]);
295
296    // use (size_t &) to get rid of a bogus compile warning
297    (size_t &) (m_Finder[(m_Heap[a].m_Indice)]) = a;
298    (size_t &) (m_Finder[(m_Heap[b].m_Indice)]) = b;
299}
300
301
302template <class T, class CmpT>
303inline bool heap_array<T, CmpT>::Less(const linker & a, const linker & b) const {
304    return m_Compare(a.m_Elem, b.m_Elem);
305}
306
307
308
309
310} // namespace common_structures
311
312#endif
Note: See TracBrowser for help on using the browser.