Implementation of java.util.Deque interface according to object oriented programming principles - abstraction, encapsulation, inheritance , polymorphism - suitable for asynchronous | non-blocking setups. It consist of three elements linked arrays, each array holding reference to its adjacent siblings together with one element from the deque, that is arrays with the pattern new Object[] { fore, element, next } where fore and next are arrays with the same pattern while element is object passed to be hold reference of.
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 {
public static Object[] empty() { return new Object[] { null }; }
public static Object element(Object[] point) { return point[1]; }
private static boolean leaf(Object[] point) {
return 1 == point.length;
}
public static Object[] next(Object[] point) {
return (Object[]) point[2];
}
public static Object[] fore(Object[] point) {
return (Object[]) point[0];
}
public static boolean remove(Object[] point) {
Object[] fore = (Object[]) point[0];
Object[] next = (Object[]) point[2];
if (fore.length == 3) {
fore[2] = next;
}
next[0] = (Object[]) point[0];
return true;
}
private Object[] points;
private final Object[] leaf;
public Point() {
Object[] empty = empty();
points = empty;
leaf = empty;
}
public boolean append(Object appendee) {
if (points == leaf) {
return prepend(appendee);
} else {
Object[] fore = edge();
Object[] next = Point.next(fore);
Object[] point = array(fore, appendee, next);
fore[2] = point;
next[0] = point;
}
return true;
}
public boolean prepend(Object prependee) {
Object[] point = array(new Object[] {}, prependee, points);
points[0] = point;
points = point;
return true;
}
private static Object[] array(Object ... objects) { return objects; }
public int size() {
if (points == leaf) { return 0; }
int i = 0;
Object[] point = points;
while(point != leaf) {
i++;
point = next(point);
}
return i;
}
public void clear() {
points = leaf;
leaf[0] = null;
}
public Object peakless() {
points = Point.next(points);
Object returnee = Point.element(Point.fore(points));
points[0] = Point.empty();
return returnee;
}
public Object endless() {
Object[] edge = edge();
if (points == edge) {
clear();
} else {
Point.remove(edge);
}
return Point.element(edge);
}
private Object[] edge() { return Point.fore(leaf); }
public Object peak() { return Point.element(points); }
public Object end() { return Point.element(edge()); }
public boolean contains(Object o) {
return null == o ? nullContained() : contained(o);
}
private boolean nullContained() {
boolean contained = false;
Object[] point = points;
while(!contained && !Point.leaf(point)) {
contained = null == point[1];
point = Point.next(point);
}
return contained;
}
private boolean contained(Object o) {
boolean contained = false;
Object[] point = points;
while(!contained && !Point.leaf(point)) {
contained = o.equals(point[1]);
point = Point.next(point);
}
return contained;
}
}
private static class Bounded extends Point {
private int capacity;
public Bounded(int boundry) { capacity = boundry; }
public boolean append(Object appendee) {
if (size() == capacity) { return false; }
return super.append(appendee);
}
public boolean prepend(Object prependee) {
if (size() == capacity) { return false; }
return super.prepend(prependee);
}
}
private static class Ascending<F> implements Iterator<F> {
interface Step { Object[] on(); }
private static class First implements Step {
private Ascending context;
private First(Ascending ascending) { context = ascending; }
@Override
public Object[] on() {
context.stepIndex++;
context.removerIndex++;
return context.of.points;
}
}
private static class Second implements Step {
private Ascending context;
private Second(Ascending ascending) { context = ascending; }
@Override
public Object[] on() {
context.stepIndex++;
context.removerIndex++;
if (context.actual == null) {
return Point.next(context.previous);
} else {
context.previous = context.actual;
return Point.next(context.actual);
}
}
}
private static class Third implements Step {
private Ascending context;
public Third(Ascending context) { this.context = context; }
@Override
public Object[] on() {
if (context.actual == null) {
return Point.next(context.previous);
} else {
context.previous = context.actual;
return Point.next(context.actual);
}
}
}
public static class NoopRemover implements Runnable {
@Override
public void run() {}
}
private static class RemoveFirst implements Runnable {
private Ascending context;
public RemoveFirst(Ascending iterator) { context = iterator; }
@Override
public void run() {
if (context.of.points == context.of.leaf) { return; }
context.of.peakless();
context.stepIndex--;
context.removerIndex--;
}
}
private static class Remover implements Runnable {
private Ascending context;
public Remover(Ascending iterator) { context = iterator; }
@Override
public void run() {
if (Point.next(context.previous) != context.actual) {
return;
}
Point.remove(context.actual);
context.actual = null;
}
}
private Point of;
private Object[] previous, actual;
private int stepIndex = 0, removerIndex = 0;
private Step[] returners;
private Runnable[] removers;
private boolean hasNext;
public Ascending(Point context) {
of = context;
hasNext = of.points != of.leaf;
returners = new Step[] { new First(this)
, new Second(this)
, new Third(this) };
removers = new Runnable[] { new NoopRemover()
, new RemoveFirst(this)
, new Remover(this) };
}
@Override
public boolean hasNext() { return hasNext; }
@Override
public F next() {
if (!hasNext()) { throw new NoSuchElementException(); }
actual = returners[stepIndex].on();
hasNext = Point.next(actual) != of.leaf;
return (F) Point.element(actual);
}
@Override
public void remove() {
if (actual == null) { return; }
removers[removerIndex].run();
}
}
private static class Descending<F> implements Iterator<F> {
private Point of;
private boolean hasNext;
private Object[] actual, previous;
public Descending(Point context) {
of = context;
hasNext = of.points != of.leaf;
}
@Override
public boolean hasNext() { return hasNext; }
@Override
public F next() {
if (!hasNext()) { throw new NoSuchElementException(); }
if (actual == null) {
actual = (previous == null) ? Point.fore(of.leaf)
: Point.fore(previous);
} else {
actual = glide(actual, Point.fore(actual));
}
hasNext = actual != of.points;
return (F) Point.element(actual);
}
private Object[] glide(Object[] former, Object[] next) {
previous = former;
return next;
}
public void remove() {
if (actual == null) { return; }
if (actual == of.points) {
of.peakless();
} else {
Point.remove(actual);
}
actual = null;
}
}
private static Point points() { return new Point(); }
private static Point points(int capacity) {
return new Bounded(capacity);
}
private Point of;
public PointDeque() { of = points(); }
public PointDeque(int capacity) {
this();
of = points(capacity);
}
@Override
public boolean isEmpty() { return of.points == of.leaf; }
@Override
public Object[] toArray() {
if (isEmpty()) { return new Object[] {}; }
int i = 0;
Object[] returnee = new Object[size()];
Object[] next = of.points;
while (next != of.leaf) {
returnee[i++] = Point.element(next);
next = Point.next(next);
}
return returnee;
}
@Override
public <T> T[] toArray(T[] a) {
if (isEmpty()) { return a; }
int i = 0;
for (Object[] t = (Object[]) of.points
; t != of.leaf && i < a.length
; t = Point.next(t)) {
a[i++] = (T) Point.element(t);
}
return a;
}
@Override
public boolean containsAll(Collection<?> c) {
if (isEmpty() || c.isEmpty()) { return false; }
boolean contains = true;
for (Iterator i = c.iterator(); contains && i.hasNext();) {
contains = contains && of.contains(i.next());
}
return contains;
}
@Override
public boolean removeAll(Collection<?> c) {
if (isEmpty()) { return false; }
boolean removed = false;
for (Object removee : c) {
while(!isEmpty() && ((null == removee && null == of.peak())
|| (null != removee
&& removee.equals(of.peak())))) {
of.peakless();
removed = true;
}
if (isEmpty()) { break; }
Object[] point = Point.next(of.points);
while(point != of.leaf) {
if (null == removee ? null == Point.element(point)
: removee.equals(Point.element(point))) {
Point.remove(point);
}
point = Point.next(point);
}
// if (isEmpty()) { break; }
}
return removed;
}
@Override
public boolean retainAll(Collection<?> c) {
if (isEmpty() || c.isEmpty()) { return false; }
boolean removed = false;
Object[] point = of.points;
while(point != of.leaf) {
Object element = Point.element(point);
if (null == element ? !nullContained(c)
: !contains(c, element)) {
if (point == of.points) {
of.peakless();
point = of.points;
} else {
Point.remove(point);
point = Point.next(point);
}
removed = true;
} else {
point = Point.next(point);
}
}
return removed;
}
private boolean nullContained(Collection c) {
boolean contains = false;
for (Iterator i = c.iterator(); !contains && i.hasNext(); ) {
contains = null == i.next();
}
return contains;
}
private boolean contains(Collection c, Object contained) {
boolean contains = false;
for (Iterator i = c.iterator(); !contains && i.hasNext(); ) {
contains = contained.equals(i.next());
}
return contains;
}
@Override
public void clear() { of.clear(); }
@Override
public void addFirst(E e) {
if (!of.prepend(e)) { throw new IllegalStateException(); }
}
@Override
public void addLast(E e) {
if (!of.append(e)) { throw new IllegalStateException(); }
}
@Override
public boolean offerFirst(E e) { return of.prepend(e); }
@Override
public boolean offerLast(E e) { return of.append(e); }
@Override
public E removeFirst() {
if (isEmpty()) { throw new NoSuchElementException(); }
return (E) of.peakless();
}
@Override
public E removeLast() {
if (isEmpty()) { throw new NoSuchElementException(); }
return (E) of.endless();
}
@Override
public E pollFirst() { return isEmpty() ? null : (E) of.peakless(); }
@Override
public E pollLast() { return isEmpty() ? null : (E) of.endless(); }
@Override
public E getFirst() {
if (isEmpty()) { throw new NoSuchElementException(); }
return (E) of.peak();
}
@Override
public E getLast() {
if (isEmpty()) { throw new NoSuchElementException(); }
return (E) of.end();
}
@Override
public E peekFirst() { return isEmpty() ? null : (E) of.peak(); }
@Override
public E peekLast() { return isEmpty() ? null : (E) of.end(); }
@Override
public boolean removeFirstOccurrence(Object o) {
if (isEmpty()) { return false; }
Object[] point = of.points;
if (null == o ? null == Point.element(point)
: o.equals(Point.element(point))) {
of.peakless();
return true;
}
point = Point.next(point);
boolean removed = false;
while (!removed && point != of.leaf) {
if (o == null && null == Point.element(point)
|| o.equals(Point.element(point))) {
removed = Point.remove(point);
}
point = Point.next(point);
}
return removed;
}
@Override
public boolean removeLastOccurrence(Object o) {
if (isEmpty()) { return false; }
boolean removed = false;
Object[] point = of.edge();
while (!removed && point != null) {
if ( o == null && null == Point.element(point)
|| o.equals(Point.element(point))) {
removed = Point.remove(point);
}
point = Point.fore(point);
}
return removed;
}
@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) {
for (E added : c) {
addLast(added);
}
return true;
}
@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 of.contains(o); }
@Override
public int size() { return of.size(); }
@Override
public Iterator<E> iterator() { return new Ascending<E>(of); }
@Override
public Iterator<E> descendingIterator() { return new Descending<E>(of); }
}
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.granular());
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("containsAllEmpty")
.summary(deque(0).containsAll(toList()) == false);
explorer.of("emptyDequeContainsAllEmpty")
.summary(deque(0).containsAll(toList()) == false);
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() == 5);
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 = 0;
for (int i = 0; i < dimension; i++) {
if (i != pivot) {
waved.add(i);
}
}
content = deque(0);
for (int i = 1; i < dimension; i++) { 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;
explorer.of("size").summary(deque(size).size() == 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();) {
result = result && i.next() == 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.
