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.     *