hnsrtreefileobj.hh

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

/*
 * HnSRTreeFileObj.hh
 * 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: HnSRTreeFileObj.hh,v 1.15 2002/09/13 17:21:25 katayama Exp $
 */

#ifndef _HnSRTreeFileObj_hh
#define _HnSRTreeFileObj_hh

#include "HnSRTree/HnObject.hh"
#include "HnSRTree/HnStatistics.hh"
#include "HnSRTree/HnBlockFile.hh"
#include "HnSRTree/HnSRTreeInfo.hh"
#include "HnSRTree/HnSRTreeBlock.hh"
#include "HnSRTree/HnSRTreeNode.hh"
#include "HnSRTree/HnSRTreeLeaf.hh"
#include "HnSRTree/HnSRTreeStack.hh"
#include "HnSRTree/HnSRTreeReinsert.hh"
#include "HnSRTree/HnSRTreeNeighbor.hh"
#include "HnSRTree/HnFTlongArray.hh"

/*{
#include "HnSRTree/HnPoint.hh"
#include "HnSRTree/HnDataItem.hh"
#include "HnSRTree/HnProperties.hh"
#include "HnSRTree/HnSphere.hh"
#include "HnSRTree/HnRect.hh"
#include "HnSRTree/HnSRTreeProto.h"
#include "HnSRTree/HnSRTreeProfileSt.h"
}*/

class HnSRTreeQueryRegion {
public:
    virtual HnBool overlaps(const HnSRTreeCluster &cluster) const = 0;
    virtual HnBool includes(const HnPoint &point) const = 0;
    virtual ~HnSRTreeQueryRegion(void) {};
};

class HnSRTreeFileObj: public HnObject {
private:
    /* split flag */
    enum SplitFlag { LEFT, RIGHT, SPLIT_NONE };

    /* reinsert flag */
    enum ReinsertFlag { REINSERT, STAY, REINSERT_NONE };

    struct REntry {
	HnSRTreeBlock::Type type;
	HnSRTreeNode node;
	HnSRTreeLeaf leaf;
	int level;

	REntry() {
	    type = HnSRTreeBlock::FREE;
	    node = HnSRTreeNode::null;
	    leaf = HnSRTreeLeaf::null;
	    level = -1;
	}
	REntry(const REntry &entry) {
	    type = entry.type;
	    node = entry.node;
	    leaf = entry.leaf;
	    level = entry.level;
	}
	REntry &operator=(const REntry &entry) {
	    type = entry.type;
	    node = entry.node;
	    leaf = entry.leaf;
	    level = entry.level;
	    return *this;
	}
    };

private:
    HnBlockFile blockFile;

    HnSRTreeInfo info;

    struct context_s {
	HnSRTreeStack stack;
	HnSRTreeQueryRegion *queryRegion;
    } context;

    HnSRTreeReinsertVector reinsertList;
    HnFTlongVector reinsertedBlocks;

    HnSRTreeProfileSt *profile;

    /* initialize */
    void initialize(void) {
	context.queryRegion = NULL;
	profile = HnSRTreeProfileSt_allocate();
    }
    void dispose(void) {
	HnSRTreeProfileSt_free(profile);
    }

    /* properties */
    HnProperties getOverriddenProperties(const HnProperties &properties) const;
    void parseProperties(const HnProperties &properties,
			 int dimension,
			 int *blockSize_return,
			 int *splitFactor_return,
			 int *reinsertFactor_return,
			 HnSRTreeInfo::StaticAlgorithm *staticAlgorithm_return,
			 HnSRTreeInfo::NonLeafFloatType *
			 nonLeafFloatType_return,
			 HnSRTreeInfo::NeighborAlgorithm *
			 neighborAlgorithm_return);

    static HnSRTreeInfo::StaticAlgorithm
        stringToStaticAlgorithm(const HnString &value);
    static HnString
        staticAlgorithmToString(HnSRTreeInfo::StaticAlgorithm value);

