/* An implementation of a binary search tree in POV-Ray */

/* Node format:
 *  A string of the format "L;R;V;D", where
 *  L is the array index of the left subchild of the node, or -1 for NULL
 *  R is the array index of the right subchild of the node, or -1 for NULL
 *  V is a flag: 1 means the node contains valid data, 0 means the node has been deleted
 *  D is the data stored at the node
 *  Due to a bug in POV-Ray, L, R, and A may contain leading spaces
 *
 *  A value of "-1" stored in an array element means that element is free memory.
 *  Likewise, if #ifdef(_BST_Memory) returns false, the element is free memory.
 */

/********** Utility macros **********/

/* L, R, V, and D must be identifiers, not R-values, so that they are passed by reference. */
/* Breaks a node up into its component strings, and returns those strings by reference */
#macro Tokenize_Data(L, R, V, D, String)
    #local Ltemp = "";
    #local Rtemp = "";
    #local Vtemp = "";
    #local Dtemp = "";
    #local state = 0;
    
    #local char = 0;
    
    #while(char <= strlen(String))
        #if(strcmp(substr(String, char, 1), ";") = 0)
            #declare state = state + 1;
        #else
            #switch(state)
                #case(0)
                    #declare Ltemp = concat(Ltemp,substr(String, char, 1)); 
                #break
                #case(1)
                    #declare Rtemp = concat(Rtemp,substr(String, char, 1)); 
                #break
                #case(2)
                    #declare Vtemp = concat(Vtemp,substr(String, char, 1));
                #break
                #else
                    #declare Dtemp = concat(Dtemp,substr(String, char, 1)); 
                #break
            #end
        #end
        #declare char = char + 1;
    #end
    #declare L = Ltemp;
    #declare R = Rtemp;
    #declare V = Vtemp;
    #declare D = Dtemp;
#end

#macro MakeData(L, R, V, D)
    concat(L, ";", R, ";", V, ";", D)
#end 

#macro Parse_String(String)
    #fopen FOut "parse_string.tmp" write
    #write(FOut,String)
    #fclose FOut
    #include "parse_string.tmp"
#end

/********** Memory-handling macros ***********/

/* Return an array index to an available element in the _BST_Memory array */
#macro _BST_NEW()
    #declare _BST_TEMP = 1;
    #local Done = false;
    #local TotalMem = dimension_size(_BST_Memory, 1);
    #while(!Done)
        #ifndef(_BST_Memory[_BST_TEMP]) 
            #declare Done = true;
        #end
        #declare _BST_TEMP = _BST_TEMP + 1;
        #if(_BST_TEMP = TotalMem)
            #declare Done = true;
            #declare _BST_TEMP = -1;
        #end
    #end
    #if(_BST_TEMP = -1)
        #error "Out of memory"
    #end
    (_BST_TEMP - 1)
#end

/********** Data-management functions **********/

/* "Data" is a string containing the data to insert in the tree.
 * "Root" is the array element that is the root of the subtree under consideration */
#macro _Insert(Data, Root)
    #local L = "";
    #local R = "";
    #local V = "";
    #local D = "";
    Tokenize_Data(L, R, V, D, _BST_Memory[Root])
    #local Comp = Parse_String(_BST_COMPFUNC) (Data, D);
    #if(Comp != 0)
        #if(Comp < 0)
            #if(val(L) =  -1)
                /* Insert node */
                #local NewNode = _BST_NEW();
                #declare _BST_Memory[NewNode] = MakeData("-1","-1","1",Data);
                #declare _BST_Memory[Root] = MakeData(str(NewNode,0,0), R, V, D);
            #else
                _Insert(Data, val(L))
            #end
        #else
            #if(val(R) = -1)
                /* Insert node */
                #local NewNode = _BST_NEW();
                #declare _BST_Memory[NewNode] = MakeData("-1","-1","1",Data);
                #declare _BST_Memory[Root] = MakeData(L, str(NewNode,0,0), V, D);
            #else
                _Insert(Data, val(R))
            #end
        #end
    #end
#end

#macro Insert(Data)
    #ifdef(_BST_Memory[0])
        _Insert(Data,0) 
    #else
        #declare _BST_Memory[0] = MakeData("-1", "-1", "1", Data);
    #end
#end

#macro _Inorder(Root, Function)
    #local L = "";
    #local R = "";
    #local V = "";
    #local D = "";
    #if(Root != -1)
        Tokenize_Data(L, R, V, D, _BST_Memory[Root])
        _Inorder(val(L), Function)
        Parse_String(Function) (D)
        _Inorder(val(R), Function)
    #end
#end
    
/* Do an inorder traversal of the tree, applying "Function" to each node */    
#macro Inorder_Traverse(Function)
    _Inorder(0, Function)
#end

/* Implementation */
#declare S = seed(394875);
#declare _BST_Memory = array[100]
#declare _BST_COMPFUNC = "strcmp";
Insert("M")
Insert("G")
Insert("S")
#declare Counter = 0;
#while(Counter < 10)
    #declare Z = chr(rand(S)*26 + 65)
    Insert(Z)
    #declare Counter = Counter + 1;
#end

#macro Print(a)
    #debug a
#end

Inorder_Traverse("Print")
#debug "\n"