|
1
|
1 /* Ddbg - Win32 Debugger for the D programming language
|
|
|
2 * Copyright (c) 2007 Jascha Wetzel
|
|
|
3 * All rights reserved. See LICENSE.TXT for details.
|
|
|
4 */
|
|
|
5
|
|
|
6 import std.string;
|
|
|
7 debug import std.stdio;
|
|
|
8
|
|
|
9 /*******************************************************************************
|
|
|
10 Double linked list
|
|
|
11 *******************************************************************************/
|
|
|
12 class List(T)
|
|
|
13 {
|
|
|
14 class Element
|
|
|
15 {
|
|
|
16 T value;
|
|
|
17 Element prev,
|
|
|
18 next;
|
|
|
19
|
|
|
20 this(T v)
|
|
|
21 {
|
|
|
22 value = v;
|
|
|
23 }
|
|
|
24 }
|
|
|
25
|
|
|
26 Element head,
|
|
|
27 tail;
|
|
|
28
|
|
|
29 List opCatAssign(T v)
|
|
|
30 {
|
|
|
31 if ( tail is null )
|
|
|
32 head = tail = new Element(v);
|
|
|
33 else {
|
|
|
34 tail.next = new Element(v);
|
|
|
35 tail.next.prev = tail;
|
|
|
36 tail = tail.next;
|
|
|
37 }
|
|
|
38 return this;
|
|
|
39 }
|
|
|
40
|
|
|
41 bool empty()
|
|
|
42 {
|
|
|
43 return head is null;
|
|
|
44 }
|
|
|
45
|
|
|
46 void clear()
|
|
|
47 {
|
|
|
48 head = null;
|
|
|
49 tail = null;
|
|
|
50 }
|
|
|
51
|
|
|
52 void remove(Element e)
|
|
|
53 {
|
|
|
54 if ( e is null )
|
|
|
55 return;
|
|
|
56 assert(e !is null);
|
|
|
57 if ( e.prev is null )
|
|
|
58 head = e.next;
|
|
|
59 else
|
|
|
60 e.prev.next = e.next;
|
|
|
61 if ( e.next is null )
|
|
|
62 tail = e.prev;
|
|
|
63 else
|
|
|
64 e.next.prev = e.prev;
|
|
|
65 }
|
|
|
66
|
|
|
67 int opApply(int delegate(inout Element) dg)
|
|
|
68 {
|
|
|
69 for ( Element e=head; e !is null; e = e.next )
|
|
|
70 {
|
|
|
71 int ret = dg(e);
|
|
|
72 if ( ret )
|
|
|
73 return ret;
|
|
|
74 }
|
|
|
75 return 0;
|
|
|
76 }
|
|
|
77
|
|
|
78 int opApplyReverse(int delegate(inout Element) dg)
|
|
|
79 {
|
|
|
80 for ( Element e=tail; e !is null; e = e.prev )
|
|
|
81 {
|
|
|
82 int ret = dg(e);
|
|
|
83 if ( ret )
|
|
|
84 return ret;
|
|
|
85 }
|
|
|
86 return 0;
|
|
|
87 }
|
|
|
88 }
|
|
|
89
|
|
|
90 /**************************************************************************************************
|
|
|
91 AVL Tree that balances itself after each insertion
|
|
|
92 **************************************************************************************************/
|
|
|
93 class AVLTree(T)
|
|
|
94 {
|
|
|
95 alias AVLNode!(T) node_t;
|
|
|
96 node_t root;
|
|
|
97 bool rebalance;
|
|
|
98
|
|
|
99 bool insert(T v)
|
|
|
100 {
|
|
|
101 if ( root is null ) {
|
|
|
102 root = new AVLNode!(T)(v);
|
|
|
103 return true;
|
|
|
104 }
|
|
|
105 else {
|
|
|
106 rebalance = false;
|
|
|
107 return insert(root, v);
|
|
|
108 }
|
|
|
109 }
|
|
|
110
|
|
|
111 bool find(VT,RT)(VT v, out RT res)
|
|
|
112 {
|
|
|
113 if ( root is null )
|
|
|
114 return false;
|
|
|
115 return root.find(v, res);
|
|
|
116 }
|
|
|
117
|
|
|
118 void traverseDepthLeft(RT)(bool delegate(RT v) proc)
|
|
|
119 {
|
|
|
120 if ( root !is null )
|
|
|
121 root.traverseDepthLeft(proc);
|
|
|
122 }
|
|
|
123
|
|
|
124 private bool insert(node_t n, T v)
|
|
|
125 {
|
|
|
126 void updateParents(node_t top=null)
|
|
|
127 {
|
|
|
128 with ( n )
|
|
|
129 {
|
|
|
130 if ( top is null )
|
|
|
131 top = n;
|
|
|
132
|
|
|
133 balance = 0;
|
|
|
134 parent.balance = 0;
|
|
|
135
|
|
|
136 node_t pp = parent.parent;
|
|
|
137 if ( pp is null )
|
|
|
138 root = top;
|
|
|
139 else
|
|
|
140 {
|
|
|
141 if ( parent is pp.left )
|
|
|
142 pp.left = top;
|
|
|
143 else
|
|
|
144 pp.right = top;
|
|
|
145 }
|
|
|
146 parent.parent = top;
|
|
|
147 top.parent = pp;
|
|
|
148 if ( top !is n )
|
|
|
149 parent = top;
|
|
|
150 }
|
|
|
151 }
|
|
|
152
|
|
|
153 with ( n )
|
|
|
154 {
|
|
|
155 if ( v < value )
|
|
|
156 {
|
|
|
157 if ( left is null )
|
|
|
158 {
|
|
|
159 left = new node_t(v, n);
|
|
|
160 --balance;
|
|
|
161 if ( balance != 0 )
|
|
|
162 rebalance = true;
|
|
|
163 }
|
|
|
164 else if ( !insert(left, v) )
|
|
|
165 return false;
|
|
|
166 }
|
|
|
167 else if ( v > value )
|
|
|
168 {
|
|
|
169 if ( right is null )
|
|
|
170 {
|
|
|
171 right = new node_t(v, n);
|
|
|
172 ++balance;
|
|
|
173 if ( balance != 0 )
|
|
|
174 rebalance = true;
|
|
|
175 }
|
|
|
176 else if ( !insert(right, v) )
|
|
|
177 return false;
|
|
|
178 }
|
|
|
179 else
|
|
|
180 return false;
|
|
|
181
|
|
|
182 if ( rebalance && parent !is null )
|
|
|
183 {
|
|
|
184 assert(balance != 0);
|
|
|
185 if ( n is parent.left )
|
|
|
186 {
|
|
|
187 if ( parent.balance > 0 )
|
|
|
188 --parent.balance;
|
|
|
189 else if ( parent.balance == 0 ) {
|
|
|
190 --parent.balance;
|
|
|
191 return true;
|
|
|
192 }
|
|
|
193 else
|
|
|
194 {
|
|
|
195 // single rotation to the right
|
|
|
196 if ( balance < 0 )
|
|
|
197 {
|
|
|
198 parent.left = right;
|
|
|
199 if ( right !is null )
|
|
|
200 right.parent = parent;
|
|
|
201 right = parent;
|
|
|
202 updateParents;
|
|
|
203 }
|
|
|
204 // double rotation to the right
|
|
|
205 else
|
|
|
206 {
|
|
|
207 assert(right !is null);
|
|
|
208 node_t r = right;
|
|
|
209 parent.left = r.right;
|
|
|
210 if ( parent.left !is null )
|
|
|
211 parent.left.parent = parent;
|
|
|
212 right = r.left;
|
|
|
213 if ( right !is null )
|
|
|
214 right.parent = n;
|
|
|
215 r.right = parent;
|
|
|
216 r.left = n;
|
|
|
217 updateParents(r);
|
|
|
218 }
|
|
|
219 }
|
|
|
220 }
|
|
|
221 else
|
|
|
222 {
|
|
|
223 if ( parent.balance < 0 )
|
|
|
224 ++parent.balance;
|
|
|
225 else if ( parent.balance == 0 ) {
|
|
|
226 ++parent.balance;
|
|
|
227 return true;
|
|
|
228 }
|
|
|
229 else
|
|
|
230 {
|
|
|
231 // single rotation to the left
|
|
|
232 if ( balance > 0 )
|
|
|
233 {
|
|
|
234 parent.right = left;
|
|
|
235 if ( left !is null )
|
|
|
236 left.parent = parent;
|
|
|
237 left = parent;
|
|
|
238 updateParents;
|
|
|
239 }
|
|
|
240 // double rotation to the left
|
|
|
241 else
|
|
|
242 {
|
|
|
243 assert(left !is null);
|
|
|
244 node_t l = left;
|
|
|
245 parent.right = l.left;
|
|
|
246 if ( parent.right !is null )
|
|
|
247 parent.right.parent = parent;
|
|
|
248 left = l.right;
|
|
|
249 if ( left !is null )
|
|
|
250 left.parent = n;
|
|
|
251
|
|
|
252 l.left = parent;
|
|
|
253 l.right = n;
|
|
|
254 updateParents(l);
|
|
|
255 }
|
|
|
256 }
|
|
|
257 }
|
|
|
258 }
|
|
|
259 rebalance = false;
|
|
|
260 return true;
|
|
|
261 }
|
|
|
262 }
|
|
|
263 }
|
|
|
264
|
|
|
265 class AVLNode(T)
|
|
|
266 {
|
|
|
267 alias AVLNode!(T) node_t;
|
|
|
268 node_t parent, left, right;
|
|
|
269 byte balance;
|
|
|
270
|
|
|
271 T value;
|
|
|
272
|
|
|
273 this(T v, node_t p = null)
|
|
|
274 {
|
|
|
275 value = v;
|
|
|
276 parent = p;
|
|
|
277 }
|
|
|
278
|
|
|
279 void traverseDepthLeft(RT)(bool delegate(RT v) proc)
|
|
|
280 {
|
|
|
281 if ( left !is null )
|
|
|
282 left.traverseDepthLeft(proc);
|
|
|
283
|
|
|
284 static if ( is(RT == AVLNode!(T)) )
|
|
|
285 {
|
|
|
286 if ( !proc(this) )
|
|
|
287 return;
|
|
|
288 }
|
|
|
289 static if ( is(RT == T) )
|
|
|
290 {
|
|
|
291 if ( !proc(value) )
|
|
|
292 return;
|
|
|
293 }
|
|
|
294 static if ( !is(RT == AVLNode!(T)) && !is(RT == T) )
|
|
|
295 static assert(0, "invalid result type for tree traversal");
|
|
|
296
|
|
|
297 if ( right !is null )
|
|
|
298 right.traverseDepthLeft(proc);
|
|
|
299 }
|
|
|
300
|
|
|
301 bool findNext(RT)(inout RT res)
|
|
|
302 {
|
|
|
303 node_t n;
|
|
|
304 if ( right is null )
|
|
|
305 {
|
|
|
306 bool found=false;
|
|
|
307 for ( n = this; n.parent !is null; n = n.parent )
|
|
|
308 {
|
|
|
309 if ( n.parent.left is n )
|
|
|
310 {
|
|
|
311 static if ( is(T : Object) )
|
|
|
312 assert(n.parent.value > n.value, "\n"~n.parent.value.toString~" parent of "~n.value.toString~"\n");
|
|
|
313 assert(n.parent.value > n.value);
|
|
|
314 n = n.parent;
|
|
|
315 found = true;
|
|
|
316 break;
|
|
|
317 }
|
|
|
318 assert(n.parent.value <= n.value);
|
|
|
319 }
|
|
|
320 if ( !found )
|
|
|
321 return false;
|
|
|
322 }
|
|
|
323 else
|
|
|
324 {
|
|
|
325 assert(right.value >= value);
|
|
|
326 n = right;
|
|
|
327 while ( n.left !is null )
|
|
|
328 {
|
|
|
329 static if ( is(T : Object) )
|
|
|
330 assert(n.left.value < n.value, "\n"~n.left.value.toString~"\tleft of\t"~n.value.toString~"\n");
|
|
|
331 assert(n.left.value < n.value);
|
|
|
332 n = n.left;
|
|
|
333 }
|
|
|
334 }
|
|
|
335
|
|
|
336 static if ( is(RT == AVLNode!(T)) )
|
|
|
337 res = n;
|
|
|
338 static if ( is(RT == T) )
|
|
|
339 res = n.value;
|
|
|
340 static if ( !is(RT == AVLNode!(T)) && !is(RT == T) )
|
|
|
341 static assert(0, "invalid result type for next node search");
|
|
|
342 return true;
|
|
|
343 }
|
|
|
344
|
|
|
345 bool findPrev(RT)(inout RT res)
|
|
|
346 {
|
|
|
347 node_t n;
|
|
|
348 if ( left is null )
|
|
|
349 {
|
|
|
350 bool found=false;
|
|
|
351 for ( n = this; n.parent !is null; n = n.parent )
|
|
|
352 {
|
|
|
353 if ( n.parent.right is n )
|
|
|
354 {
|
|
|
355 static if ( is(T : Object) )
|
|
|
356 assert(n.parent.value > n.value, "\n"~n.parent.value.toString~" parent of "~n.value.toString~"\n");
|
|
|
357 assert(n.parent.value <= n.value);
|
|
|
358 n = n.parent;
|
|
|
359 found = true;
|
|
|
360 break;
|
|
|
361 }
|
|
|
362 assert(n.parent.value <= n.value);
|
|
|
363 }
|
|
|
364 if ( !found )
|
|
|
365 return false;
|
|
|
366 }
|
|
|
367 else
|
|
|
368 {
|
|
|
369 assert(left.value < value);
|
|
|
370 n = left;
|
|
|
371 while ( n.right !is null )
|
|
|
372 {
|
|
|
373 static if ( is(T : Object) )
|
|
|
374 assert(n.right.value < n.value, "\n"~n.right.value.toString~"\tleft of\t"~n.value.toString~"\n");
|
|
|
375 assert(n.right.value < n.value);
|
|
|
376 n = n.right;
|
|
|
377 }
|
|
|
378 }
|
|
|
379
|
|
|
380 static if ( is(RT == AVLNode!(T)) )
|
|
|
381 res = n;
|
|
|
382 static if ( is(RT == T) )
|
|
|
383 res = n.value;
|
|
|
384 static if ( !is(RT == AVLNode!(T)) && !is(RT == T) )
|
|
|
385 static assert(0, "invalid result type for prev node search");
|
|
|
386 return true;
|
|
|
387 }
|
|
|
388
|
|
|
389 bool find(VT,RT)(VT v, inout RT res)
|
|
|
390 {
|
|
|
391 bool suc;
|
|
|
392 if ( value > v )
|
|
|
393 {
|
|
|
394 if ( left !is null )
|
|
|
395 return left.find(v, res);
|
|
|
396 }
|
|
|
397 else if ( value < v )
|
|
|
398 {
|
|
|
399 if ( right !is null )
|
|
|
400 return right.find(v, res);
|
|
|
401 }
|
|
|
402 else
|
|
|
403 suc = true;
|
|
|
404 static if ( is(RT == AVLNode!(T)) )
|
|
|
405 res = this;
|
|
|
406 static if ( is(RT == T) )
|
|
|
407 res = value;
|
|
|
408 static if ( !is(RT == AVLNode!(T)) && !is(RT == T) )
|
|
|
409 static assert(0, "invalid result type for tree search");
|
|
|
410 return suc;
|
|
|
411 }
|
|
|
412 }
|
|
|
413
|
|
|
414 unittest
|
|
|
415 {
|
|
|
416 AVLTree!(int) tree = new AVLTree!(int);
|
|
|
417 for ( int i = 0; i < 100; ++i )
|
|
|
418 tree.insert(i);
|
|
|
419
|
|
|
420 bool checkOrder(AVLNode!(int) n)
|
|
|
421 {
|
|
|
422 if ( n.left !is null ) {
|
|
|
423 assert(n.left.parent is n);
|
|
|
424 assert(n.left.value < n.value);
|
|
|
425 }
|
|
|
426 if ( n.right !is null ) {
|
|
|
427 assert(n.right.parent is n);
|
|
|
428 assert(n.right.value >= n.value);
|
|
|
429 }
|
|
|
430 return true;
|
|
|
431 }
|
|
|
432
|
|
|
433 tree.traverseDepthLeft(&checkOrder);
|
|
|
434
|
|
|
435 // check next
|
|
|
436 for ( int i = 0; i < 99; ++i )
|
|
|
437 {
|
|
|
438 AVLNode!(int) n;
|
|
|
439 assert(tree.find(i, n));
|
|
|
440 assert(n.value == i);
|
|
|
441 assert(n.findNext(n));
|
|
|
442 assert(n.value == i+1, .toString(i+1)~" expected, "~.toString(n.value)~" found");
|
|
|
443 }
|
|
|
444
|
|
|
445 tree = new AVLTree!(int);
|
|
|
446 for ( int i = 99; i >= 0; --i )
|
|
|
447 tree.insert(i);
|
|
|
448 tree.traverseDepthLeft(&checkOrder);
|
|
|
449
|
|
|
450 // check next
|
|
|
451 for ( int i = 0; i < 99; ++i )
|
|
|
452 {
|
|
|
453 AVLNode!(int) n;
|
|
|
454 assert(tree.find(i, n));
|
|
|
455 assert(n.value == i);
|
|
|
456 assert(n.findNext(n));
|
|
|
457 assert(n.value == i+1, .toString(i+1)~" expected, "~.toString(n.value)~" found");
|
|
|
458 }
|
|
|
459 }
|
