Need help with adt table
 

Hey everybody

Hope you guys have a great weekend. I am trying to implement a Table ADT to show city name, country, and population. I already did most of the work, but for some reason i get a small error in the main method file.the code is below:

//TestTable(main) class
class TestTable {

public static void displayCity(City c) {
System.out.println(c.getKey());
} // end displayCity

// Main entry point
public static void main(String[] args) {
TableInterface<City, String> chart = new TableBSTBased<City, String>();//this is the line that i get error
City c;

c = new City("Narragansett", "USA", 12000);
chart.tableInsert(c);
c = new City("Ocracoke", "USA", 3000);
chart.tableInsert(c);

}

}
---------------------------------------------------------
//TableInterface class

public interface TableInterface<T extends KeyedItem<KT>,
KT extends Comparable <? super KT>> {

// Table operations:
// Precondition for all operations:
// No two items of the table have the same search key.
// The table's items are sorted by search key.

public boolean tableIsEmpty();
// Determines whether a table is empty.
// Postcondition: Returns true if the table is
// empty; otherwise returns false.

public int tableLength();
// Determines the length of a table.
// Postcondition: Returns the number of items in the
// table.

public void tableInsert(T newItem)
throws TableException;
// Inserts an item into a table in its proper sorted
// order according to the item's search key.
// Precondition: The item to be inserted into the
// table is newItem, whose search key differs from
// all search keys presently in the table.
// Postcondition: If the insertion was successful,
// newItem is in its proper order in the table.
// Otherwise, the table is unchanged, and
// TableException is thrown.

public boolean tableDelete(KT searchKey);
// Deletes an item with a given search key from a
// table.
// Precondition: searchKey is the search key of the
// item to be deleted.
// Postcondition: If the item whose search key equals
// searchKey existed in the table, the item was
// deleted and method returns true. Otherwise, the
// table is unchanged and the method returns false.

public KeyedItem tableRetrieve(KT searchKey);
// Retrieves an item with a given search key from a
// table.
// Precondition: searchKey is the search key of the
// item to be retrieved.
// Postcondition: If the retrieval was successful,
// the table item with the matching search key is
// returned. If no such item exists, the method
// returns a null reference.

} // end TableInterface

--------------------------------------------------------------------------------------
//TableBSTBased class

