hnsrtreefileobj.cc

R 树

		node = stack.getTopNode();
		cursor = stack.getCursor();

		node.setCoreAt(core, cursor);
		node.setBoundingRectAt(rect, cursor);

		core = node.getCore();
		rect = node.getBoundingRect();

		writeNode(node);
		stack.pop();
	}
}

void
HnSRTreeFileObj::reinsertLeaf(HnSRTreeStack &stack,
			      const HnPoint &newPoint, const HnData &newData)
{
	HnSRTreeLeaf leaf, newLeaf;
	HnPointArray points;
	int i;
	ReinsertFlag *flags;

	leaf = stack.getTopLeaf();

	points = new_HnPointArray();
	for(i=0; i<leaf.getCount(); i++)
		points.append(leaf.getPointAt(i));
	points.append(newPoint);

	selectPoints(points, &flags);

	newLeaf = new_HnSRTreeLeaf(dimension, dataSize, 
				   blockSize, leaf.getOffset());

	for(i=0; i<leaf.getCount(); i++) {
		HnPoint point = leaf.getPointAt(i);
		HnData data = leaf.getDataAt(i);

		switch(flags[i]) {
		case STAY:
			newLeaf.append(point, data);
			break;
		case REINSERT:
			reinsertList.append(new_HnSRTreeReinsert(point, data));
			break;
		default:
			HnAbort("reinsert flag is incorrectly assigned.");
		}
	}
	switch(flags[i]) {
	case STAY:
		newLeaf.append(newPoint, newData);
		break;
	case REINSERT:
		reinsertList.append(new_HnSRTreeReinsert(newPoint, newData));
		break;
	default:
		HnAbort("reinsert flag is incorrectly assigned.");
	}

	writeLeaf(newLeaf);

	/* replace leaf with newLeaf in the stack */
	stack.pop();
	stack.push(newLeaf);

	updateCoreAndRect(stack);
}

void
HnSRTreeFileObj::selectPoints(const HnPointArray &points,
			      ReinsertFlag **flags_return)
{
	static ReinsertFlag *flags = NULL;
	int numPoints = points.length();
	int reinsertCount = numPoints * reinsertFactor / 100;
	HnPoint center;
	int i, j, axis;
	double *distances = new double[numPoints];
	int *array = new int[numPoints];

	/* initialize flags */
	if(flags != NULL)
		delete flags;
	flags = new ReinsertFlag[numPoints];

	for(i=0; i<numPoints; i++)
		flags[i] = REINSERT_NONE;

	/* calculate center */
	center = new_HnPoint(dimension);

	for(axis=0; axis<dimension; axis++) {
		double sum = 0;

		for(i=0; i<numPoints; i++)
			sum += points[i].getCoord(axis);

		center.setCoord(sum / numPoints, axis);
	}

	/* initialize array */
	for(i=0; i<numPoints; i++) {
		distances[i] = points[i].getDistance(center);
		array[i] = i;
	}

	/* sort points by distance in descent order */
	for(i=0; i<numPoints; i++) {
		for(j=i+1; j<numPoints; j++) {
			if(distances[array[i]] < distances[array[j]]) {
				int temp = array[i];
				array[i] = array[j];
				array[j] = temp;
			}
		}
	}

	/* make reinsert flags */
	i=0;
	while(i<reinsertCount) {
		flags[array[i]] = REINSERT;
		i++;
	}
	while(i<numPoints) {
		flags[array[i]] = STAY;
		i++;
	}

	if(debug) {
		fprintf(stderr, "HnSRTreeFileObj::selectPoints:\n");
		fprintf(stderr, "    REINSERT\n");
		for(i=0; i<numPoints; i++) {
			if(flags[i] == REINSERT)
				fprintf(stderr,
					"    points[%d].getDistance(center) "
					"= %g\n",
					i, points[i].getDistance(center));
		}
		fprintf(stderr, "    STAY\n");
		for(i=0; i<numPoints; i++) {
			if(flags[i] == STAY)
				fprintf(stderr,
					"    points[%d].getDistance(center) "
					"= %g\n",
					i, points[i].getDistance(center));
		}
	}

	*flags_return = flags;

	delete distances;
	delete array;
}

