rtree.java

一个java实现的R树

package rtree;

import java.util.*;

/**
 * To create a new RTree use the first two constructors. You must specify the dimension, the fill factor as
 * a float between 0 and 0.5 (0 to 50% capacity) and the variant of the RTree which is one of:
 * <ul>
 *  <li>RTREE_QUADRATIC</li>
 * </ul>
 * The first constructor creates by default a new memory resident page file. The second constructor takes
 * the page file as an argument. If the given page file is not empty, then all data are deleted.
 * <p>
 * The third constructor initializes the RTree from an already filled page file. Thus, you may store the
 * RTree into a persistent page file and recreate it again at any time.
 * <p>
 * Created: Tue May 18 12:57:35 1999
 * <p>
 * @author Hadjieleftheriou Marios
 * @version 1.003
 */
public class RTree {
    public final String version = "1.003";
    public final String date = "December 7th 1999";

    /** Page file where data is stored. */
    protected PageFile file = null;

    /** static identifier used for the parent of the root node. */
    public static final int NIL = -1;

    /** Available RTree variants. */
    public static final int RTREE_LINEAR = 0;
    public static final int RTREE_QUADRATIC = 1;
    public static final int RTREE_EXPONENTIAL = 2;
    public static final int RSTAR = 3;

    /** 
     * Creates a memory resident RTree with an empty root node, which is stored in page 0 and has a 
     * parent identifier equal to NIL. A new memory page file is created and used as a storage manager
     * by default.
     *
     * @param  dimension  The data dimension.
     * @param  fillFactor A percentage between 0 and 0.5. Used to calculate minimum number of entries
     *                    present in each node.
     * @param  capacity   The maximun number of entries that each node can hold.
     * @param  type       The RTree variant to use.
     */
    public RTree(int dimension, float fillFactor, int capacity, int type) {
	this(dimension, fillFactor, capacity, new MemoryPageFile(), type);
    }

    /** 
     * Creates a new RTree with an empty root node, which is stored in page 0 and has
     * a parent identifier equal to NIL. The given page file is used for storing the rtree nodes.
     * If the page file is not empty, than all entries will be overwritten.
     *
     * @param  dimension  The data dimension.
     * @param  fillFactor A percentage between 0 and 0.5. Used to calculate minimum number of entries
     *                    present in each node.
     * @param  capacity   The maximun number of entries that each node can hold.
     * @param  file       The page file to use for storing the nodes of the rtree.
     * @param  type       The RTree variant to use.
     */
    public RTree(int dimension, float fillFactor, int capacity, PageFile file, int type) {
	if (dimension <= 1) {
	    throw new IllegalArgumentException("Dimension must be larger than 1.");
	}

	if (fillFactor < 0 || fillFactor > 0.5) {
	    throw new IllegalArgumentException("Fill factor must be between 0 and 0.5.");
	}

	if (capacity <= 1) {
	    throw new IllegalArgumentException("Capacity must be larger than 1.");
	}

	if (type != RTREE_QUADRATIC /*&& type != RTREE_LINEAR && type != RTREE_EXPONENTIAL && type != RSTAR*/) {
	    throw new IllegalArgumentException("Invalid tree type.");
	}

	if (file.tree != null) {
	    throw new IllegalArgumentException("PageFile already in use by another rtree instance.");
	}

	file.initialize(this, dimension, fillFactor, capacity, type);
	this.file = file;

	Leaf root = new Leaf(this, NIL, 0);
	file.writeNode(root);
    }

    /**
     * Creates an rtree from an already initialized page file, probably stored into persistent storage.
     */
    public RTree(PageFile file) {
	if (file.tree != null) {
	    throw new IllegalArgumentException("PageFile already in use by another rtree instance.");
	}

	if (file.treeType == -1) {
	    throw new IllegalArgumentException("PageFile is empty. Use some other RTree constructor.");
	}

	file.tree = this;
	this.file = file;
    }

    /**
     * Retruns the maximun capacity of each Node.
     */
    public int getNodeCapacity() {
	return file.nodeCapacity;
    }

    /** 
     * Returns the percentage between 0 and 0.5, used to calculate minimum number of entries
     * present in each node.
     */
    public float getFillFactor() {
	return file.fillFactor;
    }

    /** 
     * Returns the data dimension.
     */
    public int getDimension() {
	return file.dimension;
    }

    /** 
     * Returns the page length.
     */
    public int getPageSize() {
	return file.pageSize;
    }

    /** 
     * Returns the level of the root Node, which signifies the level of the whole tree. Loads one
     * page into main memory.
     */
    public int getTreeLevel() {
	return  file.readNode(0).getLevel();
    }

    /** 
     * Returns the RTree variant used. 
     */
    public int getTreeType() {
	return file.treeType;
    }

    /**
     * Inserts a HyperCube into the tree, pointing to the data stored at the given page number.
     *
     * @param h The hypercube to insert.
     * @param page The page where the real data is stored.
     * @return The page number of the Leaf where the hypercube was inserted (the parent of the
     *         data entry.)
     */
    public int insert(HyperCube h, int page) {
	if (h  == null) {
	    throw new IllegalArgumentException("HyperCube cannot be null.");
	}

	if (h.getDimension() != file.dimension) {
	    throw new IllegalArgumentException("HyperCube dimension different than RTree dimension.");
	}

	AbstractNode root = file.readNode(0);

	Leaf l = root.chooseLeaf(h);
	return l.insert(h, page);
    }

