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

Recommended Answers

All 3 Replies

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.

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.

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

commented: if you've gone thorugh all that muck you deserve this one, but dont do it everytime, cause then these guys will never pay attention to the rules or use code tags +3
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.