hnsrtreefileobj3.cpp

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

	}
	if ( everyNeighborIsPoint ) {
	    break;
	}

	offset = neighbors.elementAt(index).getOffset();
	neighbors.removeElementAt(index);
	insertNeighbors(neighbors, numPointsInVector,
			queryPoint, maxCount, offset);

	/*
	 * Discard useless neighbors.
	 * It is unnecessary to keep points more than the max count.
	 */
	numPointsInVector = 0;
	for ( index=0; index<neighbors.size(); index++ ) {
	    if ( numPointsInVector >= maxCount ) {
		/*
		 * NOTE:
		 *	Even if the number of points is greater than
		 *	the max, neighbors that have the same distance
		 *	need to be appended together.
		 */
		double lastDistance = neighbors[index-1].getDistance();
		double nextDistance = neighbors[index  ].getDistance();

		if ( lastDistance != nextDistance ) {
		    break;
		}
	    }
	    if ( neighbors.elementAt(index).isPoint() ) {
		numPointsInVector ++;
	    }
	}
	neighbors.setSize(index);
    }

    /* make output */
    points = new_HnPointVector();
    dataItems = new_HnDataItemVector();

    for ( i=0; i<maxCount && i<neighbors.size(); i++ ) {
	points.addElement(neighbors.elementAt(i).getPoint());
	dataItems.addElement(neighbors.elementAt(i).getDataItem());
    }

    while ( i<neighbors.size() &&
	    neighbors.elementAt(i).isPoint() &&
	    neighbors.elementAt(i).getDistance() ==
	    neighbors.elementAt(i-1).getDistance() ) {
	points.addElement(neighbors.elementAt(i).getPoint());
	dataItems.addElement(neighbors.elementAt(i).getDataItem());
	i ++;
    }

    *points_return = points;
    *dataItems_return = dataItems;
}

void
HnSRTreeFileObj::insertNeighbors(HnSRTreeNeighborVector &neighbors,
				 int &numPointsInVector,
				 const HnPoint &queryPoint, int maxCount,
				 long offset)
{
    HnSRTreeBlock block = readBlock(offset);
    int i;

    if ( block.isLeaf() ) {
	HnSRTreeLeaf leaf = new_HnSRTreeLeaf(info, block);
	int numEntries = leaf.getCount();

	for ( i=0; i<numEntries; i++ ) {
	    HnPoint &point = leaf.getPointAt(i);
	    HnDataItem &dataItem = leaf.getDataItemAt(i);
	    double distance;
	    HnSRTreeNeighbor newNeighbor;

	    distance = point.getDistance(queryPoint);

	    /* skip such a point that is farther than the farthest candidate */
	    if ( numPointsInVector >= maxCount &&
		 distance > neighbors.lastElement().getDistance() ) {
		continue;
	    }

	    newNeighbor = new_HnSRTreeNeighbor(point, dataItem, distance);

	    insertNeighbor(neighbors, newNeighbor);

	    numPointsInVector ++;
	}

	profile->numVisitedLeaves ++;
	profile->numComparedLeafEntries += numEntries;
    }
    else {
	HnSRTreeNode node = new_HnSRTreeNode(info, block);
	int numEntries = node.getCount();

	for ( i=0; i<numEntries; i++ ) {
	    double distance;
	    HnSRTreeNeighbor newNeighbor;

	    distance = getMinDistance(queryPoint, node.getClusterAt(i));

	    /* skip such a node that is farther than the farthest candidate */
	    if ( numPointsInVector >= maxCount &&
		 distance > neighbors.lastElement().getDistance() ) {
		continue;
	    }

	    newNeighbor = new_HnSRTreeNeighbor(node.getOffsetAt(i), distance);

	    insertNeighbor(neighbors, newNeighbor);
	}

	profile->numVisitedNodes ++;
	profile->numComparedNodeEntries += numEntries;
    }
}

void
HnSRTreeFileObj::insertNeighbor(HnSRTreeNeighborVector &neighbors,
				const HnSRTreeNeighbor &newNeighbor)
{
    HnBool found;
    int index;

    HnSRTreeNeighborSearch::search(neighbors, newNeighbor, &found, &index);

    neighbors.insertElementAt(newNeighbor, index);
}

/*
 * Colored Neighbor Search
 */