    /**
     * Deletes a HyperCube from the leaf level of the tree. If there is no leaf containg a hypercube
     * that matches the given hypercube, the tree is left intact.
     *
     * @param h The HyperCube to delete.
     * @return The data pointer of the deleted entry, NIL if no matching entry was found.
     */
    public int delete(HyperCube h) {
	if (h == null) {
	    throw new IllegalArgumentException("HyperCube cannot be null.");
	}

	if (h.getDimension() != file.dimension) {
	    throw new IllegalArgumentException("HyperCube dimension different than RTree dimension.");
	}

	AbstractNode root = file.readNode(0);

	Leaf l = root.findLeaf(h);
	if (l != null) {
	    return l.delete(h);
	}
	return NIL;
    }

    /**
     * Returns a Vector containing all tree nodes from bottom to top, left to right.
     * CAUTION: If the tree is not memory resident, all nodes will be loaded into main memory.
     *
     * @param root The node from which the traverse should begin.
     * @return A Vector containing all Nodes in the correct order.
     */
    public Vector traverseByLevel(AbstractNode root) {
	if (root == null) {
	    throw new IllegalArgumentException("Node cannot be null.");
	}

	Vector ret = new Vector();
	Vector v = traversePostOrder(root);

	for (int i = 0; i <= getTreeLevel(); i++) {
	    Vector a = new Vector();
	    for (int j = 0; j < v.size(); j++) {
		Node n = (Node) v.elementAt(j);
		if (n.getLevel() == i) {
		    a.addElement(n);
		}
	    }
	    for (int j = 0; j < a.size(); j++) {
		ret.addElement(a.elementAt(j));
	    }
	}

	return ret;
    }

    /**
     * Returns an Enumeration containing all tree nodes from bottom to top, left to right.
     *
     * @return An Enumeration containing all Nodes in the correct order.
     */
    public Enumeration traverseByLevel() {
	class ByLevelEnum implements Enumeration {
	    // there is at least one node, the root node.
	    private boolean hasNext = true;

	    private Vector nodes;

	    private int index = 0;

	    public ByLevelEnum() {
		AbstractNode root = file.readNode(0);
		nodes = traverseByLevel(root);
	    }

	    public boolean hasMoreElements() {
		return hasNext;
	    }

	    public Object nextElement() {
		if (! hasNext) {
		    throw new NoSuchElementException("traverseByLevel");
		}

		Object n = nodes.elementAt(index);
		index++;
		if (index == nodes.size()) {
		    hasNext = false;
		}
		return n;
	    }
	};

	return new ByLevelEnum();
    }

    /**
     * Post order traverse of tree nodes. 
     * CAUTION: If the tree is not memory resident, all nodes will be loaded into main memory.
     *
     * @param root The node where the traversing should begin.
     * @return A Vector containing all tree nodes in the correct order.
     */
    public Vector traversePostOrder(AbstractNode root) {
	if (root == null) {
	    throw new IllegalArgumentException("Node cannot be null.");
	}

	Vector v = new Vector();
	v.addElement(root);

	if (root.isLeaf()) {
	} else {
	    for (int i = 0; i < root.usedSpace; i++) {
		Vector a = traversePostOrder(((Index) root).getChild(i));
		for (int j = 0; j < a.size(); j++) {
		    v.addElement(a.elementAt(j));
		}
	    }
	}
	return v;
    }

    /**
     * Post order traverse of all tree nodes, begging with root.
     * CAUTION: If the tree is not memory resident, all nodes will be loaded into main memory.
     *
     * @return An Enumeration containing all tree nodes in the correct order.
     */
    public Enumeration traversePostOrder() {
	class PostOrderEnum implements Enumeration {
	    private boolean hasNext = true;

	    private Vector nodes;

	    private int index = 0;

	    public PostOrderEnum() {
		AbstractNode root = file.readNode(0);
		nodes = traversePostOrder(root);
	    }

	    public boolean hasMoreElements() {
		return hasNext;
	    }

	    public Object nextElement() {
		if (! hasNext) {
		    throw new NoSuchElementException("traversePostOrder");
		}

		Object n = nodes.elementAt(index);
		index++;
		if (index == nodes.size()) {
		    hasNext = false;
		}
		return n;
	    }
	};

	return new PostOrderEnum();
    }

    /**
     * Pre order traverse of tree nodes.
     * CAUTION: If the tree is not memory resident, all nodes will be loaded into main memory.
     *
     * @param root The node where the traversing should begin.
     * @return A Vector containing all tree nodes in the correct order.
     */
    public Vector traversePreOrder(AbstractNode root) {
	if (root == null) {
	    throw new IllegalArgumentException("Node cannot be null.");
	}

	Vector v = new Vector();

	if (root.isLeaf()) {
	    v.addElement(root);
	} else {
	    for (int i = 0; i < root.usedSpace; i++) {
		Vector a = traversePreOrder(((Index) root).getChild(i));
		for (int j = 0; j < a.size(); j++) {
		    v.addElement(a.elementAt(j));
		}
	    }
	    v.addElement(root);
	}
	return v;
    }

    /**
     * Pre order traverse of all tree nodes, begging with root.
     * CAUTION: If the tree is not memory resident, all nodes will be loaded into main memory.
     *