Concrete

Fully persistent data structures in Java.

Implementation follows "Purely Functional Data Structures" by Chris Okasaki unless said otherwise.

PStack

O(1) operations: pushFront, peekFront, popFront, size, isEmpty. O(N) operations: reverse.

PStack<String> stack = PStack.newStack();
stack = stack.pushFront("a");
assertEquals("a", stack.peekFront());
stack = stack.popFront();
assertTrue(stack.isEmpty());

PStack runtime performance is always better than ArrayList and LinkedList (ignoring GC overhead): benchmark report, code.

Stacks support constant append operation:

PStack<String> stack1 = PStack.newStack("a", "b");
PStack<String> stack2 = PStack.newStack("c", "d");
assertEquals("[a, b, c, d]", stack1.append(stack2).toString());

PQueue

O(1) operations: pushBack, popFront, peekFront, size, isEmpty

Queue with amortized O(1) performance:

PQueue<String> queue = PQueue.newAmortizedQueue();
queue = queue.pushBack("a");
queue = queue.pushBackAll("b", "c");
assertEquals("a", queue.peekFront());
queue = queue.popFront();
assertEquals("b", queue.peekFront());
queue = queue.popFront();
assertEquals("[c]", queue.toString());

Realtime queue with guaranteed O(1) performance:

PQueue<String> queue = PQueue.newRealtimeQueue();
queue = queue.pushBack("a");
queue = queue.pushBackAll("b", "c");
assertEquals("a", queue.peekFront());
queue = queue.popFront();
assertEquals("b", queue.peekFront());
queue = queue.popFront();
assertEquals("[c]", queue.toString());

PDeque

O(1) operations: pushFront, popFront, peekFront, pushBack, peekBack, peekFront, size, isEmpty.

Deque with amortized O(1) performance:

PDeque<String> deque = PDeque.newAmortizedDeque();
deque = deque.pushBackAll("b", "c");
deque = deque.pushFront("a");
deque = deque.popBack();
assertEquals("[a, b]", deque.toString());

PArray

Random-access array.

O(log N) operations: pushFront, popFront, peekFront, set, get.

PArray<String> array = PArray.newBinaryArray();
array = array.pushFrontAll("a", "b", "c");
assertEquals("b", array.get(1));
array = array.set(1, "X");
assertEquals("[a, X, c]", array.toString());

Base Classes

• PIterable with O(1) operations: popFront, peekFront, isEmpty.
• PCollection with O(1) operations: isEmpty, clear, size.