/* NOTE: These classes should all be in their own .java files. See the zips for all classes relevant to this assignment, including those provided by the instructor. */ /* PART 1 */ /** * An array-based, linked list of Objects. * * @author Zach Tomaszewski * @date 06 Oct 2001 */ public class ListArrayBasedLinks implements ListInterface { static final int DEFAULT_SIZE = 50; ArrayNode[] arrayFrame; int head, free, size; /** * Creates a new of default capacity. */ public ListArrayBasedLinks() { this(DEFAULT_SIZE); } /** * Creates a new list of the specified capacity. */ public ListArrayBasedLinks(int capacity) { this.arrayFrame = new ArrayNode[capacity]; //fill with free nodes, except first and last indices int i; //need this below, outside of the for loop for (i = 0; i < capacity-1; i++){ arrayFrame[i] = new ArrayNode(null, i+1); } //the last node with a dead end arrayFrame[i] = new ArrayNode(null); this.free = 0; this.head = -1; this.size = 0; } /** * Determines whether this list contains any elements. * * @returns true if there are no elements; false otherwise */ public boolean isEmpty(){ return (size==0); } /** * Returns the number of elements in this list. * * @returns The number of elements in this list. */ public int size(){ return 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, ListException{ if (this.size >= arrayFrame.length) { //this list has reached capacity; throw new ListException("Cannot add item: " + "No more room in the list."); }else if (position < 1 || position > size() + 1){ throw new ListIndexOutOfBoundsException("Cannot add time: " + "Position out of bounds."); }else if (position == 1) { //adding to head int newNodeIndex = free; free = arrayFrame[free].getNext(); if (head == -1) { //new head arrayFrame[newNodeIndex] = new ArrayNode(item); }else{ //already a head; move it over arrayFrame[newNodeIndex] = new ArrayNode(item, head); } head = newNodeIndex; size++; }else{ int prev = -1; int currIndex = head; for (int i = 1; i < position; i++){ prev = currIndex; currIndex = arrayFrame[currIndex].getNext(); } int newNodeIndex = free; free = arrayFrame[free].getNext(); arrayFrame[newNodeIndex] = new ArrayNode(item, currIndex); arrayFrame[prev].setNext(newNodeIndex); size++; } } /** * 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()) */ public Object get(int position) throws ListIndexOutOfBoundsException{ if (position < 1 || position > size()){ throw new ListIndexOutOfBoundsException("Cannot add time: " + "Position out of bounds."); }else{ int tempIndex = head; for (int i = 1; i < position; i++){ tempIndex = arrayFrame[tempIndex].getNext(); } return arrayFrame[tempIndex].getItem(); } } /** * 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{ if (position < 1 || position > size() + 1){ throw new ListIndexOutOfBoundsException("Cannot add time: " + "Position out of bounds."); }else{ int prev = -1; int currIndex = head; for (int i = 1; i < position; i++){ prev = currIndex; currIndex = arrayFrame[currIndex].getNext(); } if (prev < 0) { //removing at head head = arrayFrame[currIndex].getNext(); }else { arrayFrame[prev].setNext(arrayFrame[currIndex].getNext()); } arrayFrame[currIndex] = new ArrayNode(null, free); free = currIndex; size--; } } /** * Removes all items with this list and sets the size to zero. */ public void removeAll(){ //the quick way to do it; maintains the same list length though. // this(arrayFrame.length); } }//end class /** * A utility class of nodes to be used in implementing linked lists. * Nodes are indexed by ints, rather than references to the other nodes. * These nodes are thus best used in an array-based implemenation of a list. * * @author Zach Tomaszewski * @date 06 Oct 2001 * @see ListArrayBasedLinks */ class ArrayNode { private Object item; //the item each node will contain private int nextNode; protected ArrayNode(Object item, int nextNode) { this.item = item; this.nextNode = nextNode; } protected ArrayNode(Object item){ this.item = item; this.nextNode = -1; } /** * returns the next node in the list */ protected int 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(int nextNode){ this.nextNode = nextNode; } /** * removes the link from this node to the next (sets it to null) */ protected void removeNext() { this.nextNode = -1; } }//end class /* === PART 2 of the assignment */ /** * A model of an infite, editable tape for a Turing machine. * * @author Zach Tomaszewski * @date 06 Oct 2001 */ public class EditableTuringTape implements EditableTuringTapeInterface { DoublyLinkedNode curr; //the current position public EditableTuringTape(){ curr = new DoublyLinkedNode(null, null, null); } /** * Returns the object at the current position; the list is unchanged. * * @return the Object stored at the current tape position */ public Object readValue(){ return curr.getItem(); } /** * Adds an object to the list at the current postion; * overwrites any pre-existing object at the position. * * @param newObject any Object */ public void writeValue(Object newObject){ curr.setItem(newObject); } /** * Moves to the left of the current position; * if that position does not exist, it is create */ public void moveLeft(){ if (curr.getPrev() == null) { curr.setPrev(new DoublyLinkedNode(null, null, curr)); } curr = (DoublyLinkedNode)curr.getPrev(); } /** * Moves to the left of the current position; * if that position does not exist, it is create */ public void moveRight(){ if (curr.getNext() == null) { curr.setNext(new DoublyLinkedNode(null, curr, null)); } curr = (DoublyLinkedNode)curr.getNext(); } /** * Inserts an element into the list without overwriting. * The new position becomes the current position. * * @param toRight Specifies whether the insertion is to the right (if * true) or to the left of the current position. * @return void */ public void insertPosition(boolean toRight){ if (toRight){ DoublyLinkedNode newNode = new DoublyLinkedNode(null, curr, curr.getNext()); ((DoublyLinkedNode)curr.getNext()).setPrev(newNode); curr.setNext(newNode); this.moveRight(); }else{ DoublyLinkedNode newNode = new DoublyLinkedNode(null, curr.getPrev(), curr); curr.getPrev().setNext(newNode); curr.setPrev(newNode); this.moveLeft(); } } /** * Removes an element from the list * * @param moveRight Specifies whether the current position should move to * the right (if true) or to the left of the deleted element. * @return void */ public void removePosition(boolean moveRight){ if (moveRight) { //make the move and burn the bridges this.moveRight(); if (((DoublyLinkedNode)curr.getPrev()).getPrev() == null){ //was at the end of the list; nothing to link to curr.setPrev(null); }else{ ((DoublyLinkedNode)curr.getPrev()).getPrev().setNext(curr); curr.setPrev(((DoublyLinkedNode)curr.getPrev()).getPrev()); } }else { //movin' left this.moveLeft(); if (curr.getNext().getNext() == null) { curr.setNext(null); }else{ ((DoublyLinkedNode)curr.getNext().getNext()).setPrev(curr); curr.setNext(curr.getNext().getNext()); } } } /** * Prints an EditableTuringTape * Should be inserted into your EditableTuringTape class * * @author Dan Suthers */ public void printTape() { DoublyLinkedNode printPosition = curr; // Scan to the left hand end of the list while (printPosition.getPrev() != null) { printPosition = (DoublyLinkedNode)printPosition.getPrev(); } // Print the first element on the list, // putting [] around the current position if (printPosition == curr) { System.out.print("[" + printPosition.getItem() + "]"); }else { System.out.print(printPosition.getItem()); } // Loop to scan to the right hand end of the tape, // printing out each item as we go, with [] around // the current position when it is found. while (printPosition.getNext() != null) { printPosition = (DoublyLinkedNode)printPosition.getNext(); if (printPosition == curr) { System.out.print(" [" + printPosition.getItem() + "]"); }else { System.out.print(" " + printPosition.getItem()); } } // Finish off the line System.out.println(); } }//end class /** * A utility class of nodes to be used in implementing linked lists * with links going in both directions. Note that, because this class * extends Node, all methods return Nodes. Casting is often necessary. * * @author Zach Tomaszewski * @date 06 Oct 2001 * @see EditableTuringTape */ class DoublyLinkedNode extends Node { private Node prevNode; protected DoublyLinkedNode(Object item, Node prev, Node nextNode) { super(item, nextNode); this.prevNode = prev; } protected DoublyLinkedNode(Object item){ this(item, null, null); } /** * gets the previous node */ protected Node getPrev(){ return this.prevNode; } /** * updates the link from this node to the previous one */ protected void setPrev(Node prevNode){ this.prevNode = prevNode; } /** * removes the link from this node to the previous one (sets it to null) */ protected void removePrev() { this.prevNode = null; } }//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 object contained by this node with the new object */ protected void setItem(Object newItem){ this.item = newItem; } /** * 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