/////////////////////////////////////////////////// /  /   /    /     /    /
////////////////////////UNIVERSAL INFINITREE///// /  /   /    /     /     /
/////////////////////////////////////////////// /  /   /    /     /      /
///////////////////////////Written by://///// /  /   /    /     /      /
//////////////////////////-wav_syntax-///// /  /   /    /     /      /
///////////////////////////////////////// /  /   /    /     /      /       /

/*
This is a bi-directional variable-node tree that can store any variable type needed.
It stores the memory necessary to add one or more nodes to each branch.
It rounds the addition of new nodes up to the first NULL node found in the collection,
   it searches the collection starting from the root node and down to the furthest level in left to right order.
*/

#include <iostream>

using namespace std;


template <class Type>
typedef struct TREE_NODE{
int dims;
TREE_NODE<Type>* parent;
TREE_NODE<Type>* node;
Type value;
};

template <class Type>
typedef struct TREE{
int dims;
TREE_NODE<Type>*  node;
};

//Initialize a tree so it is ready to use
template <class Type>
TREE<Type>* InitializeTree(TREE<Type>* Tree,int dimensions){
Tree=new TREE<Type>;
Tree->node=new TREE_NODE<Type>[dimensions];
Tree->node->dims=dimensions;
Tree->dims=dimensions;
    for(int i=0;i<Tree->dims;i++){
    Tree->node[i].parent=NULL;
    Tree->node[i].node=NULL;
    }
return Tree;
}


//Add a node to the tree of dimensions indices, the last argument can be omitted as it
// is used internally, but it could also be used to assign nodes to a specific node pointer
template <class Type>
TREE_NODE<Type>* AddNodeToTree(TREE<Type>*tree,
                               int dimensions,
                               TREE_NODE<Type>*frontier=NULL){
int fdims;
                if(fron==NULL){
            frontier=tree->node;
                fdims=tree->dims;
            }
            else{
            fdims=frontier->parent->dims;
            }

        for(int i=0;i<fdims;i++){
                    if(frontier[i].node==NULL){
                frontier[i].node=new TREE_NODE<Type>[dimensions];
                       for(int k=0;k<dimensions;k++){
               frontier[i].node[k].dims=0;
               frontier[i].node[k].parent=NULL;
               frontier[i].node[k].node=NULL;
               }
            frontier[i].node->parent=fron;
            frontier[i].dims=dimensions;
                return NULL;
            }
        }
return AddNodeToTree(tree,dimensions,frontier->node);
}



int main(){
TREE<int>* Tree=InitializeTree(Tree,2);     //(tree,numberOfInitialDimensionsForRootNode).
AddNodeToTree(Tree,3);                      //(tree,numberOfDimensions)
AddNodeToTree(Tree,4);
AddNodeToTree(Tree,5);
AddNodeToTree(Tree,6);

cout<<endl;

Tree->node[0].value=0;                      //The root is initialized with 2 nodes
Tree->node[1].value=1;

Tree->node[0].node[0].value=100;            //Root node 0 given 3 nodes
Tree->node[0].node[1].value=101;
Tree->node[0].node[2].value=102;

Tree->node[1].node[0].value=100;            //Root node 1 given 4 nodes
Tree->node[1].node[1].value=101;
Tree->node[1].node[2].value=102;
Tree->node[1].node[3].value=102;

Tree->node[0].node[0].node[0].value=1000;   //Child node 0 of root node 0 given 5 nodes
Tree->node[0].node[0].node[1].value=1001;
Tree->node[0].node[0].node[2].value=1002;
Tree->node[0].node[0].node[3].value=1003;
Tree->node[0].node[0].node[4].value=1004;

Tree->node[0].node[1].node[0].value=1000;   //Child node 1 of root node 0 given 6 nodes
Tree->node[0].node[1].node[1].value=1001;
Tree->node[0].node[1].node[2].value=1002;
Tree->node[0].node[1].node[3].value=1003;
Tree->node[0].node[1].node[4].value=1004;
Tree->node[0].node[1].node[5].value=1005;

/*               ///////Confused? Here's the tree version\\\\\\\\
|                                                         |
|                                                         |
|                                     Root                                |
|                  First child-------|    |------Second child             |
|                 /     |     \                 /    |    |   \           |
|              |||||  |||||| NULL             NULL  NULL NULL NULL        |
|            4 chlrn 5 cldrn                                      |
*/

cout<<"FIN!"<<endl;                         //All finished building the tree and setting values at this point, lets get the dimensions of each brach added to the tree

TREE_NODE<int>* node=Tree->list;
                                                                       //Output:
cout<<"ROOT DIMENSIONS: "<<Tree->dims<<endl;                           //2
cout<<" FIRST CHILD DIMENSIONS: "<<node[0].dims<<endl;                 //3
cout<<"  FIRST FIRST CHILD DIMENSIONS: "<<node[0].node[0].dims<<endl;  //5
cout<<"  FIRST SECOND CHILD DIMENSIONS: "<<node[0].node[1].dims<<endl; //6
cout<<" SECOND CHILD DIMENSIONS: "<<node[1].dims<<endl;                //4
return 0;
}