The java.util.Deque implementation from Object oriented programming deque implementation that consists of three elements linked arrays, each array holding reference to its adjacent siblings together with one element from deque, that is arrays with pattern new Object[] { fore, element, next } where fore and next are arrays with aforementioned pattern and element is object passed to hold reference of, has changed to hold reference to each of the ends additionally to retainAll method that when called with empty collection of elements to retain has changed to clear the deque and to return true conversely to returning false without traversing the elements to retain or remove them. The references of both ends leverage abstracting the implementation of java.util.Iterator interface to support ascending and descending behaviour changing just the sibling that is read next after the read element.
import java.util.Collection;
import java.util.Deque;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class PointDeque<E> implements Deque<E> {
private static class Point {
private static Object[] empty() {
return new Object[] { null, null, null };
}
private static Object[] prepend(Object[] to, Object[] prependee) {
prependee[2] = to;
Object[] fore = (Object[]) to[0];
if (fore != null) {
prependee[0] = fore;
fore[2] = prependee;
}
to[0] = prependee;
return prependee;
}
public static Object[] remove(Object[] removee) {
Object[] fore = (Object[]) removee[0];
Object[] next = (Object[]) removee[2];
next[0] = fore;
fore[2] = next;
return removee;
}
private static Object[] of(Object element) {
return new Object[] { null, element, null };
}
private 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]; }
private final Object[] peak;
private final Object[] leaf;
public Point() {
peak = empty();
leaf = empty();
leaf[0] = peak;
peak[2] = leaf;
}
public boolean append(Object element) {
Point.prepend(leaf, Point.of(element));
return true;
}
public boolean prepend(Object element) {
Point.prepend(Point.next(peak), Point.of(element));
return true;
}
public <T> T peakless() { return Point.element(remove(next(peak))); }
public <T> T endless() { return Point.element(remove(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 ? nullContained() : contained(o);
}
private boolean nullContained() {
boolean contained = false;
Object[] point = peak;
while(!contained && leaf != point) {
contained = null == point[1];
point = Point.next(point);
}
return contained;
}
private boolean contained(Object o) {
boolean contained = false;
Object[] point = peak;
while(!contained && leaf != point) {
contained = o.equals(point[1]);
point = Point.next(point);
}
return contained;
}
}
private static class Bounded extends Point {
private int bound;
public Bounded(int boundry) { bound = boundry; }
@Override
public boolean append(Object element) {
if (size() == bound) { return false; }
return super.append(element);
}
@Override
public boolean prepend(Object element) {
if (size() == bound) { return false; }
return super.prepend(element);
}
}
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 Point points;
public PointDeque() { points = new Point(); }
public PointDeque(int capacity) { points = new Bounded(capacity); }
@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) {
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;
}
}
}
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(E e) {
if (!points.prepend(e)) { throw new IllegalStateException(); }
}
@Override
public void addLast(E e) {
if (!points.append(e)) { throw new IllegalStateException(); } }
@Override
public boolean offerFirst(E e) { return points.prepend(e); }
@Override
public boolean offerLast(E e) { return points.append(e); }
@Override
public E removeFirst() {
if (isEmpty()) { throw new NoSuchElementException(); }
return points.peakless();
}
@Override
public E removeLast() {
if (isEmpty()) { throw new NoSuchElementException(); }
return points.endless();
}
@Override
public E pollFirst() { return isEmpty() ? null : points.peakless(); }
@Override
public E pollLast() { return isEmpty() ? null : points.endless(); }
@Override
public E getFirst() {
if (isEmpty()) { throw new NoSuchElementException(); }
return Point.element(Point.next(points.peak));
}
@Override
public E getLast() {
if (isEmpty()) { throw new NoSuchElementException(); }
return Point.element(Point.fore(points.leaf));
}
@Override
public E peekFirst() {
if (isEmpty()) { return null; }
return Point.element(Point.next(points.peak));
}
@Override
public E 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(E e) {
addLast(e);
return true;
}
@Override
public boolean offer(E e) { return offerLast(e); }
@Override
public E remove() { return removeFirst(); }
@Override
public E poll() { return pollFirst(); }
@Override
public E element() { return getFirst(); }
@Override
public E peek() { return peekFirst(); }
@Override
public boolean addAll(Collection<? extends E> c) {
boolean result = !c.isEmpty();
for (E object : c) {
addLast(object);
}
return result;
}
@Override
public void push(E e) { addFirst(e); }
@Override
public E 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<E> iterator() { return new Ascending<>(points); }
@Override
public Iterator<E> descendingIterator() {
return new Descending<>(points);
}
}
Code snippet to showcase usage:
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.timedGranular());
Object object = new Object();
Collection<?> objects = Collections.emptyList();
test.toArray();
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(); }
}
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 + " ms]";
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();
}
@Override
public void summary(boolean result) {
elapsed = (System.nanoTime() - start) / 1000;
super.summary(result);
}
public void print() {
if (questing()) {
System.out.println(explored() + " ... Exploring...");
return;
}
String string = result() ? "Passed" : "Failed";
String message = explored() + " ... " + string
+ " [elapsed: " + elapsed + " ns]";
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 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 Explorer explorer;
public PointDequeTest() { this.explorer = new Granular(); }
public PointDequeTest(Explorer explorer) { this.explorer = explorer; }
public void toArray() {
int length = 5;
Integer[] array = deque(length).toArray(new Integer[length]);
explorer.of("toArray")
.summary(toString(array).equals(stringed(length)));
length = 26;
int size = length/2;
array = deque(length).toArray(new Integer[size]);
explorer.of("toArrayUnderdimesioned")
.summary(toString(array).equals(stringed(size)));
}
public void toObjectArray() {
int length = 3;
Deque deque = deque(length);
Object[] array = deque.toArray();
explorer.of("toObjectArray");
explorer.summary(toString(array).equals(stringed(length)));
}
public void clear() {
int length = 3;
Deque deque = deque(length);
explorer.of("clear");
boolean result = deque.size() == length;
deque.clear();
explorer.summary(result && deque.size() == 0);
}
public void containsAll(Collection c) {
Deque deque = deque(7);
List contained = toList(0, 1, 5);
explorer.of("containsAll")
.summary(deque.containsAll(contained));
explorer.of("emptyContainsAll")
.summary(!deque(0).containsAll(contained));
explorer.of("emptyDequeContainsAllEmpty")
.summary(deque(0).containsAll(toList()));
explorer.of("notContainsAll")
.summary(deque(1).containsAll(contained) == false);
}
public void removeAll(Collection c) {
int length = 8;
Deque deque = deque(length);
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("removeAll");
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("removeAllUntilEmpty");
result = deque.size() == length + 3
&& deque.removeAll(toList(null, 0, 1, 2, 3, 12))
&& deque.size() == 0;
explorer.summary(result);
explorer.of("removeAllFromEmpty")
.summary(deque(0).removeAll(toList(0, 2, 5)) == false);
}
public void addFirst(Object added) {
Deque deque = deque(0);
int length = 6;
Integer[] array = new Integer[length];
for (int i = length - 1; i > - 1; i--) {
array[length - 1 - i] = i;
}
String intended = toString(array);
explorer.of("addFirst");
for (int i = 0; i < length; i++) { deque.addFirst(i); }
boolean result = deque.size() == length
&& intended.equals(toString(deque.toArray()));
explorer.summary(result);
String prefix = "addFirstToBounded";
int size = 3;
deque = deque(size, 5);
explorer.of(prefix);
result = false;
deque.addFirst(1);
result = deque.size() == size + 1;
deque.addFirst(2);
result = result && deque.size() == size + 2;
try {
deque.addFirst(3);
result = false;
} catch(IllegalStateException e) {
System.err.println(prefix + ": overflow due to capacity bound");
result = result && true;
}
explorer.summary(result);
}
public void push(Object added) {
Deque deque = deque(0);
int length = 6;
Integer[] array = new Integer[length];
for (int i = length - 1; i > - 1; i--) {
array[length - 1 - i] = i;
}
String intended = toString(array);
explorer.of("push");
for (int i = 0; i < length; i++) { deque.push(i); }
boolean result = deque.size() == length
&& intended.equals(toString(deque.toArray()));
explorer.summary(result);
String prefix = "pushToBounded";
int size = 3;
deque = deque(size, 5);
explorer.of(prefix);
result = false;
deque.push(1);
result = deque.size() == size + 1;
deque.push(2);
result = result && deque.size() == size + 2;
try {
deque.push(3);
result = false;
} catch(IllegalStateException e) {
System.err.println(prefix + ": overflow due to capacity bound");
result = result && true;
}
explorer.summary(true);
}
public void addLast(Object added) {
Deque deque = deque(1);
int length = 6, start = 1, end = length;
Integer[] array = new Integer[length];
for (int i = 0; i < length - start; i++) { array[i] = i; }
for (int i = start; i < end; i++) {
deque.addLast(i); array[i] = i;
}
String intended = toString(array);
explorer.of("addLast");
boolean result = deque.size() == length
&& intended.equals(toString(deque.toArray()));
explorer.summary(result);
deque = deque(0);
explorer.of("addLastToEmpty");
result = deque(0).size() == 0;
deque.addLast(1);
result = result && deque.size() == 1;
explorer.summary(result);
String prefix = "addLastToBounded";
int size = 3;
deque = deque(size, 5);
explorer.of(prefix);
result = false;
deque.addLast(1);
result = deque.size() == size + 1;
deque.addLast(2);
result = result && deque.size() == size + 2;
try {
deque.addLast(3);
result = false;
} catch(IllegalStateException e) {
System.err.println(prefix + ": overflow due to capacity bound");
result = result && true;
}
explorer.summary(result);
}
public void addAll(Collection c) {
Deque deque = deque(1);
Collection added = toList(1, 2, 3, 4, 5, 6);
explorer.of("addAll");
boolean result = deque.addAll(added)
&& deque.size() == added.size() + 1;
explorer.summary(result);
deque = deque(0);
explorer.of("addAllToEmpty")
.summary(deque.addAll(added)
&& deque.size() == added.size());
int size = 2, capacity = 5;
deque = deque(size, capacity);
explorer.of("addAllToBounded");
result = deque.size() == 2;
try {
deque.addAll(added);
result = false;
} catch(IllegalStateException e) {
result = result && deque.size() == capacity;
}
explorer.summary(result);
}
public void add(Object added) {
Deque deque = deque(1);
int length = 6, start = 1, end = length;
Integer[] array = new Integer[length];
for (int i = 0; i < length - start; i++) { array[i] = i; }
explorer.of("add");
for (int i = start; i < end; i++) {
deque.addLast(i);
array[i] = i;
}
String intended = toString(array);
boolean result = deque.size() == length
&& intended.equals(toString(deque.toArray()));
explorer.summary(result);
deque = deque(0);
explorer.of("addToEmpty");
result = deque.size() == 0;
deque.add(1);
result = result && deque.size() == 1;
explorer.summary(result);
String prefix = "addToBounded";
int size = 3;
deque = deque(size, 5);
explorer.of(prefix);
result = false;
deque.addLast(1);
result = deque.size() == size + 1;
deque.addLast(2);
result = result && deque.size() == size + 2;
try {
deque.add(3);
result = false;
} catch(IllegalStateException e) {
System.err.println(prefix + ": overflow due to capacity bound");
result = result && true;
}
explorer.summary(result);
}
public void offerFirst(Object added) {
Deque deque = deque(0);
explorer.of("offerFirst")
.summary(deque.offerFirst(2) && deque.size() == 1);
deque = deque(0, 1);
explorer.of("offerFirstToBounded");
boolean result = deque.offerFirst(1) && deque.size() == 1
&& !deque.offerFirst(2)
&& deque.size() == 1;
explorer.summary(result);
}
public void offerLast(Object added) {
Deque deque = deque(0);
explorer.of("offerLast");
explorer.summary(deque.offerLast(2) && deque.size() == 1);
deque = deque(0, 1);
explorer.of("offerLastToBounded");
boolean result = deque.offerLast(1) && deque.size() == 1
&& !deque.offerLast(2)
&& deque.size() == 1;
explorer.summary(result);
}
public void offer(Object added) {
Deque deque = deque(0);
explorer.of("offer");
explorer.summary(deque.offer(2) && deque.size() == 1);
deque = deque(0, 1);
explorer.of("offerToBounded");
boolean result = deque.offer(1) && deque.size() == 1
&& !deque.offer(2) && deque.size() == 1;
explorer.summary(result);
}
public void pop() {
int size = 3;
Deque<Integer> deque = deque(size);
explorer.of("pop")
.summary(0 == deque.pop() && deque.size() == size - 1);
String prefix = "popFromEmpty";
deque = deque(0);
explorer.of(prefix);
boolean result = true;
try {
deque.pop();
result = false;
} catch(NoSuchElementException e) {
System.err.println(prefix + ": deque is empty");
}
explorer.summary(result);
}
public void removeFirst() {
int size = 3;
Deque<Integer> deque = deque(size);
explorer.of("removeFirst")
.summary(0 == deque.removeFirst()
&& deque.size() == size - 1);
String prefix = "removeFirstFromEmpty";
deque = deque(0);
explorer.of(prefix);
boolean result = true;
try {
deque.removeFirst();
result = false;
} catch(NoSuchElementException e) {
System.err.println(prefix + ": deque is empty");
}
explorer.summary(result);
}
public void remove() {
int length = 3;
Deque<Integer> deque = deque(length);
explorer.of("remove");
explorer.summary(0 == deque.remove() && deque.size() == length - 1);
String prefix = "removeFromEmpty";
deque = deque(0);
explorer.of(prefix);
boolean result = true;
try {
deque.remove();
result = false;
} catch(NoSuchElementException e) {
System.err.println(prefix + ": deque is empty");
}
explorer.summary(result);
}
public void removeLast() {
int size = 5;
Deque<Integer> deque = deque(size);
deque.addLast(null);
explorer.of("removeLast");
boolean result = deque.removeLast() == null
&& deque.size() == size
&& deque.removeLast() == 4
&& deque.size() == size - 1;
explorer.summary(result);
deque = deque(1);
explorer.of("removeLastSingleElement")
.summary(deque.removeLast() == 0 && deque.size() == 0);
String prefix = "removeLastFromEmpty";
deque = deque(0);
explorer.of(prefix);
result = true;
try {
deque.removeLast();
result = false;
} catch(NoSuchElementException e) {
System.err.println(prefix + ": deque is empty");
}
explorer.summary(result);
}
public void contains(Object added) {
Deque deque = deque(7);
explorer.of("contains").summary(deque.contains(6));
explorer.of("notContains").summary(deque.contains(26) == false);
}
public void retainAll(Collection c) {
Deque deque = deque(5);
explorer.of("retainAll");
explorer.summary(deque.retainAll(toList(5, 2, 1, 7))
&& deque.size() == 2);
int size = 5;
deque = deque(size);
explorer.of("retainAllMultipleOccurences");
for (int i = 0; i < size; i++) { deque.addFirst(i); }
boolean result = deque.retainAll(toList(2, 1)) && deque.size() == 4;
explorer.summary(result);
deque = deque(5);
explorer.of("retainAllEmptyCollection");
explorer.summary(deque.retainAll(toList()) && deque.size() == 0);
deque = deque(0);
explorer.of("retainAllEmpty");
result = deque.retainAll(toList(5, 2, 1, 7)) == false
&& deque.size() == 0;
explorer.summary(result);
int length = 101;
Deque context = deque(length);
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("retainAllWithdrawRetainee");
Deque subject = deque(length);
for (int i = 0; i < length; i++) { subject.addLast(i); }
Collection waved = deque(0);
int pivot = 8;
for (int i = 0; i < dimension; i++) {
if (i != pivot) {
waved.add(i);
}
}
content = deque(0);
for (int i = 0; i < dimension; i++) {
if (i != pivot) {
content.add(i);
}
}
for (int i = 0; i < dimension; i++) { content.add(i); }
String achievee = toString(content.toArray());
Runnable summary = new Runnable() {
@Override
public void run() {
String string = PointDequeTest.toString(subject.toArray());
explorer.summary(achievee.equals(string));
}
};
retainer = new Thread(new Runnable() {
@Override
public void run() {
subject.retainAll(waved);
summary.run();
}
});
waver = new Thread(new Runnable() {
@Override
public void run() { waved.add(pivot); }
});
retainer.start();
waver.start();
explorer.of("retainAllAddRetainee");
}
public void pollFirst() {
int size = 2;
Deque<Integer> deque = deque(size);
explorer.of("pollFirst")
.summary(deque.pollFirst() == 0 && deque.size() == size - 1);
deque = deque(0);
explorer.of("pollFirstFromEmpty")
.summary(deque.pollFirst() == null && deque.size() == 0);
}
public void poll() {
int size = 2;
Deque<Integer> deque = deque(size);
explorer.of("poll")
.summary(deque.poll() == 0 && deque.size() == size - 1);
deque = deque(0);
explorer.of("pollFromEmpty")
.summary(deque.poll() == null && deque.size() == 0);
}
public void pollLast() {
int size = 2;
Deque<Integer> deque = deque(size);
explorer.of("pollLast")
.summary(deque.pollLast() == 1 && deque.size() == size - 1);
deque = deque(0);
explorer.of("pollLastFromEmpty");
explorer.summary(deque.pollLast() == null && deque.size() == 0);
}
public void getFirst() {
int size = 1;
Deque<Integer> deque = deque(size);
explorer.of("getFirst")
.summary(deque.getFirst() == 0 && deque.size() == size);
String prefix= "getFirstFromEmpty";
size = 0;
deque = deque(size);
boolean result = false;
explorer.of(prefix);
try {
deque.getFirst();
} catch(NoSuchElementException e) {
System.err.println(prefix + ": deque is empty");
result = deque.size() == size;
}
explorer.summary(result);
}
public void element() {
int size = 1;
Deque<Integer> deque = deque(size);
explorer.of("element")
.summary(deque.element() == 0 && deque.size() == size);
String prefix= "elementFromEmpty";
size = 0;
deque = deque(size);
boolean result = false;
explorer.of(prefix);
try {
deque.element();
} catch(NoSuchElementException e) {
System.err.println(prefix + ": deque is empty");
result = deque.size() == size;
}
explorer.summary(result);
}
public void peek() {
int size = 1;
Deque<Integer> deque = deque(size);
explorer.of("peek")
.summary(deque.peek() == 0 && deque.size() == size);
deque = deque(0);
explorer.of("peekFromEmpty")
.summary(deque.peek() == null && deque.size() == 0);
}
public void getLast() {
int size = 2;
Deque<Integer> deque = deque(size);
explorer.of("getLast")
.summary(deque.getLast() == 1 && deque.size() == size);
String prefix = "getLastFromEmpty";
size = 0;
deque = deque(size);
boolean result = false;
explorer.of(prefix);
try {
deque.getLast();
} catch(NoSuchElementException e) {
System.err.println(prefix + ": deque is empty");
result = deque.size() == size;
}
explorer.summary(result);
}
public void peekFirst() {
int size = 1;
Deque<Integer> deque = deque(size);
explorer.of("peekFirst")
.summary(deque.peekFirst() == 0 && deque.size() == size);
deque = deque(0);
explorer.of("peekFirstFromEmpty");
explorer.summary(deque.peekFirst() == null && deque.size() == 0);
}
public void peekLast() {
int size = 2;
Deque<Integer> deque = deque(size);
explorer.of("peekLast")
.summary(deque.peekLast() == 1 && deque.size() == size);
size = 0;
deque = deque(size);
explorer.of("peekLastFromEmpty")
.summary(deque.peekLast() == null && deque.size() == size);
}
public void removeFirstOccurrence(Object removed) {
Deque deque = deque(2);
explorer.of("removeFirstOccurrence");
deque.addFirst(0);
deque.addLast(1);
boolean result = deque.removeFirstOccurrence(0)
&& deque.size() == 3
&& deque.removeFirstOccurrence(1)
&& deque.size() == 2;
explorer.summary(result);
deque = deque(2);
deque.addLast(2);
explorer.of("removeFirstOccurrenceLastElement")
.summary(deque.removeFirstOccurrence(2)
&& deque.size() == 2);
deque = deque(0);
explorer.of("removeFirstOccurrenceFromEmpty")
.summary(!deque.removeFirstOccurrence(0)
&& deque.size() == 0);
}
public void remove(Object removed) {
Deque deque = deque(2);
deque.addFirst(0);
explorer.of("removeObject")
.summary(deque.remove(0) && deque.size() == 2);
deque = deque(0);
explorer.of("removeObjectFromEmpty")
.summary(!deque.remove(0) && deque.size() == 0);
}
public void removeLastOccurrence(Object removed) {
Deque deque = deque(2);
deque.addLast(0);
String intended = toString(new Integer[]{ 0, 1 });
explorer.of("removeLastOccurrence");
boolean result = deque.removeLastOccurrence(0)
&& deque.size() == 2
&& intended.equals(toString(deque.toArray()));
deque.addLast(null);
result = result && deque.removeLastOccurrence(null)
&& deque.size() == 2
&& intended.equals(toString(deque.toArray()));
explorer.summary(result);
deque = deque(0);
explorer.of("removeLastOccurrenceFromEmpty")
.summary(!deque.removeLastOccurrence(0)
&& deque.size() == 0);
}
public void size() {
int size = 501;
int dimension = deque(size).size();
explorer.of("size").summary(dimension == size);
}
public void iterator() {
Deque deque = deque(5);
explorer.of("iterator");
boolean result = true;
int index = 0;
for (Iterator<Integer> i = deque.iterator(); i.hasNext();) {
Integer element = i.next();
result = result && element == index++;
}
explorer.summary(result);
int size = 5;
deque = deque(size);
explorer.of("iteratorOverflown");
result = true;
boolean excepted = false;
index = 0;
for (Iterator<Integer> i = deque.iterator(); index < size + 2;) {
try {
result = result && i.next() == index;
} catch(NoSuchElementException e) {
excepted = true;
}
index++;
}
explorer.summary(result && excepted);
deque = deque(0);
Iterator<Integer> i = deque.iterator();
explorer.of("iteratorOfEmpty");
result = !i.hasNext();
excepted = false;
try {
i.next();
} catch(NoSuchElementException e) {
excepted = true;
}
explorer.summary(result && excepted);
size = 5;
deque = deque(size);
explorer.of("iteratorRemove");
Iterator<Integer> iterator = deque.iterator();
iterator.next();
iterator.remove();
explorer.summary(deque.size() == size - 1);
size = 5;
deque = deque(size);
explorer.of("iteratorRemoveFirst");
i = deque.iterator();
i.next();
i.remove();
explorer.summary(deque.size() == size - 1
&& i.next() == size - deque.size());
size = 5;
deque = deque(size);
explorer.of("iteratorRemoveAll");
i = deque.iterator();
explorer.summary(removeAll(deque, i));
deque = deque(1);
explorer.of("iteratorOfOneRemove");
i = deque.iterator();
i.next();
i.remove();
explorer.summary(deque.size() == 0);
size = 5;
deque = deque(size);
explorer.of("iteratorRemoveWithoutCallingNext");
deque.iterator().remove();
explorer.summary(deque.size() == size);
}
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() {
int size = 5;
Deque deque = deque(size);
explorer.of("descendingIterator");
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);
explorer.of("descendingIteratorOverflown");
result = true;
boolean excepted = false;
index = size + 2;
for (Iterator i = deque.descendingIterator(); index > -1;) {
try {
result = result && (Integer) i.next() == index - 3;
} catch(NoSuchElementException e) {
excepted = true;
}
index--;
}
explorer.summary(result && excepted);
deque = deque(0);
explorer.of("descendingIteratorOfEmpty");
Iterator<Integer> i = deque.descendingIterator();
result = !i.hasNext();
excepted = false;
try {
i.next();
} catch(NoSuchElementException e) {
excepted = true;
}
explorer.summary(result && excepted);
size = 5;
deque = deque(size);
explorer.of("descendingIteratorRemove");
i = deque.descendingIterator();
i.next();
i.remove();
explorer.summary(deque.size() == size - 1);
size = 5;
deque = deque(size);
explorer.of("descendingIteratorRemoveFirst");
i = deque.descendingIterator();
i.next();
i.remove();
explorer.summary(deque.size() == size - 1 && i.next() == size - 2);
size = 5;
deque = deque(size);
explorer.of("descendingIteratorRemoveAll");
i = deque.descendingIterator();
explorer.summary(removeAll(deque, i));
deque = deque(1);
explorer.of("descendingIteratorOfOneRemove");
i = deque.descendingIterator();
i.next();
i.remove();
explorer.summary(deque.size() == 0);
size = 5;
deque = deque(size);
explorer.of("descendingIteratorRemoveWithoutCallingNext");
deque.descendingIterator().remove();
explorer.summary(deque.size() == size);
}
public void overall() { explorer.overall(); }
private String stringed(int length) {
Integer[] intended = new Integer[length];
for (int i = 0; i < length; i++) { intended[i] = i; }
return toString(intended);
}
private Deque<Integer> deque(int size) {
Deque<Integer> deque = new PointDeque<>();
for (int i = 0; i < size; i++) { deque.addLast(i); }
return deque;
}
private Deque<Integer> deque(int size, int capacity) {
Deque<Integer> deque = new PointDeque<>(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;
}
}
Although the review request is for deque implementation any feedback is welcome.
