hnsrtreefileobj.cc

R 树

}

double
HnSRTreeFileObj::getMinDistance(const HnPoint &point,
				const HnSRTreeCore &core, const HnRect &rect)
{
	double sphereDistance, rectDistance, minDistance;
	double distance, radius;

	/* sphere distance */
	distance = point.getDistance(core.getCenter());
	radius = core.getRadius();

	if(distance < radius)
		sphereDistance = 0;
	else
		sphereDistance = distance - radius;

	/* rect distance */
	rectDistance = rect.getMinDistance(point);

	/* compare distances */
	if(sphereDistance > rectDistance)
		minDistance = sphereDistance;
	else
		minDistance = rectDistance;

	return minDistance;
}

double
HnSRTreeFileObj::getMaxDistance(const HnPoint &point,
				const HnSRTreeCore &core, const HnRect &rect)
{
	double sphereDistance, rectDistance, maxDistance;

	sphereDistance =
		point.getDistance(core.getCenter()) + core.getRadius();

	rectDistance = rect.getMaxDistance(point);

	if(sphereDistance < rectDistance)
		maxDistance = sphereDistance;
	else
		maxDistance = rectDistance;

	return maxDistance;
}

HnSRTreeNeighborArray
HnSRTreeFileObj::chooseNeighbors(off_t offset,
				 const HnPoint &point, int maxCount,
				 const HnSRTreeNeighborArray &neighbors)
{
	HnSRTreeBlock block = readBlock(offset);

	if(block.isNode()) {
		return chooseNeighborsInNode(block, point, maxCount,
					     neighbors);
	}
	else if(block.isLeaf()) {
		return chooseNeighborsInLeaf(block, point, maxCount,
					     neighbors);
	}
	else
		HnAbort("unexpected block type.");
}

HnSRTreeNeighborArray
HnSRTreeFileObj::chooseNeighborsInNode(const HnSRTreeBlock &block,
				       const HnPoint &point, int maxCount,
				       HnSRTreeNeighborArray neighbors)
{
	HnSRTreeNode node = new_HnSRTreeNode(dimension, block);
	int numRects = node.getCount();
	int i, j;
	struct Entry {
		int index;
		double minDistance;
		double maxDistance;
	} *array = new Entry[numRects], temp;
		
	/* initialize array */
	for(i=0; i<numRects; i++) {
		array[i].index = i;
		array[i].minDistance =
			getMinDistance(point,
				       node.getCoreAt(i), node.getRectAt(i));
		array[i].maxDistance =
			getMaxDistance(point,
				       node.getCoreAt(i), node.getRectAt(i));
	}

	/* sort array */
	for(i=0; i<numRects; i++) {
		for(j=i+1; j<numRects; j++) {
			if(array[i].minDistance > array[j].minDistance ||
			   ((array[i].minDistance == array[j].minDistance) &&
			    (array[i].maxDistance > array[j].maxDistance))) {
				temp = array[i];
				array[i] = array[j];
				array[j] = temp;
			}
		}
	}

	if(debug) {
		fprintf(stderr, "HnSRTreeFileObj::chooseNeighborsInNode: "
			"sorted rectangles\n");
		for(i=0; i<numRects; i++) {
			HnRect rect = node.getRectAt(array[i].index);
			fprintf(stderr,
				"    %2d: cnt = %7.6f, "
				"min = %7.6f, max = %7.6f, inc = %s\n",
				i, point.getDistance(rect.getCenterPoint()),
				array[i].minDistance, array[i].maxDistance,
				(rect.includes(point) ? "yes" : "no"));
		}
	}

	for(i=0; i<numRects; i++) {
		off_t offset = node.getOffsetAt(array[i].index);
		double minDistance = array[i].minDistance;

		if(neighbors.length() < maxCount) {
			/*
			 * If the number of neighbors does not reach the max,
			 * try every children to collect neighbors.
			 */
			neighbors = chooseNeighbors(offset, point, maxCount,
						    neighbors);
		}
		else {
			/*
			 * If the number of neighbors reaches the max,
			 * try rectangles which overlap with the current
			 * searching rectangle.
			 *
			 * The searching rectangle is defined as follows:
			 *	(1) It is a cube.
			 *	(2) Its center point is a target point.
			 *	(3) The width of sides is twice of the
			 *	    distance of the farthest neighbor.
			 */

			HnSRTreeNeighbor farthest;
			double farthestDistance;

			/*
			 * NOTE:
			 *	`neighbors' are assumed to be sorted.
			 */

			farthest = neighbors[neighbors.length() - 1];
			farthestDistance = farthest.getDistance();

			if(minDistance <= farthestDistance) {
				neighbors = chooseNeighbors(offset,
							    point, maxCount,
							    neighbors);
			}
		}
	}

	delete array;

	return neighbors;
}

