Created
April 13, 2012 23:41
-
-
Save msfroh/2381017 to your computer and use it in GitHub Desktop.
Immutable Lists
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public abstract class ImmutableList<T> implements Iterable<T> { | |
public abstract T head(); | |
public abstract ImmutableList<T> tail(); | |
public abstract boolean isEmpty(); | |
public ImmutableList<T> prepend(T element) { | |
return new NonEmptyList<T>(element, this); | |
} | |
@Override | |
public Iterator<T> iterator() { | |
return new Iterator<T>() { | |
private ImmutableList<T> list = ImmutableList.this; | |
@Override | |
public boolean hasNext() { | |
return !list.isEmpty(); | |
} | |
@Override | |
public T next() { | |
T element = list.head(); | |
list = list.tail(); | |
return element; | |
} | |
@Override | |
public void remove() { | |
// Java iterators must implement remove(), even though they | |
// make no sense for immutable collections. Fortunately, | |
// it is specified as an optional operation. | |
throw new RuntimeException("Cannot remove from immutable list"); | |
} | |
}; | |
} | |
public static <T> ImmutableList<T> nil() { | |
return EMPTY_LIST; | |
} | |
private static final EmptyList EMPTY_LIST = new EmptyList(); | |
private static class EmptyList extends ImmutableList { | |
@Override | |
public Object head() { | |
throw new NoSuchElementException("head() called on empty list"); | |
} | |
@Override | |
public ImmutableList tail() { | |
throw new NoSuchElementException("tail() called on empty list"); | |
} | |
@Override | |
public boolean isEmpty() { | |
return true; | |
} | |
} | |
private static class NonEmptyList<T> extends ImmutableList<T> { | |
private final T element; | |
private final ImmutableList<T> tail; | |
private NonEmptyList(final T element, final ImmutableList<T> tail) { | |
this.element = element; | |
this.tail = tail; | |
} | |
@Override | |
public T head() { | |
return element; | |
} | |
@Override | |
public ImmutableList<T> tail() { | |
return tail; | |
} | |
@Override | |
public boolean isEmpty() { | |
return false; | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public abstract class ImmutableList<T> implements Iterable<T> { | |
/* ... previous method and subclass definitions ... */ | |
public ImmutableList<T> reverse() { | |
return reverseHelper(this, ImmutableList.<T>nil()); | |
} | |
// This tail-recursive function "pours" values off the input stack | |
// onto the output stack. Unfortunately, it will also overflow the stack | |
// for a large input list. | |
private static <T> ImmutableList<T> reverseHelper(ImmutableList<T> input, | |
ImmutableList<T> output) { | |
if (input == nil()) { | |
return output; | |
} | |
return reverseHelper(input.tail(), output.prepend(input.head())); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public abstract class ImmutableList<T> implements Iterable<T> { | |
/* ... previous method and subclass definitions ... */ | |
public ImmutableList<T> reverse() { | |
ImmutableList<T> input = this; | |
ImmutableList<T> output = nil(); | |
while (input != nil()) { | |
output = output.prepend(input.head()); | |
input = input.tail(); | |
} | |
return output; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public abstract class ImmutableList<T> implements Iterable<T> { | |
/* ... previous method and static class definitions ... */ | |
public final int size() { | |
if (isEmpty()) { | |
return 0; | |
} | |
return 1 + tail().size(); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public abstract class ImmutableList<T> implements Iterable<T> { | |
/* ... previous method and static class definitions ... */ | |
public final int size() { | |
ImmutableList<T> input = this; | |
int size = 0; | |
while (!input.isEmpty()) { | |
size++; | |
input = input.tail(); | |
} | |
return size; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public abstract class ImmutableList<T> implements Iterable<T> { | |
/* ... previous method and static class definitions ... */ | |
public final int size() { | |
return sizeHelper(this, 0); | |
} | |
// This method is tail-recursive. When it calls itself, it is the last | |
// operation before returning. | |
// Unfortunately, it still overflows the stack in Java. | |
private static <T> int sizeHelper(ImmutableList<T> input, int output) { | |
if (input.isEmpty()) { | |
return output; | |
} | |
return sizeHelper(input.tail(), output + 1); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public abstract class ImmutableList<T> implements Iterable<T> { | |
/* ... previous method and static class definitions ... */ | |
public final int size() { | |
return sizeHelper(this, 0); | |
} | |
// This method compiles to roughly the same bytecode as the tail-recursive | |
// version of sizeHelper would, if the Java compiler supported tail-call | |
// optimization. (The while(true) basically gives us a "goto" back to the | |
// start of the method.) | |
private static <T> int sizeHelper(ImmutableList<T> input, int output) { | |
while (true) { | |
if (input.isEmpty()) { | |
return output; | |
} | |
output = output + 1; | |
input = input.tail(); | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public abstract class ImmutableList<T> implements Iterable<T> { | |
/* ... previous method and static class definitions ... */ | |
public static <T> ImmutableList<T> list(T... elements) { | |
ImmutableList<T> output = nil(); | |
for (int i = elements.length - 1; i >= 0 ; i--) { | |
output = output.prepend(elements[i]); | |
} | |
return output; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import org.junit.Test; | |
import static collections.ImmutableList.list; | |
import static org.junit.Assert.assertEquals; | |
public class ImmutableListTest { | |
@Test | |
public void testListIteration() { | |
ImmutableList<Integer> list = list(1, 2, 3); | |
int i = 1; | |
for (Integer l : list) { | |
assertEquals(i++, l.intValue()); | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* ... previous imports ... */ | |
public class ImmutableListTest { | |
/* ... previous test definitions ... */ | |
// This tests the size() method using a relatively large | |
// list of 100k Bytes. A recursive implementation of | |
// size() won't be able to handle that many recursive | |
// calls on the stack. | |
@Test | |
public void testSize() throws Exception { | |
int size = 100000; | |
Byte[] bytes = new Byte[size]; | |
for (int i = 0; i < size; i++) { | |
bytes[i] = (byte) (i % 256); | |
} | |
ImmutableList<Byte> byteList = list(bytes); | |
assertEquals(size, byteList.size()); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment