After reading some articles about immutability, I found out that there are persistent data structures. In the following, I implemented a stack as a persistent data structure.
What I like about the code in the current state
- it contains no if-statements
- no method is longer than one line
- it works like recursion
Implementation
The implementation is based on the abstraction Stack
, which has two concrete data-types: EmptyStack
and NonEmptyStack
. A Stack
needs to implement 4 methods as described below.
public interface Stack<E> {
/**
* @return the number of elements
*/
int size();
/**
* adds a new element to the top of the {@code Stack}
*
* @param top represents the new element to be added
* @return a {@code Stack} with {@code top} on it
*/
Stack<E> push(E top);
/**
* removes the top element of the {@code Stack}
*
* @return a {@code Stack} without the top element
*/
Stack<E> pop();
/**
* @return if {@code Stack} is empty {@code Optional.empty};
* otherwise {@code Optional.of(E)} where {@code E} is the top element
*/
Optional<E> top();
}
The EmptyStack
represents the base case: when a Stack
has no element. For each method it is easy to predict all return values:
- the
size
is always0
push()
always will return aNonEmptyStack
with the new top element and the current instance as the previous versionpop()
can't return a top element; so it always will return anEmptyStack
top()
can't return a top element; so it always will return anOptional.empty
class EmptyStack<E> implements Stack<E> {
@Override
public int size() {
return 0;
}
@Override
public Stack<E> push(E top) {
return new NonEmptyStack<>(top, this);
}
@Override
public Stack<E> pop() {
return this;
}
@Override
public Optional<E> top() {
return Optional.empty();
}
}
On the other hand there is the NonEmptyStack
which represents a Stack
that contains elements. A NonEmptyStack
is made up of its element on the top and a Stack
as its tail, which represents the previous version.
- the
size
is always the size of the previous version plus 1 for the new top element push()
always will return aNonEmptyStack
with the new top element and the current instance as the previous versionpop()
always returns the tailtop()
always returns the element which represents the top and since it can benull
I usedOptional.ofNullable
class NonEmptyStack<E> implements Stack<E> {
private final Stack<E> tail;
private final E top;
NonEmptyStack(E top, Stack<E> tail) {
this.tail = tail;
this.top = top;
}
@Override
public int size() {
return 1 + tail.size();
}
@Override
public Stack<E> push(E top) {
return new NonEmptyStack<>(top, this);
}
@Override
public Stack<E> pop() {
return tail;
}
@Override
public Optional<E> top() {
return Optional.ofNullable(top);
}
}
EmptyStack
and NonEmptyStack
are package-private therewith a client only interacts with a Stack
instead of two different implementations of it. For that I created a Factory StackFactory
which returns an EmptyStack
as a Stack
and the clients never interacts directly with a concrete implementation.
public class StackFactory<E> {
public Stack<E> create() {
return new EmptyStack<>();
}
}
Unit Tests
import org.junit.jupiter.api.Test;
import java.util.Optional;
import static org.junit.jupiter.api.Assertions.*;
class EmptyStackTest {
private final Stack<String> EMPTY_STACK = new EmptyStack<>();
@Test
void givenAnEmptyStack_whenQueryTheSize_thenExpect0() {
// arrange
// act
int size = EMPTY_STACK.size();
// assert
assertEquals(0, size);
}
@Test
void givenAnEmptyStack_whenPushAnElementToIt_thenExpectANonEmptyStack() {
// arrange
// act
Stack<String> stack = EMPTY_STACK.push("first");
// assert
assertTrue(stack instanceof NonEmptyStack);
}
@Test
void givenAnEmptyStack_whenRemoveTheFirstElement_thenExpectAnEmptyStack() {
// arrange
// act
Stack<String> stack = EMPTY_STACK.pop();
// assert
assertTrue(stack instanceof EmptyStack);
}
@Test
void givenAnEmptyStack_whenAccessTopElement_thenExpectItDoNotExists() {
// arrange
// act
Optional<String> top = EMPTY_STACK.top();
// assert
assertTrue(!top.isPresent());
}
}
import org.junit.jupiter.api.Test;
import java.util.Optional;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;
class NonEmptyStackTest {
private final String ITEM = "first";
@Test
void givenEmptyStackAndItem_whenInstantiateAndQueryTheSize_thenExpect1() {
// arrange
Stack<String> stack = new NonEmptyStack<>(ITEM, new EmptyStack<>());
// act
int size = stack.size();
// assert
assertEquals(1, size);
}
@Test
void givenNonEmptyStackWitOneItemAndANewItem_whenInstantiateAndQueryTheSize_thenExpect2() {
// arrange
NonEmptyStack<String> nonEmptyStack = new NonEmptyStack<>(ITEM, new EmptyStack<>());
Stack<String> stack = new NonEmptyStack<>(ITEM, nonEmptyStack);
// act
int size = stack.size();
// assert
assertEquals(2, size);
}
@Test
void givenEmptyStackAndItem_whenPushTheItemToTheStack_thenTheItemShouldBeInTheStack() {
// arrange
Stack<String> stack = new EmptyStack<>();
// act
Stack<String> nonEmptyStack = stack.push(ITEM);
// assert
assertEquals(Optional.of(ITEM), nonEmptyStack.top());
}
@Test
void givenNonEmptyStackAndItem_whenPushTheItemToTheStack_thenTheItemShouldBeInTheStack() {
// arrange
Stack<String> emptyStack = new EmptyStack<>();
Stack<String> firstChange = emptyStack.push("value");
// act
Stack<String> stack = firstChange.push(ITEM);
// assert
assertEquals(Optional.of(ITEM), stack.top());
}
@Test
void givenNonEmptyStackWithOneItem_whenRemoveTheTopItem_thenExpectEmptyStack() {
// arrange
Stack<String> testCandidate = new NonEmptyStack<>(ITEM, new EmptyStack<>());
// act
Stack<String> stack = testCandidate.pop();
// assert
assertTrue(stack instanceof EmptyStack);
}
@Test
void givenNonEmptyStackWithTwoItems_whenRemoveTheTopItem_thenExpectNonEmptyStack() {
// arrange
Stack<String> testCandidate = new NonEmptyStack<>(ITEM, new EmptyStack<>()).push(ITEM);
// act
Stack<String> stack = testCandidate.pop();
// assert
assertTrue(stack instanceof NonEmptyStack);
}
@Test
void givenNonEmptyStack_whenQueryTopItem_thenExpectTopItem() {
// arrange
Stack<String> stack = new NonEmptyStack<>(ITEM, new EmptyStack<>());
// act
Optional<String> top = stack.top();
// assert
assertEquals(Optional.of(ITEM), top);
}
}
Example
public class Main {
public static void main(String[] args) {
Stack<String> stack = new StackFactory<String>().create()
.push("first")
.push("second")
.push("third");
Stack<String> modified = stack.pop()
.pop();
modified.top()
.ifPresent(System.out::println); // "first"
modified.pop()
.top()
.ifPresent(System.out::println); // nothing happens
}
}
This little experiment was very entertaining. I appreciate every feedback and thank you very much for reading my code! :]