10. Ramp Tree

10.1. The Ramp Tree Struct

10.1.1. Declaration

<<typedefs>>=

typedef struct gest_node gest_node;

<<struct_ramptree>>=

struct gest_node {
<<gest_node>>
};

The Ramp Tree is a hierarchical tree data structure. Nodes on the tree are contained in a struct known as a gest_node. It is initialized with gest_node_init.

<<static_funcdefs>>=

static void gest_node_init(gest_node *n);

<<funcs>>=

static void gest_node_init(gest_node *n)
{
<<gest_node_init>>
}

10.1.2. Node Type (type)

The node type indicates whether or not is a polyramp or a monoramp. By default, it is a null node.

<<gest_node>>=

int type;

<<gest_node_init>>=

n->type = NODE_NOTHING;

<<enums>>=

enum  {
    NODE_NOTHING,
    NODE_POLYRAMP,
    NODE_MONORAMP
};

10.1.3. Modifier (modifier)

The modifier is a integer amount used to rescale the incoming ramp signal.

<<gest_node>>=

int modifier;

<<gest_node_init>>=

n->modifier = NODE_NOTHING;

10.1.4. Number of Children (nchildren)

The number of children a node has is stored by a variable nchildren. The children nodes are stored in childrenas a linked list, using the next entry.

<<gest_node>>=

int nchildren;

<<gest_node_init>>=

n->nchildren = 0;

10.1.5. Children Nodes

The actual children of a particular node is contained in a linked list (using the node itself as an entry point). The node only stores the head of the list.

<<gest_node>>=

gest_node *children;

<<gest_node_init>>=

n->children = NULL;

10.1.6. Node Target Value (target)

Every node can carry a target, though only leaves of the tree can have targets. This value is otherwise left empty.

<<gest_node>>=

gest_target *target;

<<gest_node_init>>=

n->target = NULL;

10.1.7. Next Node in List (next)

Contiguous nodes that are children to a parent node are linked together in a linked list, with each node pointing to the next with a variable called next.

<<gest_node>>=

gest_node *next;

<<gest_node_init>>=

n->next = NULL;

10.1.8. Parent Node (parent)

A pointer to the parent node is a way for nodes to keep track of position while traversing or populating the tree.

<<gest_node>>=

gest_node *parent;

<<gest_node_init>>=

n->parent = NULL;

10.1.9. Node ID

used for debugging.

<<gest_node>>=

int id;

<<gest_node_init>>=

n->id = -1;

10.1.10. Metanode

Holds optional data for a metanode. NULL by default.

<<gest_node>>=

gest_metanode *meta;

<<gest_node_init>>=

n->meta = NULL;

10.1.11. Children Getter

Optional getter function that returns children of a node.

<<gest_node>>=

gest_node* (*get)(gest_d *, gest_node *);

<<gest_node_init>>=

n->get = NULL;

10.2. Global Modifier Manipulation

The Ramp Tree manipulates the underlying rephasor signal by manipulating the incrementor value through multiplication or division.

Iteration through a node works slightly differently depending on if it is a monoramp or a polyramp. A monoramp keeps track of time from the input signal before finishing. A polyramp keeps track of time using it's own synthesized signal. Polyramps iterate through their children nodes, which can recrusively call more monoramps and polyramps.

Every sample, the Tree Ramp moves forward in time and computes a value. This value is fed into the current target callback.

Nodes in the ramptree count. So, I guess some kind of counter? We will use a counter and a limit, that way the node can be reset multiple times. Every node updates it's counter when it detects a reset.

10.3. Populating a tree with nodes

The general concept populating a tree is that nodes are created, then more nodes are created that become children of the previous nodes. Population of a tree works from left to right.

Creating a node is not only allocating a node, but also appending it to be a child of the parent node. This means all nodes need to have their parent present.

Linking the new node to the parent node is a matter of appending to the end of the children list.

10.3.1. Creating a new polyramp node

A polyramp node is a node that takes one monoramp and subdivides it into a fixed number of ramps. Each of those ramps can be a potential child node.

<<static_funcdefs>>=

static gest_node * mkpolyramp(gest_d *g,
                              gest_node *parent,
                              int div);

The new node is linked to the parent node by appending it to the end of the child list. Before this happens, a quick check is done to make sure the parent node isn't already full.

<<funcs>>=

static gest_node * mkpolyramp(gest_d *g,
                              gest_node *parent,
                              int div)
{
    gest_node *n, *last;
    int total;

    /* check to see if parent node is full */

    total = 0;
    last = NULL;

    if (parent != NULL) {
        total = node_count(parent, &last);
        if (total >= parent->modifier) {
            return NULL;
        }
    }

    n = gest_alloc(g, sizeof(gest_node));
    gest_node_init(n);
    n->type = NODE_POLYRAMP;
    n->modifier = div;
    n->parent = parent;
    n->id = g->nodepos;
    g->nodepos++;

    if (parent != NULL) {
        append_node(parent, n, last);
    }

    if (parent == NULL) {
        n->parent = n;
    }

    return n;
}

10.3.2. Creating a new monoramp node

A monoramp node takes a contiguous set of children from a polyramp node and merges them together into one ramp. A monoramp can have only one potential child node.

The monoramp takes in the number of input ramp periods it will span. It will verify there is enough room in the parent node before creating.

<<static_funcdefs>>=

