Tree interface and implementation; tree with probabilities interface and implementation; dynamictree (no separate interface yet)

DynamicTree.java

/*
 *  © Kasper van den Berg <kasper@kaspervandenberg.net> 2012
 */
package net.kaspervandenberg.smokingBehaviourSimulation.monteCarloRandomTreeWalk;

import com.google.common.collect.ImmutableMultimap;
import java.util.Collection;
import java.util.Map;
import net.kaspervandenberg.smokingBehaviourSimulation.monteCarloRandomTreeWalk.ProbabilityTree.Node;

/**
 * A ProbalityTree that creates nodes when they are needed.
 * 
 * @param <Key>
 *            The type to identify {@code Values} with
 * @param <Value>
 *            The type to store in this SimpleTree
 * 
 * @author Kasper van den Berg <kasper@kaspervandenberg.net>
 */
public class DynamicTree<Key, Value> extends ProbabilityTree<Key, Value> {
	/**
	 * Clients must supply a NodeCreator when {@link DynamicTree#builder() 
	 * building} a {@link DynamicTree}.  The {@code DynamicTree} invokes the 
	 * {@code NodeCreator} when it receives requests for unexisting nodes.
	 * 
	 * @param <Key>	The type to identify {@code Values} with.
	 * @param <Value>	The type to store in the {@code DynamicTree}
	 */
	public interface NodeCreator<Key, Value> {
		/**
		 * Specifify how to construct a new node identified via 
		 * {@code path}.
		 * 
		 * When a client asks {@link DynamicTree} for an unexisting node,
		 * {@code DynamicTree} calls {@code buildNode} to construct the
		 * requested node.
		 * 
		 * @param builder	Use {@code builder} to specifiy how to 
		 * 	construct the node identified by {@code path}.
		 * 
		 * @param path	The path this node is identified with in this
		 * 	{@code Tree}.
		 */
		void buildNode(
			ProbabilityTree.Builder<?, ? extends DynamicTree<Key, Value>, Key, Value> builder, 
			Path<Key> path);
		Collection<Path<Key>> getChildKeys(Path<Key> path);
	}
		
	static private class BuilderImpl<Key, Value> implements
		ProbabilityTree.Builder<BuilderImpl<Key, Value>, 
				DynamicTree<Key, Value>,
				Key,
				Value> {
		protected final NodeCreator<Key, Value> nodeCreator;
		protected final BuilderImpl<Key, Value> previous;

		protected BuilderImpl(NodeCreator<Key, Value> nodeCreator_,
			BuilderImpl<Key, Value> previous_) {
			this.nodeCreator = nodeCreator_;
			this.previous = previous_;
		}

		/**
		 * {@inheritDoc}
		 */
		@Override
		public DynamicTree<Key, Value> build() {
			Node<Key, Value> result = buildNode();
			return new DynamicTree<Key, Value>(nodeCreator, result);
		}

		/**
		 * {@inheritDoc}
		 */
		@Override
		public BuilderImpl<Key, Value> weight(final double weight_) {
			return new BuilderImpl<Key, Value>(nodeCreator, this) {
				@Override
				protected double getWeight() {
					return weight_; 
				}
			};
		}

		/**
		 * Create and return a fresh Builder chain.
		 * 
		 * The {@link #parent()}-method in the fresh chain returns the current
		 * chain. The chain {@code parent} returns is appended with a specialized
		 * {@link BuilderImpl} that adds the subtree to the Tree in its
		 * {@link #addChildren}-method.
		 */
		@Override
		public BuilderImpl<Key, Value> child() {
			final BuilderImpl<Key, Value> parentPrevious = this;
			return new BuilderImpl<Key, Value>(nodeCreator, null) {
				@Override
				public BuilderImpl<Key, Value> parent(
						final BuilderImpl<Key, Value> child) {
					return new BuilderImpl<Key, Value>(nodeCreator, parentPrevious) {
						@Override
						protected ImmutableMultimap.Builder<Double, Node<Key, Value>> addChildren(
							ImmutableMultimap.Builder<Double, Node<Key, Value>> builder) {
							return super.addChildren(builder)
								.put(child.getWeight(), child.buildNode());
						}
					};
				}
			};
		}

		/**
		 * {@inheritDoc}
		 */
		@Override
		public BuilderImpl<Key, Value> key(final Key key_) {
			return new BuilderImpl<Key, Value>(nodeCreator, this) {

				@Override
				protected Key getKey() {
					return key_;
				}
				
			};
		}

		/**
		 * {@inheritDoc}
		 */
		@Override
		public BuilderImpl<Key, Value> parent()
			throws IllegalStateException {
			return parent(this);
		}

		/**
		 * {@inheritDoc}
		 */
		@Override
		public BuilderImpl<Key, Value> value(final Value value_) {
			return new BuilderImpl<Key, Value>(nodeCreator, this) {

				@Override
				protected Value getValue() {
					return value_;
				}
				
			};
		}

		/**
		 * Recurses back into the {@link BuilderImpl} chain to find a parent.
		 * 
		 * @see BuilderImpl#parent()
		 * @see BuilderImpl#child()
		 * 
		 * @param caller
		 *            The outermost instance on which {@link #parent()} is
		 *            called is preserved for use in {@link #child()}.
		 * @return the parent Builder this Builder is a {@link #child()} of (see
		 *         {@link #parent()})
		 * @throws IllegalStateException
		 *             when this builder is no child of an other builder. (see
		 *             {@link #parent()})
		 */
		protected BuilderImpl<Key, Value> parent(
				final BuilderImpl<Key, Value> caller)
				throws IllegalStateException {
			if (previous != null) {
				return previous.parent(caller);
			}
			throw new IllegalStateException("This is not a child builder.");
		}

		/**
		 * Recurse back into the {@link BuilderImpl} chain and retrieve the key
		 * for the {@link SimpleTree} being build.
		 * 
		 * @see BuilderImpl#key(Object)
		 * 
		 * @return <ul>
		 *         <li>{@code key_} as supplied to {@link #key(Object)} most
		 *         recent on this chain; or</li>
		 *         <li>{@code null} if {@link #key(Object)} was never called on
		 *         this chain.</li>
		 *         </ul>
		 */
		protected Key getKey() {
			return (previous != null) ? previous.getKey() : null;
		}

		/**
		 * Recurse back into the {@link BuilderImpl} chain and retrieve the
		 * value for the {@link SimpleTree} being build.
		 * 
		 * @see BuilderImpl#key(Object)
		 * 
		 * @return <ul>
		 *         <li>{@code value_} as supplied to {@link #value(Object)} most
		 *         recent on this chain; or</li>
		 *         <li>{@code null} if {@link #value(Object)} was never called
		 *         on this chain.</li>
		 *         </ul>
		 */
		protected Value getValue() {
			return (previous != null) ? previous.getValue() : null;
		}
		
		/**
		 * Recurse back into the {@link BuilderImpl} chain and retrieve the
		 * weight of the {@link ProbalityTree} being build.
		 * 
		 * @see BuilderImpl#weight(double) 
		 * 
		 * @return <ul>
		 * 		<li>{@code weight_} as supplied to {@link #weight(double)}
		 * 		most recent on this chain; or</li>
		 * 		<li>{@code 1.0}, the default weight, if 
		 * 		{@link #weight(double) was never called on this chain.
		 * 		</li>
		 * 	</ul>
		 */
		protected double getWeight() {
			return (previous != null) ? previous.getWeight() : 1.0;
		}

		/**
		 * Build a list of children to add to this node.
		 * @see BuilderImpl#child() 
		 * 
		 * @param builder	to build the List of children
		 * 
		 * @return {@code builder} with all previously specified children added
		 */
		protected ImmutableMultimap.Builder<Double, Node<Key, Value>> addChildren(
				ImmutableMultimap.Builder<Double, Node<Key, Value>> builder) {
			if(previous != null) 
				return previous.addChildren(builder);
			else
				return builder;
		}
		/**
		 * Recursively construct a node and its children as specified with 
		 * {@link AbstractMethodError#key}, {@link #value}, and {@link #child}.
		 * 
		 * @return a fresh Node
		 */
		public Node<Key, Value> buildNode() {
			Node<Key, Value> result = new Node<Key, Value>(getKey(), getValue());
			ImmutableMultimap<Double, Node<Key, Value>> children = addChildren(
				ImmutableMultimap.<Double, Node<Key, Value>>builder()).build(); 
			for(Map.Entry<Double, Node<Key, Value>> entry: children.entries()) {
				result.add(entry.getValue(), entry.getKey());
			}
			return result;
		}
		
	}

