/* See dg_tree.h */
/* Last edited on 2014-05-15 20:42:37 by stolfilocal */

#include <stdlib.h>
#include <assert.h>

#include <affirm.h>

#include <dg_tree.h>

/* ALLOCATION */

dg_tree_node_t *dg_tree_node_new(dg_tree_node_t *pa, dg_tree_node_id_t id)
  { void *v = notnull(malloc(sizeof(dg_tree_node_t)), "no mem for dg_tree_node_t");
    dg_tree_node_t *n = (dg_tree_node_t*)v;
    /* fprintf(stderr, "+ dg_tree_node_new %d\n", (int)v); */ 
    n->pa = pa;
    LOCH(*n) = NULL;
    HICH(*n) = NULL;
    n->data = NULL;
    n->id = id;
    n->nodes = 1;
    /* fprintf(stderr, "- dg_tree_node_new\n"); */
    return n;
  }

void dg_tree_node_free(dg_tree_node_t *node)
  { affirm(LOCH(*node) == NULL, "node has ch[0]");
    affirm(HICH(*node) == NULL, "node has ch[1]");
    affirm(node->data == NULL, "node has data");
    free(node);
  }
  
void dg_free_subtree(dg_tree_node_t* root)
  { if (root != NULL)
      { dg_free_subtree(LOCH(*root)); LOCH(*root) = NULL;
        dg_free_subtree(HICH(*root)); HICH(*root) = NULL;
        dg_tree_node_free(root);
      }
  }
                    
/* MODIFYING A BINARY TREE */

void dg_tree_node_split(dg_tree_node_t *n)
  { affirm(LOCH(*n) == NULL, "node has ch[0]");
    affirm(HICH(*n) == NULL, "node has ch[1]");
    LOCH(*n) = dg_tree_node_new(n, 2 * n->id);
    HICH(*n) = dg_tree_node_new(n, 2 * n->id + 1);
    n->nodes = 3;
  }

void dg_tree_node_unsplit(dg_tree_node_t *n)
  { affirm((LOCH(*n) != NULL) && (HICH(*n) != NULL), "bad unnsplit");
    affirm(n->nodes == 3, "bad unnsplit");
    dg_tree_node_free(LOCH(*n)); LOCH(*n) = NULL;
    dg_tree_node_free(HICH(*n)); HICH(*n) = NULL;
    n->nodes = 1;
  }
  
void dg_tree_node_enclose_children(dg_tree_node_t *n, dg_tree_node_t *ch[])
  { if (n == NULL)
      { /* No node, no children: */
        ch[0] = ch[1] = NULL;
      }
    else if ((LOCH(*n) == NULL) && (HICH(*n) == NULL))
      { /* Leaf node, children are self: */
        ch[0] = ch[1] = n;
      }
    else
      { /* Get the children of {n}, even if one is NULL: */
        ch[0] = LOCH(*n);
        ch[1] = HICH(*n);
      }
  }