hnsrtreefileobj3.cpp

SR-tree is an index structure for high-dimensional nearest neighbor queries

/*
 * HnSRTreeFileObj3.cc (search methods)
 * Copyright (C) 1997 Norio Katayama
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library 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
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA
 *
 * 03/20/96 [e-mail]
 * $Id: HnSRTreeFileObj3.cc,v 1.9 2002/09/13 17:21:25 katayama Exp $
 */

#include <math.h>
#include <stdio.h>
#ifndef _MSC_VER
#include <unistd.h>
#include <sys/types.h>
#endif
#include "HnSRTree/HnSRTreeFile.hh"
#include "HnSRTree/HnSRTreeFileObj.hh"
#include "HnSRTree/HnBinarySearch.hh"
#include "HnSRTree/HnQuickSort.hh"

/*
 * Sequential Access
 */

void
HnSRTreeFileObj::getFirst(HnPoint *point_return, HnDataItem *dataItem_return)
{
    getFirst(NULL, point_return, dataItem_return);
}

class HnSRTreeRectQueryRegion: public HnSRTreeQueryRegion {
private:
    HnRect rect;
public:
    HnSRTreeRectQueryRegion(HnRect rect) {
	this->rect = rect;
    }
    HnBool overlaps(const HnSRTreeCluster &cluster) const {
	return (rect.overlaps(cluster.getRect()) &&
		rect.overlaps(cluster.getSphere()));
    }
    HnBool includes(const HnPoint &point) const {
	return rect.includes(point);
    }
};

void
HnSRTreeFileObj::getFirst(const HnRect &rect,
			  HnPoint *point_return, HnDataItem *dataItem_return)
{
    if ( rect == HnRect::null ) {
	getFirst(NULL, point_return, dataItem_return);
    }
    else {
	getFirst(new HnSRTreeRectQueryRegion(rect),
		 point_return, dataItem_return);
    }
}

class HnSRTreeSphereQueryRegion: public HnSRTreeQueryRegion {
private:
    HnSphere sphere;
public:
    HnSRTreeSphereQueryRegion(HnSphere sphere) {
	this->sphere = sphere;
    }
    HnBool overlaps(const HnSRTreeCluster &cluster) const {
	return (cluster.getRect().overlaps(sphere) &&
		cluster.getSphere().overlaps(sphere));
    }
    HnBool includes(const HnPoint &point) const {
	return sphere.includes(point);
    }
};

void
HnSRTreeFileObj::getFirst(const HnSphere &sphere,
			  HnPoint *point_return, HnDataItem *dataItem_return)
{
    if ( sphere == HnSphere::null ) {
	getFirst(NULL, point_return, dataItem_return);
    }
    else {
	getFirst(new HnSRTreeSphereQueryRegion(sphere),
		 point_return, dataItem_return);
    }
}

void
HnSRTreeFileObj::getFirst(HnSRTreeQueryRegion *queryRegion,
			  HnPoint *point_return, HnDataItem *dataItem_return)
{
    if ( context.queryRegion != NULL ) {
	delete context.queryRegion;
	context.queryRegion = NULL;
    }

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

    getNext(point_return, dataItem_return);
}

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

    if ( stack.getDepth() == 0 ) {
	/* initialize */
	block = readBlock(info.getRootOffset());
	if ( block.isNode() ) {
	    node = new_HnSRTreeNode(info, block);
	    stack.push(node);
	    profile->numVisitedNodes ++;
	}
	else if ( block.isLeaf() ) {
	    leaf = new_HnSRTreeLeaf(info, block);
	    stack.push(leaf);
	    profile->numVisitedLeaves ++;
	}
	else {
	    HnAbort("unexpected block type.");
	}
    }
    else {
	/* proceed */
	if ( stack.hasMore() ) {
	    stack.advance();
	}
	else {
	    for ( ;; ) {
		stack.pop();

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

		if ( stack.hasMore() ) {
		    break;
		}
	    }

	    stack.advance();
	}
    }

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

	    if ( node.getCount() == 0 ) {
		found = HnFALSE;
	    }
	    else if ( context.queryRegion == NULL ) {
		found = HnTRUE;
	    }
	    else {
		for ( ;; ) {
		    int cursor = stack.getCursor();
		    HnSRTreeCluster cluster = node.getClusterAt(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);
		    }

		    profile->numComparedNodeEntries ++;

		    if ( context.queryRegion->overlaps(cluster) ) {
			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(info, block);
		    stack.push(node);
		    profile->numVisitedNodes ++;
		}
		else if ( block.isLeaf() ) {
		    leaf = new_HnSRTreeLeaf(info, block);
		    stack.push(leaf);
		    profile->numVisitedLeaves ++;
		}
		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;
			*dataItem_return = HnDataItem::null;
			return;
		    }

		    if ( stack.hasMore() ) {
			break;
		    }
		}

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

	    /*
	     * search for overlapping entries
	     */

	    if ( leaf.getCount() == 0 ) {
		found = HnFALSE;
	    }
	    else if ( context.queryRegion == NULL ) {
		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);
		    }

		    profile->numComparedLeafEntries ++;

		    if ( context.queryRegion->includes(point) ) {
			found = HnTRUE;
			break;
		    }

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

		    stack.advance();
		}
	    }

	    if ( found ) {
		int cursor = stack.getCursor();
		*point_return = leaf.getPointAt(cursor);
		*dataItem_return = leaf.getDataItemAt(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;
			*dataItem_return = HnDataItem::null;
			return;
		    }

		    if ( stack.hasMore() ) {
			break;
		    }
		}

		stack.advance();
	    }
	}
    }
}