public class TableBSTBased<T extends KeyedItem<KT>, KT extends Comparable<? super KT>> implements TableInterface<T, KT> {
// binary search tree that contains the tables items
protected BinarySearchTree<T,KT> bst;
protected int size; // number of items in the table

public TableBSTBased() {
bst = new BinarySearchTree<T,KT>();
size = 0;
} // end default constructor

// table operations:
public boolean tableIsEmpty() {
return size == 0;
} // end tableIsEmpty

public int tableLength() {
return size;
} // end tableLength

public void tableInsert(T newItem)
throws TableException {
if (bst.retrieve(newItem.getKey()) == null) {
bst.insert(newItem);
++size;
}
else {
throw new TableException("Table Exception: Insertion"
+ " failed, duplicate key item");
} // end if
} // end tableInsert

public T tableRetrieve(KT searchKey) {
return bst.retrieve(searchKey);
} // end tableRetrieve

public boolean tableDelete(KT searchKey) {
try {
bst.delete(searchKey);
} // end try
catch (TreeException e) {
return false;
} //end catch
--size;
return true;
} // end tableDelete

protected void setSize(int newSize) {
size = newSize;
} // end setSize

} // end TableBSTBased
---------------------------------------------------------------------------------
//KeyedItem class
public abstract class KeyedItem<KT extends Comparable<?super KT>> {
private KT searchKey;

public KeyedItem(KT key) {
searchKey = key;
} // end constructor

public KT getKey() {
return searchKey;
} // end getKey
} // end KeyedItem
----------------------------------------------------------------------------------
//City class
public class City extends KeyedItem<String> {
// city's name will be designated as search key
private String country; // city's country
private int pop; // city's population

public City(String theCity, String theCountry,
int newPop) {
super(theCity); // makes city name the search key
country = theCountry;
pop = newPop;
} // end constructor

public String toString() {
return getKey() + ", " + country + " " + pop;
} // end toString

} // end City
--------------------------------------------------------------------------------------
//treenode class
public class TreeNode<T> {
private T item;
private TreeNode<T> leftChild;
private TreeNode<T> rightChild;

public TreeNode(T newItem) {
// Initializes tree node with item and no children.
item = newItem;
leftChild = null;
rightChild = null;
} // end constructor

public TreeNode(T newItem,
TreeNode<T> left, TreeNode<T> right) {
// Initializes tree node with item and
// the left and right children references.
item = newItem;
leftChild = left;
rightChild = right;
} // end constructor

public T getItem() {
// Returns the item field.
return item;
} // end getItem

public void setItem(T newItem) {
// Sets the item field to the new value newItem.
item = newItem;
} // end setItem

public TreeNode<T> getLeft() {
// Returns the reference to the left child.
return leftChild;
} // end getLeft

public void setLeft(TreeNode<T> left) {
// Sets the left child reference to left.
leftChild = left;
} // end setLeft

public TreeNode<T> getRight() {
// Returns the reference to the right child.
return rightChild;
} // end getRight

public void setRight(TreeNode<T> right) {
// Sets the right child reference to right.
rightChild = right;
} // end setRight
} // end TreeNode
--------------------------------------------------------------------------------------
//bst class
public class BinarySearchTree<T extends KeyedItem<KT>,
KT extends Comparable<? super KT>>
extends BinaryTreeBasis<T> {
// inherits isEmpty(), makeEmpty(), getRootItem(), and
// the use of the constructors from BinaryTreeBasis

public BinarySearchTree() {
} // end default constructor

public BinarySearchTree(T rootItem) {
super(rootItem);
} // end constructor

public void setRootItem(T newItem)
throws UnsupportedOperationException {
throw new UnsupportedOperationException();
} // end setRootItem

public void insert(T newItem) {
root = insertItem(root, newItem);
} // end insert

public T retrieve(KT searchKey) {
return retrieveItem(root, searchKey);
} // end retrieve

public void delete(KT searchKey)
throws TreeException {
root = deleteItem(root, searchKey);
} // end delete

public void delete(T item)
throws TreeException {
root = deleteItem(root, item.getKey());
} // end delete

protected TreeNode<T> insertItem(TreeNode<T> tNode,
T newItem) {
TreeNode<T> newSubtree;
if (tNode == null) {
// position of insertion found; insert after leaf
// create a new node
tNode = new TreeNode<T>(newItem, null, null);
return tNode;
} // end if
T nodeItem = tNode.getItem();

// search for the insertion position

if (newItem.getKey().compareTo(nodeItem.getKey()) < 0) {
// search the left subtree
newSubtree = insertItem(tNode.getLeft(), newItem);
tNode.setLeft(newSubtree);
return tNode;
}
else { // search the right subtree
newSubtree = insertItem(tNode.getRight(), newItem);
tNode.setRight(newSubtree);
return tNode;
} // end if
} // end insertItem

protected T retrieveItem(TreeNode<T> tNode,
KT searchKey) {
T treeItem;
if (tNode == null) {
treeItem = null;
}
else {
T nodeItem = tNode.getItem();
if (searchKey.compareTo(nodeItem.getKey()) == 0) {
// item is in the root of some subtree
treeItem = tNode.getItem();
}
else if (searchKey.compareTo(nodeItem.getKey()) < 0) {
// search the left subtree
treeItem = retrieveItem(tNode.getLeft(), searchKey);
}
else { // search the right subtree
treeItem = retrieveItem(tNode.getRight(), searchKey);
} // end if
} // end if
return treeItem;
} // end retrieveItem

protected TreeNode<T> deleteItem(TreeNode<T> tNode,
KT searchKey) {
// Calls: deleteNode.
TreeNode<T> newSubtree;
if (tNode == null) {
throw new TreeException("TreeException: Item not found");
}
else {
T nodeItem = tNode.getItem();
if (searchKey.compareTo(nodeItem.getKey()) == 0) {
// item is in the root of some subtree
tNode = deleteNode(tNode); // delete the item
}
// else search for the item
else if (searchKey.compareTo(nodeItem.getKey()) < 0) {
// search the left subtree
newSubtree = deleteItem(tNode.getLeft(), searchKey);
tNode.setLeft(newSubtree);
}
else { // search the right subtree
newSubtree = deleteItem(tNode.getRight(), searchKey);
tNode.setRight(newSubtree);
} // end if
} // end if
return tNode;
} // end deleteItem

protected TreeNode<T> deleteNode(TreeNode<T> tNode) {
// Algorithm note: There are four cases to consider:
// 1. The tNode is a leaf.
// 2. The tNode has no left child.
// 3. The tNode has no right child.
// 4. The tNode has two children.
// Calls: findLeftmost and deleteLeftmost
T replacementItem;

// test for a leaf
if ( (tNode.getLeft() == null) &&
(tNode.getRight() == null) ) {
return null;
} // end if leaf

// test for no left child
else if (tNode.getLeft() == null) {
return tNode.getRight();
} // end if no left child

// test for no right child
else if (tNode.getRight() == null) {
return tNode.getLeft();
} // end if no right child

// there are two children:
// retrieve and delete the inorder successor
else {
replacementItem = findLeftmost(tNode.getRight());
tNode.setItem(replacementItem);
tNode.setRight(deleteLeftmost(tNode.getRight()));
return tNode;
} // end if
} // end deleteNode

protected T findLeftmost(TreeNode<T> tNode) {
if (tNode.getLeft() == null) {
return tNode.getItem();
}
else {
return findLeftmost(tNode.getLeft());
} // end if
} // end findLeftmost

protected TreeNode<T> deleteLeftmost(TreeNode<T> tNode) {
if (tNode.getLeft() == null) {
return tNode.getRight();
}
else {
tNode.setLeft(deleteLeftmost(tNode.getLeft()));
return tNode;
} // end if
} // end deleteLeftmost

} // end BinarySearchTree
-------------------------------------------------------------------------------------
//binarytreebasis class
public abstract class BinaryTreeBasis<T> {
protected TreeNode<T> root;

public BinaryTreeBasis() {
root = null;
} // end default constructor

public BinaryTreeBasis(T rootItem) {
root = new TreeNode<T>(rootItem, null, null);
} // end constructor

public boolean isEmpty() {
// Returns true if the tree is empty, else returns false.
return root == null;
} // end isEmpty

public void makeEmpty() {
// Removes all nodes from the tree.
root = null;
} // end makeEmpty

public T getRootItem() throws TreeException {
// Returns the item in the trees root.
if (root == null) {
throw new TreeException("TreeException: Empty tree");
}
else {
return root.getItem();
} // end if
} // end getRootItem

public abstract void setRootItem(T newItem);
// Throws UnsupportedOperationException if operation
// is not supported.

} // end BinaryTreeBasis