	private final NodeCreator<Key, Value> nodeCreator;
	
	/**
	 * clients use {@link #builder()} to construct a probabilitytree.
	 * 
	 * Construct a iProbabilityTree with the given {@link Node} as its root.
	 * 
	 * @param root_	the root of this Tree.
	 */
	protected DynamicTree(NodeCreator<Key, Value> nodeCreator_, Node<Key, Value> root_) {
		super(root_);
		this.nodeCreator = nodeCreator_;
	}

	public static <Key, Value> Builder<?, ? extends DynamicTree<Key, Value>, Key, Value>
	builder() {
		throw new UnsupportedOperationException("Use builder(NodeCreator)");
	}

	/**
	 * Builder pattern; see {@link Builder}
	 * 
	 * @param <Key> 
	 *            The type to identify {@code Values} with
	 * @param <Value> 
	 *            The type to store in this SimpleTree
	 * @return a {@link Builder} to construct {@link SimpleTree}s with
	 */
	public static <Key, Value> Builder<?, ? extends DynamicTree<Key, Value>, Key, Value>
	builder(NodeCreator<Key, Value> nodeCreator) {
		return new BuilderImpl<Key, Value>(nodeCreator, null);
	}

	@Override
	protected Node<Key, Value> getNode(Path<Key> path) {
		Node<Key, Value> result = super.getNode(path);
		if(result == null) {
			result = super.getNode(path);
		}
		return result;
	}

	@Override
	public Collection<Path<Key>> getChildren(Path<Key> parentPath) {
		Collection<Path<Key>> children = super.getChildren(parentPath);
		if(children.isEmpty()) {
			Collection<Path<Key>> freshChildren = nodeCreator.getChildKeys(parentPath);
			for (Path<Key> childPath : freshChildren) {
				constructNode(childPath);
			}
		}
		return super.getChildren(parentPath);
	}
	
	private void constructNode(Path<Key> path) {
		BuilderImpl<Key, Value> builder = new BuilderImpl<Key, Value>(nodeCreator, null);
		builder = builder.key(path.getLast());
		nodeCreator.buildNode(builder, path);
		Node<Key, Value> freshNode = builder.buildNode();
		root.getNode(path.parent()).add(freshNode);
	}
	
}

ProbabilityTree.java

/*
 *  © Kasper van den Berg <kasper@kaspervandenberg.net> 2012
 */
package net.kaspervandenberg.smokingBehaviourSimulation.monteCarloRandomTreeWalk;

import java.util.Iterator;

/**
 *
 * @author Kasper van den Berg <kasper@kaspervandenberg.net>
 */
