package csci3230.hw3;

import java.io.File; import java.io.IOException; import java.util.ListIterator; import java.util.NoSuchElementException; import java.util.Random;

import csci3230.hw3.OutputWriter;

public class DoublyLinkedList implements Iterable { private int n; // number of elements on list private Node pre; // sentinel before first item private Node post; // sentinel after last item

public DoublyLinkedList() { pre = new Node(); post = new Node(); pre.next = post; post.prev = pre; }

// linked list node helper data type private class Node { private Item item; private Node next; private Node prev; }

public boolean isEmpty() { return n==0;} // your code} public int size() { return n;}// your code }

// add the item to the list public void add(Item item) { Node last = post.prev; Node x = new Node(); x.item = item; x.next = post; x.prev = last; post.prev = x; last.next = x; n++; // your code }

public ListIterator iterator() { return new DoublyLinkedListIterator(); }

// assumes no calls to DoublyLinkedList.add() during iteration private class DoublyLinkedListIterator implements ListIterator { private Node current = pre.next; // the node that is returned by next() private Node lastAccessed = null; // the last node to be returned by prev() or next() // reset to null upon intervening remove() or add() private int index = 0;

public boolean hasNext() { return index0;}// your code } public int previousIndex() { return index - 1;}// your code } public int nextIndex() { return index;}// your code }

public Item next() { if (!hasNext()) throw new NoSuchElementException(); lastAccessed = current; Item item = current.item; current = current.next; index++; return item;// your code }

public Item previous() { if (!hasPrevious()) throw new NoSuchElementException(); current = current.prev; index--; lastAccessed = current; return current.item;// your code }

// replace the item of the element that was last accessed by next() or previous() // condition: no calls to remove() or add() after last call to next() or previous() public void set(Item item) { if (lastAccessed == null) throw new IllegalStateException(); lastAccessed.item = item;// your code }

// remove the element that was last accessed by next() or previous() // condition: no calls to remove() or add() after last call to next() or previous() public void remove() { if (lastAccessed == null) throw new IllegalStateException(); Node x = lastAccessed.prev; Node y = lastAccessed.next; x.next = y; y.prev = x; n--; if (current == lastAccessed) current = y; else index--; lastAccessed = null;// your code }

// add element to list public void add(Item item) { Node x = current.prev; Node y = new Node(); Node z = current; y.item = item; x.next = y; y.next = z; z.prev = y; y.prev = x; n++; index++; lastAccessed = null;// your code }

}

public String toString() { StringBuilder s = new StringBuilder(); for (Item item : this) s.append(item + " "); return s.toString(); }

/* a test client * arg[1]: number of input values * arg[2]: random seed * arg[3]: output file path */ public static void main(String[] args) throws IOException { int n, seed; File outputFile; File dir = new File("."); if (args.length > 0) { n = Integer.parseInt(args[0]); seed = Integer.parseInt(args[1]); }else { n = 10; seed = 1; } if (args.length == 3) { outputFile = new File(args[2]); } else { outputFile = new File(dir.getCanonicalPath() + File.separator + "Files/testOut_DLL"); } OutputWriter out = new OutputWriter(outputFile); Random r = new Random(seed); // add elements 1, ..., n out.writeOutput("Integer items to insert: "+ n); DoublyLinkedList list = new DoublyLinkedList(); for (int i = 0; i < n; i++) list.add(r.nextInt(100)); out.writeOutput(list.toString());

ListIterator iterator = list.iterator();

// go forwards with next() and set() out.writeOutput("add 1 to each element via next() and set()"); while (iterator.hasNext()) { int x = iterator.next(); iterator.set(x + 1); } out.writeOutput(list.toString());

// go backwards with previous() and set() out.writeOutput("multiply each element by 3 via previous() and set()"); while (iterator.hasPrevious()) { int x = iterator.previous(); iterator.set(x + x + x); } out.writeOutput(list.toString());

// remove all elements that are multiples of 4 via next() and remove() out.writeOutput("remove elements that are a multiple of 4 via next() and remove()"); while (iterator.hasNext()) { int x = iterator.next(); if (x % 4 == 0) iterator.remove(); } out.writeOutput(list.toString());

// remove all even elements via previous() and remove() out.writeOutput("remove elements that are even via previous() and remove()"); while (iterator.hasPrevious()) { int x = iterator.previous(); if (x % 2 == 0) iterator.remove(); } out.writeOutput(list.toString());

// add elements via next() and add() out.writeOutput("add elements via next() and add()"); while (iterator.hasNext()) { int x = iterator.next(); iterator.add(x + 1); } out.writeOutput(list.toString());

// add elements via previous() and add() out.writeOutput("add elements via previous() and add()"); while (iterator.hasPrevious()) { int x = iterator.previous(); iterator.add(x * 10); iterator.previous(); } out.writeOutput(list.toString()); } }

The class below(LinkedListStack) is where I need help. Im suppose to complete the rest of the methods (pop,push, size, isEmpty, top). I also need help with the method that finds the maximum value.

package csci3230.hw3;

import java.io.File; import java.io.IOException; import java.util.ListIterator; import java.util.Random;

public class LinkedListStack {

DoublyLinkedList list = new DoublyLinkedList();

public int size() { // your code }

public void push(Integer s){ // your code }

public Integer pop() { // your code } public Integer top() { // your code } public boolean isEmpty() { // your code }

public String displayStack() { return (list.toString()); }

public static void main(String[] args) throws IOException { LinkedListStack stack = new LinkedListStack();

int n, seed; File outputFile; File dir = new File("."); if (args.length > 0) { n = Integer.parseInt(args[0]); seed = Integer.parseInt(args[1]); }else { n = 10; seed = 1; } if (args.length == 3) { outputFile = new File(args[2]); } else { outputFile = new File(dir.getCanonicalPath() + File.separator + "Files/testOut_Stack"); } OutputWriter out = new OutputWriter(outputFile); Random r = new Random(seed); Integer nextval; for (int i = 0; i < n; i++) { nextval = r.nextInt(10000); // your code /* retain the max value that you see among the integers generated in the stack. * In the end there should be only one integer in stack, which is the max value */ } // write the content of stack -- which is the max value -- to file out.writeOutput(stack.displayStack()); } }