HnSRTreeNeighborArray
HnSRTreeFileObj::chooseNeighborsInLeaf(const HnSRTreeBlock &block,
				       const HnPoint &point, int maxCount,
				       const HnSRTreeNeighborArray &neighbors)
{
	HnSRTreeLeaf leaf = new_HnSRTreeLeaf(dimension, dataSize, block);
	int numRects = leaf.getCount();
	HnSRTreeNeighborArray array, sorted;
	int i, count;

	/* add rectangles in the leaf */
	array = new_HnSRTreeNeighborArray(neighbors);

	for(i=0; i<numRects; i++) {
		HnPoint key = leaf.getPointAt(i);
		HnData value = leaf.getDataAt(i);
		double distance = point.getDistance(key);

		array.append(new_HnSRTreeNeighbor(key, value, distance));
	}

	sorted = HnSRTreeNeighbor::sort(array);

	/* select closer rectangles up to the max count */
	array = new_HnSRTreeNeighborArray();

	for(count = 0; count < sorted.length(); count ++) {
		if(count >= maxCount) {
			/*
			 * NOTE:
			 *	Even if the count is greater than the max,
			 *	rectangles that have the same distance
			 *	need to be appended together.
			 */

			double lastDistance = sorted[count - 1].getDistance();
			double nextDistance = sorted[count    ].getDistance();

			if(lastDistance != nextDistance)
				break;
		}

		array.append(sorted[count]);
	}

	if(debug) {
		fprintf(stderr, "HnSRTreeFileObj::getNeighborsInLeaf: \n");
		for(i=0; i<neighbors.length(); i++) {
			fprintf(stderr, "    neighbors[%d] = %s\n",
				i, (char *)array[i].toString());
		}
	}

	return array;
}

/*
 * Check
 */

void
HnSRTreeFileObj::check(void)
{
	checkBlock(HnSRTreeCore::null, HnRect::null, rootOffset);
	checkInclusion(rootOffset);
}

int
HnSRTreeFileObj::checkBlock(const HnSRTreeCore &core, 
			    const HnRect &rect, off_t offset)
{
	HnSRTreeBlock block;
	HnSRTreeNode node;
	HnSRTreeLeaf leaf;
	int i, code, level = -1;

	block = readBlock(offset);

	if(block.isNode()) {
		node = new_HnSRTreeNode(dimension, block);

		if(core != HnSRTreeCore::null) {
			if(!node.getCore().equals(core))
				HnAbort("mismatch in core %s and %s.",
					(char *)
					node.getCore().toString(),
					(char *)core.toString());
		}

		if(rect.isValid()) {
			if(!node.getBoundingRect().equals(rect))
				HnAbort("mismatch in bounding rect %s and %s.",
					(char *)
					node.getBoundingRect().toString(),
					(char *)rect.toString());
		}

		for(i=0; i<node.getCount(); i++) {
			code = checkBlock(node.getCoreAt(i),
					  node.getRectAt(i),
					  node.getOffsetAt(i));
			if(i == 0)
				level = code;
			else {
				if(code != level)
					HnAbort("the tree is not balanced at "
						"a node %08X.",	(int)offset);
			}
		}
	}
	else if(block.isLeaf()) {
		leaf = new_HnSRTreeLeaf(dimension, dataSize, block);

		if(core.isValid()) {
			if(!leaf.getCore().equals(core))
				HnAbort("mismatch in core %s and %s.",
					(char *)
					leaf.getCore().toString(),
					(char *)core.toString());
		}

		if(rect.isValid()) {
			if(!leaf.getBoundingRect().equals(rect))
				HnAbort("mismatch in bounding rect %s and %s.",
					(char *)
					leaf.getBoundingRect().toString(),
					(char *)rect.toString());
		}
	}
	else
		HnAbort("unexpected block type.");
		

	/*
	 * The `level' variable is used to confirm that the tree is balanced.
	 */

	return level + 1;
}