void
HnSRTreeFileObj::getColoredNeighbors(const HnPointVector &queryPoints,
				     int maxCount,
				     HnPointVector *points_return,
				     HnDataItemVector *dataItems_return)
{
    getColoredNeighbors(queryPoints, maxCount, points_return, dataItems_return,
			NULL);
}

static int
defaultCompColorsFunc(const void *data1, int size1,
		      const void *data2, int size2)
{
    if ( size1 == size2 ) {
	return memcmp(data1, data2, size1);
    }
    else if ( size1 < size2 ) {
	return -1;
    }
    else {
	return 1;
    }
}

void
HnSRTreeFileObj::getColoredNeighbors(const HnPointVector &queryPoints,
				     int maxCount,
				     HnPointVector *points_return,
				     HnDataItemVector *dataItems_return,
				     HnSRTreeCompColorsFunc *compColorsFunc)
{
    switch ( info.getNeighborAlgorithm() ) {
    case HnSRTreeInfo::DEPTH_FIRST:
	getColoredNeighborsByDepthFirst(queryPoints, maxCount,
					points_return, dataItems_return,
					compColorsFunc);
	break;
    case HnSRTreeInfo::BREADTH_FIRST:
	getColoredNeighborsByBreadthFirst(queryPoints, maxCount,
					  points_return, dataItems_return,
					  compColorsFunc);
	break;
    default:
	HnAbort("unexpected value for ``NeighborAlgorithm'': %d.",
		info.getNeighborAlgorithm());
    }
}

double
HnSRTreeFileObj::getDistance(const HnPointVector &queryPoints,
			     const HnPoint &point) 
{
    int i;
    double min;

    min = 0;
    for ( i=0; i<queryPoints.size(); i++ ) {
	double distance = queryPoints[i].getDistance(point);

	if ( i == 0 || distance < min ) {
	    min = distance;
	}
    }

    return min;
}

double
HnSRTreeFileObj::getMinDistance(const HnPointVector &queryPoints,
				const HnSRTreeCluster &cluster)
{
    int i;
    double min;

    min = 0;
    for ( i=0; i<queryPoints.size(); i++ ) {
	double distance = getMinDistance(queryPoints[i], cluster);

	if ( i == 0 || distance < min ) {
	    min = distance;
	}
    }

    return min;
}

double
HnSRTreeFileObj::getMaxDistance(const HnPointVector &queryPoints,
				const HnSRTreeCluster &cluster)
{
    int i;
    double max;

    max = 0;
    for ( i=0; i<queryPoints.size(); i++ ) {
	double distance = getMaxDistance(queryPoints[i], cluster);

	if ( i == 0 || distance > max ) {
	    max = distance;
	}
    }

    return max;
}

class HnSRTreeColoredNeighborSearch: HnBinarySearch {
private:
    HnSRTreeNeighborVector vector;
    HnSRTreeNeighbor key;

    HnSRTreeCompColorsFunc *compColorsFunc;
    enum Type { DISTANCE_VECTOR, COLOR_VECTOR } type;

private:
    int getNumElements(void) {
	return vector.size();
    }
    int compareToElementAt(int i) {
	HnSRTreeNeighbor element = vector.elementAt(i);

	if ( key.isPoint() && element.isPoint() ) {
	    if ( type == DISTANCE_VECTOR ) {
		double distance1 = key.getDistance();
		double distance2 = element.getDistance();

		if ( distance1 == distance2 ) {
		    HnDataItem dataItem1 = key.getDataItem();
		    HnDataItem dataItem2 = element.getDataItem();

		    return compColorsFunc(dataItem1.toCharArray(),
					  dataItem1.length(),
					  dataItem2.toCharArray(),
					  dataItem2.length());
		}
		else if ( distance1 < distance2 ) {
		    return -1;
		}
		else {
		    return 1;
		}
	    }
	    else if ( type == COLOR_VECTOR ) {
		HnDataItem dataItem1 = key.getDataItem();
		HnDataItem dataItem2 = element.getDataItem();

		return compColorsFunc(dataItem1.toCharArray(),
				      dataItem1.length(),
				      dataItem2.toCharArray(),
				      dataItem2.length());
	    }
	    else {
		HnAbort("invalid value for ``type'': %d", type);
	    }
	}
	else {
	    return key.compareTo(element);
	}
    }