void
HnSRTreeFileObj::reinsertNode(HnSRTreeStack &stack,
			      const HnSRTreeCore &newCore,
			      const HnRect &newRect, off_t newOffset)
{
	HnSRTreeNode node, newNode;
	HnSRTreeCoreArray cores;
	int i, level;
	ReinsertFlag *flags;

	node = stack.getTopNode();
	level = height - stack.getDepth();

	cores = new_HnSRTreeCoreArray();
	for(i=0; i<node.getCount(); i++)
		cores.append(node.getCoreAt(i));
	cores.append(newCore);

	selectCores(cores, &flags);

	newNode = new_HnSRTreeNode(dimension, blockSize, node.getOffset());

	for(i=0; i<node.getCount(); i++) {
		HnSRTreeCore core = node.getCoreAt(i);
		HnRect rect = node.getRectAt(i);
		off_t offset = node.getOffsetAt(i);

		switch(flags[i]) {
		case STAY:
			newNode.append(core, rect, offset);
			break;
		case REINSERT:
			reinsertList.append(new_HnSRTreeReinsert(offset,
								 level));
			break;
		default:
			HnAbort("reinsert flag is incorrectly assigned.");
		}
	}
	switch(flags[i]) {
	case STAY:
		newNode.append(newCore, newRect, newOffset);
		break;
	case REINSERT:
		reinsertList.append(new_HnSRTreeReinsert(newOffset, level));
		break;
	default:
		HnAbort("reinsert flag is incorrectly assigned.");
	}

	writeNode(newNode);

	/* replace node with newNode in the stack */
	stack.pop();
	stack.push(newNode);

	updateCoreAndRect(stack);
}

void
HnSRTreeFileObj::selectCores(const HnSRTreeCoreArray &cores,
			     ReinsertFlag **flags_return)
{
	static ReinsertFlag *flags = NULL;
	int numCores = cores.length();
	int reinsertCount = numCores * reinsertFactor / 100;
	HnPoint center;
	int i, j, axis;
	double *distances = new double[numCores];
	int *array = new int[numCores];

	/* initialize flags */
	if(flags != NULL)
		delete flags;
	flags = new ReinsertFlag[numCores];

	for(i=0; i<numCores; i++)
		flags[i] = REINSERT_NONE;

	/* calculate center */
	center = new_HnPoint(dimension);

	for(axis=0; axis<dimension; axis++) {
		double sum = 0;
		int total = 0;

		for(i=0; i<numCores; i++) {
			double coord = cores[i].getCenter().getCoord(axis);
			int weight = cores[i].getWeight();

			sum += coord * weight;
			total += weight;
		}

		center.setCoord(sum / total, axis);
	}

	/* initialize array */
	for(i=0; i<numCores; i++) {
		distances[i] = cores[i].getCenter().getDistance(center);
		array[i] = i;
	}

	/* sort cores by distance in descent order */
	for(i=0; i<numCores; i++) {
		for(j=i+1; j<numCores; j++) {
			if(distances[array[i]] < distances[array[j]]) {
				int temp = array[i];
				array[i] = array[j];
				array[j] = temp;
			}
		}
	}

	/* make reinsert flags */
	i=0;
	while(i<reinsertCount) {
		flags[array[i]] = REINSERT;
		i++;
	}
	while(i<numCores) {
		flags[array[i]] = STAY;
		i++;
	}

	if(debug) {
		fprintf(stderr, "HnSRTreeFileObj::selectCores:\n");
		fprintf(stderr, "    REINSERT\n");
		for(i=0; i<numCores; i++) {
			if(flags[i] == REINSERT)
				fprintf(stderr,
					"    cores[%d].getCenter()."
					"getDistance(center) = %g\n",
					i, cores[i].getCenter().
					getDistance(center));
		}
		fprintf(stderr, "    STAY\n");
		for(i=0; i<numCores; i++) {
			if(flags[i] == STAY)
				fprintf(stderr,
					"    cores[%d].getCenter()."
					"getDistance(center) = %g\n",
					i, cores[i].getCenter().
					getDistance(center));
		}
	}

	*flags_return = flags;

	delete distances;
	delete array;
}

