/** Test binary tree */

package FlexOr.container;

import java.util.Date;
import java.util.Enumeration;

public class TreeTest {

  public static void main (String arg[]) {
    println("Test started " + new Date());
    println("**** Standard Ordered Binary Tree");
    btTest();
    println("**** Heap");
    heapTest();
    println("Test finished " + new Date());
  }
  
  private static void heapTest() {
    try { new Heap(1, new StringGreaterThan(), new StringEqual()); }
    catch (TooSmallException e) { println("Caught too small exception."); }
    
    Heap heap = new Heap(20, new StringGreaterThan(), new StringEqual());
    if (!heap.isEmpty()) println("1  heap not empty");
    if (!(heap.size() == 0)) println("2  heap size is not 0");
    if (!heap.toString().equals("[]")) println("3 toString not []");
    
    heap.add("C"); heap.add("A");  heap.add("G");
    heap.add("P"); heap.add("E");  heap.add("H");
    heap.add("B"); heap.add("J");  heap.add("K");
    
    String str = "[ P K H J E C B A G ]";
    if (!heap.toString().equals(str)) println("4 toString " +
        heap.toString() + " should be " + str);
    
    Heap heap2 = (Heap) heap.clone();
    if (! heap.equals(heap2)) println("5 heap2 " + heap.toString() +
           " not equal to " + heap2.toString());


    String[] strings = new String [heap.size()];
    String tmp;
    int i = 0;
    
    str = "P K J H G E C B A ";
    StringBuffer sb = new StringBuffer();
    while (! heap.isEmpty()) {
      tmp = (String) heap.remove();
      strings[i++] = tmp;
      sb = sb.append(tmp + " ");
    }
    if (! sb.toString().equals(str))
       println("6 heap contained " + sb + " expected " + str);
           
    str = "A B C E G H J K P ";
    sb = new StringBuffer();
    
    heap = new Heap(strings, 20, new StringLessThan(), new StringEqual());
    while (! heap.isEmpty()) {
      sb = sb.append((String) heap.remove() + " ");
    }
    if (! sb.toString().equals(str))
       println("7 heap contained " + sb + " expected " + str);
       
    heap = (Heap) heap2.clone();
    sb = new StringBuffer();
    str = "P K H J E C B A G ";
    
    Enumeration<Object> e = heap.elements();
    while (e.hasMoreElements()) {
      sb = sb.append((String) e.nextElement() + " ");
    }
    if (! sb.toString().equals(str))
       println("8 heap contained " + sb + " expected " + str);
   
  }

  private static void btTest() {
    OrderedBinaryTree tree = new OrderedBinaryTree(new StringLessThan(),
                                                   new StringEqual());
    verify("1", tree, "[]", 0);
        
    OrderedBinaryTree tree2 = (OrderedBinaryTree) tree.clone();
    verify("2", tree2, "[]", 0);

    tree.add("F");
    verify("3", tree, "[F]", 1);
    
    tree.add("C");  tree.add("A"); tree.add("D");
    verify("4", tree, "[[[A]C[D]]F]", 4);
    
    tree2 = (OrderedBinaryTree) tree.clone();
    verify("5", tree2, "[[[A]C[D]]F]", 4);
    
    tree.add("L"); tree.add("N");
    verify("6", tree, "[[[A]C[D]]F[L[N]]]", 6);
    
    tree2 = (OrderedBinaryTree) tree.clone();
    
    tree2.remove();
    verify("7", tree2, "[[C[D]]F[L[N]]]", 5);
    
    tree2.remove();
    verify("8", tree2, "[[D]F[L[N]]]", 4);
    
    tree2.remove();
    verify("9", tree2, "[F[L[N]]]", 3);
    
    tree2.remove();
    verify("10", tree2, "[L[N]]", 2);
    
    tree2.remove();
    verify("11", tree2, "[N]", 1);
    
    tree2.remove();
    verify("12", tree2, "[]", 0);
    
    if (!tree.contains("A")) println("13 should contain A");
    if (!tree.contains("C")) println("13 should contain C");
    if (!tree.contains("D")) println("13 should contain D");
    if (!tree.contains("F")) println("13 should contain F");
    if (!tree.contains("L")) println("13 should contain L");
    if (!tree.contains("N")) println("13 should contain N");
    if (tree.contains("B")) println("13 should not contain B");
    if (tree.contains("E")) println("13 should not contain E");
    if (tree.contains("G")) println("13 should not contain G");
    if (tree.contains("M")) println("13 should not contain M");
    if (tree.contains("P")) println("13 should not contain P");
    
    tree2 = (OrderedBinaryTree) tree.clone();
    if (!tree.equals(tree2)) println("14 trees should be equal");
    tree2.remove();
    if (tree.equals(tree2)) println("15 trees should not be equal");
    tree2.add("B");
    if (tree.equals(tree2)) println("16 trees should not be equal");
    
    tree2 = (OrderedBinaryTree) tree.clone();
    if (tree2.remove("D")) verify("17", tree2, "[[[A]C]F[L[N]]]", 5);
    else println("17 Did not remove D");
    
    tree2.add("D");
    if (tree2.remove("F")) verify("18", tree2, "[[[A]C[D]]L[N]]", 5);
    else println("18 Did not remove F");
    
    tree2 = (OrderedBinaryTree) tree.clone();
    tree2.add("H"); tree2.remove("D");
    if (tree2.remove("F")) verify("19", tree2, "[[A]C[[H]L[N]]]", 5);
    else println("20 Did not remove F");
    
    tree2 = (OrderedBinaryTree) tree.clone();
    tree2.add("H"); tree2.add("E"); tree2.add("G");
    verify("21", tree2, "[[[A]C[D[E]]]F[[[G]H]L[N]]]", 9);
    if (tree2.remove("F"))
        verify("22", tree2, "[[[A]C[D]]E[[[G]H]L[N]]]", 8);
    else println("23 Did not remove F");
    
    verifyTraversal("24", tree.inOrderLRtraversal(), "ACDFLN");
    verifyTraversal("25", tree.inOrderRLtraversal(), "NLFDCA");
    verifyTraversal("26", tree.preOrderLRtraversal(), "FCADLN");
    verifyTraversal("27", tree.preOrderRLtraversal(), "FLNCDA");
    verifyTraversal("28", tree.levelOrderLRtraversal(), "FCLADN");
    verifyTraversal("29", tree.levelOrderRLtraversal(), "FLCNDA");
    verifyTraversal("30", tree.postOrderLRtraversal(), "ADCNLF");
    verifyTraversal("31", tree.postOrderRLtraversal(), "NLDACF");    
  }
  
  private static void println(String item) { System.out.println(item); }
  
  @SuppressWarnings("unused")
private static void print(String item) { System.out.print(item); }
  
  @SuppressWarnings("unused")
private static void printDebug(String item) {
    System.out.print("["+item.length()+"]");
    System.out.print(item);
  }

  private static void verify(String id, OrderedBinaryTree tree, String string,
         int count ) {
    if (!tree.toString().equals(string))
       println(id + " tree.toString() <" + tree.toString() + "> not the " +
         "expected <" + string + ">");
    if (tree.size() != count)
       println(id + " tree count " + tree.size() + " differs from expected " +
          count);
  }
  
  private static void verifyTraversal(String id,
                                      Enumeration<Object> e,
                                      String expected) {
    StringBuffer sb = new StringBuffer();
    while (e.hasMoreElements()) { sb.append(e.nextElement().toString()); }
    String actual = sb.toString();
    if (!actual.equals(expected))
      println(id + " Traversal <" + actual + "> should be <" + expected +
              ">");
  }
}