public interface ProbabilityTree<Key, Value> extends Tree<Key, Value> {
	/**
	 * Interface for constructing {@link ProbabilityTreeImpl}s.
	 * {@inhericDoc}
	 * @param <T>
	 * 	The concrete type of {@code Builder} this fluent 
	 * 	interface returns.  {@link SimpleTree#builder() } will take care of
	 * 	selecting the correct type.
	 * @param <TTree>	The type of Tree this Builder returns with 
	 * 		{@link #build() }.
	 * @param <Key>
	 *            The type of to identify {@code Values} with.
	 * @param <Value> 
	 *            The type to store into this {@link ProbabilityTreeImpl}
	 */
	public interface Builder<T extends Builder<T, TTree, Key, Value>, 
			TTree extends ProbabilityTree<Key, Value>, Key, Value> 
			extends Tree.Builder<T, TTree, Key, Value> {
		
		/**
		 * Set the {@code weight} of this {@link ProbabilityTreeImpl}-node 
		 * compared to its sibblings.
		 * 
		 * {@code weight(double}} should not be called for the root of 
		 * the built {@code ProbabilityTreeImpl}; when {@code weight(double)} 
		 * is called for the root of the tree it has no effect.
		 * 
		 * If {@code weight} is not set when the {@code ProbabilityTreeImpl}
		 * is built, it will default to {@code 1.0}.  It can be set later
		 * using {@link ProbabilityTreeImpl#setProbabilty(SimpleTree.Path, double)}
		 * 
		 * @see ProbabilityTreeImpl#add(ProbabilityTreeImpl, double) 
		 * 
		 * @param weight_
		 * 		the 'weight' of this {@code ProbabilityTreeImpl} 
		 * 		compared to its sibblings. 
		 * @return this {@code Builder} so that calls can be chained.
		 */
		public T weight(double weight_);
	}

	/**
	 * @param path
	 * the path of the node whose probabilityWeight to change (see
	 * {@link SimpleTree#getNode(SimpleTree.Path)}).
	 * @return
	 * Retrieve the probability of selecting the Node identified by {@code path}
	 * given that its parent is selected.
	 * @throws IllegalArgumentException
	 * If {@code path} points to the root, since the root cannot
	 * have a probability.
	 */
	double getProbability(Path<Key> path) throws IllegalArgumentException;

	/**
	 * @return a {@link RandomWalker} which selects a random child at each call
	 * of {@link RandomWalker#next()}
	 */
	Iterator<? extends Path<Key>> randomWalker();

	/**
	 * Change the probability of selecting the child located via {@code path} to
	 * {@code newProbabilityWeight} (given that its parent is selected).
	 *
	 * <i><b>WARNING:</b> this is an expensive operation: the cumulativeWeight
	 * of every sibling is recalculated, all siblings are removed and then
	 * re-added to their parent.</i>
	 *
	 * @param path
	 * the path of the node whose probabilityWeight to change (see
	 * {@link SimpleTree#getNode(SimpleTree.Path)}).
	 * @param newProbabilityWeight
	 * new the 'weight' of the node located via {@code path}, nodes
	 * with high weight have higher chance to be selected with
	 * {@link #getRandomChild()}; <i>NOTE: {@code weight} is like a
	 * probability, but is not exactly a probability since the sum of
	 * the weights of the children of a node don't have to add up to
	 * 1.0.</i>
	 * @throws IllegalArgumentException
	 * If {@code path} points to the root, since the root cannot
	 * have a probability.
	 */
	void setProbabilty(Path<Key> path, double newProbabilityWeight) throws IllegalArgumentException;
	
}

ProbabilityTreeImpl.java

/**
 * 
 */
package net.kaspervandenberg.smokingBehaviourSimulation.monteCarloRandomTreeWalk;

import java.util.Iterator;
import java.util.Map;
import java.util.NavigableMap;
import java.util.NoSuchElementException;
import java.util.concurrent.ConcurrentSkipListMap;

import com.google.common.collect.ImmutableMultimap;
import umontreal.iro.lecuyer.rng.MRG32k3a;
import umontreal.iro.lecuyer.rng.RandomStream;

/**
 * Tree with probability attached to its nodes.
 * 
 * @param <Key>
 *            The type to identify {@code Values} with
 * @param <Value>
 *            The type to store in this Tree
 * 
 * @author Kasper van den Berg
 */
public class ProbabilityTreeImpl<Key, Value> extends SimpleTree<Key, Value> implements ProbabilityTree<Key, Value> {
	/**
	 * Extends {@link SimpleTree.Node} with probabilities of the child Nodes.
	 * {@inheritDoc}
	 * 
	 * @param <Key>
	 *            The type to identify {@code Values} with
	 * @param <Value> 
	 *            The type to store in this Tree
	 */
	protected static class Node<Key, Value> extends SimpleTree.Node<Key, Value> {
		/**
		 * Cumulative probability weights for child nodes.
		 */
		private final NavigableMap<Double, Key> childProbabilityWeight = new ConcurrentSkipListMap<Double, Key>();

		/**
		 * total weight stored in {@link #childProbabilityWeight}
		 */
		private double total = 0.0;

		/**
		 * Used to generate random numbers.
		 */
		private final RandomStream rng = new MRG32k3a();

		public Node(Key key, Value value) {
			super(key, value);
		}

		@Override
		@SuppressWarnings("unchecked")
		public Node<Key, Value> getNode(Path<Key> path) throws NoSuchElementException, IllegalArgumentException {
			SimpleTree.Node<Key, Value> result = super.getNode(path);
			assert(result instanceof Node);
			return (Node<Key, Value>)result;
		}

		@Override
		public void add(SimpleTree.Node<Key, Value> child) {
			assert(child instanceof Node);
			add((Node<Key, Value>)child, 1.0d);
		}

