#ifndef dg_tree_H
#define dg_tree_H

/* Finite dyadic multigrids in arbitrary dimension */
/* Last edited on 2009-08-21 15:40:52 by stolfilocal */


#include <stdlib.h>
#include <assert.h>
#include "bool.h"
#include "affirm.h"
#include "indexing.h"
#include "vec.h"
#include "mdg_grid.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 an
  identifying /index/. By definition, the root node has rank 0 and
  index 1. The children of a node with rank {r} and index {k} have
  rank {r+1} and indices {2*k} (the /low/ child) and {2*k+1} (the
  /high/ child). Note that there are {2^r} nodes of rank {r}, with
  indices 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_index_t; /* Index 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_index_t index;     /* Index 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_index_t k);
  /* Creates a new node with no children, parent {pa}, and index {k}. */
  
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 index {k} and rank {r} will then represent cell {k}
  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.) */

/*
  TREE PACKS
  
  A /tree pack/ is a vector of tree node pointers that correspond to
  cells in a cell pack. The pointers may be repeated (due to fold-over
  in the toroidal topology) or may be NULL. */
  
vec_typedef(dg_tree_vec_t,dg_tree_vec,dg_tree_t);
  /* A general-purpose vector of trees. */

bool_t dg_tree_pack_is_leaf (dg_tree_vec_t *N);
  /* Returns TRUE if all the trees in the pack {N} 
    are non-{NULL}, and at least one is a leaf. */

bool_t dg_tree_pack_is_even(dg_tree_vec_t *N);
  /* Returns TRUE if all the trees in the pack {N} 
    are non-{NULL}, and the lowest cell of {N}
    has even index. */

void dg_tree_pack_child
  ( mdg_dim_t d,
    mdg_grid_size_t psz[],
    dg_tree_vec_t *N,
    mdg_axis_t i,
    int which,
    dg_tree_vec_t *NCH
  );
  /* Assumes that {N} is a tree pack at some level {r} of the tree,
    with size vector {psz[0..d-1]}. Returns in {NCH} the tree pack
    of level {r+1} which has the same size vector, 
    and whose lower cell is child {which} of the lower cell of {N}. */

void dg_tree_pack_split
  ( mdg_dim_t d,
    mdg_grid_size_t psz[],
    dg_tree_vec_t *N,
    mdg_axis_t i,
    dg_tree_vec_t *NS
  );
  /* Assumes that {N} is a tree pack at some level {r} of the tree,
    with size vector {psz[0..d-1]}. Returns in {NS} the tree pack of
    level {r+1} obtained by splitting every cell of {N} in half. That
    is, the lower cell of {NS} is the low child of the lower cell of
    {N}, and the size vector of {NS} size is {psz}, except along axis
    {i} where it is {2*psz[i]}. */

void dg_tree_pack_check (dg_tree_vec_t *N, mdg_dim_t d, mdg_grid_size_t psz[], int r);
  /* Runs some consistency checks on a tree pack {N}. If 
    {psz} is not NULL, checks whether the number of elements agrees with {psz}.
    Assumes that the pack has dimension {d}, size vector {psz}, and rank {r}. All
    non-null trees should have the same rank; if {r} is not -1, that
    common rank must be {r}. */

void dg_tree_pack_print(FILE *wr, mdg_dim_t d, mdg_grid_size_t psz[], dg_tree_vec_t *N);
  /* Prints the cells of the nodes in the tree pack {N} to {wr}.
    NULL nodes are printed as "Ø". */

/* 
  TEMPLATES
  
  A /template/ is simply a vector {psz[0..d-1]} of positive integers.
  An /instance/ of a template in a finite dyadic grid {G} is a cell
  pack {P} with size {psz[i]} along each axis {i}, whose cells 
  are cells of {G}. The lower cell of the pack is said to /fit/ 
  the template. */

typedef void dg_tree_pack_op_t(dg_tree_vec_t *N, bool_t leaf);
  /* A procedure called to process a tree pack.  The parameter {is_leaf} is 
    TRUE iff one or more of the cells in {N} is a leaf. */

void dg_tree_pack_enum
  ( mdg_dim_t d, 
    dg_tree_t G,
    mdg_grid_size_t psz[], 
    dg_tree_pack_op_t op
  );
  /* Calls {op} on every valid tree pack of {G} that fits the 
    template {psz[0..d-1]}, in top-down fashion. */

#endif