public
Created

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

  • Download Gist
DynamicTree.java
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324
/*
* © 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
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
/*
* © 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
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515
/**
*
*/
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
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441
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
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113
/*
* © 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);
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.