    HnSRTreeColoredNeighborSearch(const HnSRTreeNeighborVector &vector,
				  const HnSRTreeNeighbor &key,
				  HnSRTreeCompColorsFunc *compColorsFunc,
				  Type type) {
	this->vector = vector;
	this->key = key;

	this->compColorsFunc = compColorsFunc;
	this->type = type;
    }

public:
    static void searchDistanceVector(const HnSRTreeNeighborVector &vector,
				     const HnSRTreeNeighbor &key,
				     HnSRTreeCompColorsFunc *compColorsFunc,
				     HnBool *found_return, int *index_return) {
	HnSRTreeColoredNeighborSearch searcher(vector, key, compColorsFunc,
					       DISTANCE_VECTOR);
	searcher.searchElements(found_return, index_return);
    }
    static void searchColorVector(const HnSRTreeNeighborVector &vector,
				  const HnSRTreeNeighbor &key,
				  HnSRTreeCompColorsFunc *compColorsFunc,
				  HnBool *found_return, int *index_return) {
	HnSRTreeColoredNeighborSearch searcher(vector, key, compColorsFunc,
					       COLOR_VECTOR);
	searcher.searchElements(found_return, index_return);
    }
};

void
HnSRTreeFileObj::
searchDistanceVector(const HnSRTreeNeighborVector &vector,
		     const HnSRTreeNeighbor &key,
		     HnSRTreeCompColorsFunc *compColorsFunc,
		     HnBool *found_return, int *index_return)
{
    HnSRTreeColoredNeighborSearch::
	searchDistanceVector(vector, key, compColorsFunc,
			     found_return, index_return);
}

void
HnSRTreeFileObj::
searchColorVector(const HnSRTreeNeighborVector &vector,
		  const HnSRTreeNeighbor &key,
		  HnSRTreeCompColorsFunc *compColorsFunc,
		  HnBool *found_return, int *index_return)
{
    HnSRTreeColoredNeighborSearch::
	searchColorVector(vector, key, compColorsFunc,
			  found_return, index_return);
}

/*
 * Colored Neighbor Search (DepthFirst)
 */

void
HnSRTreeFileObj::
getColoredNeighborsByDepthFirst(const HnPointVector &queryPoints, int maxCount,
				HnPointVector *points_return,
				HnDataItemVector *dataItems_return,
				HnSRTreeCompColorsFunc *compColorsFunc)
{
    HnSRTreeNeighborVector distanceVector, colorVector;
    HnPointVector points;
    HnDataItemVector dataItems;
    int i;

    if ( compColorsFunc == NULL ) {
	compColorsFunc = defaultCompColorsFunc;
    }

    if ( queryPoints.size() == 0 ) {
	HnAbort("no query point is given.");
    }

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

    distanceVector = new_HnSRTreeNeighborVector();
    colorVector = new_HnSRTreeNeighborVector();

    chooseColoredNeighbors(info.getRootOffset(), queryPoints, maxCount,
			   distanceVector, colorVector, compColorsFunc);

    /* make output */
    points = new_HnPointVector();
    dataItems = new_HnDataItemVector();

    for ( i=0; i<distanceVector.size(); i++ ) {
	points.addElement(distanceVector[i].getPoint());
	dataItems.addElement(distanceVector[i].getDataItem());
    }

    *points_return = points;
    *dataItems_return = dataItems;
}

void
HnSRTreeFileObj::chooseColoredNeighbors(long offset,
					const HnPointVector &queryPoints,
					int maxCount,
					HnSRTreeNeighborVector &distanceVector,
					HnSRTreeNeighborVector &colorVector,
					HnSRTreeCompColorsFunc *compColorsFunc)
{
    HnSRTreeBlock block = readBlock(offset);

    if ( block.isNode() ) {
	chooseColoredNeighborsInNode(block, queryPoints, maxCount,
				     distanceVector, colorVector,
				     compColorsFunc);
    }
    else if ( block.isLeaf() ) {
	chooseColoredNeighborsInLeaf(block, queryPoints, maxCount,
				     distanceVector, colorVector,
				     compColorsFunc);
    }
    else {
	HnAbort("unexpected block type.");
    }
}

void
HnSRTreeFileObj::
chooseColoredNeighborsInNode(const HnSRTreeBlock &block,
			     const HnPointVector &queryPoints, int maxCount,
			     HnSRTreeNeighborVector &distanceVector,
			     HnSRTreeNeighborVector &colorVector,
			     HnSRTreeCompColorsFunc *compColorsFunc)
{