From 7a2e20caac9db6f789a7b3fab344b9758af45335 Mon Sep 17 00:00:00 2001 From: Harvey Harrison Date: Sun, 19 Apr 2015 21:02:06 -0700 Subject: j3dcore: flatten the directory structure a bit Signed-off-by: Harvey Harrison --- src/javax/media/j3d/BHTree.java | 1154 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 1154 insertions(+) create mode 100644 src/javax/media/j3d/BHTree.java (limited to 'src/javax/media/j3d/BHTree.java') diff --git a/src/javax/media/j3d/BHTree.java b/src/javax/media/j3d/BHTree.java new file mode 100644 index 0000000..260448c --- /dev/null +++ b/src/javax/media/j3d/BHTree.java @@ -0,0 +1,1154 @@ +/* + * Copyright 1999-2008 Sun Microsystems, Inc. All Rights Reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. Sun designates this + * particular file as subject to the "Classpath" exception as provided + * by Sun in the LICENSE file that accompanied this code. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, + * CA 95054 USA or visit www.sun.com if you need additional information or + * have any questions. + * + */ + +package javax.media.j3d; + +import java.util.ArrayList; +import java.util.Vector; + +import javax.vecmath.Point4d; + +class BHTree { + + Locale locale; + + private BHNode root; + private BHInsertStructure insertStructure = null; + + // Temporary point, so we dont generate garbage + Point4d tPoint4d = new Point4d(); + + // A flag to signal that number of renderAtoms sent to RenderBin is stable. + private boolean stable = false; + + // An estimate of the maxmium depth of this tree (upper bound). + int estMaxDepth; + + static final double LOG_OF_2 = Math.log(2); + + // Assume that the size avg. leaf node is 256 bytes. For a 64bit system, we'll + // down with max depth of 56 for an ideal balance tree. + static final int DEPTH_UPPER_BOUND = 56; + static final int INCR_DEPTH_BOUND = 5; + int depthUpperBound = DEPTH_UPPER_BOUND; + + BHTree() { + locale = null; + root = null; + } + + BHTree(Locale loc) { + locale = loc; + root = null; + } + + BHTree(BHNode bhArr[]) { + locale = null; + root = null; + create(bhArr); + } + + void setLocale(Locale loc) { + locale = loc; + } + + Locale getLocale() { + return locale; + } + + void cluster(BHInternalNode root, BHNode[] bhArr) { + + if(J3dDebug.devPhase) { + if(J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4, + "BHTree.java :In cluster length is " + bhArr.length + + "\n")) { + + for(int i=0; i= bBox.upper.x) && + (aBox.upper.y >= bBox.upper.y) && + (aBox.upper.z >= bBox.upper.z) && + (aBox.lower.x <= bBox.lower.x) && + (aBox.lower.y <= bBox.lower.y) && + (aBox.lower.z <= bBox.lower.z)); + } + + + BHLeafInterface selectAny(GeometryAtom atom, int accurancyMode) { + if (atom.source.geometryList == null) + return null; + BHNode bhNode = doSelectAny(atom, root, accurancyMode); + if (bhNode == null) { + return null; + } + + return ((BHLeafNode) bhNode).leafIF; + } + + + BHLeafInterface selectAny(GeometryAtom atoms[], int size, int accurancyMode) { + BHNode bhNode = doSelectAny(atoms, size, root, accurancyMode); + if (bhNode == null) { + return null; + } + + return ((BHLeafNode) bhNode).leafIF; + } + + + private BHNode doSelectAny(GeometryAtom atoms[],int atomSize, + BHNode bh, int accurancyMode) { + if ((bh == null) || (bh.bHull.isEmpty())) { + return null; + } + switch (bh.nodeType) { + case BHNode.BH_TYPE_LEAF: + BHLeafInterface leaf = ((BHLeafNode) bh).leafIF; + GeometryAtom atom; + int i; + + if (leaf instanceof GeometryAtom) { + GeometryAtom leafAtom = (GeometryAtom) leaf; + + if (((BHLeafNode) bh).isEnable() && + leafAtom.source.isCollidable) { + + // atom self intersection between atoms[] + for (i=atomSize-1; i >=0; i--) { + if (atoms[i] == leafAtom) { + return null; + } + } + for (i=atomSize-1; i >=0; i--) { + atom = atoms[i]; + if ((atom.source.sourceNode != leafAtom.source.sourceNode) && + (atom.source.collisionVwcBound.intersect(leafAtom.source.collisionVwcBound)) && + ((accurancyMode == WakeupOnCollisionEntry.USE_BOUNDS) || + ((leafAtom.source.geometryList != null) && + (atom.source.intersectGeometryList(leafAtom.source))))) { + return bh; + } + } + } + } else if (leaf instanceof GroupRetained) { + if (((BHLeafNode) bh).isEnable() && + ((GroupRetained) leaf).sourceNode.collidable) { + for (i=atomSize-1; i >=0; i--) { + atom = atoms[i]; + if (atom.source.collisionVwcBound.intersect(bh.bHull) && + ((accurancyMode == WakeupOnCollisionEntry.USE_BOUNDS) || + (atom.source.intersectGeometryList( + atom.source.getCurrentLocalToVworld(0), bh.bHull)))) { + return bh; + } + } + } + } + return null; + case BHNode.BH_TYPE_INTERNAL: + for (i=atomSize-1; i >=0; i--) { + atom = atoms[i]; + if (atom.source.collisionVwcBound.intersect(bh.bHull)) + { + BHNode hitNode = doSelectAny(atoms, + atomSize, + ((BHInternalNode) bh).getRightChild(), + accurancyMode); + if (hitNode != null) + return hitNode; + + return doSelectAny(atoms, atomSize, + ((BHInternalNode) bh).getLeftChild(), + accurancyMode); + } + } + return null; + } + return null; + } + + + private BHNode doSelectAny(GeometryAtom atom, BHNode bh, int accurancyMode) { + if ((bh == null) || (bh.bHull.isEmpty())) { + return null; + } + switch (bh.nodeType) { + case BHNode.BH_TYPE_LEAF: + BHLeafInterface leaf = ((BHLeafNode) bh).leafIF; + if (leaf instanceof GeometryAtom) { + GeometryAtom leafAtom = (GeometryAtom) leaf; + if ((atom.source.sourceNode != leafAtom.source.sourceNode) && + (((BHLeafNode) bh).isEnable()) && + (leafAtom.source.isCollidable) && + (atom.source.collisionVwcBound.intersect(leafAtom.source.collisionVwcBound)) && + ((accurancyMode == WakeupOnCollisionEntry.USE_BOUNDS) || + ((leafAtom.source.geometryList != null) && + (atom.source.intersectGeometryList(leafAtom.source))))) { + return bh; + } + } else if (leaf instanceof GroupRetained) { + if (((BHLeafNode) bh).isEnable() && + ((GroupRetained) leaf).sourceNode.collidable && + atom.source.collisionVwcBound.intersect(bh.bHull) && + ((accurancyMode == WakeupOnCollisionEntry.USE_BOUNDS) || + (atom.source.intersectGeometryList( + atom.source.getCurrentLocalToVworld(0), bh.bHull)))) { + return bh; + } + } + return null; + case BHNode.BH_TYPE_INTERNAL: + if (atom.source.collisionVwcBound.intersect(bh.bHull)) { + BHNode hitNode = doSelectAny(atom, + ((BHInternalNode) bh).getRightChild(), + accurancyMode); + if (hitNode != null) + return hitNode; + + return doSelectAny(atom, + ((BHInternalNode) bh).getLeftChild(), + accurancyMode); + } + return null; + } + return null; + } + + BHLeafInterface selectAny(Bounds bound, int accurancyMode, + NodeRetained armingNode) { + if (bound == null) { + return null; + } + BHNode bhNode = doSelectAny(bound, root, accurancyMode, armingNode); + if (bhNode == null) { + return null; + } + return ((BHLeafNode) bhNode).leafIF; + } + + private BHNode doSelectAny(Bounds bound, BHNode bh, int accurancyMode, + NodeRetained armingNode) { + if ((bh == null) || (bh.bHull.isEmpty())) { + return null; + } + + switch (bh.nodeType) { + case BHNode.BH_TYPE_LEAF: + BHLeafInterface leaf = ((BHLeafNode) bh).leafIF; + if (leaf instanceof GeometryAtom) { + GeometryAtom leafAtom = (GeometryAtom) leaf; + if ((((BHLeafNode) bh).isEnable()) && + (leafAtom.source.isCollidable) && + (bound.intersect(leafAtom.source.collisionVwcBound)) && + ((accurancyMode == WakeupOnCollisionEntry.USE_BOUNDS) || + ((leafAtom.source.geometryList != null) && + (leafAtom.source.intersectGeometryList( + leafAtom.source.getCurrentLocalToVworld(0), bound))))) { + return bh; + } + } else if (leaf instanceof GroupRetained) { + if ((leaf != armingNode) && + ((BHLeafNode) bh).isEnable() && + ((GroupRetained) leaf).sourceNode.collidable && + bound.intersect(bh.bHull)) { + return bh; + } + } + return null; + case BHNode.BH_TYPE_INTERNAL: + if (bound.intersect(bh.bHull)) { + BHNode hitNode = doSelectAny(bound, + ((BHInternalNode) bh).getRightChild(), + accurancyMode, + armingNode); + if (hitNode != null) + return hitNode; + + return doSelectAny(bound, + ((BHInternalNode) bh).getLeftChild(), + accurancyMode, + armingNode); + } + return null; + } + return null; + } + + + BHLeafInterface selectAny(Bounds bound, int accurancyMode, + GroupRetained armingGroup) { + if (bound == null) { + return null; + } + BHNode bhNode = doSelectAny(bound, root, accurancyMode, armingGroup); + if (bhNode == null) { + return null; + } + return ((BHLeafNode) bhNode).leafIF; + } + + private BHNode doSelectAny(Bounds bound, BHNode bh, int accurancyMode, + GroupRetained armingGroup) { + if ((bh == null) || (bh.bHull.isEmpty())) { + return null; + } + switch (bh.nodeType) { + case BHNode.BH_TYPE_LEAF: + BHLeafInterface leaf = ((BHLeafNode) bh).leafIF; + + if (leaf instanceof GeometryAtom) { + GeometryAtom leafAtom = (GeometryAtom) leaf; + if ((((BHLeafNode) bh).isEnable()) && + (leafAtom.source.isCollidable) && + (bound.intersect(leafAtom.source.collisionVwcBound)) && + (!isDescendent(leafAtom.source.sourceNode, + armingGroup, leafAtom.source.key)) && + ((accurancyMode == WakeupOnCollisionEntry.USE_BOUNDS) || + ((leafAtom.source.geometryList != null) && + (leafAtom.source.intersectGeometryList( + leafAtom.source.getCurrentLocalToVworld(0), bound))))) { + return bh; + } + } else if (leaf instanceof GroupRetained) { + GroupRetained group = (GroupRetained) leaf; + if (((BHLeafNode) bh).isEnable() && + group.sourceNode.collidable && + bound.intersect(bh.bHull) && + !isDescendent(group.sourceNode, armingGroup, group.key)) { + return bh; + } + } + return null; + case BHNode.BH_TYPE_INTERNAL: + if (bound.intersect(bh.bHull)) { + BHNode hitNode = doSelectAny(bound, + ((BHInternalNode) bh).getRightChild(), + accurancyMode, + armingGroup); + if (hitNode != null) + return hitNode; + + return doSelectAny(bound, + ((BHInternalNode) bh).getLeftChild(), + accurancyMode, + armingGroup); + } + return null; + } + return null; + } + + // Return true if node is a descendent of group + private boolean isDescendent(NodeRetained node, + GroupRetained group, + HashKey key) { + + synchronized (group.universe.sceneGraphLock) { + if (node.inSharedGroup) { + // getlastNodeId() will destroy this key + if (key != null) { + key = new HashKey(key); + } + } + + do { + if (node == group) { + return true; + } + if (node instanceof SharedGroupRetained) { + // retrieve the last node ID + String nodeId = key.getLastNodeId(); + NodeRetained prevNode = node; + Vector parents = ((SharedGroupRetained)node).parents; + for(int i=parents.size()-1; i >=0; i--) { + NodeRetained link = parents.get(i); + if (link.nodeId.equals(nodeId)) { + node = link; + break; + } + } + if (prevNode == node) { + // branch is already detach + return true; + } + } + node = node.parent; + } while (node != null); // reach Locale + } + return false; + } + + + void select(PickShape pickShape, UnorderList hitArrList) { + + if((pickShape == null)||(root == null)) + return; + + doSelect(pickShape, hitArrList, root, tPoint4d); + + } + + + private void doSelect(PickShape pickShape, UnorderList hitArrList, + BHNode bh, Point4d pickPos) { + + if ((bh == null) || (bh.bHull.isEmpty())) { + return; + } + + switch(bh.nodeType) { + case BHNode.BH_TYPE_LEAF: + if (((BHLeafNode)(bh)).isEnable() && + (((BHLeafNode) bh).leafIF instanceof GeometryAtom) && + ((GeometryAtom) (((BHLeafNode) + bh).leafIF)).source.isPickable && + pickShape.intersect(bh.bHull, pickPos)) { + hitArrList.add(bh); + } + break; + case BHNode.BH_TYPE_INTERNAL: + if (pickShape.intersect(bh.bHull, pickPos)) { + doSelect(pickShape, + hitArrList, + ((BHInternalNode)bh).getRightChild(), + pickPos); + doSelect(pickShape, + hitArrList, + ((BHInternalNode)bh).getLeftChild(), + pickPos); + } + break; + } + } + + BHNode selectAny(PickShape pickShape) { + + if((pickShape == null)||(root == null)) + return null; + + return doSelectAny(pickShape, root, tPoint4d); + + } + + + private BHNode doSelectAny(PickShape pickShape, BHNode bh, Point4d pickPos) { + + BHNode hitNode = null; + + if((bh == null) || (bh.bHull.isEmpty())) + return null; + + switch(bh.nodeType) { + case BHNode.BH_TYPE_LEAF: + if (((BHLeafNode)(bh)).isEnable() && + (((BHLeafNode) bh).leafIF instanceof GeometryAtom) && + ((GeometryAtom) (((BHLeafNode) + bh).leafIF)).source.isPickable && + pickShape.intersect(bh.bHull, pickPos)) { + return bh; + } + break; + case BHNode.BH_TYPE_INTERNAL: + if (pickShape.intersect(bh.bHull, pickPos)) { + hitNode = doSelectAny(pickShape, + ((BHInternalNode)bh).getRightChild(), + pickPos); + + if (hitNode != null) { + return hitNode; + } + + return doSelectAny(pickShape, + ((BHInternalNode)bh).getLeftChild(), + pickPos); + } + break; + } + return null; + } + + + private void create(BHNode bhArr[]) { + int i; + + if(bhArr == null) { + root = null; + return; + } + + if(bhArr.length == 1) { + bhArr[0].computeBoundingHull(); + root = (BHNode)bhArr[0]; + return; + } + + int centerValuesIndex[] = new int[bhArr.length]; + float centerValues[][] = computeCenterValues(bhArr, centerValuesIndex); + + /* + System.err.println("Length of array is " + bhArr.length); + for(int kk=0; kk depthUpperBound) { + int maxDepth = root.computeMaxDepth(0); + int leafCount = root.countNumberOfLeaves(); + double compDepth = Math.log(leafCount)/LOG_OF_2; + /* + System.err.println("BHTree - evaluate for reConstructTree ..."); + System.err.println("compDepth " + compDepth); + System.err.println("maxDepth " + maxDepth); + System.err.println("leafCount " + leafCount); + */ + + // Upper bound guard. + if(maxDepth > depthUpperBound) { + reConstructTree(leafCount); + maxDepth = root.computeMaxDepth(0); + /* + System.err.println("BHTree - Did reConstructTree ..."); + System.err.println("compDepth " + compDepth); + System.err.println("maxDepth " + maxDepth); + */ + } + + // Adjust depthUpperBound according to app. need. + // If we encounter lots of overlapping bounds, the re-balanced + // tree may not be an ideal balance tree. So there might be a + // likehood of maxDepth exceeding the preset depthUpperBound. + if(maxDepth > depthUpperBound) { + depthUpperBound = depthUpperBound + INCR_DEPTH_BOUND; + }else if((depthUpperBound != DEPTH_UPPER_BOUND) && + (maxDepth * 1.5 < depthUpperBound)) { + depthUpperBound = depthUpperBound - INCR_DEPTH_BOUND; + + if(depthUpperBound < DEPTH_UPPER_BOUND) { + // Be sure that DEPTH_UPPER_BOUND is the min. + depthUpperBound = DEPTH_UPPER_BOUND; + } + } + + // This is the only place for resetting estMaxDepth to the tree real + // maxDepth. Hence in cases where tree may get deteriorate fast, such + // as multiple inserts and deletes frequently. estMaxDepth is accuminated, + // and will lead to tree re-evaluation and possibly re-balancing. + estMaxDepth = maxDepth; + } + + } + + + // mark all elements of the node and its parent as needing updating + private void markParentChain(BHNode[] nArr, int size) { + BHNode node; + + for(int i=0; i=0; i--) { + sumCenters[i] = 0.0f; + ss[i] = 0.0f; + } + + for(i=arrLen-1; i>=0 ; i--) { + sumCenters[0] += centerValues[centerValuesIndex[i]][0]; + sumCenters[1] += centerValues[centerValuesIndex[i]][1]; + sumCenters[2] += centerValues[centerValuesIndex[i]][2]; + } + + means[0] = sumCenters[0]/(float)arrLen; + means[1] = sumCenters[1]/(float)arrLen; + means[2] = sumCenters[2]/(float)arrLen; + + for(i=arrLen-1; i>=0 ; i--) { + temp = (centerValues[centerValuesIndex[i]][0] - means[0]); + ss[0] += (temp*temp); + temp = (centerValues[centerValuesIndex[i]][1] - means[1]); + ss[1] += (temp*temp); + temp = (centerValues[centerValuesIndex[i]][2] - means[2]); + ss[2] += (temp*temp); + + } + + } + + // find the split axis (the highest ss and return its index) for + // a given set of ss values + int findSplitAxis ( float ss[] ) { + int splitAxis = -1; + float maxSS = 0.0f; + + // the largest ss index value + for (int i=0; i < 3; i++) { + if ( ss[i] > maxSS ) { + maxSS = ss[i]; + splitAxis = i; + } + } + return splitAxis; + } + + // Recursive method for constructing a binary tree. + void constructTree( BHInternalNode parent, BHNode bhArr[], + float[][] centerValues, + int[] centerValuesIndex ){ + + int i, splitAxis; + int rightSetCount = 0; + int leftSetCount = 0; + float means[] = new float[3]; + float ss[] = new float[3]; + + if(J3dDebug.devPhase) + if ( bhArr.length <= 1 ) { + // this is only here for debugging can be removed after testing + // to ensure that it never gets called + J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_1, + "constructTree - bhArr.length <= 1. Bad !!!\n"); + } + + computeMeansAndSumSquares(centerValues, centerValuesIndex, means, ss); + + splitAxis = findSplitAxis(ss); + + // an array of decision variables for storing the values of inside + // the right or left set for a particular element of bhArr. + // true if its in the left set, false if its in the right set + boolean leftOrRightSet[] = new boolean[bhArr.length]; + + if ( splitAxis == -1 ) { + // This is bad. Since we can't find a split axis, the best thing + // to do is to split the set in two sets; each with about the + // same number of elements. By doing this we can avoid constructing + // a skew tree. + + // split elements into half. + for ( i=0; i < bhArr.length; i++) { + if(leftSetCount > rightSetCount) { + rightSetCount++; + leftOrRightSet[i] = false; + } else { + leftSetCount++; + leftOrRightSet[i] = true; + } + } + } + else { + for ( i=0; i < bhArr.length; i++) { + // the split criterion, special multiple equals cases added + if ( centerValues[centerValuesIndex[i]][splitAxis] < + means[splitAxis]) { + + if(J3dDebug.devPhase) + J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4, + "Found a left element\n"); + leftSetCount++; + leftOrRightSet[i] = true; + } else if ( centerValues[centerValuesIndex[i]][splitAxis] > + means[splitAxis]) { + if(J3dDebug.devPhase) + J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4, + "Found a right element\n"); + rightSetCount++; + leftOrRightSet[i] = false; + } else { + if(J3dDebug.devPhase) + J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4, + "Found an equal element\n"); + if(leftSetCount > rightSetCount) { + rightSetCount++; + leftOrRightSet[i] = false; + } else { + leftSetCount++; + leftOrRightSet[i] = true; + } + } + } + } + + if(J3dDebug.devPhase) + J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_2, + "LeftSetCount " + leftSetCount + " RightSetCount "+ + rightSetCount + "\n"); + + + // Don't think that this guard is needed, but still like to have it. + // Just in case, bad means and the sum of squares might lead us into the guard. + if (leftSetCount == bhArr.length) { + if(J3dDebug.devPhase) + J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_1, + "Split Axis of = " + splitAxis + " didn't yield "+ + "any split among the objects ?\n"); + // split elements into half + rightSetCount = 0; + leftSetCount = 0; + for ( i=0; i < bhArr.length; i++) { + if(leftSetCount > rightSetCount) { + rightSetCount++; + leftOrRightSet[i] = false; + } else { + leftSetCount++; + leftOrRightSet[i] = true; + } + } + } else if (rightSetCount == bhArr.length) { + if(J3dDebug.devPhase) + J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_1, + "Split Axis of = " + splitAxis + " didn't yield "+ + "any split among the objects ?\n"); + // split elements into half + rightSetCount = 0; + leftSetCount = 0; + for ( i=0; i < bhArr.length; i++) { + if(leftSetCount > rightSetCount) { + rightSetCount++; + leftOrRightSet[i] = false; + } else { + leftSetCount++; + leftOrRightSet[i] = true; + } + } + } + + if(J3dDebug.devPhase) + if(J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4)) + // check to make sure that rightSet and leftSet sum to the + // number of elements in the original array. + if ( bhArr.length != (rightSetCount + leftSetCount) ) { + System.err.println("An error has occurred in spliting"); + } + + BHNode rightSet[] = new BHNode[rightSetCount]; + BHNode leftSet[] = new BHNode[leftSetCount]; + int centerValuesIndexR[] = new int[rightSetCount]; + int centerValuesIndexL[] = new int[leftSetCount]; + + rightSetCount = 0; + leftSetCount = 0; + + for (i=0; i < bhArr.length; i++) { + if ( leftOrRightSet[i] ) { // element in left set + leftSet[leftSetCount] = bhArr[i]; + centerValuesIndexL[leftSetCount] = centerValuesIndex[i]; + leftSetCount++; + } else { + rightSet[rightSetCount] = bhArr[i]; + centerValuesIndexR[rightSetCount] = centerValuesIndex[i]; + rightSetCount++; + } + } + + if (rightSet.length != 1) { + parent.rChild = new BHInternalNode(); + parent.rChild.setParent(parent); + constructTree((BHInternalNode)(parent.rChild), rightSet, centerValues, + centerValuesIndexR); + } else { + parent.rChild = rightSet[0]; + parent.rChild.setParent(parent); + } + + if (leftSet.length != 1) { + parent.lChild = new BHInternalNode(); + parent.lChild.setParent(parent); + constructTree((BHInternalNode)(parent.lChild), leftSet, centerValues, + centerValuesIndexL); + } else { + parent.lChild = leftSet[0]; + parent.lChild.setParent(parent); + } + + parent.combineBHull(parent.rChild, parent.lChild); + } + + + void reConstructTree(int numOfLeaf) { + if(root == null) + return; + + BHNode bhArr[] = new BHNode[numOfLeaf]; + int index[] = new int[1]; + index[0] = 0; + root.destroyTree(bhArr, index); + + /* + if(bhArr.length != index[0]) + System.err.println("BHTree - This isn't right!!! - bhArr.length " + + bhArr.length + " index " + index[0]); + */ + + create(bhArr); + + } + + void gatherTreeStatistics() { + + int leafCount = root.countNumberOfLeaves(); + int internalCount = root.countNumberOfInternals(); + int maxDepth = root.computeMaxDepth(0); + float averageDepth = root.computeAverageLeafDepth ( leafCount, 0); + + + System.err.println("Statistics for tree = " + this); + System.err.println("Total Number of nodes in tree = " + + (leafCount + internalCount) ); + System.err.println("Number of Leaf Nodes = " + leafCount ); + System.err.println("Number of Internal Nodes = " + internalCount ); + System.err.println("Maximum Leaf depth = " + maxDepth ); + System.err.println("Average Leaf depth = " + averageDepth ); + System.err.println("root.bHull = " + root.bHull); + // printTree(root); + + } + + + void printTree(BHNode bh) { + if(bh!= null) { + if(bh.nodeType == BHNode.BH_TYPE_INTERNAL) { + System.err.println("BH_TYPE_INTERNAL - bHull : " + bh); + System.err.println(bh.bHull); + System.err.println("rChild : " + ((BHInternalNode)bh).rChild + + " lChild : " + ((BHInternalNode)bh).lChild); + printTree(((BHInternalNode)bh).rChild); + printTree(((BHInternalNode)bh).lChild); + } + else if(bh.nodeType == BHNode.BH_TYPE_LEAF) { + System.err.println("BH_TYPE_LEAF - bHull : " + bh); + System.err.println(bh.bHull); + } + + } + + + } +} + + + + + + -- cgit v1.2.3