package ads1ss10.pa1;
import java.util.ListIterator;
/**
* B-Baum-Klasse die die fehlende Methode aus {@link AbstractBTree}
* implementiert.
*
* <p>
* In dieser Klasse müssen Sie Ihren Code einfügen und die Method
* {@link #insert insert()} implementieren.
* </p>
*
* <p>
* Sie können beliebige neue Variablen und Methoden in dieser Klasse
* hinzufügen. Wichtig ist nur, dass die oben genannten Methoden
* implementiert werden.
* </p>
*/
public class BTree extends AbstractBTree {
/**
* Hier ist die richtige Stelle für Initialisierungen die Sie für
* Ihre Implementierung benötigen.
*
* @param order
* Ordnung des B-Baumes.
*/
public BTree(int order) {
super(order);
Helper.println("BTree order: " + order);
}
/*
* (non-Javadoc)
*
* @see ads1ss10.pa1.AbstractBTree#insert(int)
*/
@Override
public void insert(int value) {
Helper.println("insert: " + value);
if(this.root == null) {
this.root = new BNode(null);
this.root.key.add(value);
this.root.child.add(null);
this.root.child.add(null);
} else {
insert_search(this.root, value);
}
}
public void insert_search(BNode node, int value) {
if(node.child.getFirst() != null) {
ListIterator<Integer> ikey = node.key.listIterator();
ListIterator<BNode> ichild = node.child.listIterator();
int key = 0;
for(int i=0; i < node.key.size(); i++) {
key = ikey.next();
BNode child = ichild.next();
if(value < key) {
insert_search(child,value);
break;
}
}
if(node.key.getLast() < value) {
insert_search(node.child.getLast(),value);
}
} else {
ListIterator<Integer> ikey = node.key.listIterator();
int key = 0;
for(int i=0; i < node.key.size(); i++) {
key = ikey.next();
if(value < key) {
node.key.add(i,value);
node.child.add(null);
break;
}
}
if(node.key.getLast() < value) {
node.key.add(node.key.size(),value);
node.child.add(null);
}
if((this.order-1) < node.key.size()) {
insert_split(node);
}
}
}
public void insert_split(BNode node) {
int midindex =
(int)(Math.
floor(node.
key.
size()/
2));
int midvalue = node.key.get(midindex);
if(node.parent == null) {
BNode newRoot = new BNode(null);
node.parent = newRoot;
newRoot.child.add(node);
this.root = newRoot;
newRoot.key.add(midvalue);
} else {
ListIterator<Integer> ikey = node.parent.key.listIterator();
int key = 0;
for(int i=0; i < node.parent.key.size(); i++) {
key = ikey.next();
if(midvalue < key) {
node.parent.key.add(i,midvalue);
break;
}
}
if(node.parent.key.getLast() < midvalue) {
node.parent.key.add(node.parent.key.size(),midvalue);
}
}
node.key.remove(midindex);
BNode leftNode = new BNode(null);
for(int i=0; i < midindex; i++) {
leftNode.key.add( node.key.getFirst() );
leftNode.child.add( node.child.getFirst() );
node.key.removeFirst();
node.child.removeFirst();
}
leftNode.child.add( node.child.getFirst() );
node.child.removeFirst();
node.parent.child.add(node.parent.key.indexOf(midvalue),leftNode);
leftNode.parent = node.parent;
if((this.order-1) < node.parent.key.size()) {
insert_split(node.parent);
}
}
/*
* (non-Javadoc)
*
* Diese Methode dient nur als Beispiel und kann entfernt werden, wenn sie
* nicht benoetigt wird!
*
* @see ads1ss10.pa1.AbstractBTree#traverseTree(ads1ss10.pa1.BNode,
* ads1ss10.pa1.BNode, int, int, boolean)
*/
@Override
public void traverseTree(BNode node, BNode parent, int child_index,
int depth, boolean end) {
if (node == null) {
return;
}
for (ListIterator<BNode> child_iterator = node.child.listIterator(); child_iterator
.hasNext();) {
BNode child = child_iterator.next();
traverseTree(child, node, node.child.indexOf(child), depth + 1, end);
}
}
}