adt.tournament.Node

   1 package adt.tournament;
   2 
   3 /**
   4  * @author Sebastian Kuerten (sebastian.kuerten@fu-berlin.de)
   5  * 
   6  */
   7 import java.util.ArrayList;
   8 import java.util.List;
   9 
  10 public class Node
  11 {
  12     int height = 0;
  13     Element element = null;
  14     Node parent = null;
  15     Node highestEqualNode = null;
  16     Node lowestEqualNode = null;
  17     Node[] childs = new Node[2];
  18 
  19     public Node(int value)
  20     {
  21         // height is 0 anyway
  22         element = new Element(value);
  23         highestEqualNode = this;
  24         lowestEqualNode = this;
  25         childs[0] = null;
  26         childs[1] = null;
  27     }
  28 
  29     public Node(Node a, Node b)
  30     {
  31         a.parent = this;
  32         b.parent = this;
  33         childs[0] = a;
  34         childs[1] = b;
  35         if (a.element.compareTo(b.element) < 0) {
  36             this.lowestEqualNode = a.lowestEqualNode;
  37             a.lowestEqualNode.highestEqualNode = this;
  38             element = a.element;
  39         } else {
  40             this.lowestEqualNode = b.lowestEqualNode;
  41             b.lowestEqualNode.highestEqualNode = this;
  42             element = b.element;
  43         }
  44         int max = a.getHeight() > b.getHeight() ? a.getHeight() : b.getHeight();
  45         height = max + 1;
  46     }
  47 
  48     @Override
  49     public String toString()
  50     {
  51         StringBuilder strb = new StringBuilder();
  52         strb.append(element.toString());
  53         strb.append(",[");
  54         if (childs[0] == null) {
  55             strb.append("none");
  56         } else {
  57             strb.append(childs[0].toString());
  58         }
  59         strb.append(",");
  60         if (childs[1] == null) {
  61             strb.append("none");
  62         } else {
  63             strb.append(childs[1].toString());
  64         }
  65         strb.append("]");
  66         return strb.toString();
  67     }
  68 
  69     public boolean isRoot()
  70     {
  71         return parent == null;
  72     }
  73 
  74     public boolean isLeaf()
  75     {
  76         return childs[0] == null && childs[1] == null;
  77     }
  78 
  79     public void removeChild(Node node)
  80     {
  81         if (childs[0] == node) {
  82             childs[0] = null;
  83         } else if (childs[1] == node) {
  84             childs[1] = null;
  85         } else {
  86             System.out.println("REMOVE: failed, denoted node is not a child");
  87         }
  88     }
  89 
  90     public void setValue(int value)
  91     {
  92         element.setValue(value);
  93     }
  94 
  95     public int getValue()
  96     {
  97         return element.value;
  98     }
  99 
 100     public Node getHighestEqualNode()
 101     {
 102         return lowestEqualNode.highestEqualNode;
 103     }
 104 
 105     public int getHeight()
 106     {
 107         return height;
 108     }
 109 
 110     public List<Node> collectDifferentDescandents()
 111     {
 112         List<Node> nodes = new ArrayList<Node>();
 113         collectDifferentDescandents(nodes, this, this);
 114         return nodes;
 115     }
 116 
 117     private void collectDifferentDescandents(List<Node> nodes, Node node,
 118             Node root)
 119     {
 120         // recurse into both children if they exist
 121         if (node.childs[0] != null) {
 122             collect(nodes, node.childs[0], root);
 123         }
 124         if (node.childs[1] != null) {
 125             collect(nodes, node.childs[1], root);
 126         }
 127     }
 128 
 129     private void collect(List<Node> nodes, Node node, Node root)
 130     {
 131         // test for pointer equality here to allow semantically equal objects
 132         // being present in the tree
 133         if (node.element == root.element) {
 134             // on this path is the same value
 135             collectDifferentDescandents(nodes, node, root);
 136         } else {
 137             // different value here, put in result list
 138             nodes.add(node);
 139         }
 140     }
 141 
 142     /**
 143      * @return whether decreasing this node's value would cause a cut to occur.
 144      */
 145     public boolean willCauseCut()
 146     {
 147         return !highestEqualNode.isRoot();
 148     }
 149 
 150     /**
 151      * Get all nodes descending from this node that are exaclty on the level
 152      * 'keep'. Returns this node itself if the level fits.
 153      * 
 154      * @param keep
 155      *            the level of nodes to get.
 156      * @return a list of nodes.
 157      */
 158     public List<Node> getNodesOnLevel(int keep)
 159     {
 160         List<Node> result = new ArrayList<Node>();
 161         getNodesOnLevel(keep, result);
 162         return result;
 163     }
 164 
 165     private void getNodesOnLevel(int keep, List<Node> result)
 166     {
 167         if (height == keep) {
 168             result.add(this);
 169             return;
 170         }
 171         if (childs[0] != null) {
 172             childs[0].getNodesOnLevel(keep, result);
 173         }
 174         if (childs[1] != null) {
 175             childs[1].getNodesOnLevel(keep, result);
 176         }
 177     }
 178 }