void
HnSRTreeFileObj::splitLeaf(HnSRTreeStack &stack,
			   const HnPoint &newPoint, const HnData &newData)
{
	HnSRTreeLeaf leaf, left, right;
	int i;
	HnPointArray points;
	SplitFlag *flags;

	leaf = stack.getTopLeaf();

	if(debug) {
		fprintf(stderr, "HnSRTreeFileObj::splitLeaf: leaf = %s\n",
			(char *)leaf.toString());
	}

	/* put points into an array */
	points = new_HnPointArray();
	for(i=0; i<leaf.getCount(); i++)
		points.append(leaf.getPointAt(i));
	points.append(newPoint);

	/* split points */
	splitPoints(points, &flags);

	/* put points into the left and right leaves */
	left = new_HnSRTreeLeaf(dimension, dataSize,
				blockSize, leaf.getOffset());
	right = allocateLeaf();

	for(i=0; i<leaf.getCount(); i++) {
		switch(flags[i]) {
		case LEFT:
			left.append(leaf.getPointAt(i),	leaf.getDataAt(i));
			break;
		case RIGHT:
			right.append(leaf.getPointAt(i), leaf.getDataAt(i));
			break;
		default:
			HnAbort("split flag is incorrectly assigned.");
		}
	}
	switch(flags[i]) {
	case LEFT:
		left.append(newPoint, newData);
		break;
	case RIGHT:
		right.append(newPoint, newData);
		break;
	default:
		HnAbort("split flag is incorrectly assigned.");
	}

	if(debug) {
		fprintf(stderr, "HnSRTreeFileObj::splitLeaf: left  = %s\n",
			(char *)left.toString());
		fprintf(stderr, "HnSRTreeFileObj::splitLeaf: right = %s\n",
			(char *)right.toString());
	}

	writeLeaf(left);
	writeLeaf(right);

	stack.pop();

	updateNode(stack,
		   left.getCore(),
		   left.getBoundingRect(), left.getOffset(),
		   right.getCore(), 
		   right.getBoundingRect(), right.getOffset());
}

void
HnSRTreeFileObj::splitNode(HnSRTreeStack &stack,
			   const HnSRTreeCore &newCore, 
			   const HnRect &newRect, off_t newOffset)
{
	HnSRTreeNode node, left, right;
	int i;
	HnSRTreeCoreArray cores;
	SplitFlag *flags;

	node = stack.getTopNode();

	if(debug) {
		fprintf(stderr, "HnSRTreeFileObj::splitNode: node = %s\n",
			(char *)node.toString());
	}

	/* put cores into an array */
	cores = new_HnSRTreeCoreArray();
	for(i=0; i<node.getCount(); i++)
		cores.append(node.getCoreAt(i));
	cores.append(newCore);

	/* split cores */
	splitCores(cores, &flags);

	/* put cores and rects into the left and right nodes */
	left = new_HnSRTreeNode(dimension, blockSize, node.getOffset());
	right = allocateNode();

	for(i=0; i<node.getCount(); i++) {
		switch(flags[i]) {
		case LEFT:
			left.append(node.getCoreAt(i),
				    node.getRectAt(i), node.getOffsetAt(i));
			break;
		case RIGHT:
			right.append(node.getCoreAt(i),
				     node.getRectAt(i), node.getOffsetAt(i));
			break;
		default:
			HnAbort("split flag is incorrectly assigned.");
		}
	}
	switch(flags[i]) {
	case LEFT:
		left.append(newCore, newRect, newOffset);
		break;
	case RIGHT:
		right.append(newCore, newRect, newOffset);
		break;
	default:
		HnAbort("split flag is incorrectly assigned.");
	}

	if(debug) {
		fprintf(stderr, "HnSRTreeFileObj::splitNode: left  = %s\n",
			(char *)left.toString());
		fprintf(stderr, "HnSRTreeFileObj::splitNode: right = %s\n",
			(char *)right.toString());
	}

	writeNode(left);
	writeNode(right);

	stack.pop();

	updateNode(stack,
		   left.getCore(),
		   left.getBoundingRect(), left.getOffset(),
		   right.getCore(),
		   right.getBoundingRect(), right.getOffset());
}

