adt.tournament.TournamentTree

   1 package adt.tournament;
   2 
   3 import java.util.List;
   4 import java.util.Random;
   5 
   6 /**
   7  * @author Sebastian Kuerten (sebastian.kuerten@fu-berlin.de)
   8  * 
   9  */
  10 public class TournamentTree
  11 {
  12     Node root;
  13 
  14     /**
  15      * Create a new TournamentTree with just one element
  16      * 
  17      * @param value
  18      *            the only value.
  19      */
  20     public TournamentTree(int value)
  21     {
  22         // parent is null
  23         root = new Node(value);
  24     }
  25 
  26     /**
  27      * Create a new TournamentTree with the denoted root.
  28      * 
  29      * @param root
  30      *            the tree's root.
  31      */
  32     public TournamentTree(Node root)
  33     {
  34         this.root = root;
  35         root.parent = null;
  36         root.lowestEqualNode.highestEqualNode = root;
  37     }
  38 
  39     /**
  40      * Create a new TournamentTree with root r with r is father of denoted nodes
  41      * a and b.
  42      * 
  43      * @param a
  44      *            one child node.
  45      * @param b
  46      *            another child node.
  47      */
  48     public TournamentTree(Node a, Node b)
  49     {
  50         // parent is null again
  51         // linking happens in constructor of Node
  52         root = new Node(a, b);
  53     }
  54 
  55     public TournamentTree link(TournamentTree other)
  56     {
  57         if (getHeight() != other.getHeight()) {
  58             System.out.println("LINK: fail, trees do not have same height");
  59         }
  60         TournamentTree result = new TournamentTree(this.root, other.root);
  61         return result;
  62     }
  63 
  64     public static TournamentTree cut(Node node)
  65     {
  66         // check some constraints concerning correctness:
  67         // we may neither call this on the root
  68         if (node.isRoot()) {
  69             System.out.println("CUT: node is root");
  70         }
  71         // nor on a node where the parent
  72         if (node.parent.element.equals(node.element)) {
  73             System.out.println("CUT: parent's element equals element");
  74         }
  75         node.parent.removeChild(node);
  76         return new TournamentTree(node);
  77     }
  78 
  79     @Override
  80     public String toString()
  81     {
  82         return root.toString();
  83     }
  84 
  85     public Node getRoot()
  86     {
  87         return root;
  88     }
  89 
  90     public int getHeight()
  91     {
  92         return root.getHeight();
  93     }
  94 
  95     public int getRootValue()
  96     {
  97         return root.element.value;
  98     }
  99 
 100     /**
 101      * Get a randomly selected leaf of this tree.
 102      * 
 103      * @param random
 104      *            a random number generator.
 105      * @return a randomly selected leaf.
 106      */
 107     public Node getRandomLeaf(Random random)
 108     {
 109         // find a random leaf
 110         // start at the root
 111         Node node = root;
 112         // as long as we don't have a leaf
 113         while (!node.isLeaf()) {
 114             // if we only have one choice, take it
 115             if (node.childs[0] == null) {
 116                 node = node.childs[1];
 117             } else if (node.childs[1] == null) {
 118                 node = node.childs[0];
 119             } else {
 120                 // otherwise, flip a coin
 121                 node = random.nextBoolean() ?
 122                         node.childs[0] : node.childs[1];
 123             }
 124         }
 125         // got a leaf, return it.
 126         return node;
 127     }
 128 
 129     public List<Node> getNodesOnLevel(int keep)
 130     {
 131         return root.getNodesOnLevel(keep);
 132     }
 133 }