class HnSRTreeRecordSort: HnQuickSort {
private:
    HnPointVector points;
    HnDataItemVector dataItems;

public:
    HnSRTreeRecordSort(HnPointVector points, HnDataItemVector dataItems) {
	this->points = points;
	this->dataItems = dataItems;
    }
    int getNumElements(void) {
	return points.size();
    }
    int compareElementsAt(int i, int j) {
	HnPoint point1 = points.elementAt(i);
	HnPoint point2 = points.elementAt(j);
	HnDataItem dataItem1 = dataItems.elementAt(i);
	HnDataItem dataItem2 = dataItems.elementAt(j);
	int axis, dimension;

	if ( (dimension = point1.getDimension()) != point2.getDimension() ) {
	    HnAbort("mismatch in dimensions.");
	}
	
	for ( axis=0; axis<dimension; axis++ ) {
	    double coord1 = point1.getCoordAt(axis);
	    double coord2 = point2.getCoordAt(axis);

	    if ( coord1 < coord2 ) {
		return -1;
	    }
	    if ( coord1 > coord2 ) {
		return 1;
	    }
	}

	if ( dataItem1.length() < dataItem2.length() ) {
	    return -1;
	}
	else if ( dataItem1.length() > dataItem2.length() ) {
	    return 1;
	}
	else {
	    return memcmp(dataItem1.toCharArray(), dataItem2.toCharArray(),
			  dataItem1.length());
	}
    }
    void swapElementsAt(int i, int j) {
	points.swapElementsAt(i, j);
	dataItems.swapElementsAt(i, j);
    }
    static void sort(HnPointVector points, HnDataItemVector dataItems) {
	HnSRTreeRecordSort sorter(points, dataItems);
	sorter.sortElements();
    }
};

void
HnSRTreeFileObj::getInRect(const HnRect &rect,
			   HnPointVector *points_return,
			   HnDataItemVector *dataItems_return)
{
    HnPointVector points;
    HnDataItemVector dataItems;
    HnPoint point;
    HnDataItem dataItem;

    /* collect results */
    points = new_HnPointVector();
    dataItems = new_HnDataItemVector();

    getFirst(rect, &point, &dataItem);

    while ( point != HnPoint::null ) {
	points.addElement(point);
	dataItems.addElement(dataItem);

	getNext(&point, &dataItem);
    }

    /* sort results */
    HnSRTreeRecordSort::sort(points, dataItems);

    *points_return = points;
    *dataItems_return = dataItems;
}

void
HnSRTreeFileObj::getInSphere(const HnSphere &sphere,
			     HnPointVector *points_return,
			     HnDataItemVector *dataItems_return)
{
    HnPointVector points;
    HnDataItemVector dataItems;
    HnPoint point;
    HnDataItem dataItem;

    /* collect results */
    points = new_HnPointVector();
    dataItems = new_HnDataItemVector();

    getFirst(sphere, &point, &dataItem);

    while ( point != HnPoint::null ) {
	points.addElement(point);
	dataItems.addElement(dataItem);