Mercurial > projects > hoofbaby

annotate src/impl/hoofbaby/util/redblack.d @ 0:3425707ddbf6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial import (hopefully this mercurial stuff works...)
author fraserofthenight
date Mon, 06 Jul 2009 08:06:28 -0700
parents
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
1 /*******************************************************************************
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
2
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
3 (this module taken from tango.util.container.RedBlack, since that
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
4 module is package-protected)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
5
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
6 copyright: Copyright (c) 2008 Kris Bell. All rights reserved
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
7
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
8 license: BSD style: $(LICENSE)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
9
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
10 version: Apr 2008: Initial release
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
11
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
12 authors: Kris, tsalm
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
13
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
14 Since: 0.99.7
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
15
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
16 Based upon Doug Lea's Java collection package
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
17
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
18 *******************************************************************************/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
19
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
20 module candy.util.redblack;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
21
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
22 template Compare (V) { alias int function (ref V a, ref V b) Compare; }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
23
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
24 private typedef int AttributeDummy;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
25
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
26 /*******************************************************************************
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
27
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
28 RedBlack implements basic capabilities of Red-Black trees,
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
29 an efficient kind of balanced binary tree. The particular
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
30 algorithms used are adaptations of those in Corman,
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
31 Lieserson, and Rivest's <EM>Introduction to Algorithms</EM>.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
32 This class was inspired by (and code cross-checked with) a
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
33 similar class by Chuck McManis. The implementations of
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
34 rebalancings during insertion and deletion are
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
35 a little trickier than those versions since they
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
36 don't swap Cell contents or use special dummy nilnodes.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
37
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
38 Doug Lea
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
39
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
40 *******************************************************************************/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
41
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
42 struct RedBlack (V, A = AttributeDummy)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
43 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
44 alias RedBlack!(V, A) Type;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
45 alias Type *Ref;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
46
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
47 enum : bool {RED = false, BLACK = true}
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
48
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
49 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
50 * Pointer to left child
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
51 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
52
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
53 package Ref left;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
54
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
55 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
56 * Pointer to right child
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
57 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
58
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
59 package Ref right;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
60
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
61 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
62 * Pointer to parent (null if root)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
63 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
64
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
65 package Ref parent;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
66
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
67 package V value;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
68
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
69 static if (!is(typeof(A) == AttributeDummy))
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
70 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
71 A attribute;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
72 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
73
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
74 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
75 * The node color (RED, BLACK)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
76 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
77
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
78 package bool color;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
79
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
80 static if (!is(typeof(A) == AttributeDummy))
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
81 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
82 final Ref set (V v, A a)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
83 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
84 attribute = a;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
85 return set (v);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
86 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
87 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
88
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
89 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
90 * Make a new Cell with given value, null links, and BLACK color.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
91 * Normally only called to establish a new root.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
92 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
93
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
94 final Ref set (V v)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
95 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
96 value = v;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
97 left = null;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
98 right = null;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
99 parent = null;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
100 color = BLACK;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
101 return this;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
102 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
103
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
104 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
105 * Return a new Ref with same value and color as self,
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
106 * but with null links. (Since it is never OK to have
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
107 * multiple identical links in a RB tree.)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
108 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
109
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
110 protected Ref dup (Ref delegate() alloc)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
111 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
112 static if (is(typeof(A) == AttributeDummy))
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
113 auto t = alloc().set (value);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
114 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
115 auto t = alloc().set (value, attribute);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
116
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
117 t.color = color;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
118 return t;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
119 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
120
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
121
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
122 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
123 * See_Also: tango.util.collection.model.View.View.checkImplementation.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
124 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
125 public void checkImplementation ()
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
126 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
127
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
128 // It's too hard to check the property that every simple
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
129 // path from node to leaf has same number of black nodes.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
130 // So restrict to the following
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
131
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
132 assert(parent is null ||
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
133 this is parent.left ||
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
134 this is parent.right);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
135
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
136 assert(left is null ||
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
137 this is left.parent);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
138
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
139 assert(right is null ||
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
140 this is right.parent);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
141
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
142 assert(color is BLACK ||
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
143 (colorOf(left) is BLACK) && (colorOf(right) is BLACK));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
144
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
145 if (left !is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
146 left.checkImplementation();
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
147 if (right !is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
148 right.checkImplementation();
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
149 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
150
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
151 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
152 * Return the minimum value of the current (sub)tree
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
153 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
154
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
155 Ref leftmost ()
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
156 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
157 auto p = this;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
158 for ( ; p.left; p = p.left) {}
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
159 return p;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
160 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
161
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
162 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
163 * Return the maximum value of the current (sub)tree
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
164 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
165 Ref rightmost ()
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
166 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
167 auto p = this;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
168 for ( ; p.right; p = p.right) {}
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
169 return p;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
170 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
171
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
172 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
173 * Return the root (parentless node) of the tree
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
174 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
175 Ref root ()
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
176 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
177 auto p = this;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
178 for ( ; p.parent; p = p.parent) {}
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
179 return p;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
180 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
181
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
182 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
183 * Return true if node is a root (i.e., has a null parent)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
184 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
185
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
186 bool isRoot ()
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
187 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
188 return parent is null;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
189 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
190
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
191
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
192 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
193 * Return the inorder successor, or null if no such
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
194 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
195
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
196 Ref successor ()
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
197 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
198 if (right)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
199 return right.leftmost;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
200
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
201 auto p = parent;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
202 auto ch = this;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
203 while (p && ch is p.right)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
204 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
205 ch = p;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
206 p = p.parent;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
207 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
208 return p;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
209 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
210
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
211 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
212 * Return the inorder predecessor, or null if no such
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
213 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
214
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
215 Ref predecessor ()
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
216 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
217 if (left)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
218 return left.rightmost;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
219
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
220 auto p = parent;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
221 auto ch = this;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
222 while (p && ch is p.left)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
223 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
224 ch = p;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
225 p = p.parent;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
226 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
227 return p;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
228 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
229
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
230 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
231 * Return the number of nodes in the subtree
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
232 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
233 int size ()
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
234 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
235 auto c = 1;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
236 if (left)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
237 c += left.size;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
238 if (right)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
239 c += right.size;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
240 return c;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
241 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
242
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
243
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
244 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
245 * Return node of current subtree containing value as value(),
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
246 * if it exists, else null.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
247 * Uses Comparator cmp to find and to check equality.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
248 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
249
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
250 Ref find (V value, Compare!(V) cmp)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
251 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
252 auto t = this;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
253 for (;;)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
254 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
255 auto diff = cmp (value, t.value);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
256 if (diff is 0)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
257 return t;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
258 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
259 if (diff < 0)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
260 t = t.left;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
261 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
262 t = t.right;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
263 if (t is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
264 break;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
265 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
266 return null;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
267 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
268
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
269
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
270 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
271 * Return node of subtree matching "value"
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
272 * or, if none found, the one just after or before
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
273 * if it doesn't exist, return null
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
274 * Uses Comparator cmp to find and to check equality.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
275 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
276 Ref findFirst (V value, Compare!(V) cmp, bool after = true)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
277 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
278 auto t = this;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
279 auto tLower = this;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
280 auto tGreater = this;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
281
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
282 for (;;)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
283 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
284 auto diff = cmp (value, t.value);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
285 if (diff is 0)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
286 return t;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
287 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
288 if (diff < 0)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
289 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
290 tGreater = t;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
291 t = t.left;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
292 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
293 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
294 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
295 tLower = t;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
296 t = t.right;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
297 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
298 if (t is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
299 break;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
300 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
301
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
302 if (after)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
303 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
304 if (cmp (value, tGreater.value) <= 0)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
305 if (cmp (value, tGreater.value) < 0)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
306 return tGreater;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
307 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
308 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
309 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
310 if (cmp (value, tLower.value) >= 0)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
311 if (cmp (value, tLower.value) > 0)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
312 return tLower;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
313 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
314
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
315 return null;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
316 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
317
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
318 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
319 * Return number of nodes of current subtree containing value.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
320 * Uses Comparator cmp to find and to check equality.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
321 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
322 int count (V value, Compare!(V) cmp)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
323 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
324 auto c = 0;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
325 auto t = this;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
326 while (t)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
327 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
328 int diff = cmp (value, t.value);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
329 if (diff is 0)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
330 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
331 ++c;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
332 if (t.left is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
333 t = t.right;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
334 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
335 if (t.right is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
336 t = t.left;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
337 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
338 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
339 c += t.right.count (value, cmp);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
340 t = t.left;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
341 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
342 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
343 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
344 if (diff < 0)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
345 t = t.left;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
346 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
347 t = t.right;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
348 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
349 return c;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
350 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
351
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
352 static if (!is(typeof(A) == AttributeDummy))
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
353 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
354 Ref findAttribute (A attribute, Compare!(A) cmp)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
355 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
356 auto t = this;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
357
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
358 while (t)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
359 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
360 if (t.attribute == attribute)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
361 return t;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
362 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
363 if (t.right is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
364 t = t.left;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
365 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
366 if (t.left is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
367 t = t.right;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
368 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
369 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
370 auto p = t.left.findAttribute (attribute, cmp);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
371
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
372 if (p !is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
373 return p;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
374 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
375 t = t.right;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
376 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
377 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
378 return null; // not reached
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
379 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
380
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
381 int countAttribute (A attrib, Compare!(A) cmp)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
382 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
383 int c = 0;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
384 auto t = this;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
385
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
386 while (t)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
387 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
388 if (t.attribute == attribute)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
389 ++c;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
390
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
391 if (t.right is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
392 t = t.left;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
393 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
394 if (t.left is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
395 t = t.right;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
396 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
397 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
398 c += t.left.countAttribute (attribute, cmp);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
399 t = t.right;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
400 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
401 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
402 return c;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
403 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
404
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
405 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
406 * find and return a cell holding (key, element), or null if no such
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
407 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
408 Ref find (V value, A attribute, Compare!(V) cmp)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
409 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
410 auto t = this;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
411
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
412 for (;;)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
413 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
414 int diff = cmp (value, t.value);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
415 if (diff is 0 && t.attribute == attribute)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
416 return t;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
417 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
418 if (diff <= 0)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
419 t = t.left;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
420 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
421 t = t.right;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
422
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
423 if (t is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
424 break;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
425 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
426 return null;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
427 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
428
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
429 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
430
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
431
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
432
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
433 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
434 * Return a new subtree containing each value of current subtree
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
435 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
436
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
437 Ref copyTree (Ref delegate() alloc)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
438 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
439 auto t = dup (alloc);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
440
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
441 if (left)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
442 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
443 t.left = left.copyTree (alloc);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
444 t.left.parent = t;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
445 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
446
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
447 if (right)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
448 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
449 t.right = right.copyTree (alloc);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
450 t.right.parent = t;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
451 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
452
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
453 return t;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
454 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
455
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
456
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
457 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
458 * There's no generic value insertion. Instead find the
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
459 * place you want to add a node and then invoke insertLeft
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
460 * or insertRight.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
461 * <P>
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
462 * Insert Cell as the left child of current node, and then
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
463 * rebalance the tree it is in.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
464 * @param Cell the Cell to add
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
465 * @param root, the root of the current tree
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
466 * Returns: the new root of the current tree. (Rebalancing
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
467 * can change the root!)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
468 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
469
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
470
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
471 Ref insertLeft (Ref cell, Ref root)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
472 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
473 left = cell;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
474 cell.parent = this;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
475 return cell.fixAfterInsertion (root);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
476 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
477
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
478 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
479 * Insert Cell as the right child of current node, and then
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
480 * rebalance the tree it is in.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
481 * @param Cell the Cell to add
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
482 * @param root, the root of the current tree
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
483 * Returns: the new root of the current tree. (Rebalancing
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
484 * can change the root!)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
485 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
486
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
487 Ref insertRight (Ref cell, Ref root)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
488 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
489 right = cell;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
490 cell.parent = this;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
491 return cell.fixAfterInsertion (root);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
492 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
493
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
494
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
495 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
496 * Delete the current node, and then rebalance the tree it is in
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
497 * @param root the root of the current tree
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
498 * Returns: the new root of the current tree. (Rebalancing
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
499 * can change the root!)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
500 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
501
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
502
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
503 Ref remove (Ref root)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
504 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
505 // handle case where we are only node
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
506 if (left is null && right is null && parent is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
507 return null;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
508
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
509 // if strictly internal, swap places with a successor
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
510 if (left && right)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
511 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
512 auto s = successor;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
513
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
514 // To work nicely with arbitrary subclasses of Ref, we don't want to
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
515 // just copy successor's fields. since we don't know what
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
516 // they are. Instead we swap positions _in the tree.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
517 root = swapPosition (this, s, root);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
518 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
519
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
520 // Start fixup at replacement node (normally a child).
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
521 // But if no children, fake it by using self
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
522
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
523 if (left is null && right is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
524 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
525 if (color is BLACK)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
526 root = this.fixAfterDeletion (root);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
527
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
528 // Unlink (Couldn't before since fixAfterDeletion needs parent ptr)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
529 if (parent)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
530 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
531 if (this is parent.left)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
532 parent.left = null;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
533 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
534 if (this is parent.right)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
535 parent.right = null;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
536 parent = null;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
537 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
538 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
539 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
540 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
541 auto replacement = left;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
542 if (replacement is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
543 replacement = right;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
544
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
545 // link replacement to parent
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
546 replacement.parent = parent;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
547
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
548 if (parent is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
549 root = replacement;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
550 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
551 if (this is parent.left)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
552 parent.left = replacement;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
553 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
554 parent.right = replacement;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
555
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
556 left = null;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
557 right = null;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
558 parent = null;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
559
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
560 // fix replacement
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
561 if (color is BLACK)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
562 root = replacement.fixAfterDeletion (root);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
563 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
564 return root;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
565 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
566
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
567 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
568 * Swap the linkages of two nodes in a tree.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
569 * Return new root, in case it changed.
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
570 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
571
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
572 static Ref swapPosition (Ref x, Ref y, Ref root)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
573 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
574 /* Too messy. TODO: find sequence of assigments that are always OK */
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
575
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
576 auto px = x.parent;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
577 bool xpl = px !is null && x is px.left;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
578 auto lx = x.left;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
579 auto rx = x.right;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
580
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
581 auto py = y.parent;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
582 bool ypl = py !is null && y is py.left;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
583 auto ly = y.left;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
584 auto ry = y.right;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
585
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
586 if (x is py)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
587 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
588 y.parent = px;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
589 if (px !is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
590 if (xpl)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
591 px.left = y;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
592 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
593 px.right = y;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
594
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
595 x.parent = y;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
596 if (ypl)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
597 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
598 y.left = x;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
599 y.right = rx;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
600 if (rx !is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
601 rx.parent = y;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
602 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
603 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
604 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
605 y.right = x;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
606 y.left = lx;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
607 if (lx !is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
608 lx.parent = y;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
609 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
610
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
611 x.left = ly;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
612 if (ly !is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
613 ly.parent = x;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
614
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
615 x.right = ry;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
616 if (ry !is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
617 ry.parent = x;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
618 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
619 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
620 if (y is px)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
621 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
622 x.parent = py;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
623 if (py !is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
624 if (ypl)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
625 py.left = x;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
626 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
627 py.right = x;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
628
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
629 y.parent = x;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
630 if (xpl)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
631 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
632 x.left = y;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
633 x.right = ry;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
634 if (ry !is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
635 ry.parent = x;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
636 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
637 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
638 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
639 x.right = y;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
640 x.left = ly;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
641 if (ly !is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
642 ly.parent = x;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
643 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
644
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
645 y.left = lx;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
646 if (lx !is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
647 lx.parent = y;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
648
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
649 y.right = rx;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
650 if (rx !is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
651 rx.parent = y;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
652 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
653 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
654 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
655 x.parent = py;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
656 if (py !is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
657 if (ypl)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
658 py.left = x;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
659 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
660 py.right = x;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
661
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
662 x.left = ly;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
663 if (ly !is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
664 ly.parent = x;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
665
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
666 x.right = ry;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
667 if (ry !is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
668 ry.parent = x;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
669
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
670 y.parent = px;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
671 if (px !is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
672 if (xpl)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
673 px.left = y;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
674 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
675 px.right = y;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
676
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
677 y.left = lx;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
678 if (lx !is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
679 lx.parent = y;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
680
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
681 y.right = rx;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
682 if (rx !is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
683 rx.parent = y;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
684 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
685
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
686 bool c = x.color;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
687 x.color = y.color;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
688 y.color = c;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
689
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
690 if (root is x)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
691 root = y;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
692 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
693 if (root is y)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
694 root = x;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
695 return root;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
696 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
697
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
698
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
699
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
700 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
701 * Return color of node p, or BLACK if p is null
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
702 * (In the CLR version, they use
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
703 * a special dummy `nil' node for such purposes, but that doesn't
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
704 * work well here, since it could lead to creating one such special
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
705 * node per real node.)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
706 *
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
707 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
708
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
709 static bool colorOf (Ref p)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
710 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
711 return (p is null) ? BLACK : p.color;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
712 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
713
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
714 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
715 * return parent of node p, or null if p is null
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
716 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
717 static Ref parentOf (Ref p)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
718 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
719 return (p is null) ? null : p.parent;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
720 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
721
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
722 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
723 * Set the color of node p, or do nothing if p is null
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
724 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
725
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
726 static void setColor (Ref p, bool c)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
727 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
728 if (p !is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
729 p.color = c;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
730 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
731
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
732 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
733 * return left child of node p, or null if p is null
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
734 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
735
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
736 static Ref leftOf (Ref p)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
737 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
738 return (p is null) ? null : p.left;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
739 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
740
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
741 /**
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
742 * return right child of node p, or null if p is null
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
743 **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
744
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
745 static Ref rightOf (Ref p)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
746 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
747 return (p is null) ? null : p.right;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
748 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
749
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
750
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
751 /** From CLR **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
752 package Ref rotateLeft (Ref root)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
753 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
754 auto r = right;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
755 right = r.left;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
756
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
757 if (r.left)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
758 r.left.parent = this;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
759
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
760 r.parent = parent;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
761 if (parent is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
762 root = r;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
763 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
764 if (parent.left is this)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
765 parent.left = r;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
766 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
767 parent.right = r;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
768
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
769 r.left = this;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
770 parent = r;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
771 return root;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
772 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
773
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
774 /** From CLR **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
775 package Ref rotateRight (Ref root)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
776 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
777 auto l = left;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
778 left = l.right;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
779
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
780 if (l.right !is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
781 l.right.parent = this;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
782
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
783 l.parent = parent;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
784 if (parent is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
785 root = l;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
786 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
787 if (parent.right is this)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
788 parent.right = l;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
789 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
790 parent.left = l;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
791
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
792 l.right = this;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
793 parent = l;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
794 return root;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
795 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
796
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
797
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
798 /** From CLR **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
799 package Ref fixAfterInsertion (Ref root)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
800 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
801 color = RED;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
802 auto x = this;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
803
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
804 while (x && x !is root && x.parent.color is RED)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
805 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
806 if (parentOf(x) is leftOf(parentOf(parentOf(x))))
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
807 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
808 auto y = rightOf(parentOf(parentOf(x)));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
809 if (colorOf(y) is RED)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
810 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
811 setColor(parentOf(x), BLACK);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
812 setColor(y, BLACK);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
813 setColor(parentOf(parentOf(x)), RED);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
814 x = parentOf(parentOf(x));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
815 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
816 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
817 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
818 if (x is rightOf(parentOf(x)))
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
819 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
820 x = parentOf(x);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
821 root = x.rotateLeft(root);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
822 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
823
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
824 setColor(parentOf(x), BLACK);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
825 setColor(parentOf(parentOf(x)), RED);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
826 if (parentOf(parentOf(x)) !is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
827 root = parentOf(parentOf(x)).rotateRight(root);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
828 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
829 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
830 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
831 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
832 auto y = leftOf(parentOf(parentOf(x)));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
833 if (colorOf(y) is RED)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
834 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
835 setColor(parentOf(x), BLACK);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
836 setColor(y, BLACK);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
837 setColor(parentOf(parentOf(x)), RED);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
838 x = parentOf(parentOf(x));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
839 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
840 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
841 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
842 if (x is leftOf(parentOf(x)))
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
843 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
844 x = parentOf(x);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
845 root = x.rotateRight(root);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
846 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
847
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
848 setColor(parentOf(x), BLACK);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
849 setColor(parentOf(parentOf(x)), RED);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
850 if (parentOf(parentOf(x)) !is null)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
851 root = parentOf(parentOf(x)).rotateLeft(root);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
852 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
853 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
854 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
855 root.color = BLACK;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
856 return root;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
857 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
858
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
859
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
860
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
861 /** From CLR **/
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
862 package Ref fixAfterDeletion(Ref root)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
863 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
864 auto x = this;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
865 while (x !is root && colorOf(x) is BLACK)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
866 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
867 if (x is leftOf(parentOf(x)))
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
868 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
869 auto sib = rightOf(parentOf(x));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
870 if (colorOf(sib) is RED)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
871 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
872 setColor(sib, BLACK);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
873 setColor(parentOf(x), RED);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
874 root = parentOf(x).rotateLeft(root);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
875 sib = rightOf(parentOf(x));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
876 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
877 if (colorOf(leftOf(sib)) is BLACK && colorOf(rightOf(sib)) is BLACK)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
878 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
879 setColor(sib, RED);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
880 x = parentOf(x);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
881 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
882 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
883 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
884 if (colorOf(rightOf(sib)) is BLACK)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
885 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
886 setColor(leftOf(sib), BLACK);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
887 setColor(sib, RED);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
888 root = sib.rotateRight(root);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
889 sib = rightOf(parentOf(x));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
890 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
891
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
892 setColor(sib, colorOf(parentOf(x)));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
893 setColor(parentOf(x), BLACK);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
894 setColor(rightOf(sib), BLACK);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
895 root = parentOf(x).rotateLeft(root);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
896 x = root;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
897 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
898 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
899 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
900 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
901 auto sib = leftOf(parentOf(x));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
902 if (colorOf(sib) is RED)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
903 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
904 setColor(sib, BLACK);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
905 setColor(parentOf(x), RED);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
906 root = parentOf(x).rotateRight(root);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
907 sib = leftOf(parentOf(x));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
908 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
909
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
910 if (colorOf(rightOf(sib)) is BLACK && colorOf(leftOf(sib)) is BLACK)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
911 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
912 setColor(sib, RED);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
913 x = parentOf(x);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
914 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
915 else
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
916 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
917 if (colorOf(leftOf(sib)) is BLACK)
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
918 {
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
919 setColor(rightOf(sib), BLACK);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
920 setColor(sib, RED);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
921 root = sib.rotateLeft(root);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
922 sib = leftOf(parentOf(x));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
923 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
924
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
925 setColor(sib, colorOf(parentOf(x)));
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
926 setColor(parentOf(x), BLACK);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
927 setColor(leftOf(sib), BLACK);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
928 root = parentOf(x).rotateRight(root);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
929 x = root;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
930 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
931 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
932 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
933
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
934 setColor(x, BLACK);
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
935 return root;
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
936 }
3425707ddbf6 Initial import (hopefully this mercurial stuff works...)
fraserofthenight
parents:
diff changeset
937 }