void
HnSRTreeFileObj::updateNode(HnSRTreeStack &stack,
			    const HnSRTreeCore &leftCore,
			    const HnRect &leftRect, off_t leftOffset,
			    const HnSRTreeCore &rightCore,
			    const HnRect &rightRect, off_t rightOffset)
{
	HnSRTreeNode node;
	int cursor;

	if(stack.getDepth() == 0)
		extendTree(leftCore, leftRect, leftOffset,
			   rightCore, rightRect, rightOffset);
	else {
		node = stack.getTopNode();
		cursor = stack.getCursor();

		node.setElementAt(leftCore, leftRect, leftOffset, cursor);

		if(node.isFull()) {
			int index = -1;

			if(stack.getDepth() != 1 &&
			   (index =
                            reinsertedBlocks.indexOf(node.getOffset())) < 0) {
				reinsertedBlocks.append(node.getOffset());
				reinsertNode(stack,
					     rightCore,
					     rightRect, rightOffset);
			}
			else {
				if(index >= 0)
					reinsertedBlocks.remove(index);
				splitNode(stack,
					  rightCore, rightRect, rightOffset);
			}
		}
		else {
			node.append(rightCore, rightRect, rightOffset);

			writeNode(node);
			updateCoreAndRect(stack);
		}
	}
}

void
HnSRTreeFileObj::extendTree(const HnSRTreeCore &leftCore,
			    const HnRect &leftRect, off_t leftOffset,
			    const HnSRTreeCore &rightCore,
			    const HnRect &rightRect, off_t rightOffset)
{
	HnSRTreeNode node;

	node = allocateNode();
	node.append(leftCore, leftRect, leftOffset);
	node.append(rightCore, rightRect, rightOffset);
	writeNode(node);

	rootOffset = node.getOffset();
	height ++;
	writeSuperBlock();
}

/*
 * Split
 */

void
HnSRTreeFileObj::splitPoints(const HnPointArray &points,
			     SplitFlag **flags_return)
{
	static SplitFlag *flags = NULL;
	int numPoints = points.length();
	int minCount = numPoints * splitFactor / 100;
	int maxCount = numPoints - minCount;
	struct {
		int axis;
		double var;
	} max;
	struct {
		int count;
		double leftVar, rightVar;
	} min;
	int axis, count;
	int i, j;
	int *array = new int[numPoints];

	/* initialize flags */
	if(flags != NULL)
		delete flags;
	flags = new SplitFlag[numPoints];

	for(i=0; i<numPoints; i++)
		flags[i] = SPLIT_NONE;

	max.axis = -1;
	max.var = -1;

	/* calculate variance */
	for(axis=0; axis<dimension; axis++) {
		double avg, var;
		double sum = 0;
		double sum2 = 0;

		for(i=0; i<numPoints; i++) {
			double coord = points[i].getCoord(axis);
			sum += coord;
			sum2 += coord * coord;
		}

		avg = sum / numPoints;
		var = sum2 / numPoints - avg * avg;

		if(max.axis == -1) {
			max.axis = axis;
			max.var = var;
		}
		else {
			if(var > max.var) {
				max.axis = axis;
				max.var = var;
			}
		}
	}

	/* sort points */
	for(i=0; i<numPoints; i++)
		array[i] = i;

	for(i=0; i<numPoints; i++) {
		for(j=i+1; j<numPoints; j++) {
			double coord1 = points[array[i]].getCoord(max.axis);
			double coord2 = points[array[j]].getCoord(max.axis);

			if(coord1 > coord2) {
				int temp = array[i];
				array[i] = array[j];
				array[j] = temp;
			}
		}
	}

	/* choose split point */