hnsrtreefileobj.hh

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

    int BuildVAMSRTree(HnPointVector &points, HnDataItemVector &dataItems,
		       int start, int end, REntry *entries, int level);
    REntry CreateRNodeBucket(HnPointVector &points,
			     HnDataItemVector &dataItems,
			     int start, int end);
    REntry CreateRNodeFromEntries(REntry *entries, int count);

    int SplitDataset(HnPointVector &points, HnDataItemVector &dataItems,
		     int start, int end, int size, int cscap, int gscap);
    int SplitDataset_VAM(HnPointVector &points, HnDataItemVector &dataItems,
			 int start, int end, int size, int cscap, int gscap);

    void SelectOnDimension_VAM(HnPointVector &points,
			       HnDataItemVector &dataItems,
			       int split_dim, int start, int end, int lo_size);

    int FindMaxVarianceDimension(HnPointVector &points, int start, int end);


    /* remove */
    HnSRTreeStack searchPoint(const HnPoint &point,
			      const HnDataItem &dataItem);

    /* sequential access */
    void getFirst(HnSRTreeQueryRegion *queryRegion,
		  HnPoint *point_return, HnDataItem *dataItem_return);

    /* neighbor search */
    double getMinDistance(const HnPoint &point,
			  const HnSRTreeCluster &cluster);
    double getMaxDistance(const HnPoint &point,
			  const HnSRTreeCluster &cluster);

    /* neighbor search (DepthFirst) */
    void getNeighborsByDepthFirst(const HnPoint &queryPoint, int maxCount,
				  HnPointVector *points_return,
				  HnDataItemVector *dataItems_return);
    void chooseNeighbors(long offset,
			 const HnPoint &queryPoint, int maxCount,
			 HnSRTreeNeighborVector &neighbors);
    void chooseNeighborsInNode(const HnSRTreeBlock &block,
			       const HnPoint &queryPoint, int maxCount,
			       HnSRTreeNeighborVector &neighbors);
    void chooseNeighborsInLeaf(const HnSRTreeBlock &block,
			       const HnPoint &queryPoint, int maxCount,
			       HnSRTreeNeighborVector &neighbors);

    /* neighbor search (BreadthFirst) */
    void getNeighborsByBreadthFirst(const HnPoint &queryPoint, int maxCount,
				    HnPointVector *points_return,
				    HnDataItemVector *dataItems_return);
    void insertNeighbors(HnSRTreeNeighborVector &neighbors,
			 int &numPointsInVector,
			 const HnPoint &queryPoint, int maxCount,
			 long offset);
    void insertNeighbor(HnSRTreeNeighborVector &neighbors,
			const HnSRTreeNeighbor &newNeighbor);

    /* colored neighbor search */
    double getDistance(const HnPointVector &queryPoints,
		       const HnPoint &point);
    double getMinDistance(const HnPointVector &queryPoints,
			  const HnSRTreeCluster &cluster);
    double getMaxDistance(const HnPointVector &queryPoints,
			  const HnSRTreeCluster &cluster);
    void searchDistanceVector(const HnSRTreeNeighborVector &distanceVector,
			      const HnSRTreeNeighbor &neighbor,
			      HnSRTreeCompColorsFunc *compColorsFunc,
			      HnBool *found_return, int *index_return);
    void searchColorVector(const HnSRTreeNeighborVector &colorVector,
			   const HnSRTreeNeighbor &neighbor,
			   HnSRTreeCompColorsFunc *compColorsFunc,
			   HnBool *found_return, int *index_return);

    /* colored neighbor search (DepthFirst) */
    void getColoredNeighborsByDepthFirst(const HnPointVector &queryPoints,
					 int maxCount,
					 HnPointVector *points_return,
					 HnDataItemVector *dataItems_return,
					 HnSRTreeCompColorsFunc *
					 compColorsFunc);
    void chooseColoredNeighbors(long offset,
				const HnPointVector &queryPoints, int maxCount,
				HnSRTreeNeighborVector &distanceVector,
				HnSRTreeNeighborVector &colorVector,
				HnSRTreeCompColorsFunc *compColorsFunc);
    void chooseColoredNeighborsInNode(const HnSRTreeBlock &block,
				      const HnPointVector &queryPoints,
				      int maxCount,
				      HnSRTreeNeighborVector &distanceVector,
				      HnSRTreeNeighborVector &colorVector,
				      HnSRTreeCompColorsFunc *compColorsFunc);
    void chooseColoredNeighborsInLeaf(const HnSRTreeBlock &block,
				      const HnPointVector &queryPoints,
				      int maxCount,
				      HnSRTreeNeighborVector &distanceVector,
				      HnSRTreeNeighborVector &colorVector,
				      HnSRTreeCompColorsFunc *
				      compColorsFunc);

    /* colored neighbor search (BreadthFirst) */
    void getColoredNeighborsByBreadthFirst(const HnPointVector &queryPoints,
					   int maxCount,
					   HnPointVector *points_return,
					   HnDataItemVector *dataItems_return,
					   HnSRTreeCompColorsFunc *
					   compColorsFunc);
    void insertColoredNeighbors(HnSRTreeNeighborVector &distanceVector,
				HnSRTreeNeighborVector &colorVector,
				int &numPointsInVector,
				const HnPointVector &queryPoints, int maxCount,
				long offset,
				HnSRTreeCompColorsFunc *compColorsFunc);
    void insertColoredNeighbor(HnSRTreeNeighborVector &distanceVector,
			       HnSRTreeNeighborVector &colorVector,
			       int &numPointsInVector,
			       const HnSRTreeNeighbor &newNeighbor,
			       HnSRTreeCompColorsFunc *compColorsFunc);

    /* check */
    int checkBlock(long offset, const HnSRTreeNode &parent, int childIndex);
    HnPointVector checkInclusion(long offset);
    void describeExclusion(long offset, const HnPoint &center);

    /* print */
    void printNode(const HnSRTreeNode &node);
    void printLeaf(const HnSRTreeLeaf &leaf);
    void measureClusters(long offset, int level,
			 HnStatistics nodeSphereRadius,
			 HnStatistics nodeSphereVolume,
			 HnStatistics nodeRectDiagonal,
			 HnStatistics nodeRectVolume,
			 HnStatistics leafSphereRadius,
			 HnStatistics leafSphereVolume,
			 HnStatistics leafRectDiagonal,
			 HnStatistics leafRectVolume);