		/**
		 * Add {@code child} to this {@code Node}'s children with 
		 * {@code weight}/{@link #total} the probability of selecting 
		 * this child with {@link #getRandomChild(Path)}.
		 * 
		 * @param child	Node to add
		 * @param weight chance of selecting {@code child}
		 */
		public void add(Node<Key, Value> child, double weight) {
			super.add(child);
			total += weight;
			childProbabilityWeight.put(total, child.getKey());
		}


		
		/**
		 * Change the probability of selecting the {@code child} to {@code newProbabilityWeight}.
		 * 
		 * <i><b>WARNING:</b> this is an expensive operation: the cumulativeWeight
		 * of every sibling is recalculated, all siblings are removed and then
		 * re-added to their parent.</i>
		 * 
		 * @param child
		 *            the child node whose probabilityWeight to change
		 * @param newProbabilityWeight
		 *            new the 'weight' of {@code child}, nodes
		 *            with high weight have higher chance to be selected with
		 *            {@link #getRandomChild()}; <i>NOTE: {@code weight} is like a
		 *            probability, but is not exactly a probability since the sum of
		 *            the weights of the children of a node don't have to add up to
		 *            1.0.</i>
		 */
		public void setProbabilty(Key child, double newProbabilityWeight) {
			if (!children.containsKey(child)) {
				throw new NoSuchElementException("Node "
						+ child.toString() + " does not exist");
			}

			assert (childProbabilityWeight.containsValue(child));
			NavigableMap<Double, Key> newChildProb = new ConcurrentSkipListMap<Double, Key>();
			Double oldTotal = 0.0d;
			Double newTotal = 0.0d;
			for (Map.Entry<Double, Key> entry : childProbabilityWeight
					.entrySet()) {
				if (child.equals(entry.getValue())) {
					newTotal += newProbabilityWeight;
				} else {
					newTotal += entry.getKey() - oldTotal;
				}
				oldTotal += entry.getKey();
				newChildProb.put(newTotal, entry.getValue());
			}
		}

		/**
		 * @param child
		 * 		the node of which to get the probability
		 * @return the weight of {@code child}
		 */
		public double getProbability(Key child) {
			if (!children.containsKey(child)) {
				throw new NoSuchElementException("Node "
						+ child.toString() + " does not exist");
			}
			
			assert (childProbabilityWeight.containsValue(child));
			double lower = 0.0;
			Iterator<Map.Entry<Double, Key>> iter = childProbabilityWeight.entrySet().iterator();
			Map.Entry<Double, Key> entry = iter.next();

			while(!entry.getValue().equals(child)) {
				lower = entry.getKey();
				entry = iter.next();
			}
			return entry.getKey() - lower;
		}
		
		/**
		 * @param thisPath
		 * 	The {@link Path} that defines the location of this Node;
		 * 	the selected child's key is {@link Path#append(Object)}ed
		 * 	to {@code path}.
		 * @return {@link Path} to one of this node's direct children
		 * 	randomly selected; each child <i>c</i>is selected with a
		 * 	probability of <i>c<sub>weight</sub></i>/{@link #total}.
		 */
		public Path<Key> getRandomChild(Path<Key> thisPath) {
			if (children.isEmpty()) {
				return null;
			}

			Double p = rng.nextDouble() * total;
			Key childKey = childProbabilityWeight.ceilingEntry(p).getValue();
			return thisPath.append(childKey);
		}
	}
	
	/**
	 * Select a random child node of the current node as next node; continue
	 * until a leaf node is reached.
	 * 
	 * @author Kasper van den Berg
	 */
	protected class RandomWalker implements
			Iterator<Path<Key>> {
		private Path<Key> next = ProbabilityTreeImpl.this.getRoot();

		/**
		 * Continue until a leaf has been reached.
		 */
		@Override
		public boolean hasNext() {
			return next != null;
		}

		/**
		 * Randomly select a child of the previous node.
		 * 
		 * @see ProbabilityTreeImpl#getRandomChild()
		 */
		@Override
		public Path<Key> next() {
			Node<Key, Value> nextNode = ProbabilityTreeImpl.this.getNode(next);
			next = nextNode.getRandomChild(next);
			return next;
		}

		@Override
		public void remove() {
			throw new UnsupportedOperationException();
		}
	}

