Overview:
There are two concerns to address: (1) bounded capacity, (2) unbounded capacity. The attempt is to address both concerns by the same principles (with the same data structure), exposing a type: PointDeque is abstract since implements java.util.Deque interface without implementing the methods the interface defines and Bounded and Unbounded classes extend PointDeque, that is the exposed type, being the deque implementations.
import java.util.Collection;
import java.util.Deque;
import java.util.Iterator;
import java.util.NoSuchElementException;
public abstract class PointDeque<E> implements Deque<E> {
public static <U> PointDeque<U> object() {
return new Deque<U>(new Unbounded());
}
public static <U> PointDeque<U> object(int capacity) {
return new Deque<U>(new Bounded(capacity));
}
private static class Ascending<F> extends Source<F> {
private Point points;
public Ascending(Point context) {
super(!context.isEmpty());
points = context;
}
@Override
public Object[] next(Object[] fore, Object[] actual) {
Object[] point = null;
if (actual == null) {
point = null == fore ? Point.next(points.peak())
: Point.next(fore);
} else {
point = Point.next(actual);
}
return point;
}
@Override
public boolean hasNext(Object[] actual) {
return Point.next(actual) != points.leaf();
}
}
private static class Descending<F> extends Source<F> {
private Point points;
public Descending(Point context) {
super(!context.isEmpty());
points = context;
}
@Override
public Object[] next(Object[] fore, Object[] actual) {
Object[] point = null;
if (actual == null) {
point = null == fore ? Point.fore(points.leaf())
: Point.fore(fore);
} else {
point = Point.fore(actual);
}
return point;
}
@Override
public boolean hasNext(Object[] actual) {
return Point.fore(actual) != points.peak();
}
}
private static abstract class Source<F> implements Iterator<F> {
private Object[] fore, actual;
private boolean hasNext;
public Source(boolean ready) { hasNext = ready; }
public abstract Object[] next(Object[] fore, Object[] actual);
public abstract boolean hasNext(Object[] actual);
@Override
public F next() {
if (!hasNext()) { throw new NoSuchElementException(); }
actual = next(fore, actual);
hasNext = hasNext(actual);
return Point.element(actual);
}
@Override
public boolean hasNext() { return hasNext; }
@Override
public void remove() {
if (actual == null) { return; }
Point.remove(actual);
actual = null;
}
}
private static class Deque<F> extends PointDeque<F> {
private Point points;
public Deque(Point lot) { points = lot; }
@Override
public boolean isEmpty() { return points.isEmpty(); }
@Override
public Object[] toArray() { return toArray(new Object[points.size()]); }
@Override
public <T> T[] toArray(T[] a) {
Object[] point = Point.next(points.peak());
int i = 0;
while(i < a.length && point != points.leaf()) {
a[i++] = Point.element(point);
point = Point.next(point);
}
return a;
}
@Override
public boolean containsAll(Collection<?> c) {
if (isEmpty()) { return c.isEmpty(); }
boolean result = true;
for (Iterator i = c.iterator(); i.hasNext() && result;) {
Object o = i.next();
boolean contained = false;
for (Object[] point = Point.next(points.peak())
; !contained && point != points.leaf()
; point = Point.next(point)) {
Object element = Point.element(point);
contained = (null == o && null == element
|| null != o && o.equals(element));
}
result = result && contained;
}
return result;
}
@Override
public boolean removeAll(Collection<?> c) {
if (isEmpty()) { return false; }
boolean result = false;
for (Object o : c) {
boolean removed = false;
for (Object[] point = Point.next(points.peak())
; point != points.leaf()
; point = Point.next(point)) {
Object element = Point.element(point);
if (null == o && null == element
|| null != o && o.equals(element)) {
Point.remove(point);
result = true;
removed = true;
}
}
}
return result;
}
@Override
public boolean retainAll(Collection<?> c) {
if (isEmpty()) { return false; }
if (c.isEmpty()) { points.clear(); return true; }
boolean result = false;
for (Object[] point = Point.next(points.peak())
; point != points.leaf()
; point = Point.next(point)) {
Object element = Point.element(point);
if (element == null && nullContained(c)
|| element != null && contained(element, c)) {
continue;
}
Point.remove(point);
result = true;
}
return result;
}
private boolean nullContained(Collection collection) {
boolean result = false;
for (Iterator i = collection.iterator(); !result && i.hasNext(); ) {
result = null == i.next();
}
return result;
}
private boolean contained(Object contained, Collection collection) {
boolean result = false;
for (Iterator i = collection.iterator(); !result && i.hasNext(); ) {
result = contained.equals(i.next());
}
return result;
}
@Override
public void clear() { points.clear(); }
@Override
public void addFirst(F e) {
if (!points.prepend(e)) { throw new IllegalStateException(); }
}
@Override
public void addLast(F e) {
if (!points.append(e)) { throw new IllegalStateException(); }
}
@Override
public boolean offerFirst(F e) { return points.prepend(e); }
@Override
public boolean offerLast(F e) { return points.append(e); }
@Override
public F removeFirst() {
if (isEmpty()) { throw new NoSuchElementException(); }
return points.peakless();
}
@Override
public F removeLast() {
if (isEmpty()) { throw new NoSuchElementException(); }
return points.endless();
}
@Override
public F pollFirst() { return isEmpty() ? null : points.peakless(); }
@Override
public F pollLast() { return isEmpty() ? null : points.endless(); }
@Override
public F getFirst() {
if (isEmpty()) { throw new NoSuchElementException(); }
return Point.element(Point.next(points.peak()));
}
@Override
public F getLast() {
if (isEmpty()) { throw new NoSuchElementException(); }
return Point.element(Point.fore(points.leaf()));
}
@Override
public F peekFirst() {
if (isEmpty()) { return null; }
return Point.element(Point.next(points.peak()));
}
@Override
public F peekLast() {
if (isEmpty()) { return null; }
return Point.element(Point.fore(points.leaf()));
}
@Override
public boolean removeFirstOccurrence(Object o) {
if (isEmpty()) { return false; }
boolean result = false;
for (Object[] point = Point.next(points.peak())
; point != points.leaf()
; point = Point.next(point)) {
Object element = Point.element(point);
if (null == o && null == element
|| null != o && o.equals(element)) {
Point.remove(point);
result = true;
break;
}
}
return result;
}
@Override
public boolean removeLastOccurrence(Object o) {
if (isEmpty()) { return false; }
boolean result = false;
for (Object[] point = Point.fore(points.leaf())
; point != points.peak()
; point = Point.fore(point)) {
Object element = Point.element(point);
if (null == o && null == element
|| null != o && o.equals(element)) {
Point.remove(point);
result = true;
break;
}
}
return result;
}
@Override
public boolean add(F e) {
addLast(e);
return true;
}
@Override
public boolean offer(F e) { return offerLast(e); }
@Override
public F remove() { return removeFirst(); }
@Override
public F poll() { return pollFirst(); }
@Override
public F element() { return getFirst(); }
@Override
public F peek() { return peekFirst(); }
@Override
public boolean addAll(Collection<? extends F> c) {
boolean result = !c.isEmpty();
for (F object : c) {
addLast(object);
}
return result;
}
@Override
public void push(F e) { addFirst(e); }
@Override
public F pop() { return removeFirst(); }
@Override
public boolean remove(Object o) { return removeFirstOccurrence(o); }
@Override
public boolean contains(Object o) { return points.contains(o); }
@Override
public int size() { return points.size(); }
@Override
public Iterator<F> iterator() { return new Ascending<>(points); }
@Override
public Iterator<F> descendingIterator() {
return new Descending<>(points);
}
}
private static interface Point {
public static Object[] empty() {
return new Object[] { null, null, null };
}
public static Object[] remove(Object[] removee) {
Object[] fore = (Object[]) removee[0];
Object[]removee[0], next = (Object[]) removee[2];
next[0] = fore;
fore[2] = next;
return removee;
}
public static Object[] of(Object element) {
return new Object[] { null, element, null };
}
public static Object[] next(Object[] point) {
return (Object[]) point[2];
}
public static Object[] fore(Object[] point) {
return (Object[]) point[0];
}
public static <T> T element(Object[] point) { return (T) point[1]; }
public static boolean nullContained(Object[] peak, Object[] leaf) {
boolean contained = false;
Object[] point = peak;
while(!contained && leaf != point) {
contained = null == point[1];
point = Point.next(point);
}
return contained;
}
public static boolean contained(Object o, Object[] peak, Object[] leaf) {
boolean contained = false;
Object[] point = peak;
while(!contained && leaf != point) {
contained = o.equals(point[1]);
point = Point.next(point);
}
return contained;
}
public Object[] peak();
public Object[] leaf();
public boolean append(Object element);
public boolean prepend(Object element);
public <T> T peakless();
public <T> T endless();
public boolean isEmpty();
public void clear();
public int size();
public boolean contains(Object o);
}
private static class Unbounded implements Point {
private final Object[] peak;
private final Object[]peak, leaf;
public Unbounded() {
peak = Point.empty();
leaf = Point.empty();
leaf[0] = peak;
peak[2] = leaf;
}
public boolean append(Object element) {
Object[] prependee = Point.of(element);
prependee[2] = leaf;
Object[] fore = (Object[]) leaf[0];
if (fore != null) {
prependee[0] = fore;
fore[2] = prependee;
}
leaf[0] = prependee;
return true;
}
public boolean prepend(Object element) {
Object[] prependee = Point.of(element);
Object[] to = Point.next(peak);
prependee[2] = to;
Object[] fore = (Object[]) to[0];
if (fore != null) {
prependee[0] = fore;
fore[2] = prependee;
}
to[0] = prependee;
return true;
}
public <T> T peakless() {
return Point.element(Point.remove(Point.next(peak)));
}
public <T> T endless() {
return Point.element(Point.remove(Point.fore(leaf)));
}
public boolean isEmpty() { return peak == leaf[0]; }
public void clear() {
peak[2] = leaf;
leaf[0] = peak;
}
public int size() {
int i = 0;
Object[] point = Point.next(peak);
while (leaf != point) {
i--;
point = Point.next(point);
}
return -i;
}
public boolean contains(Object o) {
return null == o ? Point.nullContained(peak, leaf)
: Point.contained(o, peak, leaf);
}
@Override
public Object[] peak() { return peak; }
@Override
public Object[] leaf() { return leaf; }
}
private static class Bounded implements Point {
private static Object[] empty() {
return new Object[] { null, null, null };
}
public static <T> T element(Object[] point) { return (T) point[1]; }
private final Object[] peak;
private final Object[]peak, leaf;
private int bound;
public Bounded(int boundry) {
bound = boundry;
peak = empty();
leaf = empty();
leaf[0] = peak;
peak[2] = leaf;
}
public boolean append(Object element) {
if (size() == bound) { return false; }
Object[] prependee = Point.of(element);
prependee[2] = leaf;
Object[] fore = (Object[]) leaf[0];
if (fore != null) {
prependee[0] = fore;
fore[2] = prependee;
}
leaf[0] = prependee;
return true;
}
public boolean prepend(Object element) {
if (size() == bound) { return false; }
Object[] prependee = Point.of(element);
Object[] to = Point.next(peak);
prependee[2] = to;
Object[] fore = (Object[]) to[0];
if (fore != null) {
prependee[0] = fore;
fore[2] = prependee;
}
to[0] = prependee;
return true;
}
public <T> T peakless() {
return Point.element(Point.remove(Point.next(peak)));
}
public <T> T endless() {
return Point.element(Point.remove(Point.fore(leaf)));
}
public boolean isEmpty() { return peak == leaf[0]; }
public void clear() {
peak[2] = leaf;
leaf[0] = peak;
}
public int size() {
int i = 0;
Object[] point = Point.next(peak);
while (leaf != point) {
i--;
point = Point.next(point);
}
return -i;
}
public boolean contains(Object o) {
return null == o ? Point.nullContained(peak, leaf)
: Point.contained(o, peak, leaf);
}
@Override
public Object[] peak() { return peak; }
@Override
public Object[] leaf() { return leaf; }
}
}
import java.io.PrintStream;
import java.util.Collection;
import java.util.Collections;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
public class PointDequeTest {
public static void main(String[] args) {
PointDequeTest test = new PointDequeTest(Explorers.granular());
Object object = new Object();
Collection<?> objects = Collections.emptyList();
test.toArray();
test.toArray(null);
test.clear();
test.containsAll(objects);
test.addFirst(object);
test.push(object);
test.addLast(object);
test.add(object);
test.addAll(objects);
test.offerFirst(object);
test.offerLast(object);
test.offer(object);
test.removeAll(objects);
test.removeFirst();
test.pop();
test.remove();
test.removeLast();
test.contains(object);
test.retainAll(objects);
test.pollFirst();
test.poll();
test.pollLast();
test.getFirst();
test.element();
test.getLast();
test.peekFirst();
test.peek();
test.peekLast();
test.removeFirstOccurrence(object);
test.remove(object);
test.removeLastOccurrence(object);
test.size();
test.iterator();
test.descendingIterator();
test.overall();
}
private static class Explorers {
public static Granular granular() { return new Granular(); }
public static TimedGranular timedGranular() {
return new TimedGranular();
}
public static Bulk bulk() { return new Bulk(); }
public static TimedBulk timedBulk() { return new TimedBulk(); }
public static Series series(int rounds) { return new Series(rounds); }
}
private interface Quest {
String explored();
boolean questing();
boolean result();
void summary(boolean result);
void print();
}
private interface Explorer {
Explorer of(String text);
void summary(boolean result);
void overall();
void overall(boolean result);
}
private static abstract class AbstractQuest implements Quest {
private String text;
private boolean questing = true, result;
public AbstractQuest(String explored) { text = explored; }
@Override
public void summary(boolean state) {
questing = false;
result = state;
}
@Override
public String explored() { return text; }
@Override
public boolean questing() { return questing; }
@Override
public boolean result() { return result; }
}
private static class Plain extends AbstractQuest {
public Plain(String explored) { super(explored); }
@Override
public void summary(boolean result) {
super.summary(result);
print();
}
@Override
public void print() {
if (questing()) {
System.out.println(explored() + " ... Exploring...");
return;
}
if (result()) {
System.out.println(explored() + " ... Passed");
} else {
System.err.println(explored() + " ... Failed");
}
}
}
private static class Timed extends AbstractQuest {
private long start, elapsed;
public Timed(String explored) {
super(explored);
start = System.nanoTime();
}
@Override
public void summary(boolean result) {
elapsed = (System.nanoTime() - start) / 1000;
super.summary(result);
print();
}
@Override
public void print() {
if (questing()) {
System.out.println(explored() + " ... Exploring...");
return;
}
String string = result() ? "Passed" : "Failed";
String message = explored() + " ... " + string
+ " [elapsed: " + elapsed + " micros]";
if (result()) {
System.out.println(message);
} else {
System.err.println(message);
}
}
}
private static class Granular extends AbstractExplorer {
@Override
public Explorer of(String text) { on(new Plain(text)); return this; }
}
private static class TimedGranular extends AbstractExplorer {
@Override
public Explorer of(String text) { on(new Timed(text)); return this; }
}
private static class State extends AbstractQuest {
public State(String explored) { super(explored); }
public void print() {
if (questing()) {
System.out.println(explored() + " ... Exploring...");
return;
}
String string = result() ? "Passed" : "Failed";
String message = explored() + " ... " + string;
if (result()) {
System.out.println(message);
} else {
System.err.println(message);
}
}
}
private static class TimedState extends AbstractQuest {
private long start, elapsed;
public TimedState(String explored) {
super(explored);
start = System.nanoTime();
}
public long nanos() { return elapsed; }
@Override
public void summary(boolean result) {
elapsed = (System.nanoTime() - start);
super.summary(result);
}
public void print() {
if (questing()) {
System.out.println(explored() + " ... Exploring...");
return;
}
long micros = elapsed / 1000;
String string = result() ? "Passed" : "Failed";
String message = explored() + " ... " + string
+ " [elapsed: " + micros + " nicros]";
if (result()) {
System.out.println(message);
} else {
System.err.println(message);
}
}
}
private static abstract class AbstractExplorer implements Explorer {
private Quest[] quests = {};
public void on(Quest runee) { quests = append(runee, quests); }
private Quest[] append(Quest quest, Quest ... quests) {
Quest[] runees = new Quest[quests.length + 1];
runees[runees.length - 1] = quest;
for (int i = 0; i < runees.length - 1; i++) {
runees[i] = quests[i];
}
return runees;
}
public void clear() { quests = new Quest[]{}; }
public Quest[] quests() {
Quest[] returnee = new Quest[quests.length];
for (int i = 0; i < quests.length; i++) {
returnee[i] = quests[i];
}
return returnee;
}
@Override
public void summary(boolean result) {
for (int i = quests.length - 1; i > -1; i--) {
if (quests[i].questing()) { quests[i].summary(result); break; }
}
}
@Override
public void overall() {
boolean passed = quests[0].result();
for (int i = 0; i < quests.length; i++) {
if (quests[i].questing()) {
quests[i].print();
} else {
passed = passed && quests[i].result();
}
}
overall(passed);
}
@Override
public void overall(boolean result) {
if (result) {
System.out.println();
System.out.println("Pass.");
} else {
System.err.println();
System.err.println("Fail.");
}
}
}
private static abstract class AbstractBulk extends AbstractExplorer {
@Override
public void overall() {
Quest[] quests = quests();
boolean passed = quests[0].result();
for (int i = 0; i < quests.length; i++) {
passed = passed && quests[i].result();
quests[i].print();
}
overall(passed);
}
}
private static class Bulk extends AbstractBulk {
public Explorer of(String text) { on(new State(text)); return this; }
}
private static class TimedBulk extends AbstractBulk {
@Override
public Explorer of(String explored) {
on(new TimedState(explored));
return this;
}
}
private static class Series extends AbstractBulk {
private int rounds, index;
private Object[] serieses;
public Series(int rounds) {
this.rounds = rounds;
serieses = new Object[rounds];
index = 0;
}
@Override
public Explorer of(String explored) {
on(new TimedState(explored));
return this;
}
@Override
public void overall() {
serieses[index++] = quests();
clear();
if (index < rounds) { return; }
boolean passed = true;
StringToLongArray summary = flatten();
String[] explorations = summary.keys();
for (int i = 0; i < explorations.length; i++) {
boolean result = result(explorations[i]);
double elapsed = summary.get(explorations[i]) / rounds;
print(explorations[i], result, elapsed);
passed = passed && result;
}
String prefix = rounds + " rounds";
if (passed) {
System.out.println();
System.out.println(prefix + " ... Pass.");
} else {
System.err.println();
System.err.println(prefix + " ... Fail.");
}
}
private boolean result(String exploration) {
boolean returnee = false;
for (int i = 0; i < serieses.length; i++) {
Quest[] quests = (Quest[]) serieses[i];
for (int j = 0; j < quests.length; j++) {
if (exploration.equals(quests[j].explored())) {
returnee = quests[j].result();
break;
}
}
}
return returnee;
}
private void print(String exploration, boolean result, double elapsedNanos) {
double micros = elapsedNanos / 1000;
String string = result ? "Passed" : "Failed";
String message = exploration + " ... " + string
+ " [elapsed: " + micros + " micros]";
if (result) {
System.out.println(message);
} else {
System.err.println(message);
}
}
private StringToLongArray flatten() {
StringToLongArray returnee = new StringToLongArray(-1);
for (int i = 0; i < index; i++) {
Quest[] quests = (Quest[]) serieses[i];
for (int j = 0; j < quests.length; j++) {
String exploration = quests[j].explored();
if (quests[j].questing()) { continue; }
if (returnee.get(exploration) == returnee.undefined) {
long elapsed = ((TimedState) quests[j]).nanos();
returnee.put(exploration, elapsed);
} else {
long elapsed = returnee.get(exploration);
TimedState state = (TimedState) quests[j];
returnee.put(exploration, elapsed + state.nanos());
}
}
}
return returnee;
}
public static class StringToLongArray {
public final long undefined;
private volatile String[] keys;
private volatile long[] values;
public StringToLongArray(long undefined) {
this.undefined = undefined;
keys = new String[] {};
values = new long[] {};
}
public long get(String key) {
long value = undefined;
for (int i = 0; i < keys.length; i++) {
if (key.equals(keys[i])) { value = values[i]; break; }
}
return value;
}
public long put(String key, long value) {
long returnee = undefined;
int indexOf = -1;
for (int i = 0; i < keys.length; i++) {
if (key.equals(keys[i])) { indexOf = i; break; }
}
if (indexOf == -1) {
int nextLength = keys.length + 1;
String[] nextKeys = new String[nextLength];
long[] nextValues = new long[nextLength];
for (int i = 0; i < keys.length; i++) {
nextKeys[i] = keys[i];
nextValues[i] = values[i];
}
values = nextValues;
keys = nextKeys;
indexOf = nextLength - 1;
} else {
returnee = values[indexOf];
}
values[indexOf] = value;
keys[indexOf] = key;
return returnee;
}
public String[] keys() {
String[] returnee = new String[keys.length];
for (int i = 0; i < returnee.length; i++) {
returnee[i] = keys[i];
}
return returnee;
}
}
}
private static class Display {
public void info(PrintStream stream, String message) {
stream.println(message);
}
}
private static class Blank extends Display {
public void info(PrintStream stream, String message) {}
}
private Display display;
private Explorer explorer;
{ display = new Blank(); }
public PointDequeTest() { this.explorer = new Granular(); }
public PointDequeTest(Explorer explorer) { this.explorer = explorer; }
public PointDequeTest verbose() { display = new Display(); return this; }
public void toArray() {
toArray("", deque(5));
toArray("Bounded", deque(26));
}
private void toArray(String id, Deque<Integer> deque) {
String prefix = "toArray" + id;
int length = deque.size();
Integer[] array = deque.toArray(new Integer[length]);
explorer.of(prefix)
.summary(toString(array).equals(stringed(length)));
length = 26;
int size = length/2;
array = deque(length).toArray(new Integer[size]);
explorer.of(prefix + "Underdimesioned")
.summary(toString(array).equals(stringed(size)));
}
public void toArray(Object[] a) {
int length = 3;
toObjectArray("", deque(length));
toObjectArray("Bounded", deque(length, length));
}
private void toObjectArray(String id, Deque<Integer> deque) {
Object[] array = deque.toArray();
explorer.of("toObjectArray" + id);
explorer.summary(toString(array).equals(stringed(deque.size())));
}
public void clear() {
clear("", deque(3));
clear("Bounded", deque(3, 3));
}
private void clear(String id, Deque deque) {
explorer.of("clear" + id);
deque.clear();
explorer.summary(deque.size() == 0);
}
public void containsAll(Collection c) {
containsAll("", deque(7));
containsAll("Bounded", deque(7));
}
private void containsAll(String id, Deque deque) {
List contained = toList(0, 1, 5);
explorer.of("containsAll" + id)
.summary(deque.containsAll(contained));
deque.clear();
explorer.of("empty" + id + "ContainsAll")
.summary(!deque.containsAll(contained));
explorer.of("empty" + id + "DequeContainsAllEmpty")
.summary(deque.containsAll(toList()));
deque.add(0);
explorer.of("notContainsAll" + id)
.summary(!deque.containsAll(contained));
}
public void removeAll(Collection c) {
int length = 8;
removeAll("", deque(length));
removeAll("ToBounded", deque(length, 505));
}
private void removeAll(String id, Deque deque) {
String prefix = "removeAll" + id;
int length = deque.size();
for (Iterator<Integer> i = deque.iterator(); i.hasNext();) {
deque.addFirst(i.next());
}
deque.addFirst(null);
deque.addFirst(12);
deque.addFirst(20);
deque.addFirst(31);
deque.addFirst(26);
deque.addFirst(null);
explorer.of(prefix);
boolean result = deque.size() == length * 2 + 6
&& deque.removeAll(toList(null, 0, 5, 6, 12))
&& deque.size() == ((length * 2 + 6) - 9);
explorer.summary(result);
length = 2;
deque = deque(length);
deque.addFirst(null);
deque.addFirst(2);
deque.addFirst(null);
explorer.of(prefix + "UntilEmpty");
result = deque.size() == length + 3
&& deque.removeAll(toList(null, 0, 1, 2, 3, 12))
&& deque.size() == 0;
explorer.summary(result);
explorer.of(prefix + "FromEmpty")
.summary(deque(0).removeAll(toList(0, 2, 5)) == false);
}
public void addFirst(Object added) {
addFirst("", deque(0));
addFirst("ToBounded", deque(0, 2));
}
public void addFirst(String id, Deque deque) {
int length = deque.size();
String prefix = "addFirst" + id;
boolean result = false;
explorer.of(prefix);
deque.addFirst(1);
result = deque.size() == length + 1;
deque.addFirst(2);
result = result && deque.size() == length + 2;
try {
deque.addFirst(3);
explorer.summary(result && deque.size() == length + 3);
} catch(IllegalStateException e) {
explorer.summary(result && deque.size() == length + 2);
info(System.err, prefix + ": overflow due to capacity bound");
}
}
public void push(Object added) {
push("", deque(0));
push("ToBounded", deque(0, 2));
}
private void push(String id, Deque deque) {
int length = deque.size();
String prefix = "push" + id;
boolean result = false;
explorer.of(prefix);
deque.push(1);
result = deque.size() == length + 1;
deque.push(2);
result = result && deque.size() == length + 2;
try {
deque.push(3);
explorer.summary(result && deque.size() == length + 3);
} catch(IllegalStateException e) {
explorer.summary(result && deque.size() == length + 2);
info(System.err, prefix + ": overflow due to capacity bound");
}
}
public void addLast(Object added) {
addLast("", deque(0));
addLast("ToBounded", deque(0, 2));
}
private void addLast(String id, Deque deque) {
int length = deque.size();
String prefix = "addLast" + id;
boolean result = false;
explorer.of(prefix);
deque.addLast(1);
result = deque.size() == length + 1;
deque.addLast(2);
result = result && deque.size() == length + 2;
try {
deque.addLast(3);
explorer.summary(result && deque.size() == length + 3);
} catch(IllegalStateException e) {
explorer.summary(result && deque.size() == length + 2);
info(System.err, prefix + ": overflow due to capacity bound");
}
}
public void addAll(Collection c) {
addAll("", deque(0));
addAll("ToBounded", deque(1, 6));
}
public void addAll(String id, Deque deque) {
int size = deque.size();
Collection added = toList(1, 2, 3, 4, 5, 6);
String prefix = "addAll" + id;
explorer.of(prefix);
try {
deque.addAll(added);
explorer.summary(deque.size() == size + added.size());
} catch(IllegalStateException e) {
explorer.summary(true);
info(System.err, prefix + ": overflow due to capacity bound");
}
deque.clear();
explorer.of("addAll" + id + "Empty")
.summary(deque.addAll(added) && deque.size() == added.size());
}
public void add(Object added) {
add("", deque(0));
add("ToBounded", deque(0, 2));
}
private void add(String id, Deque deque) {
int length = deque.size();
String prefix = "add" + id;
boolean result = false;
explorer.of(prefix);
deque.add(1);
result = deque.size() == length + 1;
deque.add(2);
result = result && deque.size() == length + 2;
try {
deque.add(3);
explorer.summary(result && deque.size() == length + 3);
} catch(IllegalStateException e) {
explorer.summary(result && deque.size() == length + 2);
info(System.err, prefix + ": overflow due to capacity bound");
}
}
public void offerFirst(Object added) {
offerFirst("", deque(0), true);
offerFirst("ToBounded", deque(1, 1), false);
}
private void offerFirst(String id, Deque deque, boolean intended) {
explorer.of("offerFirst" + id);
explorer.summary(deque.offerFirst(1) == intended);
}
public void offerLast(Object added) {
offerLast("", deque(0), true);
offerLast("ToBounded", deque(1, 1), false);
}
private void offerLast(String id, Deque deque, boolean intended) {
explorer.of("offerLast" + id);
explorer.summary(deque.offerLast(1) == intended);
}
public void offer(Object added) {
offer("", deque(0), true);
offer("ToBounded", deque(1, 1), false);
}
private void offer(String id, Deque deque, boolean intended) {
explorer.of("offer" + id);
explorer.summary(deque.offer(1) == intended);
}
public void pop() {
pop("", deque(3), 0);
pop("FromEmpty", deque(0), -1);
pop("FromBounded", deque(3, 3), 0);
pop("FromBoundedEmpty", deque(0, 3), -1);
}
private void pop(String id, Deque<Integer> deque, int result) {
int size = deque.size();
String prefix = "pop" + id;
explorer.of(prefix);
try {
explorer.summary(deque.pop().intValue() == result && deque.size() == size - 1);
} catch(NoSuchElementException e) {
explorer.summary(deque.size() == 0);
info(System.err, prefix + ": deque is empty");
}
}
public void removeFirst() {
removeFirst("", deque(3), 0);
removeFirst("FromEmpty", deque(0), -1);
removeFirst("FromBounded", deque(3, 3), 0);
removeFirst("FromBoundedEmpty", deque(0, 3), -1);
}
private void removeFirst(String id, Deque<Integer> deque, int result) {
int size = deque.size();
String prefix = "removeFirst" + id;
explorer.of(prefix);
try {
explorer.summary(deque.removeFirst() == result && deque.size() == size - 1);
} catch(NoSuchElementException e) {
explorer.summary(deque.size() == 0);
info(System.err, prefix + ": deque is empty");
}
}
public void remove() {
remove("", deque(3), 0);
remove("FromEmpty", deque(0), -1);
remove("FromBounded", deque(3, 3), 0);
remove("FromBoundedEmpty", deque(0, 3), -1);
}
private void remove(String id, Deque<Integer> deque, int result) {
int size = deque.size();
String prefix = "remove" + id;
explorer.of(prefix);
try {
explorer.summary(deque.remove() == result && deque.size() == size - 1);
} catch(NoSuchElementException e) {
explorer.summary(deque.size() == 0);
info(System.err, prefix + ": deque is empty");
}
}
public void removeLast() {
removeLast("", deque(3), 2);
removeLast("SingleElement", deque(1), 0);
removeLast("FromEmpty", deque(0), -1);
removeLast("SingleElementFromBounded", deque(1, 3), 0);
removeLast("FromBounded", deque(3, 3), 2);
removeLast("FromBoundedEmpty", deque(0, 3), -1);
}
private void removeLast(String id, Deque<Integer> deque, int result) {
String prefix = "removeLast" + id;
int size = deque.size();
try {
explorer.of(prefix)
.summary(deque.removeLast() == result && deque.size() == size - 1);
} catch(NoSuchElementException e) {
explorer.summary(deque.size() == 0);
info(System.err, prefix + ": deque is empty");
}
}
public void contains(Object added) {
contains("", "", deque(7), 6, true);
contains("not", "", deque(7), 26, false);
contains("", "Bounded", deque(7, 7), 6, true);
contains("not", "Bounded", deque(7, 7), 26, false);
}
private void contains(String prefix, String subfix, Deque deque, int contained, boolean intended) {
String id = prefix + (prefix.length() > 0 ? "Contains" : "contains") + subfix;
explorer.of(id).summary(deque.contains(contained) == intended);
}
public void retainAll(Collection c) {
int size = 5;
retainAll("", deque(size), toList(5, 2, 1, 7), 2);
Deque deque = deque(size);
for (int i = 0; i < size; i++) { deque.addFirst(i); }
retainAll("MultipleOccurences", deque, toList(2, 1), 4);
retainAll("EmptyCollection", deque(size), toList(), 0);
retainAllEmpty("", deque(0), toList(5, 2, 1, 7), 0);
retainAllWithdrawRetainee("", deque(101));
retainAllAddRetainee("", deque(101));
retainAll("ToBounded", deque(size, size), toList(5, 2, 1, 7), 2);
deque = deque(size, size * 2);
for (int i = 0; i < size; i++) { deque.addFirst(i); }
retainAll("MultipleOccurencesToBounded", deque, toList(2, 1), 4);
retainAll("ToBoundedEmptyCollection", deque(size, size), toList(), 0);
retainAllEmpty("Bounded", deque(0, size), toList(5, 2, 1, 7), 0);
retainAllWithdrawRetainee("ToBounded", deque(101, 202));
retainAllAddRetainee("ToBounded", deque(101, 202));
}
private void retainAll(String id, Deque deque, Collection retained, int result) {
explorer.of("retainAll" + id);
explorer.summary(deque.retainAll(retained) && deque.size() == result);
}
private void retainAllEmpty(String id, Deque deque, Collection retained, int result) {
explorer.of("retainAllEmpty" + id);
explorer.summary(!deque.retainAll(retained) && deque.size() == result);
}
private void retainAllWithdrawRetainee(String id, Deque deque) {
int length = deque.size();
Deque context = deque;
for (int i = 0; i < length; i++) { context.addLast(i); }
int dimension = length/2;
Collection retainees = deque(dimension);
Deque content = deque(dimension);
int omitted = 8;
for (int i = 0; i < dimension; i++) { if (i != omitted) { content.addLast(i); } }
String intended = toString(content.toArray());
Runnable callback = new Runnable() {
@Override
public void run() {
String string = PointDequeTest.toString(context.toArray());
explorer.summary(intended.equals(string));
}
};
Thread retainer = new Thread(new Runnable() {
@Override
public void run() {
context.retainAll(retainees);
callback.run();
}
});
Thread waver = new Thread(new Runnable() {
@Override
public void run() { retainees.remove(8); }
});
retainer.start();
waver.start();
explorer.of("retainAll" + id + "WithdrawRetainee");
}
private void retainAllAddRetainee(String id, Deque deque) {
int size = deque.size();
int length = size/2;
Deque context = deque, subject = deque;
for (int i = 0; i < size; i++) { subject.addLast(i); }
Collection waved = deque(0);
int pivot = 8;
for (int i = 0; i < length; i++) { if (i != pivot) { waved.add(i); } }
Deque content = deque(0);
for (int i = 0; i < length; i++) { if (i != pivot) { content.add(i); } }
for (int i = 0; i < length; i++) { content.add(i); }
String intended = toString(content.toArray());
Runnable callback = new Runnable() {
@Override
public void run() {
String string = PointDequeTest.toString(subject.toArray());
explorer.summary(intended.equals(string));
}
};
Thread retainer = new Thread(new Runnable() {
@Override
public void run() {
subject.retainAll(waved);
callback.run();
}
});
Thread waver = new Thread(new Runnable() {
@Override
public void run() { waved.add(pivot); }
});
retainer.start();
waver.start();
explorer.of("retainAll" + id + "AddRetainee");
}
public void pollFirst() {
pollFirst("", deque(2), 0);
pollFirst("FromBounded", deque(2, 2), 0);
pollFirst("FromEmpty", deque(0), -1);
pollFirst("FromBoundedEmpty", deque(0, 2), -1);
}
private void pollFirst(String id, Deque<Integer> deque, int intended) {
int size = deque.size() == 0 ? 0 : deque.size() - 1;
explorer.of("pollFirst" + id);
Integer element = deque.pollFirst();
element = element == null ? -1 : element.intValue();
explorer.summary(element == intended && deque.size() == size);
}
public void poll() {
poll("", deque(2), 0);
poll("FromBounded", deque(2, 2), 0);
poll("FromEmpty", deque(0), -1);
poll("FromBoundedEmpty", deque(0, 2), -1);
}
private void poll(String id, Deque<Integer> deque, int intended) {
int size = deque.size() == 0 ? 0 : deque.size() - 1;
explorer.of("poll" + id);
Integer element = deque.poll();
element = element == null ? -1 : element.intValue();
explorer.summary(element == intended && deque.size() == size);
}
public void pollLast() {
pollLast("", deque(2), 1);
pollLast("FromBounded", deque(2, 2), 1);
pollLast("FromEmpty", deque(0), -1);
pollLast("FromBoundedEmpty", deque(0, 2), -1);
}
private void pollLast(String id, Deque<Integer> deque, int intended) {
int size = deque.size() == 0 ? 0 : deque.size() - 1;
explorer.of("pollLast" + id);
Integer element = deque.pollLast();
element = element == null ? -1 : element.intValue();
explorer.summary(element == intended && deque.size() == size);
}
public void getFirst() {
getFirst("", deque(1), 0);
getFirst("FromEmpty", deque(0), -1);
getFirst("FromBounded", deque(1, 3), 0);
getFirst("FromBoundedEmpty", deque(0, 3), -1);
}
private void getFirst(String id, Deque<Integer> deque, int intended) {
int size = deque.size();
String prefix = "getFirst" + id;
try {
explorer.of(prefix)
.summary(deque.getFirst() == intended && deque.size() == size);
} catch(NoSuchElementException e) {
explorer.summary(deque.size() == 0);
info(System.err, prefix + ": deque is empty");
}
}
public void element() {
element("", deque(1), 0);
element("FromEmpty", deque(0), -1);
element("FromBounded", deque(1, 3), 0);
element("FromBoundedEmpty", deque(0, 3), -1);
}
private void element(String id, Deque<Integer> deque, int result) {
int size = deque.size();
String prefix = "element" + id;
try {
explorer.of(prefix)
.summary(deque.element() == result && deque.size() == size);
} catch(NoSuchElementException e) {
explorer.summary(deque.size() == 0);
info(System.err, prefix + ": deque is empty");
}
}
public void peek() {
peek("", deque(2), 0);
peek("FromBounded", deque(2, 2), 0);
peek("FromEmpty", deque(0), -1);
peek("FromBoundedEmpty", deque(0, 2), -1);
}
private void peek(String id, Deque<Integer> deque, int intended) {
int size = deque.size() == 0 ? 0 : deque.size();
explorer.of("peek" + id);
Integer element = deque.peek();
element = element == null ? -1 : element.intValue();
explorer.summary(element == intended && deque.size() == size);
}
public void getLast() {
getLast("", deque(1), 0);
getLast("FromEmpty", deque(0), -1);
getLast("FromBounded", deque(1, 3), 0);
getLast("FromBoundedEmpty", deque(0, 3), -1);
}
private void getLast(String id, Deque<Integer> deque, int result) {
int size = deque.size();
String prefix = "getLast" + id;
try {
explorer.of(prefix)
.summary(deque.getLast() == result && deque.size() == size);
} catch(NoSuchElementException e) {
explorer.summary(deque.size() == 0);
info(System.err, prefix + ": deque is empty");
}
}
public void peekFirst() {
peekFirst("", deque(2), 0);
peekFirst("FromBounded", deque(2, 2), 0);
peekFirst("FromEmpty", deque(0), -1);
peekFirst("FromBoundedEmpty", deque(0, 2), -1);
}
private void peekFirst(String id, Deque<Integer> deque, int intended) {
int size = deque.size() == 0 ? 0 : deque.size();
explorer.of("peekFirst" + id);
Integer element = deque.peekFirst();
element = element == null ? -1 : element.intValue();
explorer.summary(element == intended && deque.size() == size);
}
public void peekLast() {
peekLast("", deque(2), 1);
peekLast("FromBounded", deque(2, 2), 1);
peekLast("FromEmpty", deque(0), -1);
peekLast("FromBoundedEmpty", deque(0, 2), -1);
}
private void peekLast(String id, Deque<Integer> deque, int intended) {
int size = deque.size() == 0 ? 0 : deque.size();
explorer.of("peekLast" + id);
Integer element = deque.peekLast();
element = element == null ? -1 : element.intValue();
explorer.summary(element == intended && deque.size() == size);
}
public void removeFirstOccurrence(Object removed) {
int size = 2;
removeFirstOccurrence("", deque(size));
removeFirstOccurrence("FromBounded", deque(size, size * 2));
}
private void removeFirstOccurrence(String id, Deque deque) {
int size = deque.size();
deque.addFirst(0);
deque.addLast(1);
explorer.of("removeFirstOccurrence" + id);
boolean result = deque.removeFirstOccurrence(0)
&& deque.size() == size + 1
&& deque.removeFirstOccurrence(1)
&& deque.size() == size;
explorer.summary(result);
deque.addLast(2);
explorer.of("removeFirstOccurrenceLastElement" + id)
.summary(deque.removeFirstOccurrence(2) && deque.size() == size);
deque.clear();
explorer.of("removeFirstOccurrenceFromEmpty" + id)
.summary(!deque.removeFirstOccurrence(0) && deque.size() == 0);
}
public void remove(Object removed) {
removeObject("", deque(3), 0);
removeObject("FromEmpty", deque(0), -1);
removeObject("FromBounded", deque(3, 3), 0);
removeObject("FromBoundedEmpty", deque(0, 3), -1);
}
private void removeObject(String id, Deque<Integer> deque, int removed) {
int size = deque.size() == 0 ? 0 : deque.size() - 1;
String prefix = "removeObject" + id;
explorer.of(prefix);
boolean changed = deque.remove(removed);
explorer.summary(size == 0 && !changed || changed && deque.size() == size);
}
public void removeLastOccurrence(Object removed) {
Deque deque = deque(2);
String intended = toString(new Integer[]{ 0, 1 });
deque.addLast(0);
removeLastOccurrence("", deque, 0, intended);
removeLastOccurrence("FromEmpty", deque(0), -1, "");
deque = deque(2, 3);
deque.addLast(0);
removeLastOccurrence("FromBounded", deque, 0, intended);
removeLastOccurrence("FromBoundedEmpty", deque(0, 3), -1, "");
}
public void removeLastOccurrence(String id, Deque<Integer> deque
, int removed, String intended) {
int size = deque.size() == 0 ? 0 : deque.size() - 1;
String prefix = "removeLastOccurrence" + id;
explorer.of(prefix);
boolean changed = deque.removeLastOccurrence(removed);
deque.addLast(null);
changed = deque.removeLastOccurrence(null) && changed;
explorer.summary((size == 0 && !changed
|| changed && deque.size() == size)
&& intended.equals(toString(deque.toArray())));
}
public void size() {
int size = 501;
size("", deque(size), size);
size("OfBounded", deque(size, size * 2), size);
}
public void size(String id, Deque deque, int result) {
int size = deque.size();
explorer.of("size" + id).summary(result == size);
}
public void iterator() {
iterator("", deque(5));
iterator("OfBounded", deque(5, 5));
}
private void iterator(String id, Deque deque) {
boolean result = true;
int index = 0;
explorer.of("iterator" + id);
for (Iterator<Integer> i = deque.iterator(); i.hasNext();) {
result = result && i.next() == index++;
}
explorer.summary(result);
int size = deque.size();
String prefix = "iterator" + id + "Overflown";
explorer.of(prefix);
result = true;
index = 0;
for (Iterator<Integer> i = deque.iterator(); index < size + 2;) {
try {
result = result && i.next() == index;
} catch (NoSuchElementException e) {
explorer.summary(result);
info(System.err, prefix + ": iterator overflown");
}
index++;
}
explorer.of("iterator" + id + "Remove");
Iterator<Integer> iterator = deque.iterator();
iterator.next();
iterator.remove();
explorer.summary(deque.size() == size - 1);
int dimension = deque.size();
explorer.of("iterator" + id + "RemoveFirst");
Iterator<Integer> i = deque.iterator();
i.next();
i.remove();
explorer.summary(deque.size() == dimension - 1
&& i.next() == dimension + (size - dimension) - deque.size());
explorer.of("iterator" + id + "RemoveWithoutCallingNext");
dimension = deque.size();
deque.iterator().remove();
explorer.summary(deque.size() == dimension && dimension > 0);
explorer.of("iterator" + id + "RemoveAll");
i = deque.iterator();
explorer.summary(removeAll(deque, i));
deque.add(0);
explorer.of("iterator" + id + "OfOneRemove");
i = deque.iterator();
i.next();
i.remove();
explorer.summary(deque.size() == 0);
i = deque.iterator();
prefix = "iterator" + id + "OfEmpty";
explorer.of(prefix);
result = !i.hasNext();
try {
i.next();
} catch (NoSuchElementException e) {
explorer.summary(result);
info(System.err, prefix + ": deque is empty");
}
}
private boolean removeAll(Deque<Integer> deque, Iterator<Integer> i) {
int pivot = 2;
while(i.hasNext() ) { if (i.next() != pivot) { i.remove(); } }
boolean result = deque.size() == 1
&& deque.descendingIterator().next() == pivot
&& deque.removeFirst() == pivot
&& deque.size() == 0;
return result;
}
public void descendingIterator() {
descendingIterator("", deque(5));
descendingIterator("OfBounded", deque(5, 5));
}
public void descendingIterator(String id, Deque deque) {
int size = deque.size();
explorer.of("descendingIterator" + id);
boolean result = true;
int index = size - 1;
for (Iterator<Integer> i = deque.descendingIterator(); i.hasNext();) {
result = result && i.next() == index--;
}
explorer.summary(result);
size = 5;
deque = deque(size);
String prefix = "descendingIterator" + id + "Overflown";
explorer.of(prefix);
result = true;
index = size + 2;
for (Iterator i = deque.descendingIterator(); index > -1;) {
try {
result = result && (Integer) i.next() == index - 3;
} catch(NoSuchElementException e) {
explorer.summary(result);
info(System.err, prefix + ": iterator overflown");
}
index--;
}
explorer.of("descendingIterator" + id + "Remove");
Iterator<Integer> i = deque.descendingIterator();
i.next();
i.remove();
explorer.summary(deque.size() == size - 1);
explorer.of("descendingIterator" + id + "RemoveFirst");
int dimension = deque.size();
i = deque.descendingIterator();
i.next();
i.remove();
explorer.summary(deque.size() == dimension - 1
&& i.next() == dimension + (size - dimension) - deque.size());
dimension = deque.size();
explorer.of("descendingIterator" + id + "RemoveWithoutCallingNext");
deque.descendingIterator().remove();
explorer.summary(deque.size() == dimension);
explorer.of("descendingIterator" + id + "RemoveAll");
i = deque.descendingIterator();
explorer.summary(removeAll(deque, i));
prefix = "descendingIterator" + id + "OfEmpty";
explorer.of(prefix);
i = deque.descendingIterator();
result = !i.hasNext();
try {
i.next();
} catch (NoSuchElementException e) {
explorer.summary(result);
info(System.err, prefix + ": iterator overflown");
}
deque.add(0);
explorer.of("descendingIterator" + id + "OfOneRemove");
i = deque.descendingIterator();
i.next();
i.remove();
explorer.summary(deque.size() == 0);
}
private void info(PrintStream stream, String message) {
display.info(stream, message);
}
public void overall() { explorer.overall(); }
private String stringed(int length) {
Integer[] result = new Integer[length];
for (int i = 0; i < length; i++) { result[i] = i; }
return toString(result);
}
private Deque<Integer> deque(int size) {
Deque<Integer> deque = PointDeque.object();
for (int i = 0; i < size; i++) { deque.addLast(i); }
return deque;
}
private Deque<Integer> deque(int size, int capacity) {
Deque<Integer> deque = PointDeque.object(capacity);
for (int i = 0; i < size; i++) { deque.addLast(i); }
return deque;
}
private static String toString(Object[] array) {
if (array == null || array.length == 0) { return ""; }
StringBuilder result = new StringBuilder("[");
String separator = ", ";
for (int i = 0; i < array.length; i++) { result.append(array[i]).append(separator); }
result.delete(result.length() - separator.length(), result.length());
return result.append("]").toString();
}
private List<Number> toList(Object ... objects) {
List list = new java.util.ArrayList();
for (int i = 0; i < objects.length; i++) { list.add(objects[i]); }
return list;
}
}