public:
    HnSRTreeFileObj(const char *path, int dimension, int dataItemSize,
		    const HnProperties &properites = HnProperties::null);
    HnSRTreeFileObj(const char *path,
		    int dimension, int dataItemSize, 
		    HnPointVector &points, HnDataItemVector &dataItems,
		    const HnProperties &properties = HnProperties::null);
    HnSRTreeFileObj(const char *path, const char *mode);
    ~HnSRTreeFileObj(void);

    int getDimension(void) const {
	return info.getDimension();
    }
    int getDataItemSize(void) const {
	return info.getDataItemSize();
    }
    int getHeight(void) const {
	return info.getHeight();
    }
    int getBlockSize(void) const {
	return info.getBlockSize();
    }

    void store(const HnPoint &point, const HnDataItem &dataItem);
    void remove(const HnPoint &point, const HnDataItem &dataItem);
    void close(void);

    void getFirst(HnPoint *point_return, HnDataItem *dataItem_return);
    void getFirst(const HnRect &rect,
		  HnPoint *point_return, HnDataItem *dataItem_return);
    void getFirst(const HnSphere &sphere,
		  HnPoint *point_return, HnDataItem *dataItem_return);
    void getNext(HnPoint *point_return, HnDataItem *dataItem_return);
    void getInRect(const HnRect &rect,
		   HnPointVector *points_return,
		   HnDataItemVector *dataItems_return);
    void getInSphere(const HnSphere &sphere,
		     HnPointVector *points_return,
		     HnDataItemVector *dataItems_return);

    void getNeighbors(const HnPoint &point, int maxCount,
		      HnPointVector *points_return,
		      HnDataItemVector *dataItems_return);
    void getColoredNeighbors(const HnPointVector &queryPoints, int maxCount,
			     HnPointVector *points_return,
			     HnDataItemVector *dataItems_return);
    void getColoredNeighbors(const HnPointVector &queryPoints, int maxCount,
			     HnPointVector *points_return,
			     HnDataItemVector *dataItems_return,
			     HnSRTreeCompColorsFunc *compColorsFunc);

    void check(void);
    void print(HnBool verbose);

    void resetProfile(void) {
	HnSRTreeProfileSt_reset(profile);
    }
    void copyProfileInto(HnSRTreeProfileSt *profile) {
	*profile = *this->profile;
    }

    HnBool dumpToFile(const char *fileName);
    HnBool dumpToFileStream(FILE *fp);

    /* properties */
    HnProperties getDefaultProperties(void) const;
    HnProperties getProperties(void) const;
    void setProperties(const HnProperties &properties);

private:
    static HnBool debug;
public:
    static void setDebug(HnBool debug) {
	HnSRTreeFileObj::debug = debug;
    }
};

#endif /* _HnSRTreeFileObj_hh */