Mercurial > projects > aid

comparison trunk/aid/containers/heap.d @ 0:4b2e8e8a633e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Repository setup.
author revcompgeek
date Mon, 03 Mar 2008 19:28:10 -0700
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:4b2e8e8a633e
1 /*++++++++++++++++++++++++++++++++++++++++++++
2 + Heap sorted array +
3 + By Matt Peterson +
4 ++++++++++++++++++++++++++++++++++++++++++++*/
5
6 /*class Heap(Value) {
7 Value[] array;
8 int tail;
9 public int capacity(){
10 // This returns the current capacity of the heap.
11 return array.length;
12 }
13 public int size(){
14 // This returns the number of items in the heap.
15 return tail;
16 }
17
18 void capacity(int c){
19 // This sets the capacity to c.
20 if(c < tail) c = tail;
21 array.length = c;
22 }
23 void insert(Value v){
24 // Inserts a value and sorts it to it's correct position.
25 if(tail >= size()) capacity(size()+10);
26 array[++tail] = v;
27 int i = tail;
28 while(i > 0 && array[i/2] > array[i]){
29 array[i] = array[i/2];
30 array[i/2] = v;
31 i /= 2;
32 }
33 }
34 Value removeHead(){
35 Value ret = array[0];
36 array[0] = array[tail];
37 tail--;
38 i = 0;
39 while(
40 }
41
42 }*/
43
44 struct Heap(Value, Alloc = GCAllocator) {
45
46 alias ArrayHeap ContainerType;
47 alias Value ValueType;
48 alias size_t IndexType;
49
50 Value[] data; ///< backing array. null by default, grows as needed
51
52 invariant {
53 assert( tail <= data.length );
54 }
55
56 /** signature for a custom comparison function */
57 alias int delegate(Value* a, Value* b) CompareFcn;
58
59 /** Set custom comparison function. */
60 void compareFcn(CompareFcn cmp) {
61 cmpFcn = cmp;
62 }
63
64 /** Get heap contents as dynamic array slice of backing array. */
65 Value[] values() {
66 return data[0..tail];
67 }
68
69 /** Adds an item to the heap. Increases capacity if needed. */
70 void addTail(Value v) {
71 capacity(tail+1);
72 data[tail++] = v;
73 fixupTail();
74 }
75
76 /** Removes and returns the head item of the heap. If the target
77 * heap is empty an IndexOutOfBoundsException is thrown unless
78 * version=MinTLNoIndexChecking is set.
79 */
80 Value takeHead() {
81 version (MinTLNoIndexChecking) {
82 // no error checking
83 } else {
84 if (tail == 0)
85 throw new IndexOutOfBoundsException();
86 }
87 Value val = data[0];
88 data[0] = data[--tail];
89 data[tail] = Value.init;
90 fixupHead();
91 return val;
92 }
93
94 /** Removes the head item of the heap. */
95 void removeHead() {
96 version (MinTLNoIndexChecking) {
97 // no error checking
98 } else {
99 if (tail == 0)
100 throw new IndexOutOfBoundsException();
101 }
102 data[0] = data[--tail];
103 data[tail] = Value.init;
104 fixupHead();
105 }
106
107 /** Get the length of heap. */
108 size_t length() {
109 return tail;
110 }
111
112 /** Test if container is empty. */
113 bool isEmpty() {
114 return tail == 0;
115 }
116
117 /** Clear all contents. */
118 void clear() {
119 static if (is(Alloc == GCAllocator)) {
120 } else {
121 if (data.ptr)
122 Alloc.gcFree(data.ptr);
123 }
124 *this = ArrayHeap.init;
125 }
126
127 /** Get the nth item in the heap from head. */
128 Value opIndex(size_t n) {
129 return data[n];
130 }
131
132 /** Get a pointer to the nth item in the heap */
133 Value* lookup(size_t n) {
134 return &data[n];
135 }
136
137 /** Set the nth item in the heap. */
138 void opIndexAssign(Value val, size_t n) {
139 data[n] = val;
140 }
141
142 /** Duplicates a heap. */
143 ArrayHeap dup() {
144 ArrayHeap res;
145 static if (is(Alloc == GCAllocator)) {
146 res.data = data.dup;
147 } else {
148 Value* p = cast(Value*)Alloc.malloc(data.length * Value.sizeof);
149 res.data = p[0 .. data.length];
150 res.data[] = data[];
151 }
152 res.tail = tail;
153 res.cmpFcn = cmpFcn;
154 return res;
155 }
156
157 /** Test for equality of two heaps. */
158 int opEquals(ArrayHeap c) {
159 size_t len = length;
160 if (len !is c.length)
161 return 0;
162 size_t a,b;
163 a = 0;
164 b = 0;
165 TypeInfo ti = typeid(Value);
166 for (size_t k = 0; k < len; k++) {
167 if (!ti.equals(&data[a],&c.data[b]))
168 return 0;
169 a++;
170 b++;
171 }
172 return 1;
173 }
174
175 /** Compare two heaps. */
176 int opCmp(ArrayHeap c) {
177 size_t len = length;
178 if (len > c.length)
179 len = c.length;
180 size_t a,b;
181 a = 0;
182 b = 0;
183 TypeInfo ti = typeid(Value);
184 for (size_t k = 0; k < len; k++) {
185 int cmp = ti.compare(&data[a],&c.data[b]);
186 if (cmp)
187 return cmp;
188 a++;
189 b++;
190 }
191 return cast(int)length - cast(int)c.length;
192 }
193
194 /** Returns a short string representation of the heap. */
195 char[] toString() {
196 return "[ArrayHeap length " ~ std.string.toString(tail) ~ "]";
197 }
198
199 /** Iterates over the heap from head to tail calling delegate to
200 * perform an action. The value is passed to the delegate.
201 */
202 int opApplyNoKey(int delegate(inout Value x) dg){
203 int res = 0;
204 for (size_t k=0; k < tail; k++) {
205 res = dg(data[k]);
206 if (res) break;
207 }
208 return res;
209 }
210
211 /** Iterates over the heap from head to tail calling delegate to
212 * perform an action. The index from 0 and the value are passed
213 * to the delegate.
214 */
215 int opApplyWithKey(int delegate(inout size_t n, inout Value x) dg){
216 int res = 0;
217 for (size_t k=0; k < tail; k++) {
218 res = dg(k,data[k]);
219 if (res) break;
220 }
221 return res;
222 }
223
224 alias opApplyNoKey opApply;
225 alias opApplyWithKey opApply;
226
227 /** Ensure the minimum capacity of heap. */
228 void capacity(size_t cap) {
229 if (cap > data.length) {
230 cap = (cap+1)*2;
231 static if (is(Alloc == GCAllocator)) {
232 data.length = cap;
233 } else {
234 Value* p = data.ptr;
235 p = cast(Value*)Alloc.gcRealloc(p,cap*Value.sizeof);
236 p[data.length .. cap] = Value.init;
237 data = p[0 .. cap];
238 }
239 }
240 }
241
242 // Helper functions
243
244 // enforce heap invariant after a new head
245 private void fixupHead() {
246 size_t n = 0;
247 TypeInfo ti = typeid(Value);
248 if (cmpFcn is null) {
249 cmpFcn = cast(CompareFcn)&ti.compare;
250 }
251 for (;;) {
252 size_t n1 = 2*n+1;
253 if (n1 >= tail) break;
254 if ((n1 != tail-1) && (cmpFcn(&data[n1],&data[n1+1]) < 0))
255 n1++;
256 if (cmpFcn(&data[n],&data[n1]) < 0) {
257 ti.swap(&data[n],&data[n1]);
258 n = n1;
259 } else {
260 break;
261 }
262 }
263 }
264
265 // enforce heap invariant after a new tail
266 private void fixupTail() {
267 size_t n = tail-1;
268 TypeInfo ti = typeid(Value);
269 if (cmpFcn is null) {
270 cmpFcn = cast(CompareFcn)&ti.compare;
271 }
272 size_t n1 = (n-1)>>1;
273 while ((n > 0) && (cmpFcn(&data[n],&data[n1]) > 0)) {
274 ti.swap(&data[n],&data[n1]);
275 n = n1;
276 n1 = (n-1)>>1;
277 }
278 }
279
280 private CompareFcn cmpFcn;
281 private size_t tail;
282 }