hnsrtreefileobj.cc

R 树

	HnSRTreeNode node;
	int cursor, maxCount, minCount;
	int level;
	HnBool underflow;
	HnSRTreeCore core;
	HnRect rect;
	int i;

	/* search point */
	if((stack = searchPoint(point, data)) == HnSRTreeStack::null)
		HnAbort("the given point/data pair is not found in the tree.");

	if(debug) {
		fprintf(stderr, "HnSRTreeFile::remove: point is found.\n");
	}

	/* remove point */
	leaf = stack.getTopLeaf();
	cursor = stack.getCursor();
	stack.pop();

	leaf.remove(cursor);
	
	if(stack.getDepth() == 0) {
		writeLeaf(leaf);

		if(debug) {
			fprintf(stderr,	"HnSRTreeFile::remove: "
				"removal is finished.\n");
		}

		return;
	}

	/* condense tree */
	reinsertList = new_HnSRTreeReinsertArray();
	reinsertedBlocks = new_HnSRTreeOffsetArray();

	maxCount = HnSRTreeLeaf::getMaxCount(dimension, dataSize, blockSize);
	minCount = maxCount * splitFactor / 100;
	underflow = (leaf.getCount() < minCount);

	if(underflow) {
		if(debug) {
			fprintf(stderr, "HnSRTreeFile::remove: "
				"underflow (count: %d, minCount: %d) "
				"occurred in the leaf (offset: 0x%08X).\n",
				leaf.getCount(), minCount,
				(int)leaf.getOffset());
		}

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

			reinsertList.append(new_HnSRTreeReinsert(leafPoint,
								 leafData));
		}
		releaseBlock(leaf.getOffset());
	}
	else {
		writeLeaf(leaf);
		core = leaf.getCore();
		rect = leaf.getBoundingRect();
	}

	/* intermediate nodes */
	while(stack.getDepth() > 1) {
		node = stack.getTopNode();
		cursor = stack.getCursor();
		level = height - stack.getDepth();
		stack.pop();

		if(underflow) {
			node.remove(cursor);

			maxCount = HnSRTreeNode::getMaxCount(dimension,
							     blockSize);
			minCount = maxCount * splitFactor / 100;
			underflow = (node.getCount() < minCount);

			if(underflow) {
				if(debug) {
					fprintf(stderr,
						"HnSRTreeFile::remove: "
						"underflow (count: %d, "
						"minCount: %d) "
						"occurred in the node "
						"(offset: 0x%08X, "
						"level: %d).\n",
						node.getCount(), minCount,
						(int)node.getOffset(), level);
				}

				for(i=0; i<node.getCount(); i++) {
					off_t offset = node.getOffsetAt(i);
					HnSRTreeReinsert reinsert;

					reinsert =
						new_HnSRTreeReinsert(offset,
								     level);
					reinsertList.append(reinsert);
				}
				releaseBlock(node.getOffset());
			}
			else {
				writeNode(node);
				core = node.getCore();
				rect = node.getBoundingRect();
			}
		}
		else {
			node.setCoreAt(core, cursor);
			node.setBoundingRectAt(rect, cursor);

			writeNode(node);
			core = node.getCore();
			rect = node.getBoundingRect();
		}
	}
		
	/* root node */
	node = stack.getTopNode();
	cursor = stack.getCursor();
	level = height - stack.getDepth();
	stack.pop();

	if(underflow) {
		node.remove(cursor);

		if(node.getCount() == 1) {
			if(debug) {
				fprintf(stderr, "HnSRTreeFile::remove: "
					"tree is shrunken.\n");
			}

			releaseBlock(node.getOffset());
			rootOffset = node.getOffsetAt(0);
			height --;

			writeSuperBlock();
		}
		else
			writeNode(node);
	}
	else {
		node.setCoreAt(core, cursor);
		node.setBoundingRectAt(rect, cursor);

		writeNode(node);
	}

	/* reinsert orphaned entries */
	while(reinsertList.length() != 0) {
		if(reinsertList[0].getType() == HnSRTreeReinsert::POINT) {
			HnPoint point = reinsertList[0].getPoint();
			HnData data = reinsertList[0].getData();

			if(debug) {
				fprintf(stderr, "HnSRTreeFile::remove: "
					"reinserting point %s.\n",
					(char *)point.toString());
			}

			reinsertList.remove(0);
			insertPoint(point, data);
		}
		else {
			off_t offset = reinsertList[0].getOffset();
			int level = reinsertList[0].getLevel();

			if(debug) {
				fprintf(stderr, "HnSRTreeFile::remove: "
					"reinserting block 0x%08X "
					"at the level %d.\n",
					(int)offset, level);
			}

			reinsertList.remove(0);
			insertBlock(offset, level);
		}
	}

	if(debug) {
		fprintf(stderr,
			"HnSRTreeFile::remove: removal is finished.\n");
	}

	if(debug)
		check();
}

