/**
    Test cases for Assignment 4, CS 146, Spring 2002.
    Here, four different implementations of the
    Lexicographical interface are used, and three
    different lexicographically based sorting
    algorithms are applied to arrays of each type.
*/

import java.util.*;


public class A4
{

  /** @return a random string of lower case characters,
            of random length from 3 through 9.
  */
  // The string is constructed by taking characters
  //   randomly and uniformly chosen from the alphabet.
  // Since the method to get the size of the alphabet
  //   can't be both static and part of the Lexicographical
  //   interface, we instantiate a dummy TrieString from
  //   which we can get this size.
  // Here we use the property of TrieStrings that the
  //   alphabet is the same for each character position.

  public static TrieString makeRandomTrieString(Random r)        {
    int len=3+r.nextInt(7);
    TrieString ts=new TrieString("");
    int alphabetSize = ts.getAlphabetSize();
    StringBuffer s=new StringBuffer(len);
    for (int i=0; i<=len; i++)
      s.append((char) ((int)'a' + r.nextInt(
                         ts.getAlphabetSize()-1)));
    return new TrieString(new String(s));                        }





  public static void main(String[] args)            {
    TrieString ts=new TrieString("");

    // These objects are needed only to get the
    //   alphabet size for their class, as in
    //   the makeRandomTrieString method.
    // As in that method, we rely on the fact
    //   that the underlying alphabet is the same
    //   for each position, for each of the 3 classes

    TrieInteger ti= new TrieInteger(0,4);
    TrieIntegerString tis= new TrieIntegerString(0);
    TriColor tc=new TriColor();

    // Create an empty trie for each class

    Trie t= new Trie(ts.getAlphabetSize());
    Trie t2= new Trie(ti.getAlphabetSize());
    Trie t3= new Trie(tis.getAlphabetSize());
    Trie t4= new Trie(tc.getAlphabetSize());


    // Create a random array for each class

    java.util.Random r=new java.util.Random(1);
    Lexicographical[] a=new Lexicographical[100];
    Lexicographical[] b=new Lexicographical[100];
    Lexicographical[] c=new Lexicographical[100];
    Lexicographical[] d=new Lexicographical[100];

    for (int i=0; i<a.length; i++)                 {
      a[i]=makeRandomTrieString(r);
      b[i]=new TrieInteger(r.nextInt(10000),4);
      c[i]=new TrieIntegerString(r.nextInt(10000));
      d[i]=new TriColor(r);                        }


    // Make copies of these arrays, since radixSort
    //   and bucketSort (but not the use of tries)
    //   will modify them

    Lexicographical[] a1 =
        (Lexicographical[]) a.clone();
    Lexicographical[] b1 =
        (Lexicographical[]) b.clone();
    Lexicographical[] c1 =
        (Lexicographical[]) c.clone();
    Lexicographical[] d1 =
        (Lexicographical[]) d.clone();
    Lexicographical[] a2 =
        (Lexicographical[]) a.clone();
    Lexicographical[] b2 =
        (Lexicographical[]) b.clone();
    Lexicographical[] c2 =
        (Lexicographical[]) c.clone();
    Lexicographical[] d2 =
        (Lexicographical[]) d.clone();


    // Insert all of the array data into the tries
    //   for the appropriate class

    for (int i=0; i<a.length; i++)          {
      t.insert(a[i]);
      t2.insert(b[i]);
      t3.insert(c[i]);
      t4.insert(d[i]);                      }


    // Sort the TrieString arrays, using the
    //   three different sorting algorithms,

    // after printing the unsorted data

    for (int i=0; i<a.length; i++)
      System.out.print(a[i]+" ");
    System.out.println("");
    System.out.println("");

    t.traverse();
    System.out.println("");
    System.out.println("");

    LexUtils.radixSort(a,2);
    for (int i=0; i<a.length; i++)
      System.out.print(a[i]+" ");
    System.out.println("");
    System.out.println("");

    LexUtils.radixSort(a1,4);
    for (int i=0; i<a1.length; i++)
      System.out.print(a1[i]+" ");
    System.out.println("");
    System.out.println("");

    LexUtils.bucketSort(a2);
    for (int i=0; i<a2.length; i++)
      System.out.print(a2[i]+" ");
    System.out.println("");
    System.out.println("");


    // do the same tests for TrieIntegers

    for (int i=0; i<b.length; i++)
      System.out.print(b[i]+" ");
    System.out.println("");
    System.out.println("");

    t2.traverse();
    System.out.println("");
    System.out.println("");

    LexUtils.radixSort(b,2);
    for (int i=0; i<b.length; i++)
      System.out.print(b[i]+" ");
    System.out.println("");
    System.out.println("");

    LexUtils.radixSort(b1,4);
    for (int i=0; i<b1.length; i++)
      System.out.print(b1[i]+" ");
    System.out.println("");
    System.out.println("");

    LexUtils.bucketSort(b2);
    for (int i=0; i<b2.length; i++)
      System.out.print(b2[i]+" ");
    System.out.println("");
    System.out.println("");


    // do the same tests for TrieIntegerStrings

    for (int i=0; i<c.length; i++)
      System.out.print(c[i]+" ");
    System.out.println("");
    System.out.println("");

    t3.traverse();
    System.out.println("");
    System.out.println("");

    LexUtils.radixSort(c,2);
    for (int i=0; i<c.length; i++)
      System.out.print(c[i]+" ");
    System.out.println("");
    System.out.println("");

    LexUtils.radixSort(c1,4);
    for (int i=0; i<c1.length; i++)
      System.out.print(c1[i]+" ");
    System.out.println("");
    System.out.println("");

    LexUtils.bucketSort(c2);
    for (int i=0; i<c2.length; i++)
      System.out.print(c2[i]+" ");
    System.out.println("");
    System.out.println("");


    // do the same tests for TriColors

    for (int i=0; i<d.length; i++)
      System.out.print(d[i]+" ");
    System.out.println("");
    System.out.println("");

    t4.traverse();
    System.out.println("");
    System.out.println("");

    LexUtils.radixSort(d,2);
    for (int i=0; i<d.length; i++)
      System.out.print(d[i]+" ");
    System.out.println("");
    System.out.println("");

    LexUtils.radixSort(d1,4);
    for (int i=0; i<d1.length; i++)
      System.out.print(d1[i]+" ");
    System.out.println("");
    System.out.println("");

    LexUtils.bucketSort(d2);
    for (int i=0; i<d2.length; i++)
      System.out.print(d2[i]+" ");
    System.out.println("");
    System.out.println("");


}

};