4 void Clust::InsertMetric(unsigned uIndex1, unsigned uIndex2, float dMetric)
\r
6 RBInsert(uIndex1, uIndex2, dMetric);
\r
9 void Clust::DeleteMetric(unsigned uIndex)
\r
11 for (unsigned uNodeIndex = GetFirstCluster(); uNodeIndex != uInsane;
\r
12 uNodeIndex = GetNextCluster(uNodeIndex))
\r
14 if (uIndex == uNodeIndex)
\r
16 DeleteMetric(uIndex, uNodeIndex);
\r
20 void Clust::InitMetric(unsigned uMaxNodeIndex)
\r
22 m_uRBNodeCount = m_uTriangularMatrixSize;
\r
23 m_RBParent = new unsigned[m_uRBNodeCount];
\r
24 m_RBLeft = new unsigned[m_uRBNodeCount];
\r
25 m_RBRight = new unsigned[m_uRBNodeCount];
\r
26 m_RBi = new ushort[m_uRBNodeCount];
\r
27 m_RBj = new ushort[m_uRBNodeCount];
\r
28 m_RBMetric = new float[m_uRBNodeCount];
\r
29 m_RBColor = new bool[m_uRBNodeCount];
\r
34 // Initialize fields to invalid values so we have a chance
\r
35 // catch attempts to use them if they're not properly set.
\r
36 unsigned InvalidNode = m_uRBNodeCount + 1;
\r
37 for (unsigned Node = 0; Node < m_uRBNodeCount; ++Node)
\r
39 m_RBParent[Node] = InvalidNode;
\r
40 m_RBLeft[Node] = InvalidNode;
\r
41 m_RBRight[Node] = InvalidNode;
\r
42 m_RBi[Node] = InvalidNode;
\r
43 m_RBj[Node] = InvalidNode;
\r
49 void Clust::ListMetric() const
\r
51 Log("Red-black tree root=%u\n", m_RBRoot);
\r
53 Log(" Node Parent Left Right Color i j Metric\n");
\r
54 Log("----- ------ ----- ----- ----- ----- ----- ------\n");
\r
56 if (RB_NIL == m_RBRoot)
\r
60 unsigned Start = RBMin(m_RBRoot);
\r
61 for (unsigned Node = Start; RB_NIL != Node; Node = RBNext(Node))
\r
65 if (RB_NIL != m_RBParent[Node])
\r
66 Log(" %6u", m_RBParent[Node]);
\r
70 if (RB_NIL != m_RBLeft[Node])
\r
71 Log(" %5u", m_RBLeft[Node]);
\r
75 if (RB_NIL != m_RBRight[Node])
\r
76 Log(" %5u", m_RBRight[Node]);
\r
80 Log(" %s %5u %5u %g\n",
\r
81 m_RBColor[Node] ? " Red" : "Black",
\r
86 if (++Count > m_uRBNodeCount)
\r
88 Log(" ** LOOP ** \n");
\r
94 // If there is a left subtree, predecessor is the
\r
95 // largest key found under the left branch. Otherwise,
\r
96 // is first node in path to root that is a right child.
\r
97 unsigned Clust::RBPrev(unsigned Node) const
\r
99 assert(Node < m_uRBNodeCount);
\r
101 unsigned Left = m_RBLeft[Node];
\r
102 if (RB_NIL != Left)
\r
103 return RBMax(Left);
\r
107 unsigned Parent = m_RBParent[Node];
\r
108 if (RB_NIL == Parent)
\r
110 if (m_RBRight[Parent] == Node)
\r
116 // If there is a right subtree, sucessor is the
\r
117 // smallest key found under the right branch. Otherwise,
\r
118 // is first node in path to root that is a left child.
\r
119 unsigned Clust::RBNext(unsigned Node) const
\r
121 if (Node >= m_uRBNodeCount)
\r
122 Quit("RBNext(%u)", Node);
\r
123 assert(Node < m_uRBNodeCount);
\r
125 unsigned Right = m_RBRight[Node];
\r
126 if (RB_NIL != Right)
\r
127 return RBMin(Right);
\r
131 unsigned Parent = m_RBParent[Node];
\r
132 if (RB_NIL == Parent)
\r
134 if (m_RBLeft[Parent] == Node)
\r
140 // Minimum is in leftmost leaf
\r
141 unsigned Clust::RBMin(unsigned RBNode) const
\r
143 assert(RB_NIL != RBNode);
\r
146 unsigned Left = m_RBLeft[RBNode];
\r
147 if (RB_NIL == Left)
\r
153 // Maximum is in rightmost leaf
\r
154 unsigned Clust::RBMax(unsigned RBNode) const
\r
156 assert(RB_NIL != RBNode);
\r
159 unsigned Right = m_RBRight[RBNode];
\r
160 if (RB_NIL == Right)
\r
166 void Clust::DeleteMetric(unsigned uIndex1, unsigned uIndex2)
\r
168 unsigned RBNode = (unsigned) VectorIndex(uIndex1, uIndex2);
\r
172 void Clust::RBDelete(unsigned Node)
\r
176 //Log("@@ Before RBDelete(%u)\n", Node);
\r
180 unsigned Left = m_RBLeft[Node];
\r
181 unsigned Right = m_RBRight[Node];
\r
182 unsigned Parent = m_RBParent[Node];
\r
184 // If one or two nil children, splice out this node.
\r
185 if (RB_NIL == Left || RB_NIL == Right)
\r
187 // Log("@@ One child\n");
\r
188 // Child is non-NIL child, or NIL if none.
\r
189 unsigned Child = (Left != RB_NIL ? Left : Right);
\r
191 // Special case if root
\r
192 if (RB_NIL == Parent)
\r
194 assert(Node == m_RBRoot);
\r
196 if (RB_NIL != Child)
\r
197 m_RBParent[Child] = RB_NIL;
\r
202 // Update parent->child link
\r
203 if (m_RBLeft[Parent] == Node)
\r
204 m_RBLeft[Parent] = Child;
\r
207 assert(m_RBRight[Parent] == Node);
\r
208 m_RBRight[Parent] = Child;
\r
211 // Update child->parent link
\r
212 if (RB_NIL != Child)
\r
213 m_RBParent[Child] = Parent;
\r
216 //Log("@@ After RBDelete(%u)\n", Node);
\r
223 //Log("@@ RBDelete(%u) Tricky case\n", Node);
\r
226 // Trickier case, node has two children.
\r
227 assert(Left != RB_NIL && Right != RB_NIL);
\r
229 // We're going to splice out successor node from its
\r
230 // current position and insert it in place of node
\r
233 // Successor cannot be nil because there is a right child.
\r
234 unsigned Next = RBNext(Node);
\r
235 assert(Next != RB_NIL);
\r
237 // The successor of a node with two children is
\r
238 // guaranteed to have no more than one child.
\r
239 unsigned NextLeft = m_RBLeft[Next];
\r
240 unsigned NextRight = m_RBRight[Next];
\r
241 assert(RB_NIL == NextLeft || RB_NIL == NextRight);
\r
243 // Successor of node with two children cannot be the root.
\r
244 unsigned NextParent = m_RBParent[Next];
\r
245 assert(RB_NIL != NextParent);
\r
247 // Ugly special case if successor is right child
\r
251 //Log("@@ Before RBDelete(%u) (tricky next==right)\n", Node);
\r
254 m_RBParent[Next] = Parent;
\r
256 if (RB_NIL == Parent)
\r
259 m_RBParent[Next] = RB_NIL;
\r
263 if (m_RBLeft[Parent] == Node)
\r
264 m_RBLeft[Parent] = Next;
\r
267 assert(m_RBRight[Parent] == Node);
\r
268 m_RBRight[Parent] = Next;
\r
272 m_RBLeft[Next] = Left;
\r
274 if (RB_NIL != Left)
\r
275 m_RBParent[Left] = Next;
\r
278 //Log("@@ After RBDelete(%u) (tricky next==right)\n", Node);
\r
285 // Set NextChild either to the one child of successor, or nil.
\r
286 unsigned NextChild = (NextLeft != RB_NIL ? NextLeft : NextRight);
\r
288 // Splice successor from its current position
\r
289 if (m_RBLeft[NextParent] == Next)
\r
290 m_RBLeft[NextParent] = NextChild;
\r
293 assert(m_RBRight[NextParent] == Next);
\r
294 m_RBRight[NextParent] = NextChild;
\r
297 if (RB_NIL != NextChild)
\r
298 m_RBParent[NextChild] = NextParent;
\r
300 // Insert successor into position currently held by node
\r
302 if (RB_NIL == Parent)
\r
305 m_RBParent[Next] = RB_NIL;
\r
309 if (m_RBLeft[Parent] == Node)
\r
310 m_RBLeft[Parent] = Next;
\r
313 assert(m_RBRight[Parent] == Node);
\r
314 m_RBRight[Parent] = Next;
\r
318 m_RBLeft[Next] = Left;
\r
319 m_RBRight[Next] = Right;
\r
320 m_RBParent[Next] = Parent;
\r
322 m_RBParent[Left] = Next;
\r
323 m_RBParent[Right] = Next;
\r
326 //Log("@@ After RBDelete(%u)\n", Node);
\r
332 unsigned Clust::RBInsert(unsigned i, unsigned j, float fMetric)
\r
338 unsigned NewNode = VectorIndex(i, j);
\r
339 m_RBMetric[NewNode] = fMetric;
\r
340 m_RBi[NewNode] = i;
\r
341 m_RBj[NewNode] = j;
\r
343 // New node is always inserted as a leaf.
\r
344 // Proof that this is possible is found in algorithm
\r
345 // textbooks (I forget the argument).
\r
346 m_RBLeft[NewNode] = RB_NIL;
\r
347 m_RBRight[NewNode] = RB_NIL;
\r
349 unsigned NewParent = RB_NIL;
\r
350 unsigned Node = m_RBRoot;
\r
352 unsigned uCount = 0;
\r
353 while (RB_NIL != Node)
\r
356 if (fMetric < m_RBMetric[Node])
\r
357 Node = m_RBLeft[Node];
\r
359 Node = m_RBRight[Node];
\r
361 if (uCount > m_uRBNodeCount)
\r
362 Quit("Infinite loop in RBInsert");
\r
365 m_RBParent[NewNode] = NewParent;
\r
366 if (RB_NIL == NewParent)
\r
367 m_RBRoot = NewNode;
\r
370 if (fMetric < m_RBMetric[NewParent])
\r
371 m_RBLeft[NewParent] = NewNode;
\r
373 m_RBRight[NewParent] = NewNode;
\r
378 unsigned Next = RBNext(NewNode);
\r
379 if (Next != RB_NIL)
\r
380 assert(NewNode == RBPrev(Next));
\r
381 unsigned Prev = RBPrev(NewNode);
\r
382 if (Prev != RB_NIL)
\r
383 assert(NewNode == RBNext(Prev));
\r
390 void Clust::ValidateRBNode(unsigned Node, const char szMsg[]) const
\r
392 if (RB_NIL == Node)
\r
395 unsigned Parent = m_RBParent[Node];
\r
396 unsigned Left = m_RBLeft[Node];
\r
397 unsigned Right = m_RBRight[Node];
\r
399 unsigned Next = RBNext(Node);
\r
400 unsigned Prev = RBPrev(Node);
\r
402 if (RB_NIL != Next && RBPrev(Next) != Node)
\r
405 Quit("ValidateRB(%s) Node=%u Next=%u Prev(Next)=%u",
\r
406 szMsg, Node, Next, RBPrev(Next));
\r
409 if (RB_NIL != Prev && RBNext(Prev) != Node)
\r
412 Quit("ValidateRB(%s) Node=%u Prev=%u Next(Prev)=%u",
\r
413 szMsg, Node, Prev, RBNext(Prev));
\r
416 if (RB_NIL != Parent)
\r
418 if (m_RBLeft[Parent] != Node && m_RBRight[Parent] != Node)
\r
421 Quit("ValidateRB(%s): Parent %u not linked to child %u\n",
\r
422 szMsg, Parent, Node);
\r
426 if (RB_NIL != Left)
\r
428 if (m_RBParent[Left] != Node)
\r
431 Quit("ValidateRB(%s): Left child %u not linked to parent %u\n",
\r
432 szMsg, Left, Node);
\r
436 if (RB_NIL != Right)
\r
438 if (m_RBParent[Right] != Node)
\r
441 Quit("ValidateRB(%s): Right child %u not linked to parent %u\n",
\r
442 szMsg, Right, Node);
\r
446 ValidateRBNode(Left, szMsg);
\r
447 ValidateRBNode(Right, szMsg);
\r
450 void Clust::ValidateRB(const char szMsg[]) const
\r
452 if (RB_NIL == m_RBRoot)
\r
455 ValidateRBNode(m_RBRoot, szMsg);
\r
457 unsigned Node = RBMin(m_RBRoot);
\r
460 unsigned Next = RBNext(Node);
\r
461 if (RB_NIL == Next)
\r
463 if (m_RBMetric[Node] > m_RBMetric[Next])
\r
466 Quit("ValidateRBNode(%s): metric out of order %u=%g %u=%g",
\r
467 szMsg, Node, m_RBMetric[Node], Next, m_RBMetric[Next]);
\r