search-heap/SearchHeap.java

/**
 * SearchHeap:
 *     Implementation of a Search Heap of type T.
 * 
 * Designed and written by Jonathan E. Landrum.
 * 
 * Copyright (c) 2014-2015 Jonathan E. Landrum. All Rights Reserved.
 */

// Warnings are suppressed for easier compilation
@SuppressWarnings("unchecked")

public class SearchHeap<T> {
    // Root element
    private Node<T> root = new Node<T>();
    
    // Insertion point initially set to root
    private Node<T> ins = root;
    
    // Children and level counts
    private int numLevels = -1;
    
    /*
     * Constructors 
     */
    public SearchHeap() { }
    public SearchHeap(Node<T> r) {
        root = r;
        numLevels = 0;
    }
    
    /*
     * Getters
     */
    public int getNumLevels() { return numLevels; }
    public int getNumElements() { return root.getNumElements(); }
    public T getMin() { return root.getMin(); }
    public T getMax() { return root.getMax(); }
    /*
     * getNthMin():
     *     This method returns the nth minimum element in the heap.
     *     
     * Parameter:
     *     int n - The order of the element to be returned.
     * 
     * Note:
     *     This function expects a natural number for input. Non-
     *     natural input will throw an exception. An input of "1" will
     *     return the smallest element in the collection, functionally
     *     equivalent to calling getMin().
     */
    public T getNthMin(int n) {
        // Define a current node that initially points to root
        Node<T> current = root;
        
        // Short circuit for erroneous input
        if (n > current.getNumElements() || n < 1) {
            throw new IndexOutOfBoundsException(n);
        }
        
        do {
            // Check if we're at the correct node
            if (n == 1) { return current.getMin(); }
            if (n - current.getNumElements() == 0) {
                if (current.hasMax()) {
                    return current.getMax();
                } else {
                    // We only get here if the algorithm selects this node,
                    // but it shouldn't have
                    throw new UnknownErrorException();
                }
            }
            
            // Recur through the tree to find the correct node
            if ((current.hasLeftChild()) &&
                (n <= current.getLeftChild().getNumElements() + 1)) {
                /*
                 * This block says our target is not current's min
                 * (the +1 part), but our target is in current's left subtree
                 * (the current.getLeftChild().getNumElements() part).
                 */
                
                // Subtract 1 from n to represent passing up current.getMin() as an option
                --n;
                
                // Change what current points to
                current = current.getLeftChild();
            } else if (current.hasRightChild()) {
                /*
                 * This block says our target is in current's right subtree.
                 */
                
                // Subtract the total number of elements in the left subtree and middle subtree + 1 from n
                // to represent passing up the left and middle subtrees as an option
                n = n - current.getLeftChild().getNumElements() - 1;
                
                // Change what current points to
                current = current.getRightChild();
            } else {
                /*
                 * We only get here if current has no children (is a leaf),
                 * but n > 2, an obvious error, given the checks at the
                 * beginning of the loop
                 */
                throw new UnknownErrorException();
            }
        } while (n > 0);
        
        // We only get here if something goes completely awry
        throw new UnknownErrorException();
    }
    /*
     * getNthMax():
     *     This method returns the nth maximum element in the heap.
     *     
     * Parameter:
     *     int n - The order of the element to be returned.
     * 
     * Note:
     *     This function expects a natural number for input. Non-
     *     natural input will throw an exception. An input of "1" will
     *     return the largest element in the collection, functionally
     *     equivalent to calling getMax().
     */
    public T getNthMax(int n) {
        // Define a current node that initially points to root
        Node<T> current = root;
        
        // Short circuit for erroneous input
        if (n > current.getNumElements() || n < 1) { throw new IndexOutOfBoundsException(n); }
        
        do {
            // Check if we're at the correct node
            if (n == 1) { return current.getMax(); }
            if (n - current.getNumElements() == 0) {
                if (current.hasMin()) {
                    return current.getMin();
                } else {
                    // We only get here if the algorithm selects this node, but it shouldn't have
                    throw new UnknownErrorException();
                }
            }
            
            // Recur through the tree to find the correct node
            if ((current.hasRightChild()) && (n <= current.getRightChild().getNumElements() + 1)) {
                /*
                 * This block says our target is not current's max (the +1 part),
                 * but our target is in current's right subtree (the current.getRightChild().getNumElements() part).
                 */
                
                // Subtract 1 from n to represent passing up current.getMax() as an option
                --n;
                
                // Change what current points to
                current = current.getRightChild();
            } else if (current.hasMidChild()) {
                // We have to be careful here, because we can't assume current has a right child
                // in the same way we could assume current has a left child in getNthMin().
                if ((current.hasRightChild()) && (n <= current.getRightChild().getNumElements() + current.getMidChild().getNumElements() + 1)) {
                    /*
                     * This block says our target is not current's max (the +1 part),
                     * and our target is not in current's right subtree (the current.getRightChild().getNumElements() part),
                     * but our target *is* in current's middle subtree (the current.getMidChild().getNumElements() part).
                     */
                    
                    // Subtract the total number of elements in the right subtree + 1 from n
                    // to represent passing up current.getMax() as well as current's right subtree as an option
                    n = n - current.getRightChild().getNumElements() - 1;
                } else {
                    // Otherwise, if current doesn't have a right child, just subtract 1 to represent passing up current.getMax().
                    --n;
                }
                
                // Change what current points to
                current = current.getMidChild();
            } else if (current.hasLeftChild()) {
                /*
                 * This block says we've exhausted our options, and our target has to be in current's left subtree.
                 */
                if (current.hasMidChild()) {
                    // We have to be careful here, too, just as above
                    if (current.hasRightChild()) {
                        // Subtract the total number of elements in the right and middle subtrees + 1 from n
                        // to represent passing up current.getMax() as well as current's right and middle subtrees as options
                        n = n - current.getRightChild().getNumElements() - current.getMidChild().getNumElements() - 1;
                    } else {
                        // Otherwise, if current doesn't have a right child, subtract the total number of elements
                        // from the middle subtree + 1 to represent passing up the middle subtree and current.getMax().
                        n = n - current.getMidChild().getNumElements() - 1;
                    }
                    // Otherwise, if there is no middle child and no right child,
                    // just subtract 1 to represent passing up current.getMax().
                    --n;
                }
                
                // Change what current points to
                current = current.getLeftChild();
            } else {
                /*
                 * We only get here if current has no children (is a leaf), but n != 1 and n != 2,
                 * an obvious error, given the checks at the beginning of the loop
                 */
                throw new UnknownErrorException();
            }
        } while (n > 0);
        
        // We only get here if something goes completely awry
        throw new UnknownErrorException();
    }
    
