* @return An Enumeration containing all tree nodes in the correct order.     */    public Enumeration traversePreOrder() {	class PreOrderEnum implements Enumeration {	    private boolean hasNext = true;	    private Vector nodes;	    private int index = 0;	    public PreOrderEnum() {		AbstractNode root = file.readNode(0);		nodes = traversePreOrder(root);	    }	    public boolean hasMoreElements() {		return hasNext;	    }	    public Object nextElement() {		if (! hasNext) {		    throw new NoSuchElementException("traversePreOrder");		}		Object n = nodes.elementAt(index);		index++;		if (index == nodes.size()) {		    hasNext = false;		}		return n;	    }	};	return new PreOrderEnum();    }        /**     * Returns a Vector with all nodes that intersect with the given HyperCube.     * The nodes are returned in post order traversing     *     * @param h The given HyperCube that is tested for overlapping.     * @param root The node where the search should begin.     * @return A Vector containing the appropriate nodes in the correct order.     */    public Vector intersection(HyperCube h, AbstractNode root) {	if (h == null || root == null) {	    throw new IllegalArgumentException("Arguments cannot be null.");	}	if (h.getDimension() != file.dimension) {	    throw new IllegalArgumentException("HyperCube dimension different than RTree dimension.");	}	Vector v = new Vector();		if (root.getNodeMbb().intersection(h)) {	    v.addElement(root);	    if (!root.isLeaf()) {		for (int i = 0; i < root.usedSpace; i++) {		    if (root.data[i].intersection(h)) {			Vector a = intersection(h, ((Index) root).getChild(i));			for (int j = 0; j < a.size(); j++) {			    v.addElement(a.elementAt(j));			}		    }		}	    }	}	return v;    }    /**     * Returns an Enumeration with all nodes present in the tree that intersect with the given     * HyperCube. The nodes are returned in post order traversing     *     * @param h The given HyperCube that is tested for overlapping.     * @return An Enumeration containing the appropriate nodes in the correct order.     */    public Enumeration intersection(HyperCube h) {	class IntersectionEnum implements Enumeration {	    private boolean hasNext = true;	    private Vector nodes;	    private int index = 0;	    public IntersectionEnum(HyperCube hh) {		nodes = intersection(hh, file.readNode(0));		if (nodes.isEmpty()) {		    hasNext = false;		}	    }	    public boolean hasMoreElements() {		return hasNext;	    }	    	    public Object nextElement() {		if (! hasNext) {		    throw new NoSuchElementException("intersection");		}		Object c = nodes.elementAt(index);		index++;		if (index == nodes.size()) {		    hasNext = false;		}		return c;	    }	};	return new IntersectionEnum(h);    }    /**     * Returns a Vector with all Hypercubes that completely contain HyperCube <B>h</B>.     * The HyperCubes are returned in post order traversing, according to the Nodes where     * they belong.     *     * @param h The given HyperCube.     * @param root The node where the search should begin.     * @return A Vector containing the appropriate HyperCubes in the correct order.     */    public Vector enclosure(HyperCube h, AbstractNode root) {	if (h == null || root == null) throw new	    IllegalArgumentException("Arguments cannot be null.");	if (h.getDimension() != file.dimension) throw new	    IllegalArgumentException("HyperCube dimension different than RTree dimension.");	Vector v = new Vector();	if (root.getNodeMbb().enclosure(h)) {	    v.addElement(root);	    if (!root.isLeaf()) {		for (int i = 0; i < root.usedSpace; i++) {		    if (root.data[i].enclosure(h)) {			Vector a = enclosure(h, ((Index) root).getChild(i));			for (int j = 0; j < a.size(); j++) {			    v.addElement(a.elementAt(j));			}		    }		}	    }	}	return v;    }    /**     * Returns an Enumeration with all Hypercubes present in the tree that contain the given     * HyperCube. The HyperCubes are returned in post order traversing, according to the Nodes where     * they belong.     *     * @param h The given HyperCube.     * @param root The node where the search should begin.     * @return An Enumeration containing the appropriate HyperCubes in the correct order.     */    public Enumeration enclosure(HyperCube h) {	class ContainEnum implements Enumeration {	    private boolean hasNext = true;	    private Vector cubes;	    private int index = 0;	    public ContainEnum(HyperCube hh) {		cubes = enclosure(hh, file.readNode(0));		if (cubes.isEmpty()) {		    hasNext = false;		}	    }	    public boolean hasMoreElements() {		return hasNext;	    }	    	    public Object nextElement() {		if (!hasNext) throw new		    NoSuchElementException("enclosure");		Object c = cubes.elementAt(index);		index++;		if (index == cubes.size()) {		    hasNext = false;		}		return c;	    }	};	return new ContainEnum(h);    }    /**     * Returns a Vector with all Hypercubes that completely contain point <B>p</B>.     * The HyperCubes are returned in post order traversing, according to the Nodes where     * they belong.     *     * @param p The given point.     * @param root The node where the search should begin.     * @return A Vector containing the appropriate HyperCubes in the correct order.     */    public Vector enclosure(Point p, AbstractNode root) {	return enclosure(new HyperCube(p, p), root);    }    /**     * Returns an Enumeration with all Hypercubes present in the tree that contain the given     * point. The HyperCubes are returned in post order traversing, according to the Nodes where     * they belong.     *     * @param p The query point.     * @param root The node where the search should begin.     * @return An Enumeration containing the appropriate HyperCubes in the correct order.     */    public Enumeration enclosure(Point p) {	return enclosure(new HyperCube(p, p));    }    /**     * Returns the nearest HyperCube to the given point.     * [King Lum Cheung and Ada Wai-chee Fu: Enhanced Nearest Neighbor Search on the R-Tree]     *     * @param p The query point.     * @return A vector containing all the nodes lying in the search path until the nearest hypercube     *         is found. Elements are instances of AbstractNode and Data classes. The last Data instance     *         in the vector is the answer to the query.     */    public Vector nearestNeighbor(Point p) {	return nearestNeighborSearch(file.readNode(0), p, Float.POSITIVE_INFINITY);    }    /**     * Used for nearest neighbor recursive search into the RTree structure. <B>n</B> is the current     * node of the active branch list, searched. <B>p</B> is the query point. <B>nearest</B> is the      * distance of <B>p</B> from current nearest hypercube <B>h</B>.     */    protected Vector nearestNeighborSearch(AbstractNode n, Point p, float nearest) {	Vector ret = new Vector();	HyperCube h;	if (n.isLeaf()) {	    for (int i = 0; i < n.usedSpace; i++) {		float dist = n.data[i].getMinDist(p);		if (dist < nearest) {		    h = n.data[i];		    nearest = dist;		    ret.addElement(new Data(h, n.branches[i], n.pageNumber, i));		}	    }	    return ret;	} else {	    // generate Active Branch List.	    class ABLNode {		AbstractNode node;		float minDist;		public ABLNode(AbstractNode node, float minDist) {		    this.node = node;		    this.minDist = minDist;		}	    }	    ABLNode[] abl = new ABLNode[n.usedSpace];	    for (int i = 0; i < n.usedSpace; i++) {		AbstractNode ch = ((Index) n).getChild(i);		abl[i] = new ABLNode(ch , ch.getNodeMbb().getMinDist(p));	    }	    // sort ABL in ascending order of MINDIST from the query point.	    Sort.mergeSort(		abl,		new Comparator() {			public int compare(Object o1, Object o2) {			    float f = ((ABLNode) o1).minDist - 				        ((ABLNode) o2).minDist;			    // do not round the float here. It is wrong!			    if (f > 0) return 1;			    else if (f < 0) return -1;			    else  return 0;			}		}	    );	    // traverse all ABL nodes and prune irrelevant nodes according to the MINDIST heuristic.	    for (int i = 0; i < abl.length; i++) {		if (abl[i].minDist <= nearest) {		    // add node in the results vector, if it complies to the MINDIST heuristic.		    ret.addElement(abl[i].node);		    // recursively continue the search.		    Vector v = nearestNeighborSearch(abl[i].node, p, nearest);		    // find the new nearest distance and add all the nodes accessed, into the current 		    // results vector.		    try {			Object o = v.lastElement();			if (o instanceof AbstractNode) {			    for (int j = 0; j < v.size(); j++) {				ret.addElement(v.elementAt(j));			    }			    AbstractNode an = (AbstractNode) o;			    h = (HyperCube) an.getNodeMbb();			    nearest = h.getMinDist(p);			} else if (o instanceof Data) {			    // if the current node searched was a leaf, than the resulting set definetly			    // contains just one HyperCube, the nearest to the query point.			    h = ((Data) o).mbb;			    nearest = h.getMinDist(p);			    ret.addElement(o);			}		    } catch (NoSuchElementException e) {			// no nearest node or hypercube was found from this recursion step. Leave nearest			// distance intact.		    }		}	    }	    return ret;	}    }    public static void main(String[] args) {	//PersistantPageFile file = new PersistantPageFile("c:/temp/rtree.dat");	CachedPersistentPageFile file = new CachedPersistentPageFile("c:/temp/rtree.dat", 3);	//MemoryPageFile file = new MemoryPageFile();	RTree r = new RTree(2, 0.4f, 3, file, RTree.RTREE_QUADRATIC);	//RTree r = new RTree(file);	float[] f = {10, 20, 40, 70,		     30, 10, 70, 15,		     100, 70, 110, 80,		     0, 50, 30, 55,		     13, 21, 54, 78,		     3, 8, 23, 34,		     200, 29, 202, 50,		     34, 1, 35, 1,		     201, 200, 234, 203,		     56, 69, 58, 70,		     12, 67, 70, 102,		     1, 10, 10, 20	};	for (int i = 0; i < f.length;) {	    Point p1 = new Point(new float[] {f[i++],f[i++]});	    Point p2 = new Point(new float[] {f[i++],f[i++]});	    final HyperCube h = new HyperCube(p1, p2);	    r.insert(h, -2);	}	for (Enumeration e = r.traverseByLevel(); e.hasMoreElements();) {	    System.out.println(e.nextElement());	}	/*	HyperCube h = new HyperCube(new Point(new float[] {10, 15}), new Point(new float[] {23, 24}));	for (Enumeration e = r.intersection(h); e.hasMoreElements();) {	    System.out.println(e.nextElement());	}	Point p = new Point(new float[] {112, 75});	System.out.print("Nearest to " + p + " is ");	System.out.println(r.nearestNeighbor(p));	*/    }} // RTree