Created
April 1, 2011 11:57
-
-
Save msfroh/898037 to your computer and use it in GitHub Desktop.
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
final class DualBranch<T extends Comparable<T>> extends NonEmptyTree<T> { | |
private final ImmutableBinaryTree<T> leftChild; | |
private final ImmutableBinaryTree<T> rightChild; | |
public DualBranch(final T value, final ImmutableBinaryTree<T> left, final ImmutableBinaryTree<T> right) { | |
super(value); | |
leftChild = left; | |
rightChild = right; | |
} | |
@Override | |
protected ImmutableBinaryTree<T> getLeft() { | |
return leftChild; | |
} | |
@Override | |
protected ImmutableBinaryTree<T> getRight() { | |
return rightChild; | |
} | |
} |
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
final class EmptyTree<T extends Comparable<T>> extends ImmutableBinaryTree<T> { | |
private EmptyTree() { } | |
@Override | |
public ImmutableBinaryTree<T> add(final T element) { | |
return new Leaf<T>(element); | |
} | |
@Override | |
public ImmutableBinaryTree<T> remove(final T element) { | |
return this; | |
} | |
@Override | |
public boolean contains(final T element) { | |
return false; | |
} | |
@Override | |
public List<T> toList() { | |
return Collections.emptyList(); | |
} | |
@Override | |
protected ImmutableBinaryTree<T> addAll(final ImmutableBinaryTree<T> tree) { | |
return tree; | |
} | |
@SuppressWarnings("rawtypes") | |
private static final EmptyTree INSTANCE = new EmptyTree(); | |
@SuppressWarnings("unchecked") | |
static <U extends Comparable<U>> ImmutableBinaryTree<U> instance() { | |
return INSTANCE; | |
} | |
} |
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 ImmutableBinaryTree<T extends Comparable<T>> implements ImmutableSet<T> { | |
@Override | |
public abstract ImmutableBinaryTree<T> add(T element); | |
@Override | |
public abstract ImmutableBinaryTree<T> remove(T element); | |
protected abstract ImmutableBinaryTree<T> addAll(ImmutableBinaryTree<T> tree); | |
public static <U extends Comparable<U>> ImmutableBinaryTree<U> create() { | |
return EmptyTree.instance(); | |
}; | |
public static <U extends Comparable<U>> ImmutableBinaryTree<U> create(final U... elems) { | |
ImmutableBinaryTree<U> tree = create(); | |
for (U elem : elems) { | |
tree = tree.add(elem); | |
} | |
return tree; | |
}; | |
} |
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
final class Leaf<T extends Comparable<T>> extends NonEmptyTree<T> { | |
Leaf(final T val) { | |
super(val); | |
} | |
@Override | |
protected ImmutableBinaryTree<T> getLeft() { | |
return EmptyTree.instance(); | |
} | |
@Override | |
protected ImmutableBinaryTree<T> getRight() { | |
return EmptyTree.instance(); | |
} | |
} |
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
final class LeftBranch<T extends Comparable<T>> extends SingleBranch<T> { | |
LeftBranch(final T val, final ImmutableBinaryTree<T> child) { | |
super(val, child); | |
} | |
@Override | |
protected ImmutableBinaryTree<T> getLeft() { | |
return getChild(); | |
} | |
@Override | |
protected ImmutableBinaryTree<T> getRight() { | |
return EmptyTree.instance(); | |
} | |
} |
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
abstract class NonEmptyTree<T extends Comparable<T>> extends ImmutableBinaryTree<T> { | |
private final T value; | |
public NonEmptyTree(final T val) { | |
value = val; | |
} | |
protected abstract ImmutableBinaryTree<T> getLeft(); | |
protected abstract ImmutableBinaryTree<T> getRight(); | |
@Override | |
public final ImmutableBinaryTree<T> add(final T element) { | |
if (value.equals(element)) { | |
return this; | |
} | |
return addAll(new Leaf<T>(element)); | |
} | |
@Override | |
public final ImmutableBinaryTree<T> remove(final T element) { | |
if (value.equals(element)) { | |
return getLeft().addAll(getRight()); | |
} | |
if (value.compareTo(element) > 0) { | |
return replaceChildren(getLeft().remove(element), getRight()); | |
} | |
return replaceChildren(getLeft(), getRight().remove(element)); | |
} | |
@Override | |
protected ImmutableBinaryTree<T> addAll(final ImmutableBinaryTree<T> tree) { | |
ImmutableBinaryTree<T> emptyTree = EmptyTree.instance(); | |
if (tree == emptyTree) { | |
return this; | |
} | |
NonEmptyTree<T> nTree = (NonEmptyTree<T>) tree; | |
if (value.equals(nTree.value)) { | |
return replaceChildren(getLeft().addAll(nTree.getLeft()), getRight().addAll(nTree.getRight())); | |
} | |
if (value.compareTo(nTree.value) > 0) { | |
return replaceChildren(getLeft().addAll(tree), getRight()); | |
} | |
return replaceChildren(getLeft(), getRight().addAll(tree)); | |
} | |
private ImmutableBinaryTree<T> | |
replaceChildren(final ImmutableBinaryTree<T> leftBranch, final ImmutableBinaryTree<T> rightBranch) { | |
if (leftBranch == getLeft() && rightBranch == getRight()) { | |
return this; | |
} | |
ImmutableBinaryTree<T> emptyTree = EmptyTree.instance(); | |
if (leftBranch == emptyTree && rightBranch == emptyTree) { | |
return new Leaf<T>(value); | |
} | |
if (leftBranch == emptyTree) { | |
return new RightBranch<T>(value, rightBranch); | |
} | |
if (rightBranch == emptyTree) { | |
return new LeftBranch<T>(value, leftBranch); | |
} | |
return new DualBranch<T>(value, leftBranch, rightBranch); | |
} | |
@Override | |
public final boolean contains(final T element) { | |
if (value.equals(element)) { | |
return true; | |
} | |
if (value.compareTo(element) > 0) { | |
return getLeft().contains(element); | |
} | |
return getRight().contains(element); | |
} | |
@Override | |
public final List<T> toList() { | |
List<T> list = new LinkedList<T>(); | |
list.addAll(getLeft().toList()); | |
list.add(value); | |
list.addAll(getRight().toList()); | |
return list; | |
} | |
} |
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
final class RightBranch<T extends Comparable<T>> extends SingleBranch<T> { | |
RightBranch(final T val, final ImmutableBinaryTree<T> child) { | |
super(val, child); | |
} | |
@Override | |
protected ImmutableBinaryTree<T> getLeft() { | |
return EmptyTree.instance(); | |
} | |
@Override | |
protected ImmutableBinaryTree<T> getRight() { | |
return getChild(); | |
} | |
} |
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
abstract class SingleBranch<T extends Comparable<T>> extends NonEmptyTree<T> { | |
private final ImmutableBinaryTree<T> child; | |
SingleBranch(final T val, final ImmutableBinaryTree<T> childTree) { | |
super(val); | |
child = childTree; | |
} | |
protected final ImmutableBinaryTree<T> getChild() { | |
return child; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment