JAVA Coding Question 1: Implement a Treque (triple-ended queue). This is an impl
ID: 3594726 • Letter: J
Question
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:
1.size(), get(i), and set(i,x) should each take constant time (O(1)).
2.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|}).
Please fill up the Treque.java file.
Thank you!
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)");
}
}
Explanation / Answer
Below is your Treque class
Treque.java
package comp2402a2;
import java.util.AbstractList;
import java.util.List;
/**
*/
public class Treque<T> extends AbstractList<T> {
/**
* You decide on the instance variables you need.
*/
protected MyArrayDeque<T> front;
protected MyArrayDeque<T> back;
public Treque(Class<T> t) {
front = new MyArrayDeque<T>(t);
back = new MyArrayDeque<T>(t);
}
public T get(int i) {
// If the index exists in 'front' get i from front
if (i < front.size())
return front.get(i);
// else if index exists in back get index from back (less mod front)
else
return back.get(i - front.size());
}
public T set(int i, T x) {
// If index exists in front 'set' i in front
if (i < front.size())
return front.set(i, x);
// else if index exists in back set index from back (less mod front)
else
return back.set(i - front.size(), x);
}
public void add(int i, T x) {
// If i exists in front 'add' x to i index in front
if (i < front.size())
front.add(i, x);
// else i exists in back 'add' x to i index in back (less mod front)
else
back.add(i - front.size(), x);
// Must rebalance as this may unbalance our arrays
reBalance();
}
public T remove(int i) {
// Declare
T x;
// If i is in front then remove element i
if (i < front.size())
x = front.remove(i);
// else remove from back position i (less mod front)
else
x = back.remove(i - front.size());
// Must rebalance as this may unbalance our array
reBalance();
return x;
}
protected void reBalance() {
// the front and back can have a delta of 0 or 1.
// If this is 2 you will pop an item front the front/back and add it to
// the back/front
if (front.size() == back.size() + 2) {
back.add(0, front.remove(front.size() - 1));
// Or vise versa
} else if (back.size() == front.size() + 2) {
front.add(front.size(), back.remove(0));
}
}
public int size() {
return front.size() + back.size();
}
public static void main(String[] args) {
// List<Integer> tr = new ArrayDeque<Integer>(Integer.class);
List<Integer> tr = new Treque<Integer>(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)");
}
}
Sample Output
Appending 1000000 items...done (0.100165425s)
Prepending 1000000 items...done (0.29070654900000004s)
Midpending(?!) 1000000 items...done (0.117135681s)
Removing 1000000 items from the back...done (0.034894994000000006s)
Removing 1000000 items from the front...done (0.049840127000000005s)
Removing 1000000 items from the middle...done (0.054792603s)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.