JAVA Coding

Question 1:

Implement a Treque (triple-ended queue). This is an implementation of the List interface that allows for fast modifications at the front, back, and middle. You can make your Treque a subclass of AbstractList so that you don't have to write all the List methods from scratch. The performance requirements for a Treque are:

size(), get(i), and set(i,x) should each take constant time (O(1)).

add(i,x) and remove(i) should be fast if the value of i is close to 0, n or n/2. More precisely, the amortized running time of these operations should be O(1 + min{i, n-i, |n/2-i|}).

The provided starting code is:

package comp2402a2;

/** */ public interface AbstractTable { /** * You decide on the instance variables you need. */

public int rows(); public int cols(); public T get(int i, int j); public T set(int i, int j, T x); public void addRow(int i); public void removeRow(int i); public void addCol(int j); public void removeCol(int j); public String toString(); }

------------------------------------------------------------------------------------------------------------------------------------------------------------

and:

package comp2402a2;

import java.util.AbstractList; import java.util.List;

/** */ public class Treque extends AbstractList { /** * You decide on the instance variables you need. */

public Treque(Class t) { // Put your own code here throw new UnsupportedOperationException("Constructor not yet implemented"); }

public T get(int i) { if (i < 0 || i > size() - 1) throw new IndexOutOfBoundsException(); // Put your own code here instead of throwing this exception throw new UnsupportedOperationException("get(i) not yet implemented"); }

public T set(int i, T x) { if (i < 0 || i > size() - 1) throw new IndexOutOfBoundsException(); // Put your own code here instead of throwing this exception throw new UnsupportedOperationException("set(i,x) not yet implemented"); }

public void add(int i, T x) { if (i < 0 || i > size()) throw new IndexOutOfBoundsException(); // Put your own code here throw new UnsupportedOperationException("add(i,x) not yet implemented"); }

public T remove(int i) { if (i < 0 || i > size() - 1) throw new IndexOutOfBoundsException(); // Put your own code here throw new UnsupportedOperationException("remove(i) not yet implemented"); }

public int size() { // Put your own code here throw new UnsupportedOperationException("size() not yet implemented"); }

public static void main(String[] args) { //List tr = new ArrayDeque(Integer.class); List tr = new Treque(Integer.class); int K = 1000000; Stopwatch s = new Stopwatch(); System.out.print("Appending " + K + " items..."); System.out.flush(); s.start(); for (int i = 0; i < K; i++) { tr.add(i); } s.stop(); System.out.println("done (" + s.elapsedSeconds() + "s)");

System.out.print("Prepending " + K + " items..."); System.out.flush(); s.start(); for (int i = 0; i < K; i++) { tr.add(0, i); } s.stop(); System.out.println("done (" + s.elapsedSeconds() + "s)");

System.out.print("Midpending(?!) " + K + " items..."); System.out.flush(); s.start(); for (int i = 0; i < K; i++) { tr.add(tr.size()/2, i); } s.stop(); System.out.println("done (" + s.elapsedSeconds() + "s)");

System.out.print("Removing " + K + " items from the back..."); System.out.flush(); s.start(); for (int i = 0; i < K; i++) { tr.remove(tr.size()-1); } s.stop(); System.out.println("done (" + s.elapsedSeconds() + "s)");

System.out.print("Removing " + K + " items from the front..."); System.out.flush(); s.start(); for (int i = 0; i < K; i++) { tr.remove(0); } s.stop(); System.out.println("done (" + s.elapsedSeconds() + "s)");

System.out.print("Removing " + K + " items from the middle..."); System.out.flush(); s.start(); for (int i = 0; i < K; i++) { tr.remove(tr.size()/2); } s.stop(); System.out.println("done (" + s.elapsedSeconds() + "s)"); }

}