File: reorderBinary.c

package info (click to toggle)
r-cran-phylobase 0.8.6-1
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, buster, sid
  • size: 1,308 kB
  • sloc: cpp: 306; ansic: 247; xml: 135; lisp: 38; sh: 9; makefile: 5
file content (66 lines) | stat: -rw-r--r-- 1,693 bytes parent folder | download | duplicates (3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/*
  reorderBinary.c:
    Given a root node, reorder a tree either as postorder or preorder.
  Works only on binary trees, in which each internal node has exactly 2
  descendants. Function inputs are derived from a phylo4 edge matrix.
  The new descendant node ordering is stored in descendantNew.
*/

#include <R.h>

typedef struct {
    int *descendantNew;
    int *ancestor;
    int *left;
    int *right;
    int nEdges;
    int index;
    } tree;

void postorderBinary(tree*, int node);
void preorderBinary(tree*, int node);

void reorderBinary(int *descendantNew, int *root, int *ancestor, int *left,
    int *right, int *nEdges, int *order) {

    tree tr;
    tr.ancestor = ancestor;
    tr.left = left;
    tr.right = right;
    tr.descendantNew = descendantNew;
    tr.nEdges = *nEdges;
    tr.index = 0;

    if (*order==0) {
      postorderBinary(&tr, *root);
    } else if (*order==1) {
      preorderBinary(&tr, *root);
    } else {
      error("invalid order type");
    }

}

// postorder: continue traversing to the end, then record node
void postorderBinary(tree *tr, int node) {
    for (int i=0; i<tr->nEdges; i++) {
        if (tr->ancestor[i]==node) {
            postorderBinary(tr, tr->left[i]);
            postorderBinary(tr, tr->right[i]);
        }
     }
    tr->descendantNew[tr->index] = node;
    tr->index += 1;
}

// preorder: record node first, then continue traversing
void preorderBinary(tree *tr, int node) {
    tr->descendantNew[tr->index] = node;
    tr->index += 1;
    for (int i=0; i<tr->nEdges; i++) {
        if (tr->ancestor[i]==node) {
            preorderBinary(tr, tr->left[i]);
            preorderBinary(tr, tr->right[i]);
        }
    }
}