FHlazySearchTree.java

import java.util.NoSuchElementException;
import cs_1c.Traverser;

public class FHlazySearchTree<E extends Comparable<? super E>> implements
      Cloneable {
   protected int mSize;
   protected int mSizeHard;
   protected FHlazySTNode<E> mRoot;

   public FHlazySearchTree() {
      clear();
   }

   public boolean empty() {
      return (mSize == 0);
   }

   public int size() {
      return mSize;
   }

   public int sizeHard() {
      return mSizeHard;
   }

   public void clear() {
      mSize = 0;
      mSizeHard = 0;
      mRoot = null;
   }

   public int showHeight() {
      return findHeight(mRoot, -1);
   }

   public E findMin() {
      if (mRoot == null || findMin(mRoot) == null)
         throw new NoSuchElementException();
      return findMin(mRoot).data;
   }

   public E findMax() {
      if (mRoot == null || findMax(mRoot) == null)
         throw new NoSuchElementException();
      return findMax(mRoot).data;
   }

   public E find(E x) {
      FHlazySTNode<E> resultNode;
      resultNode = find(mRoot, x);
      if (resultNode == null)
         throw new NoSuchElementException();
      return resultNode.data;
   }

   public boolean contains(E x) {
      return find(mRoot, x) != null;
   }

   public boolean insert(E x) {
      int oldSize = mSize;
      mRoot = insert(mRoot, x);
      return (mSize != oldSize);
   }

   public boolean remove(E x) {
      int oldSize = mSize;
      mRoot = remove(mRoot, x);
      return (mSize != oldSize);
   }

   public <F extends Traverser<? super E>> void traverse(F func) {
      traverse(func, mRoot);
   }

   public Object clone() throws CloneNotSupportedException {
      FHlazySearchTree<E> newObject = (FHlazySearchTree<E>) super.clone();
      newObject.clear(); // can't point to other's data

      newObject.mRoot = cloneSubtree(mRoot);
      newObject.mSize = mSize;
      newObject.mSizeHard = mSizeHard;

      return newObject;
   }

   public boolean collectGarbage() {
      int oldSize = mSizeHard;
      collectGarbage(mRoot);
      return (mSizeHard != oldSize);
   }

   // private helper methods ----------------------------------------
   protected FHlazySTNode<E> findMin(FHlazySTNode<E> root) {
      if (root == null)
         return null;
      FHlazySTNode<E> leftChild = findMin(root.lftChild);
      // if the left side does exist
      if (leftChild != null)
         return leftChild;
      if (!root.deleted)
         return root;
      // this entire subtree does not have min, move to the right side
      return findMin(root.rtChild);
   }

   protected FHlazySTNode<E> findMax(FHlazySTNode<E> root) {
      if (root == null)
         return null;
      FHlazySTNode<E> rightChild = findMax(root.rtChild);
      if (rightChild != null)
         return rightChild;
      if (!root.deleted)
         return root;
      return findMax(root.lftChild);
   }

   protected FHlazySTNode<E> findMaxHard(FHlazySTNode<E> root) {
      // Same as normal BST findMax()
      if (root == null)
         return null;
      if (root.rtChild == null)
         return root;
      return findMaxHard(root.rtChild);
   }

   protected FHlazySTNode<E> findMinHard(FHlazySTNode<E> root) {
      // Same as normal BST findMin()
      if (root == null)
         return null;
      if (root.lftChild == null)
         return root;
      return findMinHard(root.lftChild);
   }

   protected FHlazySTNode<E> insert(FHlazySTNode<E> root, E x) {
      int compareResult; // avoid multiple calls to compareTo()

      if (root == null) {
         mSize++;
         mSizeHard++;
         // adding as a leaf
         return new FHlazySTNode<E>(x, null, null);
      }

      compareResult = x.compareTo(root.data);
      if (compareResult < 0)
         root.lftChild = insert(root.lftChild, x);
      else if (compareResult > 0)
         root.rtChild = insert(root.rtChild, x);
      else if (root.deleted) {
         // replacement is valid
         root.deleted = false;
         mSize++;
         return root;
      }
      return root;
   }

   protected FHlazySTNode<E> remove(FHlazySTNode<E> root, E x) {
      int compareResult;

      if (root == null)
         return null;

      compareResult = x.compareTo(root.data);
      if (compareResult < 0) {
         root.lftChild = remove(root.lftChild, x);
      } else if (compareResult > 0) {
         root.rtChild = remove(root.rtChild, x);
      } else {
         // found the node - make deleted true
         if (!root.deleted) {
            root.deleted = true;
            mSize--;
         }
      }
      return root;
   }

   protected FHlazySTNode<E> hardRemove(FHlazySTNode<E> root, E x) {
      int compareResult; // avoid multiple calls to compareTo()
      if (root == null)
         return null;
      compareResult = x.compareTo(root.data);
      if (compareResult < 0 && root.lftChild != null)
         root.lftChild = hardRemove(root.lftChild, x);
      else if (compareResult > 0 && root.rtChild != null)
         root.rtChild = hardRemove(root.rtChild, x);
      else {
         if (root.lftChild != null && root.rtChild != null) {
            // requires checks for mSize and mSizeHard validation
            FHlazySTNode<E> replacement = findMinHard(root.rtChild);
            root.data = replacement.data;
            if (root.deleted)
               mSize++;
            if (!replacement.deleted)
               root.deleted = false;
            root.rtChild = hardRemove(root.rtChild, root.data);
            if (x.equals(mRoot.data))
               mRoot = root;
         } else {
            mSizeHard--;
            if (!root.deleted)
               mSize--;
            root = (root.lftChild != null) ? root.lftChild : root.rtChild;
            if (x.equals(mRoot.data))
               mRoot = root;
         }
      }
      return root;
   }

   protected <F extends Traverser<? super E>> void traverse(F func,
         FHlazySTNode<E> treeNode) {
      if (treeNode == null)
         return;
      traverse(func, treeNode.lftChild);
      if (!treeNode.deleted) {
         func.visit(treeNode.data);
      }
      traverse(func, treeNode.rtChild);
   }

   protected FHlazySTNode<E> find(FHlazySTNode<E> root, E x) {
      int compareResult; // avoid multiple calls to compareTo()

      if (root == null)
         return null;

      compareResult = x.compareTo(root.data);
      if (compareResult < 0)
         return find(root.lftChild, x);
      if (compareResult > 0)
         return find(root.rtChild, x);
      if (root.deleted)// found a deleted node
         return null;
      return root; // found
   }

   protected FHlazySTNode<E> cloneSubtree(FHlazySTNode<E> root) {
      FHlazySTNode<E> newNode;
      if (root == null)
         return null;

      // does not set myRoot which must be done by caller
      newNode = new FHlazySTNode<E>(root.data, cloneSubtree(root.lftChild),
            cloneSubtree(root.rtChild));
      return newNode;
   }

   protected int findHeight(FHlazySTNode<E> treeNode, int height) {
      int leftHeight, rightHeight;
      if (treeNode == null)
         return height;
      height++;
      leftHeight = findHeight(treeNode.lftChild, height);
      rightHeight = findHeight(treeNode.rtChild, height);
      return (leftHeight > rightHeight) ? leftHeight : rightHeight;
   }

   protected void collectGarbage(FHlazySTNode<E> root) {
      if (root == null) {
         return;
      }
      // traverses down to leaves first to prevent hardRemoving subtrees
      collectGarbage(root.lftChild);
      collectGarbage(root.rtChild);
      if (root.deleted) {
         hardRemove(mRoot, root.data);
      }
   }
}