HnPointArray
HnSRTreeFileObj::checkInclusion(off_t offset)
{
	HnSRTreeBlock block;
	HnPointArray sum = new_HnPointArray();

	block = readBlock(offset);

	if(block.isNode()) {
		HnSRTreeNode node = new_HnSRTreeNode(dimension, block);
		int i, j;

		for(i=0; i<node.getCount(); i++) {
			HnPointArray points =
				checkInclusion(node.getOffsetAt(i));
			HnPoint center = node.getCoreAt(i).getCenter();
			double radius = node.getCoreAt(i).getRadius();

			for(j=0; j<points.length(); j++) {
				double distance;

				distance = points[j].getDistance(center);
				
				if(distance > radius) {
					describeExclusion(node.getOffsetAt(i),
							  center);
					HnAbort("point (%s) is not included "
						"in the core (center = %s, "
						"raidus = %g) of the node %08X"
						" when the distance is %g.",
						(char *)points[j].toString(),
						(char *)center.toString(),
						radius, (int)offset, distance);
				}
			}

			sum.append(points);
		}
	}
	else if(block.isLeaf()) {
		HnSRTreeLeaf leaf =
			new_HnSRTreeLeaf(dimension, dataSize, block);
		int i;

		for(i=0; i<leaf.getCount(); i++)
			sum.append(leaf.getPointAt(i));
	}
	else
		HnAbort("unexpected block type.");

	return sum;
}

void
HnSRTreeFileObj::describeExclusion(off_t offset, const HnPoint &center)
{
	HnSRTreeBlock block = readBlock(offset);

	if(block.isNode()) {
		HnSRTreeNode node = new_HnSRTreeNode(dimension, block);
		int i;

		for(i=0; i<node.getCount(); i++) {
			HnSRTreeCore core = node.getCoreAt(i);
			HnRect rect = node.getRectAt(i);
			double sphereDistance, rectDistance;

			sphereDistance = 
				core.getCenter().getDistance(center)
					+ core.getRadius();

			rectDistance = rect.getMaxDistance(center);
			
			printf("    %2d: core = %s, rect = %s, "
			       "sphereDistance = %g, rectDistance = %g\n",
			       i, (char *)core.toString(),
			       (char *)rect.toString(),
			       sphereDistance, rectDistance);
		}
	}
	else if(block.isLeaf()) {
		HnSRTreeLeaf leaf =
			new_HnSRTreeLeaf(dimension, dataSize, block);
		int i;

		for(i=0; i<leaf.getCount(); i++) {
			HnPoint point = leaf.getPointAt(i);
			double distance = point.getDistance(center);

			printf("    %2d: point = %s, distance = %g\n",
			       i, (char *)point.toString(), distance);
		}
	}
	else
		HnAbort("unexpected block type.");
}

/*
 * Print
 */

