一个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"); }