FHlazySTNode.java

public class FHlazySTNode<E extends Comparable< ? super E > >
{
   // use public access so the tree or other classes can access members 
   public FHlazySTNode<E> lftChild, rtChild;
   public E data;
   public FHlazySTNode<E> myRoot;  // needed to test for certain error
   public boolean deleted;

   public FHlazySTNode( E d, FHlazySTNode<E> lft, FHlazySTNode<E> rt )
   {
      lftChild = lft; 
      rtChild = rt;
      data = d;
   }
   
   public FHlazySTNode()
   {
      this(null, null, null);
   }
   
   // function stubs -- for use only with AVL Trees when we extend
   public int getHeight() { return 0; }
   boolean setHeight(int height) { return true; }
}

Main.java

// CIS 1C Assignment #4
// Instructor Solution Client

import java.io.IOException;
import java.util.NoSuchElementException;

import cs_1c.*;

class PrintObject<E> implements Traverser<E> {
   public void visit(E x) {
      System.out.print(x + " ");
   }
};

// ------------------------------------------------------
public class Main {
   // ------- main --------------
   public static void main(String[] args) throws Exception {
      mainProgramTesting();
      extraCreditTesting();
   }

   public static void mainProgramTesting() throws CloneNotSupportedException {
      int k;
      FHlazySearchTree<Integer> searchTree = new FHlazySearchTree<Integer>();
      PrintObject<Integer> intPrinter = new PrintObject<Integer>();

      searchTree.traverse(intPrinter);

      System.out.println("\ninitial size: " + searchTree.size());
      searchTree.insert(50);
      searchTree.insert(20);
      searchTree.insert(30);
      searchTree.insert(70);
      searchTree.insert(10);
      searchTree.insert(60);

      System.out.println("After populating -- traversal and sizes: ");
      searchTree.traverse(intPrinter);
      System.out.println();
      checkTreeSizes(searchTree);

      System.out.println("Collecting garbage on new tree - should be "
            + "no garbage.");
      treeCollectGarbage(searchTree);
      System.out.println();
      checkTreeSizes(searchTree);

      // test assignment operator
      FHlazySearchTree<Integer> searchTree2 = (FHlazySearchTree<Integer>) searchTree
            .clone();
      System.out.println("\n\nAttempting 1 removal: ");
      if (searchTree.remove(20))
         System.out.println("removed " + 60);
      System.out.println();
      checkTreeSizes(searchTree);

      System.out.println("Collecting Garbage - should clean 1 item. ");
      treeCollectGarbage(searchTree);
      System.out.println();
      checkTreeSizes(searchTree);

      System.out.println("Collecting Garbage again - no change expected. ");
      treeCollectGarbage(searchTree);
      System.out.println();
      checkTreeSizes(searchTree);

      // test soft insertion and deletion:

      System.out.println("Adding 'hard' 22 - should see new sizes. ");
      searchTree.insert(22);
      searchTree.traverse(intPrinter);
      System.out.println();
      checkTreeSizes(searchTree);

      System.out.println("\nAfter soft removal. ");
      searchTree.remove(22);
      searchTree.traverse(intPrinter);
      System.out.println();
      checkTreeSizes(searchTree);

      System.out.println("Repeating soft removal. Should see no change. ");
      searchTree.remove(22);
      searchTree.traverse(intPrinter);
      System.out.println();
      checkTreeSizes(searchTree);

      System.out.println("Soft insertion. Hard size should not change. ");
      searchTree.insert(22);
      searchTree.traverse(intPrinter);
      System.out.println();
      checkTreeSizes(searchTree);

      System.out.println("\n\nAttempting 100 removals: ");
      for (k = 100; k > 0; k--) {
         if (searchTree.remove(k)) {
            System.out.println("removed " + k);
            System.out.println();
            checkTreeSizes(searchTree);
            checkTreeSizes(searchTree2);
         }
      }
      searchTree.traverse(intPrinter);
      treeCollectGarbage(searchTree);

      System.out.println("\nsearch_tree now:");
      searchTree.traverse(intPrinter);
      System.out.println();
      checkTreeSizes(searchTree);
      searchTree.traverse(intPrinter);

      System.out.println("\n\nsearchTree2:\n\n");
      checkTreeSizes(searchTree2);
      searchTree2.insert(500);
      searchTree2.insert(200);
      searchTree2.insert(300);
      searchTree2.insert(700);
      searchTree2.insert(100);
      searchTree2.insert(600);
      searchTree2.traverse(intPrinter);
      System.out.println("\nPost insertion:");
      checkTreeSizes(searchTree2);
      System.out.println("\nRemoving every element except 700");
      System.out.println("Finding min of tree 2 : " + searchTree2.findMin());
      for (int i = 0; i < 700; i++) {
         if (searchTree2.remove(i)) {
            System.out.println("removed " + i);
            System.out.println("Finding min of tree 2 : "
                  + searchTree2.findMin());
            System.out.println("Finding max of tree 2 : "
                  + searchTree2.findMax());
         }
      }
      System.out.println("\nTesting after removal");
      System.out.println("Is mRoot still (hard)existing? : "
            + (searchTree2.mRoot != null));
      System.out.println("Is mRoot still (soft)existing? : "
            + (!searchTree2.mRoot.deleted));
      System.out.println("mRoot data: " + searchTree2.mRoot.data);

      System.out.println("Trying to find 50 using find()");
      try {
         searchTree2.find(50);
         System.out.println("50 is found : " + searchTree2.find(50));
      } catch (NoSuchElementException e) {
         System.out
               .println("50 is not found. This should be expected because 50 is soft-removed");
      }
      // remove the last node
      checkTreeSizes(searchTree2);
      System.out.println("Removing last undeleted node(700)");
      searchTree2.remove(700);
      treeCollectGarbage(searchTree2);
      System.out.println("\nAfter collectGarbage()");
      checkTreeSizes(searchTree2);
      System.out.println("Is mRoot still (hard)existing? : "
            + (searchTree2.mRoot != null));
      try {
         // an error should occur - all the nodes are deleted
         System.out.println("Finding min of tree 2 : " + searchTree2.findMin());
      } catch (NoSuchElementException e) {
         System.out
               .println("No such element exception occured because findMin() found 0 nodes.\n");
      }
      checkTreeSizes(searchTree2);
      System.out
            .println("\nRepopulating tree 0-499, and then deleting 200-399.");
      for (int i = 0; i < 500; i++) {
         searchTree2.insert(i);
      }
      for (int i = 200; i < 400; i++) {
         searchTree2.remove(i);
      }
      checkTreeSizes(searchTree2);
      treeCollectGarbage(searchTree2);
      checkTreeSizes(searchTree2);
   }

