binaries/src/muscle/redblack.cpp

   1 #include "muscle.h"\r
   2 #include "clust.h"\r
   3 \r
   4 void Clust::InsertMetric(unsigned uIndex1, unsigned uIndex2, float dMetric)\r
   5         {\r
   6         RBInsert(uIndex1, uIndex2, dMetric);\r
   7         }\r
   8 \r
   9 void Clust::DeleteMetric(unsigned uIndex)\r
  10         {\r
  11         for (unsigned uNodeIndex = GetFirstCluster(); uNodeIndex != uInsane;\r
  12           uNodeIndex = GetNextCluster(uNodeIndex))\r
  13                 {\r
  14                 if (uIndex == uNodeIndex)\r
  15                         continue;\r
  16                 DeleteMetric(uIndex, uNodeIndex);\r
  17                 }\r
  18         }\r
  19 \r
  20 void Clust::InitMetric(unsigned uMaxNodeIndex)\r
  21         {\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
  30         m_RBRoot = RB_NIL;\r
  31 \r
  32 #if     DEBUG\r
  33         {\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
  38                 {\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
  44                 }\r
  45         }\r
  46 #endif\r
  47         }\r
  48 \r
  49 void Clust::ListMetric() const\r
  50         {\r
  51         Log("Red-black tree root=%u\n", m_RBRoot);\r
  52         Log("\n");\r
  53         Log(" Node  Parent   Left  Right  Color      i      j  Metric\n");\r
  54         Log("-----  ------  -----  -----  -----  -----  -----  ------\n");\r
  55 \r
  56         if (RB_NIL == m_RBRoot)\r
  57                 return;\r
  58 \r
  59         unsigned Count = 0;\r
  60         unsigned Start = RBMin(m_RBRoot);\r
  61         for (unsigned Node = Start; RB_NIL != Node; Node = RBNext(Node))\r
  62                 {\r
  63                 Log("%5u", Node);\r
  64 \r
  65                 if (RB_NIL != m_RBParent[Node])\r
  66                         Log("  %6u", m_RBParent[Node]);\r
  67                 else\r
  68                         Log("        ");\r
  69 \r
  70                 if (RB_NIL != m_RBLeft[Node])\r
  71                         Log("  %5u", m_RBLeft[Node]);\r
  72                 else\r
  73                         Log("       ");\r
  74 \r
  75                 if (RB_NIL != m_RBRight[Node])\r
  76                         Log("  %5u", m_RBRight[Node]);\r
  77                 else\r
  78                         Log("       ");\r
  79 \r
  80                 Log("  %s  %5u  %5u  %g\n",\r
  81                   m_RBColor[Node] ? "  Red" : "Black",\r
  82                   m_RBi[Node],\r
  83                   m_RBj[Node],\r
  84                   m_RBMetric[Node]);\r
  85 \r
  86                 if (++Count > m_uRBNodeCount)\r
  87                         {\r
  88                         Log(" ** LOOP ** \n");\r
  89                         break;\r
  90                         }\r
  91                 }\r
  92         }\r
  93 \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
  98         {\r
  99         assert(Node < m_uRBNodeCount);\r
 100 \r
 101         unsigned Left = m_RBLeft[Node];\r
 102         if (RB_NIL != Left)\r
 103                 return RBMax(Left);\r
 104 \r
 105         for (;;)\r
 106                 {\r
 107                 unsigned Parent = m_RBParent[Node];\r
 108                 if (RB_NIL == Parent)\r
 109                         return RB_NIL;\r
 110                 if (m_RBRight[Parent] == Node)\r
 111                         return Parent;\r
 112                 Node = Parent;\r
 113                 }\r
 114         }\r
 115 \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
 120         {\r
 121         if (Node >= m_uRBNodeCount)\r
 122                 Quit("RBNext(%u)", Node);\r
 123         assert(Node < m_uRBNodeCount);\r
 124 \r
 125         unsigned Right = m_RBRight[Node];\r
 126         if (RB_NIL != Right)\r
 127                 return RBMin(Right);\r
 128 \r
 129         for (;;)\r
 130                 {\r
 131                 unsigned Parent = m_RBParent[Node];\r
 132                 if (RB_NIL == Parent)\r
 133                         return RB_NIL;\r
 134                 if (m_RBLeft[Parent] == Node)\r
 135                         return Parent;\r
 136                 Node = Parent;\r
 137                 }\r
 138         }\r
 139 \r
 140 // Minimum is in leftmost leaf\r
 141 unsigned Clust::RBMin(unsigned RBNode) const\r
 142         {\r
 143         assert(RB_NIL != RBNode);\r
 144         for (;;)\r
 145                 {\r
 146                 unsigned Left = m_RBLeft[RBNode];\r
 147                 if (RB_NIL == Left)\r
 148                         return RBNode;\r
 149                 RBNode = Left;\r
 150                 }\r
 151         }\r
 152 \r
 153 // Maximum is in rightmost leaf\r
 154 unsigned Clust::RBMax(unsigned RBNode) const\r
 155         {\r
 156         assert(RB_NIL != RBNode);\r
 157         for (;;)\r
 158                 {\r
 159                 unsigned Right = m_RBRight[RBNode];\r
 160                 if (RB_NIL == Right)\r
 161                         return RBNode;\r
 162                 RBNode = Right;\r
 163                 }\r
 164         }\r
 165 \r
 166 void Clust::DeleteMetric(unsigned uIndex1, unsigned uIndex2)\r
 167         {\r
 168         unsigned RBNode = (unsigned) VectorIndex(uIndex1, uIndex2);\r
 169         RBDelete(RBNode);\r
 170         }\r
 171 \r
 172 void Clust::RBDelete(unsigned Node)\r
 173         {\r
 174 #if     DEBUG\r
 175         ValidateRB();\r
 176         //Log("@@ Before RBDelete(%u)\n", Node);\r
 177         //ListMetric();\r
 178 #endif\r
 179 \r
 180         unsigned Left = m_RBLeft[Node];\r
 181         unsigned Right = m_RBRight[Node];\r
 182         unsigned Parent = m_RBParent[Node];\r
 183 \r
 184 // If one or two nil children, splice out this node.\r
 185         if (RB_NIL == Left || RB_NIL == Right)\r
 186                 {\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
 190 \r
 191         // Special case if root\r
 192                 if (RB_NIL == Parent)\r
 193                         {\r
 194                         assert(Node == m_RBRoot);\r
 195                         m_RBRoot = Child;\r
 196                         if (RB_NIL != Child)\r
 197                                 m_RBParent[Child] = RB_NIL;\r
 198                         return;\r
 199                         }\r
 200 \r
 201         // Typical case.\r
 202         // Update parent->child link\r
 203                 if (m_RBLeft[Parent] == Node)\r
 204                         m_RBLeft[Parent] = Child;\r
 205                 else\r
 206                         {\r
 207                         assert(m_RBRight[Parent] == Node);\r
 208                         m_RBRight[Parent] = Child;\r
 209                         }\r
 210 \r
 211         // Update child->parent link\r
 212                 if (RB_NIL != Child)\r
 213                         m_RBParent[Child] = Parent;\r
 214 \r
 215 #if     DEBUG\r
 216                 //Log("@@ After RBDelete(%u)\n", Node);\r
 217                 //ListMetric();\r
 218                 ValidateRB();\r
 219 #endif\r
 220                 return;\r
 221                 }\r
 222 \r
 223         //Log("@@ RBDelete(%u) Tricky case\n", Node);\r
 224         //ListMetric();\r
 225 \r
 226 // Trickier case, node has two children.\r
 227         assert(Left != RB_NIL && Right != RB_NIL);\r
 228 \r
 229 // We're going to splice out successor node from its\r
 230 // current position and insert it in place of node\r
 231 // to be deleted.\r
 232 \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
 236 \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
 242 \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
 246 \r
 247 // Ugly special case if successor is right child\r
 248         if (Next == Right)\r
 249                 {\r
 250 #if DEBUG\r
 251                 //Log("@@ Before RBDelete(%u) (tricky next==right)\n", Node);\r
 252                 //ListMetric();\r
 253 #endif\r
 254                 m_RBParent[Next] = Parent;\r
 255 \r
 256                 if (RB_NIL == Parent)\r
 257                         {\r
 258                         m_RBRoot = Next;\r
 259                         m_RBParent[Next] = RB_NIL;\r
 260                         }\r
 261                 else\r
 262                         {\r
 263                         if (m_RBLeft[Parent] == Node)\r
 264                                 m_RBLeft[Parent] = Next;\r
 265                         else\r
 266                                 {\r
 267                                 assert(m_RBRight[Parent] == Node);\r
 268                                 m_RBRight[Parent] = Next;\r
 269                                 }\r
 270                         }\r
 271 \r
 272                 m_RBLeft[Next] = Left;\r
 273 \r
 274                 if (RB_NIL != Left)\r
 275                         m_RBParent[Left] = Next;\r
 276 \r
 277 #if     DEBUG\r
 278                 //Log("@@ After RBDelete(%u) (tricky next==right)\n", Node);\r
 279                 //ListMetric();\r
 280                 ValidateRB();\r
 281 #endif\r
 282                 return;\r
 283                 }\r
 284 \r
 285 // Set NextChild either to the one child of successor, or nil.\r
 286         unsigned NextChild = (NextLeft != RB_NIL ? NextLeft : NextRight);\r
 287 \r
 288 // Splice successor from its current position\r
 289         if (m_RBLeft[NextParent] == Next)\r
 290                 m_RBLeft[NextParent] = NextChild;\r
 291         else\r
 292                 {\r
 293                 assert(m_RBRight[NextParent] == Next);\r
 294                 m_RBRight[NextParent] = NextChild;\r
 295                 }\r
 296 \r
 297         if (RB_NIL != NextChild)\r
 298                 m_RBParent[NextChild] = NextParent;\r
 299 \r
 300 // Insert successor into position currently held by node\r
 301 // to be deleted.\r
 302         if (RB_NIL == Parent)\r
 303                 {\r
 304                 m_RBRoot = Next;\r
 305                 m_RBParent[Next] = RB_NIL;\r
 306                 }\r
 307         else\r
 308                 {\r
 309                 if (m_RBLeft[Parent] == Node)\r
 310                         m_RBLeft[Parent] = Next;\r
 311                 else\r
 312                         {\r
 313                         assert(m_RBRight[Parent] == Node);\r
 314                         m_RBRight[Parent] = Next;\r
 315                         }\r
 316                 }\r
 317 \r
 318         m_RBLeft[Next] = Left;\r
 319         m_RBRight[Next] = Right;\r
 320         m_RBParent[Next] = Parent;\r
 321 \r
 322         m_RBParent[Left] = Next;\r
 323         m_RBParent[Right] = Next;\r
 324 \r
 325 #if     DEBUG\r
 326         //Log("@@ After RBDelete(%u)\n", Node);\r
 327         //ListMetric();\r
 328         ValidateRB();\r
 329 #endif\r
 330         }\r
 331 \r
 332 unsigned Clust::RBInsert(unsigned i, unsigned j, float fMetric)\r
 333         {\r
 334 #if     DEBUG\r
 335         ValidateRB();\r
 336 #endif\r
 337 \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
 342 \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
 348 \r
 349         unsigned NewParent = RB_NIL;\r
 350         unsigned Node = m_RBRoot;\r
 351 \r
 352         unsigned uCount = 0;\r
 353         while (RB_NIL != Node)\r
 354                 {\r
 355                 NewParent = Node;\r
 356                 if (fMetric < m_RBMetric[Node])\r
 357                         Node = m_RBLeft[Node];\r
 358                 else\r
 359                         Node = m_RBRight[Node];\r
 360                 ++uCount;\r
 361                 if (uCount > m_uRBNodeCount)\r
 362                         Quit("Infinite loop in RBInsert");\r
 363                 }\r
 364 \r
 365         m_RBParent[NewNode] = NewParent;\r
 366         if (RB_NIL == NewParent)\r
 367                 m_RBRoot = NewNode;\r
 368         else\r
 369                 {\r
 370                 if (fMetric < m_RBMetric[NewParent])\r
 371                         m_RBLeft[NewParent] = NewNode;\r
 372                 else\r
 373                         m_RBRight[NewParent] = NewNode;\r
 374                 }\r
 375 \r
 376 #if     DEBUG\r
 377         {\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
 384         ValidateRB();\r
 385         }\r
 386 #endif\r
 387         return NewNode;\r
 388         }\r
 389 \r
 390 void Clust::ValidateRBNode(unsigned Node, const char szMsg[]) const\r
 391         {\r
 392         if (RB_NIL == Node)\r
 393                 return;\r
 394 \r
 395         unsigned Parent = m_RBParent[Node];\r
 396         unsigned Left = m_RBLeft[Node];\r
 397         unsigned Right = m_RBRight[Node];\r
 398 \r
 399         unsigned Next = RBNext(Node);\r
 400         unsigned Prev = RBPrev(Node);\r
 401 \r
 402         if (RB_NIL != Next && RBPrev(Next) != Node)\r
 403                 {\r
 404                 ListMetric();\r
 405                 Quit("ValidateRB(%s) Node=%u Next=%u Prev(Next)=%u",\r
 406                   szMsg, Node, Next, RBPrev(Next));\r
 407                 }\r
 408 \r
 409         if (RB_NIL != Prev && RBNext(Prev) != Node)\r
 410                 {\r
 411                 ListMetric();\r
 412                 Quit("ValidateRB(%s) Node=%u Prev=%u Next(Prev)=%u",\r
 413                   szMsg, Node, Prev, RBNext(Prev));\r
 414                 }\r
 415 \r
 416         if (RB_NIL != Parent)\r
 417                 {\r
 418                 if (m_RBLeft[Parent] != Node && m_RBRight[Parent] != Node)\r
 419                         {\r
 420                         ListMetric();\r
 421                         Quit("ValidateRB(%s): Parent %u not linked to child %u\n",\r
 422                           szMsg, Parent, Node);\r
 423                         }\r
 424                 }\r
 425 \r
 426         if (RB_NIL != Left)\r
 427                 {\r
 428                 if (m_RBParent[Left] != Node)\r
 429                         {\r
 430                         ListMetric();\r
 431                         Quit("ValidateRB(%s): Left child %u not linked to parent %u\n",\r
 432                           szMsg, Left, Node);\r
 433                         }\r
 434                 }\r
 435 \r
 436         if (RB_NIL != Right)\r
 437                 {\r
 438                 if (m_RBParent[Right] != Node)\r
 439                         {\r
 440                         ListMetric();\r
 441                         Quit("ValidateRB(%s): Right child %u not linked to parent %u\n",\r
 442                           szMsg, Right, Node);\r
 443                         }\r
 444                 }\r
 445 \r
 446         ValidateRBNode(Left, szMsg);\r
 447         ValidateRBNode(Right, szMsg);\r
 448         }\r
 449 \r
 450 void Clust::ValidateRB(const char szMsg[]) const\r
 451         {\r
 452         if (RB_NIL == m_RBRoot)\r
 453                 return;\r
 454 \r
 455         ValidateRBNode(m_RBRoot, szMsg);\r
 456 \r
 457         unsigned Node = RBMin(m_RBRoot);\r
 458         for (;;)\r
 459                 {\r
 460                 unsigned Next = RBNext(Node);\r
 461                 if (RB_NIL == Next)\r
 462                         break;\r
 463                 if (m_RBMetric[Node] > m_RBMetric[Next])\r
 464                         {\r
 465                         ListMetric();\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
 468                         }\r
 469                 Node = Next;\r
 470                 }\r
 471         }\r