From a48e7f9fd525b4da828605fb7be4d2a35dde4e23 Mon Sep 17 00:00:00 2001
From: Nicholas Noll <nbnoll@eml.cc>
Date: Tue, 28 Apr 2020 16:32:06 -0700
Subject: feat: prototype of rerooting function

---
 sys/libbio/phylo.c | 59 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 59 insertions(+)

(limited to 'sys/libbio/phylo.c')

diff --git a/sys/libbio/phylo.c b/sys/libbio/phylo.c
index 316537c..4a4bcb1 100644
--- a/sys/libbio/phylo.c
+++ b/sys/libbio/phylo.c
@@ -146,3 +146,62 @@ phylo·ladderize(bio·Node *root)
 
     return 0;
 }
+
+static
+error
+rotateparent(bio·Node *node, bio·Node *to)
+{
+    error err;
+    bio·Node *it, *prev;
+
+    if (node->parent == to) {
+        return 0;
+    }
+
+    prev = nil;
+    for (it = node->child; it != nil; it = it->sibling) {
+        if (it == to) goto FOUND;
+        prev = it;
+    }
+    errorf("inconsistent topology: attempting to rotate to non-child");
+    return 1;
+
+FOUND:
+    if (err = rotateparent(node->parent, node), err) {
+        errorf("failure: broken tree");
+        return err;
+    }
+
+    if (!prev) {
+        node->child   = node->parent;
+    } else {
+        prev->sibling = node->parent;
+    }
+    node->parent->sibling = it->sibling;
+    node->parent          = to;
+
+    return 0;
+}
+
+#define FLOAT_PREC .00000001
+error
+phylo·reroot(bio·Tree *tree, bio·Node *node, double d)
+{
+    bio·Node *old;
+    bio·Node *new;
+
+    // TODO: should check that node is part of this tree?
+    
+    old = tree->root;
+    if (fabs(d) < FLOAT_PREC)            new = node;
+    if (fabs(d-node->dist) < FLOAT_PREC) new = node->parent;
+    else {
+        new = tree->heap.alloc(tree->h, 1, sizeof(*new));
+        memset(new, 0, sizeof(*new));
+    }
+
+    // TODO: Use rotateparent() to perform necessary flips
+
+    tree->root = new;
+    return 0;
+}
-- 
cgit v1.2.1