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
