#ifndef dg_tree_H
#define dg_tree_H

/* Binary trees fo dyadic multigrids */
/* Last edited on 2014-05-15 20:43:03 by stolfilocal */

#include <dg_grid.h>
#include <bool.h>
#include <vec.h>
#include <stdlib.h>

/* 
  THE INFINITE BINARY TREE

  The /infinite binary tree/ is an infinite collection of nodes where
  every node has two distinguished children (/low/ and /high/), and
  every node can be reached from a distinguished /root node/ by a
  finite sequence of parent-to-child steps.
  
  Every node of the infinite binary tree has a /rank/ and a
  unique positive integer /identifier/. By definition, the root node has rank 0 and
  identifier 1. The children of a node with rank {r} and identifier {id} have
  rank {r+1} and identifiers {2*id} (the /low/ child) and {2*id+1} (the
  /high/ child). Note that there are {2^r} nodes of rank {r}, with
  identifiers ranging from {2^r} to {2^{r+1}- 1}.

  FINITE BINARY TREES

  A /finite binary tree/ is a finite segment of the infinite one.
  It is either an /empty tree/ which contains no nodes (not even the root),
  or a node whose two children are finite trees (possibly empty). */

typedef int32_t dg_tree_node_count_t; /* Number of nodes in a tree. */

typedef uint64_t dg_tree_node_id_t; /* Identifier of a node in the infinite tree. */

typedef struct dg_tree_node_t       /* A node in a finite binary tree. */
  { struct dg_tree_node_t *pa;      /* Parent node. */
    struct dg_tree_node_t *ch[2];   /* Children nodes. */
    dg_tree_node_count_t nodes;     /* Total number of nodes in this subtree. */
    dg_tree_node_id_t id;           /* Identifier of this node in the infinite tree. */
    void *data;                     /* Multipurpose data pointer. */
  } dg_tree_node_t;
  
typedef dg_tree_node_t* dg_tree_t;
  /* A tree is represented by a pointer to its root node. */

#define LOCH(n) ((n).ch[0])
#define HICH(n) ((n).ch[1])
  /* The low and high children of a node {n}. */

#define dg_MAX_NODES (1073741824L)
  /* Maximum number of nodes allowed in a finite binary tree. */

dg_tree_node_t *dg_tree_node_new(dg_tree_node_t *pa, dg_tree_node_id_t id);
  /* Creates a new node with no children, parent {pa}, and identifier {id}. */
  
void dg_tree_node_free(dg_tree_node_t *n);
  /* Reclaims the storage used by {n}, which must not have
    any children. */

/*
   MODIFYING A BINARY TREE 
   
   These procedures modify a node {n} at the fringe of a binary tree.
   They fix {n->nodes}, but the fields of {n}'s ancestors will have to
   be fixed by the caller. */

void dg_tree_node_split(dg_tree_node_t *n);
  /* The node {n} must have no children. Creates two new nodes and
    appends them as the children of {n}.  */

void dg_tree_node_unsplit(dg_tree_node_t *n);
  /* The node {n} must have two children and no grandchildren. Deletes and
    reclaims the children of {n} (but not the {data} records),
    leaving {n} childless. */

void dg_free_subtree(dg_tree_node_t* n);
  /* Recursively reclaims {n} and its descendents. */

/*
  FINITE MULTIGRIDS
  
  A /finite {d}-dimensional multigrid/ is a finite subset {G} of an
  infinite {d}-dimensional grid {G*}, consisting of one or more cells
  together with all their faces, such that (1) the union {\U G} is the
  whole torus {T^d}, (2) for every cell of {G} in any level {r > 0},
  its parent and its sister are also in {G}.
  
  By /level {r}/ of a finite grid {G} we mean the set of all items of
  {G} which come from level {r} of {G*}. Obviously every item at level
  {r > 0} is contained in some item at level {r-1}.
  
  A /leaf item/ of a finite grid {G} is an item of {G} that does not
  contain any other item of {G}. The union of all leaf
  items of {G} is the root cell {C0}.
  
  Observe that a face of a leaf cell (or leaf item) need not be itself
  a leaf item. It can be checked that the leaf items are pairwise
  disjoint, and comprise a partition of {C0}, called the /diagram/ of
  {G}, denoted by {L(G)}.

  FINITE MULTIGRIDS AS TREES
  
  A finite multigrid {G} can be represented by a finite binary tree
  {T}, where each {dg_tree_node_t} represents a cell of {G}, and the
  parent-child relations between the nodes of {T} mirror the
  containment relations between the cells of {G}.
  
  A tree node of identifier {id} and rank {r} will then represent cell {id}
  of the multigrid, in layer {r}. If both children of the node are
  NULL, then that cell is a leaf cell of {G}.  Otherwise, both children
  must be non-null.  */

/*
  ENCLOSING NODES
  
  If {T} is a binary tree representing a finite {d}-dimensional grid
  {G}, we define the /enclosing node/ {T(C)} of an arbitrary dyadic
  cell {C} as the node of {T} with maximum rank whose cell contains
  {C}; or NULL if there is no such node. */

void dg_tree_node_enclose_children(dg_tree_node_t *, dg_tree_node_t *ch[]);
  /* Given an enclosing node {n} in a grid {T} for a cell {C},
    returns in {ch[0..1]} enclosures for the children of {C}.
    
    Namely, if {n} is null or is a leaf node, sets 
    {ch[0] = ch[1] = n}; otherwise, sets {ch[0] = LOCH(n),
    ch[1] = HICH(n)}. (Note that one of them may be NULL.) */

#endif