HnSRTreeStack
HnSRTreeFileObj::searchPoint(const HnPoint &point, const HnData &data)
{
	HnSRTreeStack stack;
	HnSRTreeBlock block;
	HnSRTreeNode node;
	HnSRTreeLeaf leaf;
	HnBool found;

	stack = new_HnSRTreeStack();

	block = readBlock(rootOffset);
	if(block.isNode()) {
		node = new_HnSRTreeNode(dimension, block);
		stack.push(node);
	}
	else if(block.isLeaf()) {
		leaf = new_HnSRTreeLeaf(dimension, dataSize, block);
		stack.push(leaf);
	}
	else
		HnAbort("unexpected block type.");

	for(;;) {
		if(stack.isTopNode()) {
			node = stack.getTopNode();
		
			/*
			 * search for overlapping entries
			 */

			for(;;) {
				int cursor = stack.getCursor();
				HnRect rect = node.getRectAt(cursor);

				if(debug) {
					fprintf(stderr,
						"comparing with a rect"
						" #%d at a node %08X "
						"on the level %d.\n",
						cursor,
						(int)node.getOffset(),
						stack.getDepth() - 1);
				}

				if(rect.includes(point)) {
					found = HnTRUE;
					break;
				}

				if(!stack.hasMore()) {
					found = HnFALSE;
					break;
				}

				stack.advance();
			}

			if(found) {
				int cursor = stack.getCursor();
				block = readBlock(node.getOffsetAt(cursor));

				if(block.isNode()) {
					node = new_HnSRTreeNode(dimension,
								block);
					stack.push(node);
				}
				else if(block.isLeaf()) {
					leaf = new_HnSRTreeLeaf(dimension,
								dataSize,
								block);
					stack.push(leaf);
				}
				else
					HnAbort("unexpected block type.");
			}
			else {
				/*
				 * go up until the top node has some remaining
				 * entries or the stack is empty.
				 */

				for(;;) {
					stack.pop();

					if(stack.getDepth() == 0)
						return HnSRTreeStack::null;

					if(stack.hasMore())
						break;
				}

				stack.advance();
			}
		}
		else {
			leaf = stack.getTopLeaf();

			/*
			 * search for overlapping entries
			 */

			for(;;) {
				int cursor = stack.getCursor();
				HnPoint leafPoint = leaf.getPointAt(cursor);
				HnData leafData = leaf.getDataAt(cursor);

				if(debug) {
					fprintf(stderr,
						"comparing with "
						"a point #%d at "
						"a leaf %08X "
						"on the level %d.\n",
						cursor,
						(int)leaf.getOffset(),
						stack.getDepth() - 1);
				}

				if(leafPoint.equals(point) &&
				   leafData.equals(data)) {
					found = HnTRUE;
					break;
				}

				if(!stack.hasMore()) {
					found = HnFALSE;
					break;
				}

				stack.advance();
			}

			if(found)
				return stack;
			else {
				/*
				 * go up until the top node has some remaining
				 * entries or the stack is empty.
				 */

				for(;;) {
					stack.pop();

					if(stack.getDepth() == 0)
						return HnSRTreeStack::null;

					if(stack.hasMore())
						break;
				}

				stack.advance();
			}
		}
	}
}

/*
 * Sequential Access
 */

void
HnSRTreeFileObj::getFirst(HnPoint *point_return, HnData *data_return)
{
	getFirst(HnRect::null, point_return, data_return);
}

void
HnSRTreeFileObj::getFirst(const HnRect &rect,
			  HnPoint *point_return, HnData *data_return)
{
	HnSRTreeStack stack;

	context.stack = stack = new_HnSRTreeStack();
	context.rect = rect;

	getNext(point_return, data_return);
}

