Mercurial > projects > ddbg_continued

comparison src/container.d @ 1:4a9dcbd9e54f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
-files of 0.13 beta -fixes so that it now compiles with the current dmd version
author marton@basel.hu
date Tue, 05 Apr 2011 20:44:01 +0200
parents
children
comparison
equal deleted inserted replaced
0:586e4a649642 1:4a9dcbd9e54f
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 }