Final Assignment for CS310 Fall 2010

Let's start working on the Assignment.

It says that You will create a class to represent Trees, and a Map class that is implemented using a chained hash table.

And it also says that You will write a simple application that performs queries on family tree (genealogical) data.

Where should I gat started????

/* 
<span style="font-size:x-large;">This is the list what professor gave us</span>.

<span style="color:#0033FF;">* Class Tree<T></span>

*1295476711*Class Node<T>
import java.util.*;

/**
 * Represents a node of the Tree < T > class. 
 */
class Node < T > {

    // a data object of type T
    public T data;
    // a List < Node < T > > of children nodes
    public List<Node<T>> children;
    // a reference to this node's Node < T > parent
    public Node<T> parent;
   
    /**
     * Default constructor
     */
    public Node() { }
 
    /**
     * Constructor for creating a Node<T> with an instance of T.
     * @param data an instance of T.
     */
    public Node(T data) { }
     
    /**
     * Return the children of this node
     * @return List < Node < T > > of the children 
     */
    public List < Node < T > > getChildren() { 
  // if there are no children then the returned List is empty
  
    }
   
    /**
     * Return the parent of this node. 
     * @return parent Node<T>
     */
    public Node < T  > getParentNode() {}

    /**
     * set the parent of this node. 
     * @param parent of this Node < T >
     */
    public void setParentNode(Node < T > parent) {}
    
    /**
     * Returns the number of immediate children of this node.
     * @return number of immediate children.
     */
    public int getNumberOfChildren() { 

    }
     
    /**
     * Adds a child to the list of children for this node. The addition of
     * the first child will create a new List < Node < T > >.
     * @param child a Node < T > object to add.
     * @return the Node < T> with added new child.     
     */
    public Node<T> addChild(T child) { }
    
    /**
     * get a child from the list of children for this node. 
     * @param child T to get.
     * @return the node < T > of the child.   
     */     
    public Node<T> getChild(T  child) throws ChildNotFoundException { 
 
    }    

    /**
     * Remove a child from the list of children for this node. 
     * @param child T to remove.
     */     
    public void removeChild(T  child) throws ChildNotFoundException { 
      
    }

    /**
     * Return the data of this node. 
     * @return T data object of this node
     */  
    public T getData() {}
 
    /**
     * Set the T data object of this node. 
     * @parm T data object to set
     */
    public void setData(T data) { }
     
    /**
     * Return a String representation of the node, this includes the T data objects
     * of this node and its children, and the parent of this node. (See output from main().)
     * @return String representation of the node
     */
    public String toString() {    

    }
    
    public static void main(String[] args) {
     System.out.println("Build Tree");
     System.out.println("  0  ");
     System.out.println(" / \\ ");
     System.out.println("1   2");    
     System.out.println("|   |");
     System.out.println("3   4");     
     
     Node<Integer> n0 = new Node<Integer>(new Integer(0));
  Node<Integer> n1 = n0.addChild(new Integer(1));
     Node<Integer> n2 = n0.addChild(new Integer(2));    
     Node<Integer> n3 = n1.addChild(new Integer(3));    
     Node<Integer> n4 = n2.addChild(new Integer(4)); 
  System.out.println();
  
     System.out.println("Display Tree");
     ArrayList<Node<Integer>> nodeArray = new ArrayList<Node<Integer>>();
     nodeArray.add(n0);nodeArray.add(n1);nodeArray.add(n2);
     for (int i=0; i<3; i++) {
      Node<Integer> node = nodeArray.get(i);
      int numChildren = node.getNumberOfChildren();
      System.out.println("Child " + node.getData() + " has " + numChildren + (numChildren>1?" children: ":" child: "));
      List<Node<Integer>> L = node.getChildren();
      Iterator iter = L.iterator();
      while (iter.hasNext()) {
       Node<Integer> child = (Node<Integer>) iter.next();
       Integer childData = child.getData();
       Node<Integer> parent = child.getParentNode();
       Integer parentData = parent.getData();
       System.out.println("Child " + childData + " of parent " + parentData);
      }
      System.out.println();
     }
     
     System.out.println("Test toString on n0: ");
     System.out.println(n0);  
     System.out.println();
     
     System.out.println("Test removeChild: remove child 4 of 2 and child 2 of 0:"); 
     try {
      n2.removeChild(new Integer(4));
      n0.removeChild(new Integer(2));
       System.out.println(n0); 
       System.out.println(n2);
       System.out.println();
  } catch(ChildNotFoundException e) {
    System.out.println("removeChild fails");
    }    
      
    System.out.println("Test getChild:");  
      try {
       n1 = n0.getChild(new Integer(1));
     System.out.println("getChild(1) passes");        
    } catch(ChildNotFoundException e) {
    System.out.println("getChild fails");
    }    
      try {
       n2 = n0.getChild(new Integer(2));
    } catch(ChildNotFoundException e) {
     System.out.println("getChild(2) passes"); 
    }
    System.out.println();
      
     System.out.println("Test setData: setData of n1 to 11:");        
      n1.setData(new Integer(11));
      System.out.println(n1);
   }
}

*1295476712*Class ChainedHashTable
import java.util.*;