    /*
     * insert():
     *     This method adds a new element to the heap.
     * 
     * Calls:
     *     reheap()
     *     
     *     //////////////////\\\\\\\\\\\\\\\\\\
     *     TO DO: Implement This
     *     \\\\\\\\\\\\\\\\\\//////////////////
     *     
     * Parameter:
     *     T element - The element to be inserted into the heap.
     * 
     * Note :
     *     The structure of this method forms a natural less-than-
     *     or-equal-to relation. As the collection has a least element,
     *     it thus forms a total ordering.
     */
    public void insert(T element) {
        // Define a current node that initially references the insertion point
        Node<T> current = ins;
        
        // Insert the element
         if (!current.hasMin()) {
            /* 
             * The node is completely empty; insert the element as current's min.
             */
            current.setMin(element);
        } else if (!current.hasMax()) {
            /*
             * The node is partially empty; determine which value goes in which slot.
             */
            if (current.getMin().compareTo(element) > 0) {
                // Current's min is greater than the element, so
                // it becomes max and the element becomes min.
                current.setMax(current.getMin());
                current.setMin(element);
            } else {
                // Current's min is less than or equal to the
                // element, so the element becomes the max.
                current.setMax(element);
            }
        } else {
            /*
             * The insertion point is full. Create a new node to hold
             * the element, and determine where to put the new node.
             */
            Node<T> newNode = new Node<T>(element);
            
            // Check to see where the new node goes.
            if (current.hasParent()) {
                /*
                 * Avoids null pointer exceptions when current points to root.
                 */
                if (current.isLeftChild()) {
                    // Current is a left child, so newNode becomes the middle child.
                    // Point the three nodes at each other.
                    current.setRightSibling(newNode);
                    current.getParent().setMidChild(newNode);
                    newNode.setLeftSibling(current);
                    newNode.setParent(current.getParent());
                } else if (current.isMidChild()) {
                    // Current is a middle child, so newNode becomes the right child.
                    // Point the three nodes at each other.
                    current.setRightSibling(newNode);
                    current.getParent().setRightChild(newNode);
                    newNode.setLeftSibling(current);
                    newNode.setParent(current.getParent());
                } else {
                    /*
                     * Current is a right child. Determine if we need to
                     * move to a right subtree or create a new level.
                     */
                    
                    // Iterate current up the tree until a right sibling is found. If no right sibling
                    // is found, current is an external node, and a new level should be created.
                    while (!current.hasRightSibling()) {
                        if (current.hasParent()) {
                            // Move current to the parent node.
                            current = current.getParent();
                            
                            // Check to see if the new current has a right sibling.
                            if (current.hasRightSibling()) {
                                // Move current into adjacent subtree and terminate the loop.
                                current = current.getRightSibling();
                                break;
                            }
                        } else {
                            // Current is the root node. Increment the
                            // number of levels and terminate the loop.
                            ++numLevels;
                            break;
                        }
                    }
                    
                    // Iterate through the tree until the bottom row is reached.
                    while (current.hasLeftChild()) {
                        current = current.getLeftChild();
                    }
                    
                    // Point current and the new node at each other.
                    current.setLeftChild(newNode);
                    newNode.setParent(current);
                        
                }
            } else {
                /*
                 * This case only happens when the insertion point is the root.
                 */
                
                // Point the two nodes at each other.
                current.setLeftChild(newNode);
                newNode.setParent(current);
            }
            
            // Point ins at the new node.
            ins = newNode;
        }
    }
}