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

---
 include/libbio.h       |  5 ++++-
 sys/libbio/io/newick.c |  6 ++---
 sys/libbio/phylo.c     | 59 ++++++++++++++++++++++++++++++++++++++++++++++++++
 sys/libbio/test.c      | 17 ++++++++-------
 4 files changed, 75 insertions(+), 12 deletions(-)

diff --git a/include/libbio.h b/include/libbio.h
index 5d6f6f8..9eebb0b 100644
--- a/include/libbio.h
+++ b/include/libbio.h
@@ -20,6 +20,9 @@ typedef struct bio·Tree
 {
     bio·Node *root;
     int       nleaf;
+
+    mem·Allocator heap;
+    void         *h;
 } bio·Tree;
 
 // clade functions
@@ -32,7 +35,7 @@ error phylo·countleafs(bio·Node *node, int *n);
 error phylo·ladderize(bio·Node *root);
 
 /* newick i/o */
-error  bio·readnewick(io·Peeker stream, void*, mem·Allocator heap, void*, bio·Tree* tree);
+error  bio·readnewick(io·Peeker stream, void*, bio·Tree* tree);
 error  bio·writenewick(bio·Tree tree, io·Putter out, void*);
 
 // -----------------------------------------------------------------------
diff --git a/sys/libbio/io/newick.c b/sys/libbio/io/newick.c
index cc6d3ff..038b41c 100644
--- a/sys/libbio/io/newick.c
+++ b/sys/libbio/io/newick.c
@@ -329,7 +329,7 @@ ERROR:
 }
 
 error
-bio·readnewick(io·Peeker stream, void *s, mem·Allocator heap, void *h, bio·Tree *tree)
+bio·readnewick(io·Peeker stream, void *s, bio·Tree *tree)
 {
     error err;
     struct Parser p;
@@ -350,8 +350,8 @@ bio·readnewick(io·Peeker stream, void *s, mem·Allocator heap, void *h, bio·T
         .tok   = (struct Token){ 0 },
         .fimpl = s,
         .file  = stream,
-        .himpl = h,
-        .heap  = heap,
+        .himpl = tree->h,
+        .heap  = tree->heap,
     };
     err = parse(&p);
     if (err) {
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;
+}
diff --git a/sys/libbio/test.c b/sys/libbio/test.c
index baccd42..5059ce6 100644
--- a/sys/libbio/test.c
+++ b/sys/libbio/test.c
@@ -93,22 +93,23 @@ test·newick()
 {
     error err;
     bio·Tree t;
-    mem·Arena *mem;
+    mem·Arena *heap;
     Stream    *fd[2];
 
     io·Peeker     rdr;
     io·Putter     wtr;
-    mem·Allocator al;
 
-    mem = mem·newarena(mem·sys, nil);
-    rdr = (io·Peeker){.get = &io·getbyte, .unget  = &io·ungetbyte};
-    wtr = (io·Putter){.put = &io·putbyte, .putstr = &io·putstring};
-    al  = (mem·Allocator) { .alloc = &mem·arenaalloc, .free = nil, };
+    heap = mem·newarena(mem·sys, nil);
+    rdr  = (io·Peeker){.get = &io·getbyte, .unget  = &io·ungetbyte};
+    wtr  = (io·Putter){.put = &io·putbyte, .putstr = &io·putstring};
 
     fd[0] = io·open("/home/nolln/root/data/test/zika.nwk", "r");
     fd[1] = io·open("/home/nolln/root/data/test/zika.proc.nwk", "w");
 
-    err = bio·readnewick(rdr, fd[0], al, mem, &t);
+    t.h    = heap;
+    t.heap = (mem·Allocator){ .alloc = &mem·arenaalloc, .free = nil, };
+
+    err = bio·readnewick(rdr, fd[0], &t);
     phylo·ladderize(t.root);
 
     printf("Loaded tree with %d leafs and %d nodes\n", t.nleaf, t.root->nnode);
@@ -119,7 +120,7 @@ test·newick()
     io·close(fd[0]); 
     io·close(fd[1]);
 
-    mem·freearena(mem);
+    mem·freearena(heap);
     return 0;
 }
 
-- 
cgit v1.2.1