/* NOTE: Each of these classes belong in their own .java file These classes are only the ones I wrote for this assignment; they rely on a number of other classes provide by the instructor for this assignment. See the zip file for all relevant classes. */ /* -- PART 1: Vector-based implementation of a list -- */ import java.util.Vector; /** * A vector-based (not that you need to know that) list of Objects. * * @author Zach Tomaszewski * @date 29 Sept 2001 */ public class ListVectorBased implements ListInterface { Vector vector; public ListVectorBased() { vector = new Vector(); } /** * Determines whether this list contains any elements. * * @returns true if there are no elements; false otherwise */ public boolean isEmpty(){ return vector.isEmpty(); } /** * Returns the number of elements in this list. * * @returns The number of elements in this list. */ public int size(){ return vector.size(); } /** * Inserts an item at the specified position on the list, shifting all other * items in the list up one position. * * @param position The position at which to insert the item * @param item The Object to insert * @throws ListIndexOutOfBoundsException * if (position < 1 || position > size() + 1) */ public void add(int position, Object item) throws ListIndexOutOfBoundsException{ try{ vector.add(position - 1, item); }catch (ArrayIndexOutOfBoundsException aioobe){ throw new ListIndexOutOfBoundsException("Position at which to add " + "is not within list range."); } } /** * Returns the item at the specified position on the list. * The list is unchanged. * * @param position The position to retrieve * @throws ListIndexOutOfBoundsException * if (position < 1 || position > size() + 1) */ public Object get(int position) throws ListIndexOutOfBoundsException{ try{ return vector.get(position - 1); }catch (ArrayIndexOutOfBoundsException aioobe){ throw new ListIndexOutOfBoundsException("Position to retrieve " + "is not within list range."); } } /** * Removes the item at the specified position from the list. * All items with higher positions are shifted down. * * @param position The position to remove * @throws ListIndexOutOfBoundsException * if (position < 1 || position > size() + 1) */ public void remove(int position) throws ListIndexOutOfBoundsException{ try{ vector.remove(position - 1); }catch (ArrayIndexOutOfBoundsException aioobe){ throw new ListIndexOutOfBoundsException("Position to remove " + "is not within list range."); } } /** * Removes all items with this list and sets the size to zero. */ public void removeAll(){ vector.clear(); } }//end class /* PART 2 of the assignment: linked lists */ /** * An ordered list of Objects. Objects can be duplicated in the list. * Uses a linked list and tediously implements recursive calls in the place * of any iterative loop. * * @author Zach Tomaszewski (javadoc based on that of SortedListInterface by Dan Suthers) * @date 29 Sept 2001 */ public class SortedListRecursiveLinked implements SortedListInterface{ private Node head; private int size; public SortedListRecursiveLinked() { head = null; size = 0; } /** * Determines whether a sorted list is empty. * @return boolean true if it is empty. */ public boolean isEmpty(){ return (size == 0); } /** * Returns the number of items that are in a sorted list. * @return int number of items in the list. */ public int sortedSize(){ return size; } /** * Inserts item into its proper sorted position in a sorted list. * @param item The item to add * @precondition item is comparable to all items in the list, which has * not yet reached its maximum capacity. * @postcondition item has been inserted in its proper position, shifting * other items up in position if necessary. * sortedSize() is incremented by one. * @exception Throws an exception if the item cannot be placed on the list. */ public void sortedAdd(Comparable item) throws ImplementationLimitException { Node prev = this.locateNode(item, true); if (prev == null){ //head of the list Node newNode = new Node(item, head); head = newNode; }else if (prev.getNext() == null){ //end of the list prev.setNext(new Node(item)); }else { Node newNode = new Node(item, prev.getNext()); prev.setNext(newNode); } this.size++; } /** * Deletes item from a sorted list. * @param item, a Comparable object * @precondition item is present in the list * @postcondition item has been removed from the list, shifting * other items down in position if necessary. * sortedSize() is decremented by one. * @exception throws ItemNotFoundException if the item is not found. */ public void sortedRemove(Comparable item) throws ItemNotFoundException{ int position = this.locatePosition(item); Node curr, prev; if (position <= 0) { //not in the list throw new ItemNotFoundException("Could not find item to delete."); }else if (position == 1){ // deleting head head = head.getNext(); this.size--; }else if (position == this.sortedSize()) { //deleting end prev = this.locateNode(item, true); prev.setNext(null); this.size--; }else { //somewhere in the list prev = this.locateNode(item, true); curr = prev.getNext(); prev.setNext(curr.getNext()); this.size--; } } /** * Returns the item at position of a sorted list. * @param position an int * @return a Comparable Object found at position * @precondition position is in range [1 .. sortedSize()] * @postcondition The list is left unchanged. * @exception Throws an exception if the position is out of range. */ public Comparable sortedGet(int position) throws InvalidPositionException{ if (position < 1 || position > this.sortedSize()) { throw new InvalidPositionException("Provided position " + "is out of list range."); }else{ Node curr = head; curr = this.findPositionNode(curr, 1, position); return (Comparable)curr.getItem(); } } /** * A recursive way to find a node corresponding with a certain position * (rather than a for loop) */ private Node findPositionNode (Node curr, int currPosition, int findPosition){ if (currPosition == findPosition) { // we're there return curr; }else { return findPositionNode(curr.getNext(), ++currPosition, findPosition); } } /** * Returns the position where the item is in a sorted list, or -1 * if it is not found. Item and the list are unchanged. * @param item a Comparable object to be positioned in the list. * @return an int giving the position in [1 .. sortedSize()] or -1 * Returns the item at position of a sorted list. * @precondition item is Comparable to all objects on the list * @postcondition The list is left unchanged. */ public int locatePosition(Comparable item){ int counter = 1; Node curr = head; return findNodePosition(item, curr, counter); } private int findNodePosition (Comparable item, Node curr, int currPosition){ if (curr == null) { //hit the end return -1; }else if (((Comparable)curr.getItem()).compareTo(item) == 0) { //we found it return currPosition; }else { return this.findNodePosition(item, curr.getNext(), ++currPosition); } } /** * A utility method to find a node or position. * * @param item Item to find * @param returnPreviousNode if set to true, this method will return the * node just previous to the one that matches the correct position. * Note that if the item belongs at the head of the list, prev will * be null. * @returns the node corresponding to the position where the item * should be placed. */ private Node locateNode(Comparable item, boolean returnPreviousNode) { int counter = 1; Node curr = head; Node prev = null; return findItemNode(item, prev, curr, returnPreviousNode); } /* overloaded locatedNode method */ private Node locateNode(Comparable item){ return this.locateNode(item, false); } private Node findItemNode(Comparable item, Node prev, Node curr, boolean returnPrevNode){ if (curr == null) { // end of the list, item goes here return (returnPrevNode) ? prev : curr; }else if (((Comparable)curr.getItem()).compareTo(item) >= 0) { //we just passed everything smaller; item goes here return (returnPrevNode) ? prev : curr; }else { //still looking return findItemNode(item, curr, curr.getNext(), returnPrevNode); } } }//end class /** * An ordered list of Objects. Objects can be duplicated in the list. * Uses a linked list and iterative methods. * * @author Zach Tomaszewski (javadoc based on that of SortedListInterface by Dan Suthers) * @date 29 Sept 2001 */ public class SortedListIterativeLinked implements SortedListInterface{ private Node head; private int size; public SortedListIterativeLinked() { head = null; size = 0; } /** * Determines whether a sorted list is empty. * @return boolean true if it is empty. */ public boolean isEmpty(){ return (size == 0); } /** * Returns the number of items that are in a sorted list. * @return int number of items in the list. */ public int sortedSize(){ return size; } /** * Inserts item into its proper sorted position in a sorted list. * @param item The item to add * @precondition item is comparable to all items in the list, which has * not yet reached its maximum capacity. * @postcondition item has been inserted in its proper position, shifting * other items up in position if necessary. * sortedSize() is incremented by one. * @exception Throws an exception if the item cannot be placed on the list. */ public void sortedAdd(Comparable item) throws ImplementationLimitException { Node prev = this.locateNode(item, true); if (prev == null){ //head of the list Node newNode = new Node(item, head); head = newNode; }else if (prev.getNext() == null){ //end of the list prev.setNext(new Node(item)); }else { Node newNode = new Node(item, prev.getNext()); prev.setNext(newNode); } this.size++; } /** * Deletes item from a sorted list. * @param item, a Comparable object * @precondition item is present in the list * @postcondition item has been removed from the list, shifting * other items down in position if necessary. * sortedSize() is decremented by one. * @exception throws ItemNotFoundException if the item is not found. */ public void sortedRemove(Comparable item) throws ItemNotFoundException{ int position = this.locatePosition(item); Node curr, prev; if (position <= 0) { //not in the list throw new ItemNotFoundException("Could not find item to delete."); }else if (position == 1){ // deleting head head = head.getNext(); this.size--; }else if (position == this.sortedSize()) { //deleting end prev = this.locateNode(item, true); prev.setNext(null); this.size--; }else { //somewhere in the list prev = this.locateNode(item, true); curr = prev.getNext(); prev.setNext(curr.getNext()); this.size--; } } /** * Returns the item at position of a sorted list. * @param position an int * @return a Comparable Object found at position * @precondition position is in range [1 .. sortedSize()] * @postcondition The list is left unchanged. * @exception Throws an exception if the position is out of range. */ public Comparable sortedGet(int position) throws InvalidPositionException{ if (position < 1 || position > this.sortedSize()) { throw new InvalidPositionException("Provided position " + "is out of list range."); }else{ Node curr = head; for (int i = 1; i < position; i++){ curr = curr.getNext(); } return (Comparable)curr.getItem(); } } /** * Returns the position where the item is in a sorted list, or -1 * if it is not found. Item and the list are unchanged. * @param item a Comparable object to be positioned in the list. * @return an int giving the position in [1 .. sortedSize()] or -1 * @precondition item is Comparable to all objects on the list * @postcondition The list is left unchanged. */ public int locatePosition(Comparable item){ int counter = 1; Node curr = head; while (counter <= this.sortedSize()){ if (((Comparable)curr.getItem()).compareTo(item) == 0) { return counter; }else{ curr = curr.getNext(); counter++; } } return -1; //didn't find it } /** * A utility method to find a node or position. * * @param item Item to find * @param returnPreviousNode if set to true, this method will return the * node just previous to the one that matches the correct position. Note that if the item belongs at the head of the list, prev will be null. * @returns the node corresponding to the position where the item * should be placed. */ private Node locateNode(Comparable item, boolean returnPreviousNode) { int counter = 1; Node curr = head; Node prev = null; while (counter <= this.sortedSize() && ((Comparable)curr.getItem()).compareTo(item) < 0){ prev = curr; curr = curr.getNext(); counter++; } return (returnPreviousNode) ? prev : curr; } private Node locateNode(Comparable item){ return this.locateNode(item, false); } }//end class /** * A utility class of nodes to be used in implementing linked lists. * * @author Zach Tomaszewski * @date 29 Sept 2001 * @see SortedListInterativeLinked, SortedListRecursiveLinked */ class Node { private Object item; //the item each node will contain private Node nextNode; protected Node(Object item, Node nextNode) { this.item = item; this.nextNode = nextNode; } protected Node(Object item){ this.item = item; this.nextNode = null; } /** * returns the next node in the list */ protected Node getNext(){ return this.nextNode; } /** * returns the object contained by this node */ protected Object getItem(){ return this.item; } /** * updates the link from this node to the next */ protected void setNext(Node nextNode){ this.nextNode = nextNode; } /** * removes the link from this node to the next (sets it to null) */ protected void removeNext() { this.nextNode = null; } }//end class