Created
March 28, 2011 12:52
-
-
Save msfroh/890401 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
public class ImmutableBinaryTree<T extends Comparable<T>> implements ImmutableSet<T> { | |
private final ImmutableBinaryTree<T> left; | |
private final ImmutableBinaryTree<T> right; | |
private final T value; | |
public ImmutableBinaryTree(ImmutableBinaryTree<T> left, | |
ImmutableBinaryTree<T> right, T value) { | |
this.left = left; | |
this.right = right; | |
this.value = value; | |
} |
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
@Override | |
public ImmutableBinaryTree<T> add(T element) { | |
if ( value.compareTo(element) == 0 ) { | |
return this; // Element already exists | |
} | |
return addSubtree(new ImmutableBinaryTree<T>(null, null, element)); | |
} | |
private ImmutableBinaryTree<T> addSubtree( ImmutableBinaryTree<T> subTree ) { | |
if ( subTree == null ) | |
{ | |
return this; | |
} | |
if ( value.compareTo(subTree.value) == 0 ) { | |
// Need to merge subTree children with this tree's children | |
final ImmutableBinaryTree<T> newLeft = left !=null ? left.addSubtree(subTree.left) : subTree.left; | |
final ImmutableBinaryTree<T> newRight = right !=null ? right.addSubtree(subTree.right) : subTree.left; | |
return new ImmutableBinaryTree<T>(newLeft, newRight, value); | |
} else if ( value.compareTo(subTree.value) < 0 ) { | |
// Element goes on right subtree | |
if ( right != null ) { | |
return new ImmutableBinaryTree<T>(left, right.addSubtree(subTree), value); | |
} else { | |
return new ImmutableBinaryTree<T>(left, subTree, value); | |
} | |
} else { | |
// Element goes on left subtree | |
if ( left != null ) { | |
return new ImmutableBinaryTree<T>(left.addSubtree(subTree), right, value); | |
} else { | |
return new ImmutableBinaryTree<T>(subTree, right, value); | |
} | |
} | |
} |
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
@Override | |
public ImmutableBinaryTree<T> remove(T element) { | |
if ( value.compareTo(element) == 0 ) { | |
if ( left == null && right == null ) | |
return null; | |
if ( left == null ) return right; | |
if ( right == null ) return left; | |
return left.addSubtree(right); | |
} | |
if ( value.compareTo(element) < 0 && right != null ) { | |
return new ImmutableBinaryTree<T>(left, right.remove(element), value); | |
} | |
else if ( value.compareTo(element) > 0 && left != null ) { | |
return new ImmutableBinaryTree<T>(left.remove(element), right, value); | |
} | |
return this; // Element not found | |
} |
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
@Override | |
public boolean contains(T element) { | |
if ( value.equals( element) ) { | |
return true; | |
} | |
else if ( value.compareTo(element) < 0 ) { | |
return right == null ? false : right.contains(element); | |
} | |
else { | |
return left == null ? false : left.contains(element); | |
} | |
} |
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
@Override | |
public List<T> toList() { | |
final List<T> asList = new LinkedList<T>(); | |
if ( left != null ) { asList.addAll(left.toList()); } | |
asList.add(value); | |
if ( right != null ) { asList.addAll(right.toList()); } | |
return asList; | |
} |
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
@Override | |
public String toString() { | |
return innerToString(""); | |
} | |
private String innerToString( String prefix ) { | |
StringBuilder builder = new StringBuilder(); | |
if ( left != null ) { | |
builder.append( left.innerToString(prefix + " ")); | |
} | |
builder.append(prefix).append(value).append("\n"); | |
if ( right != null ) { | |
builder.append( right.innerToString(prefix + " ")); | |
} | |
return builder.toString(); | |
} |
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 java.util.List; | |
public interface ImmutableSet<T extends Comparable<T>> { | |
ImmutableSet<T> add( T element ); | |
ImmutableSet<T> remove( T element ); | |
boolean contains( T element ); | |
List<T> toList(); | |
} |
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 java.util.Iterator; | |
import java.util.List; | |
import java.util.Random; | |
import java.util.Set; | |
import java.util.TreeSet; | |
public final class ImmutableTreeRunner { | |
private static final Random RANDOM = new Random(); | |
/** | |
* @param args | |
*/ | |
public static void main(String[] args) { | |
final Integer firstValue = Integer.valueOf( RANDOM.nextInt(1000)); | |
ImmutableSet<Integer> immutableSet = new ImmutableBinaryTree<Integer>(null, null, firstValue); | |
final Set<Integer> mutableSet = new TreeSet<Integer>(); | |
mutableSet.add(firstValue); | |
// Add 100 random integers in the [0,1000) range | |
for ( int i = 0; i < 100; i++ ) | |
{ | |
final int value = RANDOM.nextInt(1000); | |
mutableSet.add(value); | |
immutableSet = immutableSet.add(value); | |
} | |
List<Integer> immutableValues = immutableSet.toList(); | |
System.out.println( immutableValues.toString() ); | |
System.out.println( mutableSet.toString() ); | |
// Remove 100 random integers in the [0,1000) range | |
for ( int i = 0; i < 100; i++ ) | |
{ | |
final int value = RANDOM.nextInt(1000); | |
mutableSet.remove( value ); | |
immutableSet = immutableSet.remove(value); | |
} | |
immutableValues = immutableSet.toList(); | |
assert( immutableValues.size() == mutableSet.size() ); | |
Iterator<Integer> immutableValueIter = immutableValues.iterator(); | |
Iterator<Integer> mutableValueIter = mutableSet.iterator(); | |
System.out.println( immutableValues.toString() ); | |
System.out.println( mutableSet.toString() ); | |
while ( true ) { | |
assert( immutableValueIter.hasNext() == mutableValueIter.hasNext() ); | |
if ( immutableValueIter.hasNext() != mutableValueIter.hasNext() ) throw new RuntimeException("hasNext doesn't match"); | |
if ( !immutableValueIter.hasNext() ) { break; } | |
final Integer immutableVal = immutableValueIter.next(); | |
final Integer mutableVal = mutableValueIter.next(); | |
assert( immutableVal.equals(mutableVal)); | |
} | |
System.out.println(immutableSet.toString()); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment