+++ /dev/null
-#include "muscle.h"\r
-#include "clust.h"\r
-\r
-void Clust::InsertMetric(unsigned uIndex1, unsigned uIndex2, float dMetric)\r
- {\r
- RBInsert(uIndex1, uIndex2, dMetric);\r
- }\r
-\r
-void Clust::DeleteMetric(unsigned uIndex)\r
- {\r
- for (unsigned uNodeIndex = GetFirstCluster(); uNodeIndex != uInsane;\r
- uNodeIndex = GetNextCluster(uNodeIndex))\r
- {\r
- if (uIndex == uNodeIndex)\r
- continue;\r
- DeleteMetric(uIndex, uNodeIndex);\r
- }\r
- }\r
-\r
-void Clust::InitMetric(unsigned uMaxNodeIndex)\r
- {\r
- m_uRBNodeCount = m_uTriangularMatrixSize;\r
- m_RBParent = new unsigned[m_uRBNodeCount];\r
- m_RBLeft = new unsigned[m_uRBNodeCount];\r
- m_RBRight = new unsigned[m_uRBNodeCount];\r
- m_RBi = new ushort[m_uRBNodeCount];\r
- m_RBj = new ushort[m_uRBNodeCount];\r
- m_RBMetric = new float[m_uRBNodeCount];\r
- m_RBColor = new bool[m_uRBNodeCount];\r
- m_RBRoot = RB_NIL;\r
-\r
-#if DEBUG\r
- {\r
-// Initialize fields to invalid values so we have a chance\r
-// catch attempts to use them if they're not properly set.\r
- unsigned InvalidNode = m_uRBNodeCount + 1;\r
- for (unsigned Node = 0; Node < m_uRBNodeCount; ++Node)\r
- {\r
- m_RBParent[Node] = InvalidNode;\r
- m_RBLeft[Node] = InvalidNode;\r
- m_RBRight[Node] = InvalidNode;\r
- m_RBi[Node] = InvalidNode;\r
- m_RBj[Node] = InvalidNode;\r
- }\r
- }\r
-#endif\r
- }\r
-\r
-void Clust::ListMetric() const\r
- {\r
- Log("Red-black tree root=%u\n", m_RBRoot);\r
- Log("\n");\r
- Log(" Node Parent Left Right Color i j Metric\n");\r
- Log("----- ------ ----- ----- ----- ----- ----- ------\n");\r
-\r
- if (RB_NIL == m_RBRoot)\r
- return;\r
-\r
- unsigned Count = 0;\r
- unsigned Start = RBMin(m_RBRoot);\r
- for (unsigned Node = Start; RB_NIL != Node; Node = RBNext(Node))\r
- {\r
- Log("%5u", Node);\r
-\r
- if (RB_NIL != m_RBParent[Node])\r
- Log(" %6u", m_RBParent[Node]);\r
- else\r
- Log(" ");\r
-\r
- if (RB_NIL != m_RBLeft[Node])\r
- Log(" %5u", m_RBLeft[Node]);\r
- else\r
- Log(" ");\r
-\r
- if (RB_NIL != m_RBRight[Node])\r
- Log(" %5u", m_RBRight[Node]);\r
- else\r
- Log(" ");\r
-\r
- Log(" %s %5u %5u %g\n",\r
- m_RBColor[Node] ? " Red" : "Black",\r
- m_RBi[Node],\r
- m_RBj[Node],\r
- m_RBMetric[Node]);\r
-\r
- if (++Count > m_uRBNodeCount)\r
- {\r
- Log(" ** LOOP ** \n");\r
- break;\r
- }\r
- }\r
- }\r
-\r
-// If there is a left subtree, predecessor is the\r
-// largest key found under the left branch. Otherwise,\r
-// is first node in path to root that is a right child.\r
-unsigned Clust::RBPrev(unsigned Node) const\r
- {\r
- assert(Node < m_uRBNodeCount);\r
-\r
- unsigned Left = m_RBLeft[Node];\r
- if (RB_NIL != Left)\r
- return RBMax(Left);\r
-\r
- for (;;)\r
- {\r
- unsigned Parent = m_RBParent[Node];\r
- if (RB_NIL == Parent)\r
- return RB_NIL;\r
- if (m_RBRight[Parent] == Node)\r
- return Parent;\r
- Node = Parent;\r
- }\r
- }\r
-\r
-// If there is a right subtree, sucessor is the\r
-// smallest key found under the right branch. Otherwise,\r
-// is first node in path to root that is a left child.\r
-unsigned Clust::RBNext(unsigned Node) const\r
- {\r
- if (Node >= m_uRBNodeCount)\r
- Quit("RBNext(%u)", Node);\r
- assert(Node < m_uRBNodeCount);\r
-\r
- unsigned Right = m_RBRight[Node];\r
- if (RB_NIL != Right)\r
- return RBMin(Right);\r
-\r
- for (;;)\r
- {\r
- unsigned Parent = m_RBParent[Node];\r
- if (RB_NIL == Parent)\r
- return RB_NIL;\r
- if (m_RBLeft[Parent] == Node)\r
- return Parent;\r
- Node = Parent;\r
- }\r
- }\r
-\r
-// Minimum is in leftmost leaf\r
-unsigned Clust::RBMin(unsigned RBNode) const\r
- {\r
- assert(RB_NIL != RBNode);\r
- for (;;)\r
- {\r
- unsigned Left = m_RBLeft[RBNode];\r
- if (RB_NIL == Left)\r
- return RBNode;\r
- RBNode = Left;\r
- }\r
- }\r
-\r
-// Maximum is in rightmost leaf\r
-unsigned Clust::RBMax(unsigned RBNode) const\r
- {\r
- assert(RB_NIL != RBNode);\r
- for (;;)\r
- {\r
- unsigned Right = m_RBRight[RBNode];\r
- if (RB_NIL == Right)\r
- return RBNode;\r
- RBNode = Right;\r
- }\r
- }\r
-\r
-void Clust::DeleteMetric(unsigned uIndex1, unsigned uIndex2)\r
- {\r
- unsigned RBNode = (unsigned) VectorIndex(uIndex1, uIndex2);\r
- RBDelete(RBNode);\r
- }\r
-\r
-void Clust::RBDelete(unsigned Node)\r
- {\r
-#if DEBUG\r
- ValidateRB();\r
- //Log("@@ Before RBDelete(%u)\n", Node);\r
- //ListMetric();\r
-#endif\r
-\r
- unsigned Left = m_RBLeft[Node];\r
- unsigned Right = m_RBRight[Node];\r
- unsigned Parent = m_RBParent[Node];\r
-\r
-// If one or two nil children, splice out this node.\r
- if (RB_NIL == Left || RB_NIL == Right)\r
- {\r
-// Log("@@ One child\n");\r
- // Child is non-NIL child, or NIL if none.\r
- unsigned Child = (Left != RB_NIL ? Left : Right);\r
-\r
- // Special case if root\r
- if (RB_NIL == Parent)\r
- {\r
- assert(Node == m_RBRoot);\r
- m_RBRoot = Child;\r
- if (RB_NIL != Child)\r
- m_RBParent[Child] = RB_NIL;\r
- return;\r
- }\r
-\r
- // Typical case.\r
- // Update parent->child link\r
- if (m_RBLeft[Parent] == Node)\r
- m_RBLeft[Parent] = Child;\r
- else\r
- {\r
- assert(m_RBRight[Parent] == Node);\r
- m_RBRight[Parent] = Child;\r
- }\r
-\r
- // Update child->parent link\r
- if (RB_NIL != Child)\r
- m_RBParent[Child] = Parent;\r
-\r
-#if DEBUG\r
- //Log("@@ After RBDelete(%u)\n", Node);\r
- //ListMetric();\r
- ValidateRB();\r
-#endif\r
- return;\r
- }\r
-\r
- //Log("@@ RBDelete(%u) Tricky case\n", Node);\r
- //ListMetric();\r
-\r
-// Trickier case, node has two children.\r
- assert(Left != RB_NIL && Right != RB_NIL);\r
-\r
-// We're going to splice out successor node from its\r
-// current position and insert it in place of node\r
-// to be deleted.\r
-\r
-// Successor cannot be nil because there is a right child.\r
- unsigned Next = RBNext(Node);\r
- assert(Next != RB_NIL);\r
-\r
-// The successor of a node with two children is\r
-// guaranteed to have no more than one child.\r
- unsigned NextLeft = m_RBLeft[Next];\r
- unsigned NextRight = m_RBRight[Next];\r
- assert(RB_NIL == NextLeft || RB_NIL == NextRight);\r
-\r
-// Successor of node with two children cannot be the root.\r
- unsigned NextParent = m_RBParent[Next];\r
- assert(RB_NIL != NextParent);\r
-\r
-// Ugly special case if successor is right child\r
- if (Next == Right)\r
- {\r
-#if DEBUG\r
- //Log("@@ Before RBDelete(%u) (tricky next==right)\n", Node);\r
- //ListMetric();\r
-#endif\r
- m_RBParent[Next] = Parent;\r
-\r
- if (RB_NIL == Parent)\r
- {\r
- m_RBRoot = Next;\r
- m_RBParent[Next] = RB_NIL;\r
- }\r
- else\r
- {\r
- if (m_RBLeft[Parent] == Node)\r
- m_RBLeft[Parent] = Next;\r
- else\r
- {\r
- assert(m_RBRight[Parent] == Node);\r
- m_RBRight[Parent] = Next;\r
- }\r
- }\r
-\r
- m_RBLeft[Next] = Left;\r
-\r
- if (RB_NIL != Left)\r
- m_RBParent[Left] = Next;\r
-\r
-#if DEBUG\r
- //Log("@@ After RBDelete(%u) (tricky next==right)\n", Node);\r
- //ListMetric();\r
- ValidateRB();\r
-#endif\r
- return;\r
- }\r
-\r
-// Set NextChild either to the one child of successor, or nil.\r
- unsigned NextChild = (NextLeft != RB_NIL ? NextLeft : NextRight);\r
-\r
-// Splice successor from its current position\r
- if (m_RBLeft[NextParent] == Next)\r
- m_RBLeft[NextParent] = NextChild;\r
- else\r
- {\r
- assert(m_RBRight[NextParent] == Next);\r
- m_RBRight[NextParent] = NextChild;\r
- }\r
-\r
- if (RB_NIL != NextChild)\r
- m_RBParent[NextChild] = NextParent;\r
-\r
-// Insert successor into position currently held by node\r
-// to be deleted.\r
- if (RB_NIL == Parent)\r
- {\r
- m_RBRoot = Next;\r
- m_RBParent[Next] = RB_NIL;\r
- }\r
- else\r
- {\r
- if (m_RBLeft[Parent] == Node)\r
- m_RBLeft[Parent] = Next;\r
- else\r
- {\r
- assert(m_RBRight[Parent] == Node);\r
- m_RBRight[Parent] = Next;\r
- }\r
- }\r
-\r
- m_RBLeft[Next] = Left;\r
- m_RBRight[Next] = Right;\r
- m_RBParent[Next] = Parent;\r
-\r
- m_RBParent[Left] = Next;\r
- m_RBParent[Right] = Next;\r
-\r
-#if DEBUG\r
- //Log("@@ After RBDelete(%u)\n", Node);\r
- //ListMetric();\r
- ValidateRB();\r
-#endif\r
- }\r
-\r
-unsigned Clust::RBInsert(unsigned i, unsigned j, float fMetric)\r
- {\r
-#if DEBUG\r
- ValidateRB();\r
-#endif\r
-\r
- unsigned NewNode = VectorIndex(i, j);\r
- m_RBMetric[NewNode] = fMetric;\r
- m_RBi[NewNode] = i;\r
- m_RBj[NewNode] = j;\r
-\r
-// New node is always inserted as a leaf.\r
-// Proof that this is possible is found in algorithm\r
-// textbooks (I forget the argument).\r
- m_RBLeft[NewNode] = RB_NIL;\r
- m_RBRight[NewNode] = RB_NIL;\r
-\r
- unsigned NewParent = RB_NIL;\r
- unsigned Node = m_RBRoot;\r
-\r
- unsigned uCount = 0;\r
- while (RB_NIL != Node)\r
- {\r
- NewParent = Node;\r
- if (fMetric < m_RBMetric[Node])\r
- Node = m_RBLeft[Node];\r
- else\r
- Node = m_RBRight[Node];\r
- ++uCount;\r
- if (uCount > m_uRBNodeCount)\r
- Quit("Infinite loop in RBInsert");\r
- }\r
-\r
- m_RBParent[NewNode] = NewParent;\r
- if (RB_NIL == NewParent)\r
- m_RBRoot = NewNode;\r
- else\r
- {\r
- if (fMetric < m_RBMetric[NewParent])\r
- m_RBLeft[NewParent] = NewNode;\r
- else\r
- m_RBRight[NewParent] = NewNode;\r
- }\r
-\r
-#if DEBUG\r
- {\r
- unsigned Next = RBNext(NewNode);\r
- if (Next != RB_NIL)\r
- assert(NewNode == RBPrev(Next));\r
- unsigned Prev = RBPrev(NewNode);\r
- if (Prev != RB_NIL)\r
- assert(NewNode == RBNext(Prev));\r
- ValidateRB();\r
- }\r
-#endif\r
- return NewNode;\r
- }\r
-\r
-void Clust::ValidateRBNode(unsigned Node, const char szMsg[]) const\r
- {\r
- if (RB_NIL == Node)\r
- return;\r
-\r
- unsigned Parent = m_RBParent[Node];\r
- unsigned Left = m_RBLeft[Node];\r
- unsigned Right = m_RBRight[Node];\r
-\r
- unsigned Next = RBNext(Node);\r
- unsigned Prev = RBPrev(Node);\r
-\r
- if (RB_NIL != Next && RBPrev(Next) != Node)\r
- {\r
- ListMetric();\r
- Quit("ValidateRB(%s) Node=%u Next=%u Prev(Next)=%u",\r
- szMsg, Node, Next, RBPrev(Next));\r
- }\r
-\r
- if (RB_NIL != Prev && RBNext(Prev) != Node)\r
- {\r
- ListMetric();\r
- Quit("ValidateRB(%s) Node=%u Prev=%u Next(Prev)=%u",\r
- szMsg, Node, Prev, RBNext(Prev));\r
- }\r
-\r
- if (RB_NIL != Parent)\r
- {\r
- if (m_RBLeft[Parent] != Node && m_RBRight[Parent] != Node)\r
- {\r
- ListMetric();\r
- Quit("ValidateRB(%s): Parent %u not linked to child %u\n",\r
- szMsg, Parent, Node);\r
- }\r
- }\r
-\r
- if (RB_NIL != Left)\r
- {\r
- if (m_RBParent[Left] != Node)\r
- {\r
- ListMetric();\r
- Quit("ValidateRB(%s): Left child %u not linked to parent %u\n",\r
- szMsg, Left, Node);\r
- }\r
- }\r
-\r
- if (RB_NIL != Right)\r
- {\r
- if (m_RBParent[Right] != Node)\r
- {\r
- ListMetric();\r
- Quit("ValidateRB(%s): Right child %u not linked to parent %u\n",\r
- szMsg, Right, Node);\r
- }\r
- }\r
-\r
- ValidateRBNode(Left, szMsg);\r
- ValidateRBNode(Right, szMsg);\r
- }\r
-\r
-void Clust::ValidateRB(const char szMsg[]) const\r
- {\r
- if (RB_NIL == m_RBRoot)\r
- return;\r
-\r
- ValidateRBNode(m_RBRoot, szMsg);\r
-\r
- unsigned Node = RBMin(m_RBRoot);\r
- for (;;)\r
- {\r
- unsigned Next = RBNext(Node);\r
- if (RB_NIL == Next)\r
- break;\r
- if (m_RBMetric[Node] > m_RBMetric[Next])\r
- {\r
- ListMetric();\r
- Quit("ValidateRBNode(%s): metric out of order %u=%g %u=%g",\r
- szMsg, Node, m_RBMetric[Node], Next, m_RBMetric[Next]);\r
- }\r
- Node = Next;\r
- }\r
- }\r
git://source.jalview.org / jabaws.git / blobdiff