   public static void extraCreditTesting() {
      // ------------EXTRA CREDIT PORTION------------------

      System.out.println("\n\nExtra Credit portion\n\n");
      EBookEntry[] bookArray = null;
      try {
         bookArray = initializeEBooks();
      } catch (IOException e) {
         System.out.println("Unable to load.");
      }
      FHlazySearchTree<EBookEntry> bookTree = new FHlazySearchTree<EBookEntry>();
      PrintObject<EBookEntry> bookPrinter = new PrintObject<EBookEntry>();
      EBookEntry.setSortType(EBookEntry.SORT_BY_ID);
      for (int i = 0; i < bookArray.length; i++) {
         bookTree.insert(bookArray[i]);
      }

      System.out.println("The # of EBookEntries : " + bookArray.length);
      checkTreeSizes(bookTree);
      for (int i = 0; i < 2000; i++) { // soft remove half the books
         bookTree.remove(bookTree.findMax());
      }
      System.out.println("After removing 2000 books");
      checkTreeSizes(bookTree);
      treeCollectGarbage(bookTree);
      checkTreeSizes(bookTree);
      for (int i = 0; i < 2850; i++) {
         bookTree.remove(bookTree.findMax());
      }
      System.out
            .println("After removing 2850 more books (Should have 13 left)");
      bookTree.traverse(bookPrinter);
      checkTreeSizes(bookTree);
      treeCollectGarbage(bookTree);
      checkTreeSizes(bookTree);
      for (int i = 0; i < bookArray.length; i++) {
         bookTree.insert(bookArray[i]);
      }
      System.out.println("Recharged books");
      checkTreeSizes(bookTree);
      System.out.println("Find the first entry from bookArray");
      System.out.println(bookTree.find(bookArray[0]));
      for (int i = 0; i < 1500; i++) {
         bookTree.remove(bookArray[i]);
      }
      System.out.println("Removed 1500 books.");
      checkTreeSizes(bookTree);
      treeCollectGarbage(bookTree);
      checkTreeSizes(bookTree);
      bookTree.clear();
      System.out.println("Cleared all books.");
      checkTreeSizes(bookTree);
      bookTree.traverse(bookPrinter);
      System.out
            .println("Nothing should be printed above, because there is 0 size.");
      treeCollectGarbage(bookTree);
      checkTreeSizes(bookTree);
      System.out.println("");
   }

   public static EBookEntry[] initializeEBooks() throws IOException {
      EBookEntryReader bookInput = new EBookEntryReader("catalog-short4.txt");
      int arraySize;

      // how we test the success of the read:
      if (bookInput.readError()) {
         System.out.println("couldn't open " + bookInput.getFileName()
               + " for input.");
         throw new IOException();
      }
      System.out.println("Successfully read from " + bookInput.getFileName());
      // create an array of objects for our own use:
      arraySize = bookInput.getNumBooks();
      EBookEntry[] bookArray = new EBookEntry[arraySize];
      for (int k = 0; k < arraySize; k++)
         bookArray[k] = bookInput.getBook(k);
      return bookArray;
   }

   public static <E> void treeCollectGarbage(
         FHlazySearchTree<? extends Comparable<? super E>> tree) {
      System.out.println("Garbage collecting...");
      tree.collectGarbage();
   }

   public static <E> void checkTreeSizes(
         FHlazySearchTree<? extends Comparable<? super E>> tree) {
      System.out.println("The tree's soft size: " + tree.size()
            + " and its hard size: " + tree.sizeHard());
   }

}