|
0
|
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 } |