public class ChainedHashTable <T > {
    private static final int DEFAULT_TABLE_SIZE = 101;

    /** array of Lists. */
    private List<T> [ ] theLists; 
    
    // number of elements in hash table
  private int currentSize;
  
    /**
     * Construct the hash table.
     */
    public ChainedHashTable( ) { }

    /**
     * Insert into the hash table. If the item is
     * already present, then do nothing.
     * @param x the item to insert.
     */
    public void insert( T x )  {  
    // use doHash(x) to get the hash code for x

    }
    
    /**
     * Find an element in the hash table. Return a reference
     * to the item if it is present; otherwise, return null.
     * @param x the item to find.
     */
    public T find( T x )  {  }    

    /**
     * Remove from the hash table.
     * @param x the item to remove.
     */
    public void remove( T x ) {  }

    /**
     * Determine whether an item is in the hash table.
     * @param x the item to search for.
     * @return true if x is found.
     */
    public boolean contains( T x ) {  }

    /**
     * Make the hash table logically empty.
     */
    public void makeEmpty( ) {  }
    
    /**
     * return the number of elements in the hash table.
     */
    public int size( )  {  } 
    
    /**
     * return true if the hash table is empty.
     */
    public boolean isEmpty( ) { }     
    

    private int doHash( T x )
    {
        int hashVal = x.hashCode( );

        hashVal %= theLists.length;
        if( hashVal < 0 )
            hashVal += theLists.length;

        return hashVal;
    }
    
    public static void main( String [ ] args )
    {
        ChainedHashTable<Integer> Table = new ChainedHashTable<Integer>( );

        for( int i = 0; i < 10; i++ )
            Table.insert( i );
            
        boolean allFound = true;
        for( int i = 0; i < 10; i++ ) {
          boolean T_F = Table.contains(i);
          if (!T_F) {
           allFound = false;
           break;
          }
        } 
        
        if (allFound) {
          System.out.println("insert() and contains() pass");
        }        
            
        allFound = true;
        int j=0;
        for( int i = 0; i < 10; i++ ) {
          Integer x = Table.find(i);
    if (j > 0) {
     System.out.print(", ");
    }  
    System.out.print(x);
          if (x == null) {
           allFound = false;
           break;
          }
          j++;
        }
        
        if (allFound) {
          System.out.println("find() passes");
        }
        
        for( int i = 0; i < 10; i++ )
            Table.remove( i );
            
        boolean foundAny = false;
        for( int i = 0; i < 10; i++ ) {
          Integer x = Table.find(i);
          if (x != null) {
           foundAny = true;
           break;
          }
        }  

        if (!foundAny) {
          System.out.println("remove() passes");
        }

   Table.makeEmpty();
   
   if (Table.isEmpty() && Table.size() ==0) 
      System.out.println("makeEmpty(), isEmpty(), and size pass()");
    }

}

*1295476713*Class MyMap
import java.util.*;

public class MyMap<KeyType, ValueType> {
 public MyMap() {
  items = new ChainedHashTable<Entry<KeyType,ValueType>>(); 
 } 
 
 /* map key to value. Create a new (key,val) Entry and store it in the ChainedHashTable. */
 public void put( KeyType key, ValueType val ) { 

 } 

 /* get the value that key is mapped to by retrieving the Entry from the ChainedHashTable. */
 public ValueType get( KeyType key ) { 
 } 

 /* return true if the map is empty; otherwise, return false. */
 public boolean isEmpty() { 

 }
 
 /* return the size of the map */
 public int size() {

 }

 /* make the map empty. */
 public void makeEmpty() { 
 
 }

 private ChainedHashTable<Entry<KeyType,ValueType>> items; 

 /* An Entry is a (key,value) pair */
 public static class Entry<KeyType, ValueType> {
 // Note: KeyType and ValueType should provide toString() methods
  private KeyType key;
  private ValueType val;
  
  Entry( KeyType k, ValueType v ) {
   key=k;
   val=v;
  }

  public int hashCode() {
   return key.hashCode();
  }

  public boolean equals( Object rhs ) {
  // Two Entry objects are equal if they have the same key value.  
   return rhs instanceof Entry && 
   key.equals( ((Entry<KeyType, ValueType>)rhs).key ); 
  } 
  
  public KeyType getKey() {return key;}
  public ValueType getValue() {return val;}
  public String toString() {
   return (key.toString() + "," + val.toString());
  }
 }
 
   public static void main( String [ ] args ) {
        MyMap<String,String> M = new MyMap<String,String>( );

        System.out.println("Insert Carver and Nordstrom.");
        M.put("Carver","CS310-003");
        M.put("Nordstrom","CS310-002");
        System.out.println("Insert Carver again.");
        M.put("Carver","CS310-001");
        System.out.println("M.size: " + M.size());
        System.out.println("Get Carver: " + M.get("Carver"));
        System.out.println("is empty: " + M.isEmpty()); 
        System.out.println("Make empty"); 
        M.makeEmpty();
        System.out.println("is empty: " + M.isEmpty()); 
   }
}


</span>
*?

Those are Java codes.

Also He gave us the description of the application.

I'll keep posting my progress here.

Check it out man!! lol