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