-------------------------------------------------------------------------------------
//tableexception class
public class TableException extends RuntimeException {
public TableException(String s) {
super(s);
} // end constructor

private final static long serialVersionUID = 2006L;
} // end TreeException
------------------------------------------------------------------------------------
//treeexception class
public class TreeException extends RuntimeException {
public TreeException(String s) {
super(s);
} // end constructor

private final static long serialVersionUID = 2006L;
} // end TreeException

Sorry if it looks like long, i dont know how else to put the code here.
I get the error in the testTable class. I would apperciate if you guys could help with my problem as soon as possible.

Thank you

Re: Need help with adt table
 

No wonder no one has responded yet to this thread. You have not used code tags while adding your code and have pasted the complete thing, Just looking at the darned thing will most probably chase away anyone and everyone with an intention to help you.
I do not know what is the problem with most of you beginners not using code tags, its as simple as just adding two lines one [ code=java ] before your code and [ /code ] (without the spaces between [(or ]) and code) after it, despite it being mentioned in the community rules and the announcements at the top of the forum.

Re: Need help with adt table
 

Also try to reduce the amount of code you post. Just post the relevant parts. Add the exact error messages or example output to show us the problem.

Re: Need help with adt table
 

class TestTable {



    public static void displayCity(City c) {

        System.out.println(c.getKey());

    }  // end displayCity



    // Main entry point

    public static void main(String[] args) {

        TableInterface<City, String> chart =

                new TableBSTBased<City, String>();

        City c;

        c = new City("Narragansett", "USA", 12000);

        chart.tableInsert(c);

        c = new City("Ocracoke", "USA", 3000);

        chart.tableInsert(c);



        // If a table iterator class called TableIteratorBST

        // is available for the class TableBSTBased (as created

        // in Programming Problem 2, you can also do the

        // following:

        TableIteratorBST<City> iter = new TableIteratorBST<City>(chart);

        while (iter.hasNext()) {

            displayCity(iter.next());

        } // end while

    } // end main

} // end TestTable

You need implement own TableIteratorBST.java class
For all, who want to help read first http://www.cs.auckland.ac.nz/compsci105s2c/
You have TreeIterator.java example
quuba