moonboat / datastructure / BTree

0 0

   

BTree

2015-01-15  moonboat
package ods;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.SortedSet;
import java.util.TreeSet;

/**
 * An implementation of a B Tree
 * @author morin
 *
 * @param
 */
public class BTree implements SSet {

Factory f;
protected Comparator c;

/**
* The maximum number of children of a node (an odd number)
*/
int b;

    /** b div 2
     */
int B; 
/**
* Number of elements stored in the tree
*/
int n;
/**
* The block storage mechanism
*/
BlockStore bs;
/**
* The index of the root node
*/
int ri;
/**
* Find the index, i, at which x should be inserted into the null-padded
* sorted array, a
* @param a
*            the sorted array (padded with null entries)
* @param x
*            the value to search for
* @return i or -i-1 if a[i] equals x
*/
protected int findIt(T[] a, T x) {
int lo = 0, hi = a.length;
while (hi != lo) {
int m = (hi+lo)/2;
int cmp = a[m] == null ? -1 : c.compare(x, a[m]);
if (cmp < 0)
hi = m;      // look in first half
else if (cmp > 0)
lo = m+1;    // look in second half
else
return -m-1; // found it
}
return lo;
}

static class DuplicateValueException extends Exception {
private static final long serialVersionUID = 1L;
}
/**
* A node in a B-tree which has an array of up to b keys and up to b children
*/
protected class Node {
/**
* This block's index
*/
int id;
/**
* The keys stored in this block
*/
T[] keys;
/**
* The indicies of the children of this block (if any)
*/
int[] children;
/**
* Constructor
*/
public Node() {
keys = f.newArray(b);
children = new int[b+1];
Arrays.fill(children, 0, children.length, -1);
id = bs.placeBlock(this);
}
public boolean isLeaf() {
return children[0] < 0;
}

/**
* Test if this block is full (contains b keys)
* @return true if the block is full
*/
public boolean isFull() {
return keys[keys.length-1] != null;
}

/**
* Count the number of keys in this block, using binary search
* @return the number of keys in this block
*/
public int size() {
int lo = 0, h = keys.length;
while (h != lo) {
int m = (h+lo)/2;
if (keys[m] == null)
h = m;
else
lo = m+1;
}
return lo;
}

/**
* Add the value x to this block
* @param x
*            the value to add
* @param ci
*            the index of the child associated with x
* @return true on success or false if x was not added
*/
public boolean add(T x, int ci) {
int i = findIt(keys, x);
if (i < 0) return false;
if (i < keys.length-1) System.arraycopy(keys, i, keys, i+1, b-i-1);
keys[i] = x;
if (i < keys.length-1) System.arraycopy(children, i+1, children, i+2, b-i-1);
children[i+1] = ci;
return true;
}
/**
* Remove the i'th value from this block - don't affect this block's
* children
* @param i
*            the index of the element to remove
* @return the value of the element removed
*/
public T remove(int i) {
T y = keys[i];
System.arraycopy(keys, i+1, keys, i, b-i-1);
keys[keys.length-1] = null;
return y;
}
/**
* Split this node into two nodes
* @return the newly created block, which has the larger keys
*/
protected Node split() {
Node w = new Node();
int j = keys.length/2;
System.arraycopy(keys, j, w.keys, 0, keys.length-j);
Arrays.fill(keys, j, keys.length, null);
System.arraycopy(children, j+1, w.children, 0, children.length-j-1);
Arrays.fill(children, j+1, children.length, -1);
bs.writeBlock(id, this);
return w;
}

public String toString() {
StringBuffer sb = new StringBuffer();
sb.append("[");
for (int i = 0; i < b; i++) {
sb.append("(" + (children[i] < 0 ? "." : children[i]) + ")");
sb.append(keys[i] == null ? "_" : keys[i].toString());
}
sb.append("(" + (children[b] < 0 ? "." : children[b]) + ")");
return sb.toString();
}
}
/**
* Construct an empty BTree that uses a DefaultComparator 
* @param b the block size
* @param clz the class of objects stored in this BTree
*/
public BTree(int b, Class clz) {
this(b, new DefaultComparator(), clz);
}
/**
* Construct an empty BTree
* @param b the block size
* @param c the comparator to use
* @param clz the class of objects stored in this BTree
*/
public BTree(int b, Comparator c, Class clz) {
this.c = c;
b += 1 - (b % 2);
this.b = b;
B = b/2;
f = new Factory(clz);
bs = new BlockStore();
ri = new Node().id;
n = 0;
}
public boolean add(T x) {
Node w;
try {
w = addRecursive(x, ri);
} catch (DuplicateValueException e) {
return false;
}
if (w != null) {   // root was split, make new root
Node newroot = new Node();
x = w.remove(0);
bs.writeBlock(w.id, w);
newroot.children[0] = ri;
newroot.keys[0] = x;
newroot.children[1] = w.id;
ri = newroot.id;
bs.writeBlock(ri, newroot);
}
n++;
return true;
}
/**
* Add the value x in the subtree rooted at the node with index ui
* This method adds x into the subtree rooted at the node u whose index is
* ui. If u is split by this operation then the return value is the Node
* that was created when u was split
* @param x
*            the element to add
* @param ui
*            the index of the node, u, at which to add x
* @return a new node that was created when u was split, or null if u was
*         not split
*/
protected Node addRecursive(T x, int ui) throws DuplicateValueException {
Node u = bs.readBlock(ui);
int i = findIt(u.keys, x);
if (i < 0) throw new DuplicateValueException();
if (u.children[i] < 0) { // leaf node, just add it
u.add(x, -1);
bs.writeBlock(u.id, u);
} else {
Node w = addRecursive(x, u.children[i]);
if (w != null) {  // child was split, w is new child 
x = w.remove(0);
bs.writeBlock(w.id, w);
u.add(x, w.id);
bs.writeBlock(u.id, u);
}
}
return u.isFull() ? u.split() : null;
}
public boolean remove(T x) {
if (removeRecursive(x, ri)) {
n--;
Node r = bs.readBlock(ri);
if (r.size() == 0 && n > 0) // root has only one child
ri = r.children[0];  
return true;
}
return false;
}

/**
* Remove the value x from the subtree rooted at the node with index ui
* @param x
*            the value to remove
* @param ui
*            the index of the subtree to remove x from
* @return true if x was removed and false otherwise
*/
protected boolean removeRecursive(T x, int ui) {
if (ui < 0) return false;  // didn't find it
Node u = bs.readBlock(ui);
int i = findIt(u.keys, x);
if (i < 0) { // found it
i = -(i+1);
if (u.isLeaf()) {
u.remove(i);
} else {
u.keys[i] = removeSmallest(u.children[i+1]);
checkUnderflow(u, i+1);
}
return true;  
} else if (removeRecursive(x, u.children[i])) {
checkUnderflow(u, i);
return true;
}
return false;
}

/**
* Remove the smallest value in the subtree rooted at the node with index ui
* @param ui
*            the index of a subtree
* @return the value that was removed
*/
protected T removeSmallest(int ui) {
Node u = bs.readBlock(ui);
if (u.isLeaf()) 
return u.remove(0);
T y = removeSmallest(u.children[0]);  
checkUnderflow(u, 0);
return y;
}

/**
* Check if an underflow has occurred in the i'th child of u and, if so, fix it 
* by borrowing from or merging with a sibling
* @param u 
* @param i
*/
protected void checkUnderflow(Node u, int i) {
if (u.children[i] < 0) return;
if (i == 0) 
checkUnderflowZero(u, i); // use u's right sibling
else
checkUnderflowNonZero(u,i);
}
protected void merge(Node u, int i, Node v, Node w) {
Utils.myassert(v.id == u.children[i]);
Utils.myassert(w.id == u.children[i+1]);
int sv = v.size();
int sw = w.size();
// copy keys from w to v
System.arraycopy(w.keys, 0, v.keys, sv+1, sw);
System.arraycopy(w.children, 0, v.children, sv+1, sw+1);
// add key to v and remove it from u
v.keys[sv] = u.keys[i];
System.arraycopy(u.keys, i+1, u.keys, i, b-i-1);
u.keys[b-1] = null;
System.arraycopy(u.children, i+2, u.children, i+1, b-i-1);
u.children[b] = -1;
}
/**
* Check if an underflow has occured in the i'th child of u and, if so, fix
* it
* @param u
*            a node
* @param i
*            the index of a child in u
*/
protected void checkUnderflowNonZero(Node u, int i) {
Node w = bs.readBlock(u.children[i]);  // w is child of u
if (w.size() < B-1) {  // underflow at w
Node v = bs.readBlock(u.children[i-1]); // v left of w
if (v.size() > B) {  // w can borrow from v
shiftLR(u, i-1, v, w);
} else { // v will absorb w
merge(u, i-1, v, w);
}
}
}
/**
* Shift keys from v into w
* @param u
*            the parent of v and w
* @param i
*            the index w in u.children
* @param v
*            the right sibling of w
* @param w
*            the left sibling of v
*/
protected void shiftLR(Node u, int i, Node v, Node w) {
int sw = w.size();
int sv = v.size();
int shift = ((sw+sv)/2) - sw;  // num. keys to shift from v to w
// make space for new keys in w
System.arraycopy(w.keys, 0, w.keys, shift, sw);
System.arraycopy(w.children, 0, w.children, shift, sw+1);
// move keys and children out of v and into w (and u)
w.keys[shift-1] = u.keys[i];
u.keys[i] = v.keys[sv-shift];
System.arraycopy(v.keys, sv-shift+1, w.keys, 0, shift-1);
Arrays.fill(v.keys, sv-shift, sv, null);
System.arraycopy(v.children, sv-shift+1, w.children, 0, shift);
Arrays.fill(v.children, sv-shift+1, sv+1, -1);
}

protected void checkUnderflowZero(Node u, int i) {
Node w = bs.readBlock(u.children[i]); // w is child of u
if (w.size() < B-1) {  // underflow at w
Node v = bs.readBlock(u.children[i+1]); // v right of w
if (v.size() > B) { // w can borrow from v
shiftRL(u, i, v, w);
} else { // w will absorb w
merge(u, i, w, v);
u.children[i] = w.id;
}
}
}

/**
* Shift keys from node v into node w
* @param u the parent of v and w
* @param i the index w in u.children
* @param v the left sibling of w
* @param w the right sibling of v
*/
protected void shiftRL(Node u, int i, Node v, Node w) {
int sw = w.size();
int sv = v.size();
int shift = ((sw+sv)/2) - sw;  // num. keys to shift from v to w
// shift keys and children from v to w
w.keys[sw] = u.keys[i];
System.arraycopy(v.keys, 0, w.keys, sw+1, shift-1);
System.arraycopy(v.children, 0, w.children, sw+1, shift);
u.keys[i] = v.keys[shift-1];
// delete keys and children from v
System.arraycopy(v.keys, shift, v.keys, 0, b-shift);
Arrays.fill(v.keys, sv-shift, b, null);
System.arraycopy(v.children, shift, v.children, 0, b-shift+1);
Arrays.fill(v.children, sv-shift+1, b+1, -1);
}

public void clear() {
n = 0;
bs.clear();
ri = new Node().id;
}

public Comparator comparator() {
return c;
}

public T find(T x) {
T z = null;
int ui = ri;
while (ui >= 0) {
Node u = bs.readBlock(ui);
int i = findIt(u.keys, x);
if (i < 0) return u.keys[-(i+1)]; // found it
if (u.keys[i] != null)
z = u.keys[i];
ui = u.children[i];
}
return z;
}

public T findGE(T x) {
return find(x);
}

public T findLT(T x) {
T z = null;
int ui = ri;
while (ui >= 0) {
Node u = bs.readBlock(ui);
int i = findIt(u.keys, x);
if (i < 0) i = -(i+1);
if (i > 0)
z = u.keys[i-1];
ui = u.children[i];
}
return z;
}
protected class BTIterator implements Iterator {
protected List nstack;
protected List istack;

public BTIterator() {
nstack = new ArrayList(); // (Node.class);
istack = new ArrayList(); // (Integer.class);
if (n == 0) return;
int ui = ri;
do {
Node u = bs.readBlock(ui);
nstack.add(u);
istack.add(0);
ui = u.children[0];
} while (ui >= 0);
}

public BTIterator(T x) {
Node u; int i;
nstack = new ArrayList(); // (Node.class);
istack = new ArrayList(); // (Integer.class);
if (n == 0) return;
int ui = ri;
do {
u = bs.readBlock(ui);
i = findIt(u.keys, x);
nstack.add(u);
if (i < 0) {
istack.add(-(i+1));
return;
}
istack.add(i);
ui = u.children[i];
} while (ui >= 0);
if (i == u.size())
advance();
}

public boolean hasNext() {
return !nstack.isEmpty();
}

public T next() {
Node u = nstack.get(nstack.size()-1);
int i = istack.get(istack.size()-1);
T y = u.keys[i++];
istack.set(istack.size()-1, i);
advance();
return y;
}
protected void advance() {
Node u = nstack.get(nstack.size()-1);
int i = istack.get(istack.size()-1);
if (u.isLeaf()) { // this is a leaf, walk up
while (!nstack.isEmpty() && i == u.size()) {
nstack.remove(nstack.size()-1);
istack.remove(istack.size()-1);
if (!nstack.isEmpty()) {
u = nstack.get(nstack.size()-1);
i = istack.get(istack.size()-1);
}
}
} else { // this is an internal node, walk down
int ui = u.children[i];
do {
u = bs.readBlock(ui);
nstack.add(u);
istack.add(0);
ui = u.children[0];
} while (ui >= 0);
}
}


public void remove() {
throw new UnsupportedOperationException();
}
}

public Iterator iterator(T x) {
return new BTIterator(x);
}

public int size() {
return n;
}

public Iterator iterator() {
return new BTIterator();
}

public String toString() {
StringBuffer sb = new StringBuffer();
toString(ri, sb);
return sb.toString();
}

/**
* A recursive algorithm for converting this tree into a string
* @param ui
*            the subtree to add to the the string
* @param sb
*            a StringBuffer for building the string
*/
public void toString(int ui, StringBuffer sb) {
if (ui < 0) return;
Node u = bs.readBlock(ui);
int i = 0;
while(i < b && u.keys[i] != null) {
toString(u.children[i], sb);
sb.append(u.keys[i++] + ", ");
}
toString(u.children[i], sb);
}

/**
* Simple test method
* @param args
*/
public static void main(String[] args) {
int b = 60, n = 100000, c = 10, reps = 500;
BTree t = new BTree(b, Integer.class);
SortedSet ss = new TreeSet();
for (int seed = 0; seed < reps; seed++) {
System.out.println("Adding " + n + " elements");
java.util.Random rand = new java.util.Random(seed);
for (int i = 0; i < n; i++) {
int x = rand.nextInt(c*n);
Utils.myassert(t.add(x) == ss.add(x));
}
if (n <= 100) {
System.out.println(t);
for (Integer xx : t)
System.out.print(xx + ", ");
System.out.println();
Iterator it = t.iterator(c*n/2); 
while (it.hasNext()) {
System.out.print(it.next() + ", ");
}
System.out.println();
}
System.out.println("ss.size() = " + ss.size());
System.out.println("t.size()  = " + t.size());
System.out.println("Checking equality");
for (int i = 0; i < n; i++) {
int x = rand.nextInt(c*n);
// System.out.println(t.findLT(x) + " < " + x + " <= " + t.find(x));
Utils.myassert(Utils.equals(t.find(x),Utils.findGE(ss, x)));
Utils.myassert(Utils.equals(t.findLT(x),Utils.findLT(ss, x)));
// System.out.println(t + " (added " + x + ")");
}
System.out.println("Removing elements");
for (int i = 0; i < 10*c*n; i++) {
int x = rand.nextInt(c*n);
Utils.myassert(t.remove(x) == ss.remove(x));
// System.out.println(t + "(removed " + x + ")");
}

System.out.println("Checking equality");
for (int i = 0; i < n; i++) {
int x = rand.nextInt(c*n);
// System.out.println(t.findLT(x) + " < " + x + " <= " + t.find(x));
Utils.myassert(Utils.equals(t.find(x),Utils.findGE(ss, x)));
Utils.myassert(Utils.equals(t.findLT(x),Utils.findLT(ss, x)));
// System.out.println(t + " (added " + x + ")");
}

System.out.println("ss.size() = " + ss.size());
System.out.println("t.size()  = " + t.size());
}

}
}


    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。如发现有害或侵权内容,请点击这里 或 拨打24小时举报电话:4000070609 与我们联系。

    猜你喜欢

    0条评论

    发表

    请遵守用户 评论公约

    类似文章
    喜欢该文的人也喜欢 更多