	/**
	 * {@inheritDoc}
	 */
	static private class BuilderImpl<Key, Value> implements
			ProbabilityTree.Builder<BuilderImpl<Key, Value>, ProbabilityTreeImpl<Key, Value>, Key, Value> {
		protected final BuilderImpl<Key, Value> previous;

		protected BuilderImpl(BuilderImpl<Key, Value> previous_) {
			this.previous = previous_;
		}

		/**
		 * {@inheritDoc}
		 */
		@Override
		public ProbabilityTreeImpl<Key, Value> build() {
			Node<Key, Value> result = buildNode();
			return new ProbabilityTreeImpl<Key, Value>(result);
		}

		/**
		 * {@inheritDoc}
		 */
		@Override
		public BuilderImpl<Key, Value> weight(final double weight_) {
			return new BuilderImpl<Key, Value>(this) {
				@Override
				protected double getWeight() {
					return weight_; 
				}
			};
		}

		/**
		 * Create and return a fresh Builder chain.
		 * 
		 * The {@link #parent()}-method in the fresh chain returns the current
		 * chain. The chain {@code parent} returns is appended with a specialized
		 * {@link BuilderImpl} that adds the subtree to the Tree in its
		 * {@link #addChildren}-method.
		 */
		@Override
		public BuilderImpl<Key, Value> child() {
			final BuilderImpl<Key, Value> parentPrevious = this;
			return new BuilderImpl<Key, Value>(null) {
				@Override
				public BuilderImpl<Key, Value> parent(
						final BuilderImpl<Key, Value> child) {
					return new BuilderImpl<Key, Value>(parentPrevious) {
						@Override
						protected ImmutableMultimap.Builder<Double, Node<Key, Value>> addChildren(
							ImmutableMultimap.Builder<Double, Node<Key, Value>> builder) {
							return super.addChildren(builder)
								.put(child.getWeight(), child.buildNode());
						}
					};
				}
			};
		}

		/**
		 * {@inheritDoc}
		 */
		@Override
		public BuilderImpl<Key, Value> key(final Key key_) {
			return new BuilderImpl<Key, Value>(this) {

				@Override
				protected Key getKey() {
					return key_;
				}
				
			};
		}

		/**
		 * {@inheritDoc}
		 */
		@Override
		public BuilderImpl<Key, Value> parent()
			throws IllegalStateException {
			return parent(this);
		}

		/**
		 * {@inheritDoc}
		 */
		@Override
		public BuilderImpl<Key, Value> value(final Value value_) {
			return new BuilderImpl<Key, Value>(this) {

				@Override
				protected Value getValue() {
					return value_;
				}
				
			};
		}

		/**
		 * Recurses back into the {@link BuilderImpl} chain to find a parent.
		 * 
		 * @see BuilderImpl#parent()
		 * @see BuilderImpl#child()
		 * 
		 * @param caller
		 *            The outermost instance on which {@link #parent()} is
		 *            called is preserved for use in {@link #child()}.
		 * @return the parent Builder this Builder is a {@link #child()} of (see
		 *         {@link #parent()})
		 * @throws IllegalStateException
		 *             when this st_builder is no child of an other st_builder. (see
		 *             {@link #parent()})
		 */
		protected BuilderImpl<Key, Value> parent(
				final BuilderImpl<Key, Value> caller)
				throws IllegalStateException {
			if (previous != null) {
				return previous.parent(caller);
			}
			throw new IllegalStateException("This is not a child builder.");
		}

		/**
		 * Recurse back into the {@link BuilderImpl} chain and retrieve the key
		 * for the {@link SimpleTree} being build.
		 * 
		 * @see BuilderImpl#key(Object)
		 * 
		 * @return <ul>
		 *         <li>{@code key_} as supplied to {@link #key(Object)} most
		 *         recent on this chain; or</li>
		 *         <li>{@code null} if {@link #key(Object)} was never called on
		 *         this chain.</li>
		 *         </ul>
		 */
		protected Key getKey() {
			return (previous != null) ? previous.getKey() : null;
		}

		/**
		 * Recurse back into the {@link BuilderImpl} chain and retrieve the
		 * value for the {@link SimpleTree} being build.
		 * 
		 * @see BuilderImpl#key(Object)
		 * 
		 * @return <ul>
		 *         <li>{@code value_} as supplied to {@link #value(Object)} most
		 *         recent on this chain; or</li>
		 *         <li>{@code null} if {@link #value(Object)} was never called
		 *         on this chain.</li>
		 *         </ul>
		 */
		protected Value getValue() {
			return (previous != null) ? previous.getValue() : null;
		}
		
		/**
		 * Recurse back into the {@link BuilderImpl} chain and retrieve the
		 * weight of the {@link ProbalityTree} being build.
		 * 
		 * @see BuilderImpl#weight(double) 
		 * 
		 * @return <ul>
		 * 		<li>{@code weight_} as supplied to {@link #weight(double)}
		 * 		most recent on this chain; or</li>
		 * 		<li>{@code 1.0}, the default weight, if 
		 * 		{@link #weight(double) was never called on this chain.
		 * 		</li>
		 * 	</ul>
		 */
		protected double getWeight() {
			return (previous != null) ? previous.getWeight() : 1.0;
		}

		/**
		 * Build a list of children to add to this node.
		 * @see BuilderImpl#child() 
		 * 
		 * @param st_builder	to build the List of children
		 * 
		 * @return {@code st_builder} with all previously specified children added
		 */
		protected ImmutableMultimap.Builder<Double, Node<Key, Value>> addChildren(
				ImmutableMultimap.Builder<Double, Node<Key, Value>> builder) {
			if(previous != null) 
				return previous.addChildren(builder);
			else
				return builder;
		}
		/**
		 * Recursively construct a node and its children as specified with 
		 * {@link AbstractMethodError#key}, {@link #value}, and {@link #child}.
		 * 
		 * @return a fresh Node
		 */
		protected Node<Key, Value> buildNode() {
			Node<Key, Value> result = new Node<Key, Value>(getKey(), getValue());
			ImmutableMultimap<Double, Node<Key, Value>> children = addChildren(
				ImmutableMultimap.<Double, Node<Key, Value>>builder()).build(); 
			for(Map.Entry<Double, Node<Key, Value>> entry: children.entries()) {
				result.add(entry.getValue(), entry.getKey());
			}
			return result;
		}
	}

	/**
	 * Clients use {@link #st_builder()} to construct a ProbabilityTreeImpl.
	 * 
	 * Construct a iProbabilityTree with the given {@link Node} as its root.
	 * 
	 * @param root_	the root of this Tree.
	 */
	protected ProbabilityTreeImpl(Node<Key, Value> root_) {
		super(root_);
	}

	/**
	 * Builder pattern; see {@link Builder}
	 * 
	 * @param <Key> 
	 *            The type to identify {@code Values} with
	 * @param <Value> 
	 *            The type to store in this SimpleTree
	 * @return a {@link Builder} to construct {@link SimpleTree}s with
	 */
	public static <Key, Value> 
	ProbabilityTree.Builder<?, ? extends ProbabilityTreeImpl<Key, Value>, Key, Value>
	pt_builder() {
		return new BuilderImpl<Key, Value>(null);
	}

	/**
	 * Change the probability of selecting the child located via {@code path} to
	 * {@code newProbabilityWeight} (given that its parent is selected).
	 * 
	 * <i><b>WARNING:</b> this is an expensive operation: the cumulativeWeight
	 * of every sibling is recalculated, all siblings are removed and then
	 * re-added to their parent.</i>
	 * 
	 * @param path
	 *            the path of the node whose probabilityWeight to change (see
	 *            {@link SimpleTree#getNode(SimpleTree.Path)}).
	 * @param newProbabilityWeight
	 *            new the 'weight' of the node located via {@code path}, nodes
	 *            with high weight have higher chance to be selected with
	 *            {@link #getRandomChild()}; <i>NOTE: {@code weight} is like a
	 *            probability, but is not exactly a probability since the sum of
	 *            the weights of the children of a node don't have to add up to
	 *            1.0.</i>
	 * @throws IllegalArgumentException  
	 * 	If {@code path} points to the root, since the root cannot
	 * 	have a probability.
	 */
	@Override
	public void setProbabilty(Path<Key> path, double newProbabilityWeight) 
		throws IllegalArgumentException
	{
		Node<Key, Value> parent;
		try {
			parent = getNode(path.parent());
		} catch (IllegalStateException e) {
			throw new IllegalArgumentException(
				"Root of this Tree cannot have a probability.",
				e);
		}
		Key child = path.getLast();
		parent.setProbabilty(child, newProbabilityWeight);
	}