    static HnSRTreeInfo::NonLeafFloatType
        stringToNonLeafFloatType(const HnString &value);
    static HnString
        nonLeafFloatTypeToString(HnSRTreeInfo::NonLeafFloatType value);

    static HnSRTreeInfo::NeighborAlgorithm
        stringToNeighborAlgorithm(const HnString &value);
    static HnString
        neighborAlgorithmToString(HnSRTreeInfo::NeighborAlgorithm value);

    /* super block */
    void writeSuperBlock(void);
    void readSuperBlock(void);

    /* block */
    HnSRTreeBlock readBlock(long offset);
    void writeBlock(const HnSRTreeBlock &block);
    long allocateBlock(void);
    void releaseBlock(long offset);

    /* leaf */
    void writeLeaf(const HnSRTreeLeaf &leaf);
    HnSRTreeLeaf allocateLeaf(void);

    /* node */
    void writeNode(const HnSRTreeNode &node);
    HnSRTreeNode allocateNode(void);

    /* store */
    void insertPoint(const HnPoint &point, const HnDataItem &dataItem);
    void insertBlock(long offset, int level);
    HnSRTreeStack chooseLeaf(const HnPoint &point);
    int chooseSubtree(const HnSRTreeNode &node, const HnPoint &point);
    HnSRTreeStack chooseNode(const HnPoint &centroid, int level);
    void updateCluster(HnSRTreeStack stack);

    void reinsertLeaf(HnSRTreeStack &stack,
		      const HnPoint &newPoint, const HnDataItem &newDataItem);
    void selectPoints(const HnPointArray &points, ReinsertFlag **flags_return);
    void reinsertNode(HnSRTreeStack &stack,
		      const HnSRTreeCluster &newCluster, long newOffset);
    void selectClusters(const HnSRTreeClusterArray &clusters,
			ReinsertFlag **flags_return);

    void splitLeaf(HnSRTreeStack &stack,
		   const HnPoint &newPoint, const HnDataItem &newDataItem);
    void splitNode(HnSRTreeStack &stack,
		   const HnSRTreeCluster &newCluster, long newOffset);

    void updateNode(HnSRTreeStack &stack,
		    const HnSRTreeCluster &leftCluster, long leftOffset,
		    const HnSRTreeCluster &rightCluster, long rightOffset);
    void extendTree(const HnSRTreeCluster &leftCluster, long leftOffset,
		    const HnSRTreeCluster &rightCluster, long rightOffset);

    /* split */
    void splitPoints(const HnPointArray &points, SplitFlag **flags_return);
    void splitClusters(const HnSRTreeClusterArray &clusters,
		       SplitFlag **flags_return);

    /* construction */
    void searchPoint(const HnPointVector &points, int offset, int count,
		     double keyCoord, int axis, int order,
		     HnBool *found_return, int *index_return);
    void searchCluster(const HnSRTreeClusterVector &clusters,
		       int offset, int count,
		       double keyCoord, int axis, int order,
		       HnBool *found_return, int *index_return);
    void selectPoint(HnPointVector &points, HnDataItemVector &dataItems,
		     int offset, int count, int axis, int index);
    void selectCluster(HnSRTreeClusterVector &clusters,
		       HnFTlongVector &offsets,
		       int offset, int count, int axis, int index);
    void sortPoints(HnPointVector &points, HnDataItemVector &dataItems,
		    int offset, int count, int sortDimension);
    void sortClusters(HnSRTreeClusterVector &clusters, HnFTlongVector &offsets,
		      int offset, int count, int sortDimension);
    int getMaxVarianceAxis(HnPointVector &points, int offset, int count);
    int getMaxVarianceAxis(HnSRTreeClusterVector &clusters,
			   int offset, int count);

    /* construction (VAM) */
    void constructTree_VAM(HnPointVector &points, HnDataItemVector &dataItems);
    REntry CreateVAMSRTree(HnPointVector &points, HnDataItemVector &dataItems);