static gest_node * mkmonoramp(gest_d *g,
                              gest_node *parent,
                              int ninputs);

Similar to mkpolyramp, the parent node is checked for room.

<<funcs>>=

static gest_node * mkmonoramp(gest_d *g,
                              gest_node *parent,
                              int ninputs)
{
    gest_node *n, *last;
    int total;

    last = NULL;

    if (parent != NULL) {
        total = node_count(parent, &last);
        total += ninputs;
        if (total > parent->modifier) return NULL;
    }

    n = gest_alloc(g, sizeof(gest_node));
    gest_node_init(n);

    n->type = NODE_MONORAMP;
    n->modifier = ninputs;
    n->parent = parent;
    n->id = g->nodepos;
    g->nodepos++;

    if (parent != NULL) {
        append_node(parent, n, last);
    }

    return n;
}

10.4. Some Ramp Tree Functions

10.4.1. Node Count

node_count counts the number of children in a node.

<<static_funcdefs>>=

static int node_count(gest_node *node, gest_node **last);

<<funcs>>=

static int node_count(gest_node *node, gest_node **last)
{
    int total;
    int i;
    gest_node *child;

    total = 0;

    if (node == NULL) {
        return -1;
    }

    child = node->children;

    for (i = 0; i < node->nchildren; i++) {
        if (child->type == NODE_MONORAMP) {
            /* monoramps eat up M ramps */
            total += child->modifier;
        } else if (child->type == NODE_POLYRAMP) {
            /* polyramps always occupy one ramp */
            total++;
        }

        if (last != NULL && i == node->nchildren - 1) {
            *last = child;
        }

        child = child->next;
    }

    return total;
}

10.4.2. Append Node to Parent

Append a node to a parent node with append_node.

<<static_funcdefs>>=

static void append_node(gest_node *parent,
                        gest_node *node,
                        gest_node *last);

<<funcs>>=

static void append_node(gest_node *parent,
                        gest_node *node,
                        gest_node *last)
{
    if (last == NULL) {
        parent->children = node;
    } else {
        last->next = node;
    }

    parent->nchildren++;
}

10.4.3. Dive To Target

Dive into node tree until next target is found.

<<static_funcdefs>>=

static gest_node * dive_to_target(gest_d *g,
                                  gest_node *node);

A special edge case is handled when target node is a monoramp with a modifier greater than 1. It will be explicitely applied before being returned. The correspdoning reverting happens in mktargetbefore the next target is set.

<<funcs>>=

static gest_node * dive_to_target(gest_d *g,
                                  gest_node *node)
{
    if (node->meta != NULL) node = get_node(g, node);

    if (node->target != NULL) {
        apply_modifier(g, node);
        return node;
    }

    while (node->target == NULL) {
        apply_modifier(g, node);

        /* go to left-most child */
        node = acquire_children(g, node);
        if (node == NULL) break;
    }

    if (node->type == NODE_MONORAMP && node->modifier > 1) {
        apply_modifier(g, node);
    }

    return node;
}

10.4.4. Revert/Apply Modifiers

<<static_funcdefs>>=

static void revert_modifier(gest_d *g, gest_node *node);
static void apply_modifier(gest_d *g, gest_node *node);

It's a bit of a hack, but the tree traversal setup will go through metanodes and try to revert them. There is no situation where a metanode will need to be reverted, so it can be safely skipped.

A node is considered to be a metanode if the meta pointer is not emtpy.

The reason why this is a hack is because we are doing it here and not in the tree traversal used to find the next node. However, doing it there would require more changes.

<<funcs>>=

static void revert_modifier(gest_d *g, gest_node *node)
{
    if (node->meta != NULL) return;

    if (node->type == NODE_POLYRAMP) {
        g->num /= node->modifier;
    } else if (node->type == NODE_MONORAMP) {
        g->den /= node->modifier;
    }
}

<<funcs>>=

static void apply_modifier(gest_d *g, gest_node *node)
{
    if (node->type == NODE_POLYRAMP) {
        g->num *= node->modifier;
    } else if (node->type == NODE_MONORAMP) {
        g->den *= node->modifier;
    }
}

10.4.5. Acquiring Children From Nodes

Some level of abstraction now required for getting children from Nodes. This is done to make metanodes possible, which can change every time the node is descended upon.

For now, it just does the behavior it did before.

<<static_funcdefs>>=

static gest_node* acquire_children(gest_d *g, gest_node *n);
static gest_node* get_node(gest_d *g, gest_node *n);

<<funcs>>=

static gest_node* get_node(gest_d *g, gest_node *n)
{
    while (n->get != NULL) {
        n = n->get(g, n);
    }

    return n;
}

static gest_node* acquire_children(gest_d *g, gest_node *n)
{
    gest_node *children;

    children = n->children;
    children = get_node(g, children);

    return children;
}

10.5. Target Getter

The function node_target is used to get the target associated with a node. This layer of abstraction is needed for metatargets.

<<static_funcdefs>>=

static gest_target *node_target(gest_d *g, gest_node *node);

<<funcs>>=

static gest_target *node_target(gest_d *g, gest_node *node)
{
    gest_target *t;

    if (node == NULL) return NULL;

    t = node->target;

    if (node->target != NULL && node->target->get != NULL) {
        while (1) {
            t = t->get(g, t);
            if (t->meta == NULL) break;
        }
    }

    return t;
}

prev | home | next