	/**
	 * @param path
	 *            the path of the node whose probabilityWeight to change (see
	 *            {@link SimpleTree#getNode(SimpleTree.Path)}).
	 * @return 
	 * 	Retrieve the probability of selecting the Node identified by {@code path}
	 * 	given that its parent is selected.
	 * @throws IllegalArgumentException  
	 * 	If {@code path} points to the root, since the root cannot
	 * 	have a probability.
	 */
	@Override
	public double getProbability(Path<Key> path) throws IllegalArgumentException {
		Node<Key, Value> parent;
		try {
			parent = getNode(path.parent());
		} catch (IllegalStateException e) {
			throw new IllegalArgumentException(
				"Root of this Tree cannot have a probability.",
				e);
		}
		Key child = path.getLast();
		return parent.getProbability(child);
	}
	
	/**
	 * @return a {@link RandomWalker} which selects a random child at each call
	 *         of {@link RandomWalker#next()}
	 */
	@Override
	public Iterator<? extends Path<Key>> randomWalker() {
		return new RandomWalker();
	}

	@Override
	protected Node<Key, Value> getNode(Path<Key> path) {
		SimpleTree.Node<Key, Value> result = super.getNode(path);
		assert(result instanceof Node);
		return (Node<Key, Value>)result;
	}
}

SimpleTree.java

package net.kaspervandenberg.smokingBehaviourSimulation.monteCarloRandomTreeWalk;

import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;

import com.google.common.collect.Collections2;
import com.google.common.collect.ImmutableList;

/**
 * Stores {@code Value} in a tree structure indexed by {@link Path} of
 * {@code Key}.
 * 
 * @param <Key>
 *            The type to identify {@code Values} with
 * @param <Value>
 *            The type to store in this SimpleTree
 * 
 * @author Kasper van den Berg
 */
public class SimpleTree<Key, Value> implements Tree<Key, Value> {
	/**
	 * Contains the data of this SimpleTree
	 * 
	 * @param <Key>
	 *            The type to identify {@code Values} with
	 * @param <Value> 
	 *            The type to store in this SimpleTree
	 */
	protected static class Node<Key, Value> {
		/**
		 * The direct children of this tree node
		 */
		protected final Map<Key, Node<Key, Value>> children = new HashMap<Key, Node<Key, Value>>();

		/**
		 * The {@code Key} that identifies this node among its siblings
		 */
		protected final Key key;

		/**
		 * The value stored in this node
		 * 
		 * @see #getValue()
		 */
		protected final Value value;

		/**
		 * Construct a Node with the given {@code key} and {@code value} at its
		 * root.
		 * 
		 * The constructed Node does not contain any children. Use
		 * {@link SimpleTree#add(SimpleTree)} to add these node.
		 * 
		 * @param key
		 *            the {@code Key} to identify this node with.
		 * @param value
		 *            the {@code Value} to store in this Node
		 */
		public Node(Key key, Value value) {
			this.key = key;
			this.value = value;
		}

		/**
		 * @return The value stored at this node
		 */
		public Value getValue() {
			return value;
		}

		/**
		 * @return the key that identifies this node
		 */
		public Key getKey() {
			return key;
		}

		/**
		 * Traverse the tree nodes via {@code path} and return the Node {@code path}
		 * points to.
		 * 
		 * @param path
		 *            The {@link Path} that defines the location of the Node to
		 *            retrieve.
		 * @return the tree Node at the location {@code path}
		 * @throws NoSuchElementException
		 *             when {@code path} is invalid for this tree
		 * @throws IllegalArgumentException
		 *             when {@code path.getFirst()} is not the {@link #key} of this
		 *             Node
		 */
		public Node<Key, Value> getNode(Path<Key> path)
				throws NoSuchElementException, IllegalArgumentException {
			if (path.startsWith(this.key)) {
				if (path.size() == 1) {
					return this;
				} else {
					Path<Key> subpath = path.stripFirst();
					Key subkey = subpath.getFirst();
					if (children.containsKey(subkey)) {
						return children.get(subkey).getNode(subpath);
					} else {
						throw new NoSuchElementException("Path not found: " + path);
					}
				}
			}
			throw new IllegalArgumentException(
					"Paths in this tree should start with  " + this.key);
		}

		/**
		 * Add {@code child} as a direct child of this node.
		 * 
		 * The child's location is
		 * {@code new SimpleTree.Path(this.getThisPAth(), child.key)}.
		 * 
		 * @param child
		 *            a Node to add as a direct child of this Node
		 */
		public void add(Node<Key, Value> child) {
			children.put(child.key, child);
		}

		/**
		 * @param thisPath
		 * 		the Path to this Node
		 * @return all direct children of this  Node
		 */
		public Collection<Path<Key>> getChildren(Path<Key> thisPath) {
			return Collections2.transform(children.keySet(), Path.toPath(thisPath));
		}
	}

	/**
	 * Follow the Path through the SimpleTree, starting at the root of the tree, until
	 * the end of the Path.
	 * 
	 * @author Kasper van den Berg
	 */
	protected class PathIterator implements Iterator<Path<Key>> {
		private Path<Key> followedPath;
		private Iterator<Key> partIter;

		public PathIterator(Path<Key> path_) {
			this.followedPath = new Path<Key>();
			this.partIter = path_.parts();
		}

		@Override
		public boolean hasNext() {
			return partIter.hasNext();
		}

		@Override
		public Path<Key> next() {
			followedPath = followedPath.append(partIter.next());
			return followedPath;
		}

		@Override
		public void remove() {
			throw new UnsupportedOperationException();
		}
	}