void
HnSRTreeFileObj::getNext(HnPoint *point_return, HnData *data_return)
{
	HnSRTreeStack &stack = context.stack;
	HnSRTreeBlock block;
	HnSRTreeNode node;
	HnSRTreeLeaf leaf;
	HnBool found;

	if(stack.getDepth() == 0) {
		/* initialize */
		block = readBlock(rootOffset);
		if(block.isNode()) {
			node = new_HnSRTreeNode(dimension, block);
			stack.push(node);
		}
		else if(block.isLeaf()) {
			leaf = new_HnSRTreeLeaf(dimension, dataSize, block);
			stack.push(leaf);
		}
		else
			HnAbort("unexpected block type.");
	}
	else {
		/* proceed */
		if(stack.hasMore())
			stack.advance();
		else {
			for(;;) {
				stack.pop();

				if(stack.getDepth() == 0) {
					*point_return = HnPoint::null;
					*data_return = HnData::null;
					return;
				}

				if(stack.hasMore())
					break;
			}

			stack.advance();
		}
	}

	for(;;) {
		if(stack.isTopNode()) {
			node = stack.getTopNode();
		
			/*
			 * search for overlapping entries
			 */

			if(context.rect.isInvalid())
				found = HnTRUE;
			else {
				for(;;) {
					int cursor = stack.getCursor();
					HnRect rect = node.getRectAt(cursor);

					if(debug) {
						fprintf(stderr,
							"comparing with a rect"
							" #%d at a node %08X "
							"on the level %d.\n",
							cursor,
							(int)node.getOffset(),
							stack.getDepth() - 1);
					}

					if(context.rect.overlaps(rect)) {
						found = HnTRUE;
						break;
					}

					if(!stack.hasMore()) {
						found = HnFALSE;
						break;
					}

					stack.advance();
				}
			}

			if(found) {
				int cursor = stack.getCursor();
				block = readBlock(node.getOffsetAt(cursor));

				if(block.isNode()) {
					node = new_HnSRTreeNode(dimension,
								block);
					stack.push(node);
				}
				else if(block.isLeaf()) {
					leaf = new_HnSRTreeLeaf(dimension,
								dataSize,
								block);
					stack.push(leaf);
				}
				else
					HnAbort("unexpected block type.");
			}
			else {
				/*
				 * go up until the top node has some remaining
				 * entries or the stack is empty.
				 */

				for(;;) {
					stack.pop();

					if(stack.getDepth() == 0) {
						*point_return = HnPoint::null;
						*data_return = HnData::null;
						return;
					}

					if(stack.hasMore())
						break;
				}

				stack.advance();
			}
		}
		else {
			leaf = stack.getTopLeaf();

			/*
			 * search for overlapping entries
			 */

			if(context.rect.isInvalid())
				found = HnTRUE;
			else {
				for(;;) {
					int cursor = stack.getCursor();
					HnPoint point =
						leaf.getPointAt(cursor);

					if(debug) {
						fprintf(stderr,
							"comparing with "
							"a point #%d at "
							"a leaf %08X "
							"on the level %d.\n",
							cursor,
							(int)leaf.getOffset(),
							stack.getDepth() - 1);
					}

					if(context.rect.includes(point)) {
						found = HnTRUE;
						break;
					}

					if(!stack.hasMore()) {
						found = HnFALSE;
						break;
					}

					stack.advance();
				}
			}

			if(found) {
				int cursor = stack.getCursor();
				*point_return = leaf.getPointAt(cursor);
				*data_return = leaf.getDataAt(cursor);
				return;
			}
			else {
				/*
				 * go up until the top node has some remaining
				 * entries or the stack is empty.
				 */

				for(;;) {
					stack.pop();

					if(stack.getDepth() == 0) {
						*point_return = HnPoint::null;
						*data_return = HnData::null;
						return;
					}

					if(stack.hasMore())
						break;
				}

				stack.advance();
			}
		}
	}
}

/*
 * Neighbor Search
 */

void
HnSRTreeFileObj::getNeighbors(const HnPoint &point, int maxCount,
			      HnPointArray *points_return,
			      HnDataArray *values_return)
{
	HnSRTreeNeighborArray neighbors = new_HnSRTreeNeighborArray();
	HnPointArray points;
	HnDataArray values;
	int i;

	if(point.getDimension() != getDimension())
		HnAbort("mismatch in the dimensions (point: %d, file: %d)",
			point.getDimension(), getDimension());

        if(maxCount <= 0)
		HnAbort("invalid max count %d.", maxCount);

	neighbors = chooseNeighbors(rootOffset, point, maxCount, neighbors);

	/* make output */
	points = new_HnPointArray();
	values = new_HnDataArray();

	for(i=0; i<neighbors.length(); i++) {
		points.append(neighbors[i].getPoint());
		values.append(neighbors[i].getData());
	}

	*points_return = points;
	*values_return = values;