/***************************/
/* Tree building functions */
/***************************/

Tree Build(ItemNo Fp, ItemNo Lp, int Dep, Tree Node);
        /* Returns an optimal decision tree of depth at most Dep <= 2 
	      for Item[Fp..Lp],	Fp <= Lp.
	   Node is the optimal leaf for Item[Fp..Lp]. */
	   
Tree Build2Contin(ItemNo Fp, ItemNo Lp, Attribute Att, int Dep, Tree Node);
        /* Returns an optimal decision tree of depth at most Dep <= 2
	      for Item[Fp..Lp], Fp <= Lp, 
	      where the root is a continous split on attribute Att.
	   Node is the optimal leaf for Item[Fp..Lp]. */

Tree Build2Discr(ItemNo Fp, ItemNo Lp, Attribute Att, int Dep, Tree Node);
        /* Returns an optimal decision tree of depth at most Dep <= 2
	      for Item[Fp..Lp], Fp <= Lp, 
	      where the root is a discrete branch on attribute Att.
	   Node is the optimal leaf for Item[Fp..Lp]. */
	  
ItemNo InitContinArrays(ItemNo Fp, ItemNo Lp, Attribute Att);
       /* Sorts Item[Fp..Lp] and returns the index Kp of the first item with
             known continuous attribute Att.
	  Sets Error_L,Error_U[Kp..Lp] to Infinity. */
	  
void SecondSplitContin(ItemNo Fp, ItemNo Lp, Attribute Att1, Attribute Att2);
     /* Split Item[Fp..Lp] first on continuous Att1, then on continuous Att2. 
        If this gives better results than the best privious ones, 
	   store them in ContinArrays. 
	Att1 might be None. */

void SecondSplitDiscr(ItemNo Fp, ItemNo Lp, Attribute Att1, Attribute Att2);
     /* Split Item[Fp..Lp] first on continuous Att1, then on discrete Att2. 
        If this gives better results than the best privious ones, 
	   store them in ContinArrays. */

Tree IntervalTest(Attribute Att, IntervalSplit IntSpl);	
     /* Returns a decision tree with interval split on attribute Att at the root.
        All necessary information must be contained in IntSpl. */

Tree DiscrTest(ItemNo Fp, ItemNo Lp, Attribute Att);	
     /* Returns a decision tree for Item[Fp..Lp] with a discrete branch 
           on attribute Att at the root. */

Tree MakeLeaf(ClassNo C, ItemCount Freq, ItemCount Error);
        /* Returns a leaf node with BestClass = C, Freq, and Error */	   
	   
	   
/***************************************************/
/* Procedures for creating optimal interval splits */
/***************************************************/

SuperList InitSuperList(ItemNo Fp, ItemNo Lp, Attribute Att1, Attribute Att2);
             /* Returns a Superlist of Item[Fp..Lp] on continous attributes Att1, Att2.
	        Att1 might be None. */

void MergeSuperList(SuperList SL);
     /* Merges the elements in SL until only 1 element remains. 
        SL != Nil. */	   
	
AllList InitAllList(ItemList IL, Attribute Att1, Attribute Att2);
        /* Returns an AllList of the items in IL where Att1 is the y-value and 
	      Att2 is the x-value.
	   Att1 might be None.
	   All items are assumed to have identical Att2 values and to be sorted on Att1. */

AllList MergeAllLists(AllList AL1, AllList AL2);
        /* Merges AllLists AL1 and AL2 destroying both, and returns the result.
	   Assumes that all x-values in AL1 are smaller than all x-values in AL2 */	
	   
AllList MergeIntervals(AllList AL1, AllList AL2);
           /* Merges the first elements of AL1, AL2 and returns the result
	         as a one element AllList.
              Assumes that the x-values of AL1 are smaller than the x-values of AL2.
              AL1 and AL2 are not modified. */           	   
	
void MergeInts(AllIntervals I1, AllIntervals I2, AllIntervals I);
        /* Merges the intervals in I1 and I2 into I.
	   Assumes that the values in I1 are smaller than the values in I2. */	   


/*******************/
/* List procedures */
/*******************/

ItemList MakeItemList(ItemNo Fp, ItemNo Lp);
            /* Returns an ItemList consisting of Item[Fp..Lp]. */
	    
ItemList SortItemList(ItemList IL, int Length, Attribute Att);	    
            /* Returns IL sorted on continuous attribute Att.
	       IL is destroyed. 
	       Length must be the number of items in IL. 
	       The order of elements with the same Att value is not changed. */

void ReleaseItemList(ItemList IL);
     /* Removes IL from memory. */
	
	
/*****************/
/* Miscellaneous */
/*****************/

void Error(int n, String s1, String s2);
        /* Prints an error message */

void Sort(ItemNo Fp, ItemNo Lp, Attribute Att);
        /* Sorts Item[Fp..Lp] on continuous attribute Att. */

ItemNo Group(ItemNo Fp, ItemNo Lp, Attribute Att, DiscrValue V);
       /* Groups together all items with disrcete Att value V and returns 
             the index of the last item with attribute value V.
          I.e. DVal(Item[Lp..Kp], Att) == V when Group returns Kp. */
	  
void Swap(ItemNo i1, ItemNo i2);
        /* Swaps Item[i1] and Item[i2]. */	  

void MoveIntervals(IntervalSplit *IntSplS, IntervalSplit *IntSplD);
        /* Moves the content of IntSplS to IntSplD. The content of IntSplS is destroyed. */
        	
void InitFreq(ItemNo Fp, ItemNo Lp, Attribute Att);
        /* Initializes the freqency global arrays with the values for Item[Fp..Lp] 
              and discrete attribute Att.
           Att might be None. */
	
	
/****************************************/
/* Initialization and release functions */
/****************************************/

AllList MakeALRecord();   
           /* Returns an initialized ALRecord. */
	   
void ReleaseAllList(AllList AL);
        /* Removes AllList AL from memory. */
	
AllIntervals MakeAllIntervals();
                /* Returns an initialized AllIntervals array. */	   
	
void ReleaseAllIntervals(AllIntervals AllInt);
        /* Removes AllInt from memory. */	
	
SuperList RemoveElSL(SuperList SL);
             /* Removes the first element of SuperList SL and returns the 
	           remaining SuperList.
		SL != Nil. */