	/**
	 * Interface for constructing {@link SimpleTree}s.
	 * 
	 * Use {@link SimpleTree#builder()} to retrieve a {@code Builder} for this tree.
	 * 
	 * @author Kasper van den Berg
	 * 
	 * @param <T>
	 * 	The concrete type of {@code Builder} this fluent 
	 * 	interface returns.  {@link SimpleTree#builder() } will take care of
	 * 	selecting the correct type.
	 * @param <TTree>	The type of Tree this Builder returns with 
	 * 		{@link #build() }.
	 * @param <Key>
	 *            The type of to identify {@code Values} with.
	 * @param <Value> 
	 *            The type to store into this {@link SimpleTree}
	 */
	public interface Builder<T extends Builder<T, TTree, Key, Value>, 
			TTree extends SimpleTree<Key, Value>, Key, Value> 
			extends Tree.Builder<T, TTree, Key, Value> {
	}

	/**
	 * Builds {@link SimpleTree}
	 * 
	 * @author Kasper van den Berg
	 * @param <Key>
	 *            see {@link Builder} & {@link SimpleTree}
	 * @param <Value>
	 *            see {@link Builder} & {@link SimpleTree}
	 */
	static private class BuilderImpl<Key, Value> implements 
			Builder<BuilderImpl<Key, Value>, SimpleTree<Key, Value>, Key, Value> {
		/** Builders are linked together via {@code previous} */
		protected final BuilderImpl<Key, Value> previous;

		protected BuilderImpl(BuilderImpl<Key, Value> previous_) {
			previous = previous_;
		}

		@Override
		public SimpleTree<Key, Value> build() {
			SimpleTree<Key, Value> result = new SimpleTree<Key, Value>(buildNode());
			return result;
		}

		/**
		 * Chain a specialized {@link BuilderImpl} which returns {@code key_} in
		 * {@link #getKey()}
		 */
		@Override
		public BuilderImpl<Key, Value> key(final Key key_) {
			return new BuilderImpl<Key, Value>(this) {
				@Override
				protected Key getKey() {
					return key_;
				}
			};
		}

		/**
		 * Chain a specialized {@link BuilderImpl} which returns {@code value_}
		 * in {@link #getValue()}
		 */
		@Override
		public BuilderImpl<Key, Value> value(final Value value_) {
			return new BuilderImpl<Key, Value>(this) {
				@Override
				protected Value getValue() {
					return value_;
				}
			};
		}

		/**
		 * Create and return a fresh Builder chain.
		 * 
		 * The {@link #parent()}-method in the fresh chain returns the current
		 * chain. The chain {@code parent} returns is appended with a specialized
		 * {@link BuilderImpl} that adds the subtree to the SimpleTree in its
		 * {@link #addChildren}-method.
		 */
		@Override
		public BuilderImpl<Key, Value> child() {
			final BuilderImpl<Key, Value> parentPrevious = this;
			return new BuilderImpl<Key, Value>(null) {
				@Override
				public BuilderImpl<Key, Value> parent(
						final BuilderImpl<Key, Value> child) {
					return new BuilderImpl<Key, Value>(parentPrevious) {
						@Override
						protected ImmutableList.Builder<Node<Key, Value>> addChildren(
							ImmutableList.Builder<Node<Key, Value>> builder) {
							return super.addChildren(builder).add(child.buildNode());
						}
						
					};
				}
			};
		}

		@Override
		public BuilderImpl<Key, Value> parent() throws IllegalStateException {
			return parent(this);
		}

		/**
		 * Recurses back into the {@link BuilderImpl} chain to find a parent.
		 * 
		 * @see BuilderImpl#parent()
		 * @see BuilderImpl#child()
		 * 
		 * @param caller
		 *            The outermost instance on which {@link #parent()} is
		 *            called is preserved for use in {@link #child()}.
		 * @return the parent Builder this Builder is a {@link #child()} of (see
		 *         {@link #parent()})
		 * @throws IllegalStateException
		 *             when this builder is no child of an other builder. (see
		 *             {@link #parent()})
		 */
		protected BuilderImpl<Key, Value> parent(
				final BuilderImpl<Key, Value> caller)
				throws IllegalStateException {
			if (previous != null) {
				return previous.parent(caller);
			}
			throw new IllegalStateException("This is not a child builder.");
		}

		/**
		 * Recurses back into the {@link BuilderImpl} chain and retrieve the key
		 * for the {@link SimpleTree} being build.
		 * 
		 * @see BuilderImpl#key(Object)
		 * 
		 * @return <ul>
		 *         <li>{@code key_} as supplied to {@link #key(Object)} most
		 *         recent on this chain; or</li>
		 *         <li>{@code null} if {@link #key(Object)} was never called on
		 *         this chain.</li>
		 *         </ul>
		 */
		protected Key getKey() {
			return (previous != null) ? previous.getKey() : null;
		}

		/**
		 * Recurses back into the {@link BuilderImpl} chain and retrieve the
		 * value for the {@link SimpleTree} being build.
		 * 
		 * @see BuilderImpl#key(Object)
		 * 
		 * @return <ul>
		 *         <li>{@code value_} as supplied to {@link #value(Object)} most
		 *         recent on this chain; or</li>
		 *         <li>{@code null} if {@link #value(Object)} was never called
		 *         on this chain.</li>
		 *         </ul>
		 */
		protected Value getValue() {
			return (previous != null) ? previous.getValue() : null;
		}

		/**
		 * Build a list of children to add to this node.
		 * @see BuilderImpl#child() 
		 * 
		 * @param builder	to build the List of children
		 * 
		 * @return {@code builder} with all previously specified children added
		 */
		protected ImmutableList.Builder<Node<Key, Value>> addChildren(
				ImmutableList.Builder<Node<Key, Value>> builder) {
			if(previous != null) 
				return previous.addChildren(builder);
			else
				return builder;
			
		}

		/**
		 * Recursively construct a node and its children as specified with 
		 * {@link AbstractMethodError#key}, {@link #value}, and {@link #child}.
		 * 
		 * @return a fresh Node
		 */
		protected Node<Key, Value> buildNode() {
			Node<Key, Value> result = new Node<Key, Value>(getKey(), getValue());
			ImmutableList<Node<Key, Value>> children = addChildren(
				ImmutableList.<Node<Key, Value>>builder()).build(); 
			for(Node<Key, Value> child: children) {
				result.add(child);
			}
			return result;
		}
	}

