leaf.java

一个java实现的R树

package rtree;

import java.util.*;

/**
 * A Leaf node. Containts pointers to the real data.
 * <p>
 * Created: Tue May 18 13:04:08 1999
 * <p>
 * @author Hadjieleftheriou Marios
 * @version 1.002
 */
public class Leaf extends AbstractNode {
    
    protected Leaf(RTree tree, int parent, int pageNumber) {
	// Leaf nodes belong by default to level 0.
	super(tree, parent, pageNumber, 0);
    }

    protected Leaf(RTree tree, int parent) {
	// Leaf nodes belong by default to level 0.
	super(tree, parent, -1, 0);
    }

    protected Leaf chooseLeaf(HyperCube h) {
	return this;
    }

    protected Leaf findLeaf(HyperCube h) {
	for (int i = 0; i < usedSpace; i++) {
	    if (data[i].enclosure(h)) {
		return this;
	    }
	}

	return null;
    }

    /**
     * Inserts a new HyperCube into the Leaf. If there is space left, then the insertion is straightforward and
     * adjustTree must be called. Otherwise, a split must occur and two new leaves must be created.
     *
     * @param h The HyperCube that represents the MBB of the data.
     * @param page The page number where the real data resides.
     * @return The page number of the Leaf where the hypercube was inserted.
     */
    protected int insert(HyperCube h, int page) {
	if (usedSpace < tree.getNodeCapacity()) {
	    data[usedSpace] = h;
	    branches[usedSpace] = page;
	    usedSpace++;
	    tree.file.writeNode(this);
	    Index p = (Index) getParent();
	    if (p != null) {
		p.adjustTree(this, null);
	    }
	    return pageNumber;
	} else {
	    Leaf[] a = splitLeaf(h, page);
	    Leaf l = a[0];
	    Leaf ll = a[1];

	    if (isRoot()) {
		// root is full, so we must split it. From now on root will be
		// an Index and not a Leaf.
		l.parent = 0;
		l.pageNumber = -1;
		ll.parent = 0;
		ll.pageNumber = -1;
		tree.file.writeNode(l);
		tree.file.writeNode(ll);
		// create the new root node. It belongs to pageNumber 0 and level 1.
		Index r = new Index(tree, RTree.NIL, 0, 1);
		r.addData(l.getNodeMbb(), l.pageNumber);
		r.addData(ll.getNodeMbb(), ll.pageNumber);
		tree.file.writeNode(r);
	    } else {
		// use old page number for left child, a new page number for the right child.
		l.pageNumber = pageNumber;
		ll.pageNumber = -1;
		tree.file.writeNode(l);
		tree.file.writeNode(ll);
		Index p = (Index) getParent();
		p.adjustTree(l, ll);
	    }

	    // Find which is the parent Leaf of the inserted hypercube and return it's page number.
	    for (int i = 0; i < l.usedSpace; i++) {
		if (l.branches[i] == page) {
		    return l.pageNumber;
		}
	    }

	    for (int i = 0; i < ll.usedSpace; i++) {
		if (ll.branches[i] == page) {
		    return ll.pageNumber;
		}
	    }

	    return -1;
	}
    }

    /**
     * Deletes an entry for the leaf.
     * [A. Guttman 'R-trees a dynamic index structure for spatial searching']
     * 3.3. Deletion
     *
     * @param h  The hypercube that corresponds to the entry to be deleted.
     * @return The data pointer of the deleted entry.
     **/
    protected int delete(HyperCube h) {
	for (int i = 0; i < usedSpace; i++) {
	    if (data[i].equals(h)) {
		int pointer = branches[i];
		deleteData(i);
		tree.file.writeNode(this);
		Vector q = new Vector();
		condenseTree(q);

		// reinsert eliminated leaves.
		for (int l = 0; l < q.size(); l++) {
		    AbstractNode n = (AbstractNode) q.elementAt(l);
		    if (n.isLeaf()) {
			for (int j = 0; j < n.usedSpace; j++) {
			    tree.insert(n.data[j], n.branches[j]);
			}
		    } else {
			// this is not what Gutman says, but it will work anyway...
			Vector v = tree.traversePostOrder(n);
			for (int j = 0; j < v.size(); j++) {
			    AbstractNode m = (AbstractNode) v.elementAt(j);
			    if (m.isLeaf()) {
				for (int k = 0; k < m.usedSpace; k++) {
				    tree.insert(m.data[k], m.branches[k]);
				}
			    }
			    tree.file.deletePage(m.pageNumber);
			}
		    }
		    tree.file.deletePage(n.pageNumber);
		}

		return pointer;
	    }
	}
	return RTree.NIL;
    }

    private Leaf[] splitLeaf(HyperCube h, int page) {
	int[][] group = null;

	switch (tree.getTreeType()) {
	case tree.RTREE_LINEAR:
	    break;
	case tree.RTREE_QUADRATIC:
	    group = quadraticSplit(h, page);
	    break;
	case tree.RTREE_EXPONENTIAL:
	    break;
	case tree.RSTAR:
	    break;
	default:
	    throw new IllegalStateException("Invalid tree type.");
	}

	Leaf l = new Leaf(tree, parent);
	Leaf ll = new Leaf(tree, parent);

	int[] g1 = group[0];
	int[] g2 = group[1];

	for (int i = 0; i < g1.length; i++) {
	    l.addData(data[g1[i]], branches[g1[i]]);
	}
	    
	for (int i = 0; i < g2.length; i++) {
	    ll.addData(data[g2[i]], branches[g2[i]]);
	}

	return new Leaf[] {l, ll};
    }

    /**
     * Returns the pointer of the <i>i-th</i> data entry.
     *
     * @param  i The index of the child in the data array.
     * @return The pointer of the <i>i-th</i> child.
     */
    public int getDataPointer(int i) {
	if (i < 0 || i >= usedSpace) {
	    throw new IndexOutOfBoundsException("" + i);
	}

	return branches[i];
    }

} // Leaf