← Back to branch summary

~frankencode/drycore/trunk

« back to all changes in this revision

Viewing changes to dry/Heap.hpp

  • Committer: Frank Mertens
  • Date: 2013-02-27 18:43:50 UTC
  • Revision ID: frank@cyblogic.de-20130227184350-ypu14rj5e2r8gwqz
Initial commit.

Show diffs side-by-side

added added

removed removed

Lines of Context:
dry/Heap.hpp
 
1
 /*
 
2
  * Copyright (C) 2007-2013 Frank Mertens.
 
3
  *
 
4
  * This program is free software; you can redistribute it and/or
 
5
  * modify it under the terms of the GNU General Public License
 
6
  * as published by the Free Software Foundation; either version
 
7
  * 2 of the License, or (at your option) any later version.
 
8
  */
 
9
#ifndef DRY_HEAP_HPP
 
10
#define DRY_HEAP_HPP
 
11
 
 
12
#include "containers.hpp"
 
13
 
 
14
namespace dry
 
15
{
 
16
 
 
17
template<class T, template<class T> class Order = Ascending>
 
18
class GenericHeap: public Container< T, GenericHeap<T, Order> >, public Order<T>
 
19
{
 
20
public:
 
21
        typedef T Item;
 
22
 
 
23
        ~GenericHeap()
 
24
        {
 
25
                if (bufOwner_)
 
26
                {
 
27
                        delete[] buf_;
 
28
                        buf_ = 0;
 
29
                }
 
30
        }
 
31
 
 
32
        inline int size() const { return size_; }
 
33
        inline int fill() const { return fill_; }
 
34
        inline int length() const { return fill_; }
 
35
        inline bool isFull() const { return fill_ == size_; }
 
36
        inline bool isEmpty() const { return fill_ == 0; }
 
37
 
 
38
        inline void push(const T &item)
 
39
        {
 
40
                DRY_ASSERT(fill_ < size_);
 
41
                buf_[fill_] = item;
 
42
                ++fill_;
 
43
                passUpLast();
 
44
        }
 
45
 
 
46
        inline void pop(T *item)
 
47
        {
 
48
                DRY_ASSERT(fill_ > 0);
 
49
                *item = buf_[0];
 
50
                --fill_;
 
51
                buf_[0] = buf_[fill_];
 
52
                passDownFromTop();
 
53
        }
 
54
 
 
55
        inline T pop() {
 
56
                T item;
 
57
                pop(&item);
 
58
                return item;
 
59
        }
 
60
 
 
61
        inline T top() { DRY_ASSERT(!isEmpty()); return buf_[0]; }
 
62
 
 
63
        inline void clear() { fill_ = 0; }
 
64
 
 
65
        inline static int parent(int i) { return (i - 1) / 2; }
 
66
        inline static int leftChild(int i) { return 2 * i + 1; }
 
67
        inline static int rightChild(int i) { return 2 * i + 2; }
 
68
 
 
69
        void xchg(int i, int j)
 
70
        {
 
71
                T h = buf_[i];
 
72
                buf_[i] = buf_[j];
 
73
                buf_[j] = h;
 
74
        }
 
75
 
 
76
        int min(int i, int j, int k)
 
77
        {
 
78
                int h = Order<T>::below(buf_[i], buf_[j]) ? i : j;
 
79
                return Order<T>::below(buf_[h], buf_[k]) ? h : k;
 
80
        }
 
81
 
 
82
        void passUpLast()
 
83
        {
 
84
                if (fill_ == 1) return;
 
85
                int i = fill_ - 1;
 
86
                while (i != 0) {
 
87
                        int j;
 
88
                        j = parent(i);
 
89
                        if (Order<T>::below(buf_[j], buf_[i])) break;
 
90
                        xchg(i, j);
 
91
                        i = j;
 
92
                }
 
93
        }
 
94
 
 
95
        void passDownFromTop()
 
96
        {
 
97
                if (fill_ == 0) return;
 
98
                int i = 0;
 
99
                while (true) {
 
100
                        int j, lc, rc;
 
101
                        lc = leftChild(i);
 
102
                        rc = rightChild(i);
 
103
 
 
104
                        if (rc < fill_) {
 
105
                                j = min(i, lc, rc);
 
106
                                if (j == i) break;
 
107
 
 
108
                                xchg(i, j);
 
109
                                i = j;
 
110
                        }
 
111
                        else if (lc < fill_) {
 
112
                                if (Order<T>::below(buf_[lc], buf_[i])) xchg(i, lc);
 
113
                                break;
 
114
                        }
 
115
                        else
 
116
                                break;
 
117
                }
 
118
        }
 
119
 
 
120
protected:
 
121
        GenericHeap(int size)
 
122
                : fill_(0),
 
123
                  size_(size),
 
124
                  bufOwner_(true),
 
125
                  buf_(new T[size])
 
126
        {}
 
127
 
 
128
        GenericHeap(T *buf, int size)
 
129
                : fill_(0),
 
130
                  size_(size),
 
131
                  bufOwner_(false),
 
132
                  buf_(buf)
 
133
        {}
 
134
 
 
135
        int fill_;    // current number of elements
 
136
        int size_;    // maximal number of elements
 
137
        bool bufOwner_;
 
138
        T *buf_;    // memory buffer used for storing elements
 
139
};
 
140
 
 
141
template<class T>
 
142
class Heap: public GenericHeap<T, FlexibleSortOrder>
 
143
{
 
144
public:
 
145
        typedef GenericHeap<T, FlexibleSortOrder> Super;
 
146
 
 
147
        inline static Ref<Heap> create(int size, int order = SortOrder::Ascending) {
 
148
                return new Heap(size, order);
 
149
        }
 
150
        inline static Ref<Heap> create(T *buf, int size, int order = SortOrder::Ascending) {
 
151
                return new Heap(buf, size, order);
 
152
        }
 
153
 
 
154
        void reset(int order) {
 
155
                Super::clear();
 
156
                Super::setSortOrder(order);
 
157
        }
 
158
 
 
159
private:
 
160
        Heap(int size, int order)
 
161
                : GenericHeap<T, FlexibleSortOrder>(size)
 
162
        {
 
163
                Super::setSortOrder(order);
 
164
        }
 
165
        Heap(T *buf, int size, int order)
 
166
                : GenericHeap<T, FlexibleSortOrder>(buf, size)
 
167
        {
 
168
                Super::setSortOrder(order);
 
169
        }
 
170
};
 
171
 
 
172
template<class T>
 
173
class MinHeap: public GenericHeap<T, Ascending>
 
174
{
 
175
public:
 
176
        inline static Ref<MinHeap> create(int size) {
 
177
                return new MinHeap(size);
 
178
        }
 
179
        inline static Ref<MinHeap> create(T *buf, int size) {
 
180
                return new MinHeap(buf, size);
 
181
        }
 
182
private:
 
183
        MinHeap(int size): GenericHeap<T, Ascending>(size) {}
 
184
        MinHeap(T *buf, int size): GenericHeap<T, Ascending>(buf, size) {}
 
185
};
 
186
 
 
187
template<class T>
 
188
class MaxHeap: public GenericHeap<T, Descending>
 
189
{
 
190
public:
 
191
        inline static Ref<MaxHeap> create(int size) {
 
192
                return new MaxHeap(size);
 
193
        }
 
194
        inline static Ref<MaxHeap> create(T *buf, int size) {
 
195
                return new MaxHeap(buf, size);
 
196
        }
 
197
private:
 
198
        MaxHeap(int size): GenericHeap<T, Descending>(size) {}
 
199
        MaxHeap(T *buf, int size): GenericHeap<T, Descending>(buf, size) {}
 
200
};
 
201
 
 
202
} // namespace dry
 
203
 
 
204
#endif // DRY_HEAP_H