KTreeNode.java

Go to the documentation of this file.

package aud;
 
import aud.util.Graphvizable;
import aud.util.GraphvizDecorable;
import aud.util.GraphvizDecorator;
import aud.util.Sys;
 
public class KTreeNode<Key extends Comparable<Key> >
  implements Graphvizable, GraphvizDecorable {
 
  protected class Entry {
    Entry(Key key,KTreeNode<Key> child) {
      this.key=key;
      this.child=child;
    }
    Entry(Entry other) {
      this.key=other.key;
      this.child=other.child;
    }
    final Key      key;
    KTreeNode<Key> child;
 
    @Override public String toString() {
      return key!=null ? key.toString() : "null";
    }
  }
 
  KTreeNode<Key>  parent_ = null;
  Vector<Entry>   entries_;
 
  protected int compareKeys(Key a,Key b) {
    if (a==null) return -1;
    if (b==null) return +1;
    else         return a.compareTo(b);
  }
 
  public KTreeNode() {
    entries_=new Vector<Entry>();
    entries_.push_back(new Entry(null,null)); // left child with key null
  }
 
  public KTreeNode(Key key) {
    entries_=new Vector<Entry>();
    entries_.push_back(new Entry(null,null)); // left child with key null
    entries_.push_back(new Entry(key,null));
  }
  public int getK() { return entries_.size(); }
 
  public Key getKey(int k) {
    assert(0<k && k<getK());
    return entries_.at(k).key;
  }
 
  public KTreeNode<Key> getChild(int k) {
    assert(0<=k && k<getK());
    return entries_.at(k).child;
  }
 
  public Key find(Key key) {
    for (int i=1;i<entries_.size();++i) {
      int cmp=compareKeys(key,entries_.at(i).key);
      if (cmp==0)
        return entries_.at(i).key;
      else if (cmp<0) {
        if (entries_.at(i-1).child==null)
          return null;
        else
          return entries_.at(i-1).child.find(key);
      }
    }
    return entries_.back().child!=null ? entries_.back().child.find(key) : null;
  }
 
  int getIndexOfChild(KTreeNode<Key> child) {
    assert(child!=null);
    for (int i=0;i<entries_.size();++i)
      if (entries_.at(i).child==child)
        return i;
    return -1;
  }
 
  Entry insert(Key key,int k) {
    assert(key!=null);
    assert(0<=k && k<=getK()); // unchecked
 
    Entry entry=new Entry(key,null);
    entries_.insert(k+1,entry);
 
    assert(entries_.at(k+1)==entry);
    assert(k==0 || compareKeys(entries_.at(k-1).key,key)<0);
    assert(k+2>=getK() || compareKeys(key,entries_.at(k+2).key)<0);
 
    return entry;
  }
 
  void split(int k) {
    assert(1<k && k<getK()-1);
    KTreeNode<Key> tmpRoot=new KTreeNode<Key>(getKey(k));
    // note: tmpRoot is never used as a node, we "steal" its entries below
 
    KTreeNode<Key> left=new KTreeNode<Key>(getKey(1));
    left.entries_.at(0).child=entries_.at(0).child;
    left.entries_.at(1).child=entries_.at(1).child; // left
    for (int i=2;i<k;++i)
      left.entries_.push_back(entries_.at(i));
    tmpRoot.entries_.front().child=left;
    left.updateChildrensParent();
 
    KTreeNode<Key> right=new KTreeNode<Key>(getKey(k+1));
    right.entries_.at(0).child=entries_.at(k).child;
    right.entries_.at(1).child=entries_.at(k+1).child; // right
    for (int i=k+2;i<getK();++i)
      right.entries_.push_back(entries_.at(i));
    tmpRoot.entries_.back().child=right;
    right.updateChildrensParent();
 
    // steal entries_ from tmpRoot, parent remains same
    this.entries_=tmpRoot.entries_;
    left.parent_=right.parent_=this;
  }
 
  void mergeChild(int k) {
    KTreeNode<Key> child=getChild(k);
    assert(child!=null);
 
    // insert entries of child
    for (int i=child.getK()-1;i>0;--i)
      entries_.insert(k+1,child.entries_.at(i));
 
    // update their parent reference
    for (int i=0;i<child.getK();++i)
      if (child.entries_.at(i).child!=null) {
        assert(child.entries_.at(i).child.parent_==child);
        child.entries_.at(i).child.parent_=this;
      }
 
    entries_.at(k).child=child.entries_.at(0).child;
  }
 
  private void updateChildrensParent() {
    for (Entry e : entries_) {
      if (e.child!=null)
        e.child.parent_=this;
    }
  }
 
  public void checkConsistency() {
    if (parent_!=null) {
      int i=parent_.getIndexOfChild(this);
      if (i<0)
        throw new RuntimeException("parent-child mismatch");
    }
    for (int i=0; i<entries_.size(); ++i) {
      if (entries_.at(i).child!=null) {
        if (entries_.at(i).child.parent_!=this)
          throw new RuntimeException("invalid parent");
      }
      if (i>1) {
        if (compareKeys(entries_.at(i-1).key,entries_.at(i).key)>=0) {
          throw new RuntimeException("invalid order of entries");
        }
      }
      // missing: check if children's keys fit in
 
      if (entries_.at(i).child!=null)
        entries_.at(i).child.checkConsistency();
    }
  }
 
  @Override public String toString() {
    java.util.Iterator<Entry> ii=entries_.iterator();
    assert(ii.hasNext());
    Entry entry=ii.next();
    assert(entry.key==null);
    String rv="";
    while (ii.hasNext()) {
      rv+=ii.next().toString();
      if (ii.hasNext())
        rv+=" | ";
    }
    return rv;
  }
 
  @Override public GraphvizDecorator getDecorator() {
    return null;
  }
 
  @Override public String toDot() {
    String dot="graph BinaryTree {\n";
 
    GraphvizDecorator decorator=getDecorator();
    if (decorator!=null) {
      String d=decorator.getGlobalStyle();
      if (d!=null) dot+=" "+d+";\n";
      d=decorator.getGraphDecoration(this);
      if (d!=null) dot+=" graph ["+d+"];\n";
    }
    dot+=treeToDot(null);
 
    dot+="\n}\n";
    //System.out.println(dot);
    return dot;
  }
 
  private String dotRef() {
    return toString()+"-"+hashCode();
  }
 
  protected String dotLabel() { return toString(); }
 
  private String treeToDot(KTreeNode<Key> parent) {
    // Currently no "root" or "same rank" tags. Do we require them?
 
    GraphvizDecorator decorator=getDecorator();
    String dot =" \""+dotRef()+"\" [label=\""+dotLabel()+"\",";
    dot+=(decorator!=null) ? decorator.getFullNodeDecoration(this) : "shape=box";
    dot+="];\n";
 
    int k=0;
    for (Entry entry : entries_) {
      if (entry.child!=null)
        dot+=entry.child.treeToDot(this);
      else
        dot+=dotLeaf("-"+k);
      ++k;
    }
 
    dot+="\n";
 
    if (parent!=null) { // edge is identified by "lower" node
      dot+=" \""+parent.dotRef()+"\" -- \""+
      dotRef()+"\" ["; // no edge labels currently
      dot+=(decorator!=null) ? decorator.getFullEdgeDecoration(this) : "";
      dot+="];\n";
    }
 
    return dot;
  }
 
  private String dotLeaf(String side) {
    String dummy="\""+dotRef()+"-"+side+"\"";
    String dot=" "+dummy+" [shape=point];\n";
    dot+=" \""+dotRef()+"\" -- "+dummy+" [];\n";
    return dot;
  }
 
  public String toTikZ() {
    return "\\"+toTikZ(0)+";\n";
  }
  protected String tikzNodeStyle() { return ""; }
  protected String toTikZ(int level) {
    String spaces=Sys.indent(level);
    String tex=spaces+"node "+tikzNodeStyle()+" {"+toString()+"}\n";
 
    int k=0;
    for (Entry entry : entries_) {
      if (entry.child!=null)
        tex+=spaces+" child {\n"+entry.child.toTikZ(level+1)+" }\n";
      // else
      ++k;
    }
 
    return tex;
  }
 
  public static void main(String[] args) {
    KTreeNode<String> node=new KTreeNode<String>("a");
    node.insert("b",1);
    node.insert("c",2);
    node.insert("d",3);
    node.insert("e",4);
 
    System.out.println(node.find("b"));
    System.out.println(node.find("d"));
    System.out.println(node.find("x"));
 
    //String dot=node.toDot();
    //System.out.println(dot);
    aud.util.DotViewer.displayWindow(node,"KTreeNode");
 
    node.split(3);
    //System.out.println(dot=node.toDot());
    aud.util.DotViewer.displayWindow(node,"KTreeNode split");
 
    System.out.println(node.find("b"));
    System.out.println(node.find("d"));
    System.out.println(node.find("x"));
 
    System.out.println(node.toTikZ());
 
    node.mergeChild(0);
    //System.out.println(dot=node.toDot());
    aud.util.DotViewer.displayWindow(node,"KTreeNode merge 0");
 
    System.out.println(node.find("b"));
    System.out.println(node.find("d"));
    System.out.println(node.find("x"));
 
    node.mergeChild(3);
    //System.out.println(dot=node.toDot());
    aud.util.DotViewer.displayWindow(node,"KTreeNode merge 3"); // FIXME
 
    System.out.println(node.find("b"));
    System.out.println(node.find("d"));
    System.out.println(node.find("x"));
 
    node.checkConsistency();
  }
}