source: branches/alilink/GDE/MUSCLE/src/unused/redblack.cpp

Last change on this file was 10835, checked in by westram, 12 years ago
  • directly build $ARBHOME/bin/muscle
  • fixed problematic subdir generation
    1. create subdir if needed
    2. recall make on target
  • moved unused source files out of sight
File size: 10.2 KB
Line 
1#include "muscle.h"
2#include "clust.h"
3
4void Clust::InsertMetric(unsigned uIndex1, unsigned uIndex2, float dMetric)
5        {
6        RBInsert(uIndex1, uIndex2, dMetric);
7        }
8
9void Clust::DeleteMetric(unsigned uIndex)
10        {
11        for (unsigned uNodeIndex = GetFirstCluster(); uNodeIndex != uInsane;
12          uNodeIndex = GetNextCluster(uNodeIndex))
13                {
14                if (uIndex == uNodeIndex)
15                        continue;
16                DeleteMetric(uIndex, uNodeIndex);
17                }
18        }
19
20void Clust::InitMetric(unsigned uMaxNodeIndex)
21        {
22        m_uRBNodeCount = m_uTriangularMatrixSize;
23        m_RBParent = new unsigned[m_uRBNodeCount];
24        m_RBLeft = new unsigned[m_uRBNodeCount];
25        m_RBRight = new unsigned[m_uRBNodeCount];
26        m_RBi = new ushort[m_uRBNodeCount];
27        m_RBj = new ushort[m_uRBNodeCount];
28        m_RBMetric = new float[m_uRBNodeCount];
29        m_RBColor = new bool[m_uRBNodeCount];
30        m_RBRoot = RB_NIL;
31
32#if     DEBUG
33        {
34// Initialize fields to invalid values so we have a chance
35// catch attempts to use them if they're not properly set.
36        unsigned InvalidNode = m_uRBNodeCount + 1;
37        for (unsigned Node = 0; Node < m_uRBNodeCount; ++Node)
38                {
39                m_RBParent[Node] = InvalidNode;
40                m_RBLeft[Node] = InvalidNode;
41                m_RBRight[Node] = InvalidNode;
42                m_RBi[Node] = InvalidNode;
43                m_RBj[Node] = InvalidNode;
44                }
45        }
46#endif
47        }
48
49void Clust::ListMetric() const
50        {
51        Log("Red-black tree root=%u\n", m_RBRoot);
52        Log("\n");
53        Log(" Node  Parent   Left  Right  Color      i      j  Metric\n");
54        Log("-----  ------  -----  -----  -----  -----  -----  ------\n");
55
56        if (RB_NIL == m_RBRoot)
57                return;
58
59        unsigned Count = 0;
60        unsigned Start = RBMin(m_RBRoot);
61        for (unsigned Node = Start; RB_NIL != Node; Node = RBNext(Node))
62                {
63                Log("%5u", Node);
64
65                if (RB_NIL != m_RBParent[Node])
66                        Log("  %6u", m_RBParent[Node]);
67                else
68                        Log("        ");
69
70                if (RB_NIL != m_RBLeft[Node])
71                        Log("  %5u", m_RBLeft[Node]);
72                else
73                        Log("       ");
74
75                if (RB_NIL != m_RBRight[Node])
76                        Log("  %5u", m_RBRight[Node]);
77                else
78                        Log("       ");
79
80                Log("  %s  %5u  %5u  %g\n",
81                  m_RBColor[Node] ? "  Red" : "Black",
82                  m_RBi[Node],
83                  m_RBj[Node],
84                  m_RBMetric[Node]);
85
86                if (++Count > m_uRBNodeCount)
87                        {
88                        Log(" ** LOOP ** \n");
89                        break;
90                        }
91                }
92        }
93
94// If there is a left subtree, predecessor is the
95// largest key found under the left branch. Otherwise,
96// is first node in path to root that is a right child.
97unsigned Clust::RBPrev(unsigned Node) const
98        {
99        assert(Node < m_uRBNodeCount);
100
101        unsigned Left = m_RBLeft[Node];
102        if (RB_NIL != Left)
103                return RBMax(Left);
104
105        for (;;)
106                {
107                unsigned Parent = m_RBParent[Node];
108                if (RB_NIL == Parent)
109                        return RB_NIL;
110                if (m_RBRight[Parent] == Node)
111                        return Parent;
112                Node = Parent;
113                }
114        }
115
116// If there is a right subtree, sucessor is the
117// smallest key found under the right branch. Otherwise,
118// is first node in path to root that is a left child.
119unsigned Clust::RBNext(unsigned Node) const
120        {
121        if (Node >= m_uRBNodeCount)
122                Quit("RBNext(%u)", Node);
123        assert(Node < m_uRBNodeCount);
124
125        unsigned Right = m_RBRight[Node];
126        if (RB_NIL != Right)
127                return RBMin(Right);
128
129        for (;;)
130                {
131                unsigned Parent = m_RBParent[Node];
132                if (RB_NIL == Parent)
133                        return RB_NIL;
134                if (m_RBLeft[Parent] == Node)
135                        return Parent;
136                Node = Parent;
137                }
138        }
139
140// Minimum is in leftmost leaf
141unsigned Clust::RBMin(unsigned RBNode) const
142        {
143        assert(RB_NIL != RBNode);
144        for (;;)
145                {
146                unsigned Left = m_RBLeft[RBNode];
147                if (RB_NIL == Left)
148                        return RBNode;
149                RBNode = Left;
150                }
151        }
152
153// Maximum is in rightmost leaf
154unsigned Clust::RBMax(unsigned RBNode) const
155        {
156        assert(RB_NIL != RBNode);
157        for (;;)
158                {
159                unsigned Right = m_RBRight[RBNode];
160                if (RB_NIL == Right)
161                        return RBNode;
162                RBNode = Right;
163                }
164        }
165
166void Clust::DeleteMetric(unsigned uIndex1, unsigned uIndex2)
167        {
168        unsigned RBNode = (unsigned) VectorIndex(uIndex1, uIndex2);
169        RBDelete(RBNode);
170        }
171
172void Clust::RBDelete(unsigned Node)
173        {
174#if     DEBUG
175        ValidateRB();
176        //Log("@@ Before RBDelete(%u)\n", Node);
177        //ListMetric();
178#endif
179
180        unsigned Left = m_RBLeft[Node];
181        unsigned Right = m_RBRight[Node];
182        unsigned Parent = m_RBParent[Node];
183
184// If one or two nil children, splice out this node.
185        if (RB_NIL == Left || RB_NIL == Right)
186                {
187//              Log("@@ One child\n");
188        // Child is non-NIL child, or NIL if none.
189                unsigned Child = (Left != RB_NIL ? Left : Right);
190
191        // Special case if root
192                if (RB_NIL == Parent)
193                        {
194                        assert(Node == m_RBRoot);
195                        m_RBRoot = Child;
196                        if (RB_NIL != Child)
197                                m_RBParent[Child] = RB_NIL;
198                        return;
199                        }
200
201        // Typical case.
202        // Update parent->child link
203                if (m_RBLeft[Parent] == Node)
204                        m_RBLeft[Parent] = Child;
205                else
206                        {
207                        assert(m_RBRight[Parent] == Node);
208                        m_RBRight[Parent] = Child;
209                        }
210
211        // Update child->parent link
212                if (RB_NIL != Child)
213                        m_RBParent[Child] = Parent;
214
215#if     DEBUG
216                //Log("@@ After RBDelete(%u)\n", Node);
217                //ListMetric();
218                ValidateRB();
219#endif
220                return;
221                }
222
223        //Log("@@ RBDelete(%u) Tricky case\n", Node);
224        //ListMetric();
225
226// Trickier case, node has two children.
227        assert(Left != RB_NIL && Right != RB_NIL);
228
229// We're going to splice out successor node from its
230// current position and insert it in place of node
231// to be deleted.
232
233// Successor cannot be nil because there is a right child.
234        unsigned Next = RBNext(Node);
235        assert(Next != RB_NIL);
236
237// The successor of a node with two children is
238// guaranteed to have no more than one child.
239        unsigned NextLeft = m_RBLeft[Next];
240        unsigned NextRight = m_RBRight[Next];
241        assert(RB_NIL == NextLeft || RB_NIL == NextRight);
242
243// Successor of node with two children cannot be the root.
244        unsigned NextParent = m_RBParent[Next];
245        assert(RB_NIL != NextParent);
246
247// Ugly special case if successor is right child
248        if (Next == Right)
249                {
250#if DEBUG
251                //Log("@@ Before RBDelete(%u) (tricky next==right)\n", Node);
252                //ListMetric();
253#endif
254                m_RBParent[Next] = Parent;
255
256                if (RB_NIL == Parent)
257                        {
258                        m_RBRoot = Next;
259                        m_RBParent[Next] = RB_NIL;
260                        }
261                else
262                        {
263                        if (m_RBLeft[Parent] == Node)
264                                m_RBLeft[Parent] = Next;
265                        else
266                                {
267                                assert(m_RBRight[Parent] == Node);
268                                m_RBRight[Parent] = Next;
269                                }
270                        }
271
272                m_RBLeft[Next] = Left;
273
274                if (RB_NIL != Left)
275                        m_RBParent[Left] = Next;
276
277#if     DEBUG
278                //Log("@@ After RBDelete(%u) (tricky next==right)\n", Node);
279                //ListMetric();
280                ValidateRB();
281#endif
282                return;
283                }
284
285// Set NextChild either to the one child of successor, or nil.
286        unsigned NextChild = (NextLeft != RB_NIL ? NextLeft : NextRight);
287
288// Splice successor from its current position
289        if (m_RBLeft[NextParent] == Next)
290                m_RBLeft[NextParent] = NextChild;
291        else
292                {
293                assert(m_RBRight[NextParent] == Next);
294                m_RBRight[NextParent] = NextChild;
295                }
296
297        if (RB_NIL != NextChild)
298                m_RBParent[NextChild] = NextParent;
299
300// Insert successor into position currently held by node
301// to be deleted.
302        if (RB_NIL == Parent)
303                {
304                m_RBRoot = Next;
305                m_RBParent[Next] = RB_NIL;
306                }
307        else
308                {
309                if (m_RBLeft[Parent] == Node)
310                        m_RBLeft[Parent] = Next;
311                else
312                        {
313                        assert(m_RBRight[Parent] == Node);
314                        m_RBRight[Parent] = Next;
315                        }
316                }
317
318        m_RBLeft[Next] = Left;
319        m_RBRight[Next] = Right;
320        m_RBParent[Next] = Parent;
321
322        m_RBParent[Left] = Next;
323        m_RBParent[Right] = Next;
324
325#if     DEBUG
326        //Log("@@ After RBDelete(%u)\n", Node);
327        //ListMetric();
328        ValidateRB();
329#endif
330        }
331
332unsigned Clust::RBInsert(unsigned i, unsigned j, float fMetric)
333        {
334#if     DEBUG
335        ValidateRB();
336#endif
337
338        unsigned NewNode = VectorIndex(i, j);
339        m_RBMetric[NewNode] = fMetric;
340        m_RBi[NewNode] = i;
341        m_RBj[NewNode] = j;
342
343// New node is always inserted as a leaf.
344// Proof that this is possible is found in algorithm
345// textbooks (I forget the argument).
346        m_RBLeft[NewNode] = RB_NIL;
347        m_RBRight[NewNode] = RB_NIL;
348
349        unsigned NewParent = RB_NIL;
350        unsigned Node = m_RBRoot;
351
352        unsigned uCount = 0;
353        while (RB_NIL != Node)
354                {
355                NewParent = Node;
356                if (fMetric < m_RBMetric[Node])
357                        Node = m_RBLeft[Node];
358                else
359                        Node = m_RBRight[Node];
360                ++uCount;
361                if (uCount > m_uRBNodeCount)
362                        Quit("Infinite loop in RBInsert");
363                }
364
365        m_RBParent[NewNode] = NewParent;
366        if (RB_NIL == NewParent)
367                m_RBRoot = NewNode;
368        else
369                {
370                if (fMetric < m_RBMetric[NewParent])
371                        m_RBLeft[NewParent] = NewNode;
372                else
373                        m_RBRight[NewParent] = NewNode;
374                }
375
376#if     DEBUG
377        {
378        unsigned Next = RBNext(NewNode);
379        if (Next != RB_NIL)
380                assert(NewNode == RBPrev(Next));
381        unsigned Prev = RBPrev(NewNode);
382        if (Prev != RB_NIL)
383                assert(NewNode == RBNext(Prev));
384        ValidateRB();
385        }
386#endif
387        return NewNode;
388        }
389
390void Clust::ValidateRBNode(unsigned Node, const char szMsg[]) const
391        {
392        if (RB_NIL == Node)
393                return;
394
395        unsigned Parent = m_RBParent[Node];
396        unsigned Left = m_RBLeft[Node];
397        unsigned Right = m_RBRight[Node];
398
399        unsigned Next = RBNext(Node);
400        unsigned Prev = RBPrev(Node);
401
402        if (RB_NIL != Next && RBPrev(Next) != Node)
403                {
404                ListMetric();
405                Quit("ValidateRB(%s) Node=%u Next=%u Prev(Next)=%u",
406                  szMsg, Node, Next, RBPrev(Next));
407                }
408
409        if (RB_NIL != Prev && RBNext(Prev) != Node)
410                {
411                ListMetric();
412                Quit("ValidateRB(%s) Node=%u Prev=%u Next(Prev)=%u",
413                  szMsg, Node, Prev, RBNext(Prev));
414                }
415
416        if (RB_NIL != Parent)
417                {
418                if (m_RBLeft[Parent] != Node && m_RBRight[Parent] != Node)
419                        {
420                        ListMetric();
421                        Quit("ValidateRB(%s): Parent %u not linked to child %u\n",
422                          szMsg, Parent, Node);
423                        }
424                }
425
426        if (RB_NIL != Left)
427                {
428                if (m_RBParent[Left] != Node)
429                        {
430                        ListMetric();
431                        Quit("ValidateRB(%s): Left child %u not linked to parent %u\n",
432                          szMsg, Left, Node);
433                        }
434                }
435
436        if (RB_NIL != Right)
437                {
438                if (m_RBParent[Right] != Node)
439                        {
440                        ListMetric();
441                        Quit("ValidateRB(%s): Right child %u not linked to parent %u\n",
442                          szMsg, Right, Node);
443                        }
444                }
445
446        ValidateRBNode(Left, szMsg);
447        ValidateRBNode(Right, szMsg);
448        }
449
450void Clust::ValidateRB(const char szMsg[]) const
451        {
452        if (RB_NIL == m_RBRoot)
453                return;
454
455        ValidateRBNode(m_RBRoot, szMsg);
456
457        unsigned Node = RBMin(m_RBRoot);
458        for (;;)
459                {
460                unsigned Next = RBNext(Node);
461                if (RB_NIL == Next)
462                        break;
463                if (m_RBMetric[Node] > m_RBMetric[Next])
464                        {
465                        ListMetric();
466                        Quit("ValidateRBNode(%s): metric out of order %u=%g %u=%g",
467                          szMsg, Node, m_RBMetric[Node], Next, m_RBMetric[Next]);
468                        }
469                Node = Next;
470                }
471        }
Note: See TracBrowser for help on using the repository browser.