void
HnSRTreeFileObj::print(void)
{
	class Statistics {
	private:
		double min;
		double max;
		double sum;
		int count;

	public:
		Statistics(void) {
			min = 0;
			max = 0;
			sum = 0;
			count = 0;
		}
		void add(double utility) {
			if(count == 0) {
				min = utility;
				max = utility;
			}
			else {
				if(utility < min)
					min = utility;
				if(utility > max)
					max = utility;
			}
			sum += utility;
			count ++;
		}
		double getMin(void) const {
			return min;
		}
		double getMax(void) const {
			return max;
		}
		double getAverage(void) const {
			return (double)sum / count;
		}
	};

	Statistics blockUtility, rootUtility, nodeUtility, leafUtility;

	off_t offset, size;
	double utility;
	int numNodes, numLeaves, numPoints, numFreeBlocks;

	readSuperBlock();

	fseek(fp, 0, SEEK_END);
	size = ftell(fp);

	numNodes = 0;
	numLeaves = 0;
	numPoints = 0;
	numFreeBlocks = 0;

	for(offset = blockSize; offset < size; offset += blockSize) {
		HnSRTreeBlock block = readBlock(offset);

		if(block.isNode()) {
			HnSRTreeNode node = new_HnSRTreeNode(dimension, block);

			printNode(node);

			utility = (double)node.getSize() / blockSize;

			blockUtility.add(utility);
			if(offset == rootOffset)
				rootUtility.add(utility);
			else
				nodeUtility.add(utility);

			numNodes ++;
		}
		else if(block.isLeaf()) {
			HnSRTreeLeaf leaf =
				new_HnSRTreeLeaf(dimension, dataSize, block);

			printLeaf(leaf);

			utility = (double)leaf.getSize() / blockSize;

			blockUtility.add(utility);
			leafUtility.add(utility);

			numLeaves ++;
			numPoints += leaf.getCount();
		}
		else if(block.isFree())
			numFreeBlocks ++;
		else
			HnAbort("unexpected block type.");
	}

	printf("SuperBlock\n");
	printf("    dimension     : %d\n", dimension);
	printf("    dataSize      : %d\n", dataSize);
	printf("    blockSize     : %d\n", blockSize);
	printf("    fileSize      : %d\n", fileSize);
	printf("    freeOffset    : 0x%08X\n", (unsigned int)freeOffset);
	printf("    rootOffset    : 0x%08X\n", (unsigned int)rootOffset);
	printf("    height        : %d\n", height);
	printf("    splitFactor   : %d\n", splitFactor);
	printf("    reinsertFactor: %d\n", reinsertFactor);

	printf("File Size is 0x%08X\n", (unsigned int)size);

	printf("Block utility      : "
	       "avg %8.5f %%, min %8.5f %%, max %8.5f %%\n",
	       blockUtility.getAverage() * 100,
	       blockUtility.getMin() * 100,
	       blockUtility.getMax() * 100);

	printf("Root block utility : "
	       "    %8.5f %%\n",
	       rootUtility.getAverage() * 100);

	printf("Node block utility : "
	       "avg %8.5f %%, min %8.5f %%, max %8.5f %%\n",
	       nodeUtility.getAverage() * 100,
	       nodeUtility.getMin() * 100,
	       nodeUtility.getMax() * 100);

	printf("Leaf block utility : "
	       "avg %8.5f %%, min %8.5f %%, max %8.5f %%\n",
	       leafUtility.getAverage() * 100,
	       leafUtility.getMin() * 100,
	       leafUtility.getMax() * 100);

	printf("Number of nodes : %d\n", numNodes);
	printf("Number of leaves: %d\n", numLeaves);
	printf("Number of free blocks: %d\n", numFreeBlocks);
	printf("Number of leaf points: %d\n", numPoints);
}

void
HnSRTreeFileObj::printNode(const HnSRTreeNode &node)
{
	int i;
	HnRectArray rects;

	printf("Block (0x%08X)\n",
	       (unsigned int)node.getOffset());
	printf("    type       : NODE\n");
	printf("    count      : %d\n", node.getCount());
	printf("    utility    : %d (%g %%)\n",
	       (int)node.getSize(), 
	       (double)node.getSize() / blockSize * 100);

	/* children */
	for(i=0; i<node.getCount(); i++) {
		printf("    %5d: core = %s, rect = %s, offset = 0x%08X\n",
		       i,
		       (char *)node.getCoreAt(i).toString(),
		       (char *)node.getRectAt(i).toString(),
		       (unsigned int)node.getOffsetAt(i));
	}
}

void
HnSRTreeFileObj::printLeaf(const HnSRTreeLeaf &leaf)
{
	int i;

	printf("Block (0x%08X)\n",
	       (unsigned int)leaf.getOffset());
	printf("    type    : LEAF\n");
	printf("    count   : %d\n", leaf.getCount());
	printf("    utility : %d (%g %%)\n",
	       (int)leaf.getSize(),
	       (double)leaf.getSize() / blockSize * 100);

	for(i=0; i<leaf.getCount(); i++) {
		printf("    %5d: %s\n", i,
		       (char *)leaf.getPointAt(i).toString());
	}
}

void
HnSRTreeFileObj::setDebug(HnBool flag)
{
	debug = flag;
}