	protected final Node<Key, Value> root;
	
	/**
	 * Clients use {@link #builder()} to construct a SimpleTree.
	 * 
	 * Construct a SimpleTree with the given {@link Node} as its root.
	 * 
	 * @param root_	the root of this SimpleTree.
	 */
	protected SimpleTree(Node<Key, Value> root_) {
		this.root = root_;
	}

	/**
	 * Builder pattern; see {@link Builder}
	 * 
	 * @param <Key> 
	 *            The type to identify {@code Values} with
	 * @param <Value> 
	 *            The type to store in this SimpleTree
	 * @return a {@link Builder} to construct {@link SimpleTree}s with
	 */
	public static <Key, Value> Builder<? extends Builder<?, ? extends SimpleTree<Key, Value>, Key, Value>,
			? extends SimpleTree<Key, Value>, Key, Value> builder() {
		return new BuilderImpl<Key, Value>(null);
	}

	/**
	 * @param path	Path to the node whose value to return.
	 * @return 	The value stored at the node
	 */
	@Override
	public Value getValueOf(Path<Key> path) {
		return getNode(path).getValue();
	}
		
	/**
	 * @return The path that identifies the root of this SimpleTree
	 */
	@Override
	public Path<Key> getRoot() {
		return new Path<Key>(root.getKey());
	}
	
	/**
	 * @param parentPath
	 * 		Path to the node whose children to retrieve
	 * @return a collection of {@link Path}s to the children of {@code parentPath}
	 */
	@Override
	public Collection<Path<Key>> getChildren(Path<Key> parentPath) {
		return getNode(parentPath).getChildren(parentPath);
	}

	/**
	 * @param path
	 *            the path to follow
	 * @return an iterator that visits all this SimpleTree and all its descendants on
	 *         {@code path}
	 */
	@Override
	public Iterator<? extends Path<Key>> followPath(Path<Key> path) {
		return new PathIterator(path);
	}

	/**
	 * @param path
	 * 		The path of the node
	 * @return {@link Node} {@code path} points to
	 */
	protected Node<Key, Value> getNode(Path<Key> path) {
		return root.getNode(path);
	}
}

Tree.java

/*
 *  © Kasper van den Berg <kasper@kaspervandenberg.net> 2012
 */
package net.kaspervandenberg.smokingBehaviourSimulation.monteCarloRandomTreeWalk;

import java.util.Collection;
import java.util.Iterator;

/**
 * Stores {@code Value} in a tree structure indexed by {@link Path} of
 * {@code Key}.
 * 
 * @param <Key>
 *            The type to identify {@code Values} with
 * @param <Value>
 *            The type to store in this SimpleTree
 *
 * @author Kasper van den Berg <kasper@kaspervandenberg.net>
 */
public interface Tree<Key, Value> {

	/**
	 * Interface for constructing {@link Tree}s.
	 * 
	 * Classes implementing {@link Tree} should have a static method 
	 * {@code builder()} which returns a builder that can build concrete 
	 * {@code Trees}
	 * 
	 * @author Kasper van den Berg
	 * 
	 * @param <T>	The concrete type of {@code Builder} this fluent 
	 * 		interface returns.  The implementation should select the 
	 * 		correct type.
	 * @param <TTree>	The type of Tree this Builder returns with 
	 * 		{@link #build() }.
	 * @param <Key>
	 *            The type of to identify {@code Values} with.
	 * @param <Value>
	 *            The type to store into this {@link Tree}
	 */
	public interface Builder<T extends Builder<T, TTree, Key, Value>, TTree extends Tree<Key, Value>, Key, Value> {
		/**
		 * @return a {@link Tree} build to as specified using this
		 *         {@code Builder}.
		 */
		public TTree build();

		/**
		 * Set the {@code Key} of this {@link Tree}.
		 * 
		 * @param key_
		 *            the value for the constructed tree's key
		 * @return this {@code Builder} so that calls can be chained.
		 */
		public T key(Key key_);

		/**
		 * Set the {@code value} contained in this node of the {@link Tree}.
		 * 
		 * @param value_
		 *            the {@code value} for the this node in the constructed
		 *            Tree.
		 * @return this {@code Builder} so that calls can be chained.
		 */
		public T value(Value value_);

		/**
		 * Add a child to the {@link Tree} to construct.
		 * 
		 * @return a fresh Builder with which the building of the child is
		 *         directed. <i>NOTE: This return differs from the other methods
		 *         in {@code Builder}.</i>
		 */
		public T child();

		/**
		 * @return the {@code Builder} with which to construct the parent of
		 *         this node.
		 * @throws IllegalStateException
		 *             when this {@code Builder} was not created via
		 *             {@link #child()}
		 */
		public T parent() throws IllegalStateException;

	}

	/**
	 * @param path
	 * the path to follow
	 * @return an iterator that visits all this SimpleTree and all its descendants on
	 * {@code path}
	 */
	Iterator<? extends Path<Key>> followPath(Path<Key> path);

	/**
	 * @param parentPath
	 * 		Path to the node whose children to retrieve
	 * @return a collection of {@link Path}s to the children of {@code parentPath}
	 */
	Collection<Path<Key>> getChildren(Path<Key> parentPath);

	/**
	 * @return The path that identifies the root of this SimpleTree
	 */
	Path<Key> getRoot();

	/**
	 * @param path	Path to the node whose value to return.
	 * @return 	The value stored at the node
	 */
	Value getValueOf(Path<Key> path);
	
}