hnsrtreefileobj.cpp

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

/*
 * HnSRTreeFileObj.cc
 * 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.cc,v 1.19 2002/09/13 03:48:26 katayama Exp $
 */

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

HnBool HnSRTreeFileObj::debug = HnFALSE;

/*
 * Properties
 */

HnProperties
HnSRTreeFileObj::getDefaultProperties(void) const
{
    HnProperties props = new_HnProperties();

    props.setProperty(HnSRTreeBlockSize, HnSRTreeDefaultBlockSize);
    props.setProperty(HnSRTreeSplitFactor, HnSRTreeDefaultSplitFactor);
    props.setProperty(HnSRTreeReinsertFactor, HnSRTreeDefaultReinsertFactor);
    props.setProperty(HnSRTreeStaticAlgorithm, HnSRTreeDefaultStaticAlgorithm);
    props.setProperty(HnSRTreeNonLeafFloatType,
		      HnSRTreeDefaultNonLeafFloatType);

    props.setProperty(HnSRTreeNeighborAlgorithm,
		      HnSRTreeDefaultNeighborAlgorithm);

    return props;
}

HnProperties
HnSRTreeFileObj::getOverriddenProperties(const HnProperties &properties) const
{
    HnProperties newProps = new_HnProperties(getDefaultProperties());
    int i, size;

    if ( properties != HnProperties::null ) {
	size = properties.size();
	for ( i=0; i<size; i++ ) {
	    HnString key, value;

	    key = properties.getKeyAt(i);
	    value = properties.getValueAt(i);

	    if ( newProps.getProperty(key) == HnString::null ) {
		HnAbort("invalid property key `%s'.", (char *)key);
	    }

	    newProps.setProperty(key, value);
	}
    }

    return newProps;
}

void
HnSRTreeFileObj::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)
{
    HnString key, value;
    int blockSize, splitFactor, reinsertFactor;
    HnSRTreeInfo::StaticAlgorithm staticAlgorithm;
    HnSRTreeInfo::NonLeafFloatType nonLeafFloatType;
    HnSRTreeInfo::NeighborAlgorithm neighborAlgorithm;

    /* blockSize */
    key = HnSRTreeBlockSize;
    if ( (value = properties.getProperty(key)) == HnString::null ) {
	HnAbort("property `%s' is not found.", (char *)key);
    }
    if ( (blockSize = HnString::parseInt(value)) <= 0 ) {
	HnAbort("block size %d is out of range.", blockSize);
    }

    /* splitFactor */
    key = HnSRTreeSplitFactor;
    if ( (value = properties.getProperty(key)) == HnString::null ) {
	HnAbort("property `%s' is not found.", (char *)key);
    }
    splitFactor = HnString::parseInt(value);
    if ( splitFactor < 0 || splitFactor > 50 ) {
	HnAbort("split factor %d is out of range.", splitFactor);
    }

    /* reinsertFactor */
    key = HnSRTreeReinsertFactor;
    if ( (value = properties.getProperty(key)) == HnString::null ) {
	HnAbort("property `%s' is not found.", (char *)key);
    }
    reinsertFactor = HnString::parseInt(value);
    if ( reinsertFactor < 0 || reinsertFactor > 50 ) {
	HnAbort("reinsert factor %d is out of range.", reinsertFactor);
    }

    /* staticAlgorithm */
    key = HnSRTreeStaticAlgorithm;
    if ( (value = properties.getProperty(key)) == HnString::null ) {
	HnAbort("property `%s' is not found.", (char *)key);
    }
    staticAlgorithm = stringToStaticAlgorithm(value);
    if ( staticAlgorithm == HnSRTreeInfo::NONSTATIC ) {
	HnAbort("the string `%s' is invalid for the property `%s'.",
		(char *)value, (char *)key);
    }

    /* nonLeafFloatType */
    key = HnSRTreeNonLeafFloatType;
    if ( (value = properties.getProperty(key)) == HnString::null ) {
	HnAbort("property `%s' is not found.", (char *)key);
    }
    nonLeafFloatType = stringToNonLeafFloatType(value);

    /* neighborAlgorithm */
    key = HnSRTreeNeighborAlgorithm;
    if ( (value = properties.getProperty(key)) == HnString::null ) {
	HnAbort("property `%s' is not found.", (char *)key);
    }
    neighborAlgorithm = stringToNeighborAlgorithm(value);

    *blockSize_return = blockSize;
    *splitFactor_return = splitFactor;
    *reinsertFactor_return = reinsertFactor;
    *staticAlgorithm_return = staticAlgorithm;
    *nonLeafFloatType_return = nonLeafFloatType;
    *neighborAlgorithm_return = neighborAlgorithm;
}

HnProperties
HnSRTreeFileObj::getProperties(void) const
{
    HnProperties props = new_HnProperties();

    props.setProperty(HnSRTreeBlockSize,
		      HnString::valueOf(info.getBlockSize()));

    props.setProperty(HnSRTreeSplitFactor,
		      HnString::valueOf(info.getSplitFactor()));

    props.setProperty(HnSRTreeReinsertFactor,
		      HnString::valueOf(info.getReinsertFactor()));

    props.setProperty(HnSRTreeStaticAlgorithm,
		      staticAlgorithmToString(info.getStaticAlgorithm()));

    props.setProperty(HnSRTreeNonLeafFloatType,
		      nonLeafFloatTypeToString(info.getNonLeafFloatType()));

    props.setProperty(HnSRTreeNeighborAlgorithm,
		      neighborAlgorithmToString(info.getNeighborAlgorithm()));

    return props;
}

void
HnSRTreeFileObj::setProperties(const HnProperties &properties)
{
    int i, size;

    size = properties.size();
    for ( i=0; i<size; i++ ) {
	HnString key, value;

	key = properties.getKeyAt(i);
	value = properties.getValueAt(i);

	if ( key.equals(HnSRTreeNeighborAlgorithm) ) {
	    info.setNeighborAlgorithm(stringToNeighborAlgorithm(value));
	}
	else {
	    HnAbort("setting the property ``%s'' is not allowed.",
		    (char *)key);
	}
    }
}

HnSRTreeInfo::StaticAlgorithm
HnSRTreeFileObj::stringToStaticAlgorithm(const HnString &value)
{
    if ( value.equals("NONSTATIC") ) {
	return HnSRTreeInfo::NONSTATIC;
    }
    else if ( value.equals("VAM_ORIGINAL") ) {
	return HnSRTreeInfo::VAM_ORIGINAL;
    }
    else if ( value.equals("VAM_CORRECTED") ) {
	return HnSRTreeInfo::VAM_CORRECTED;
    }
    else {
	HnAbort("invalid value for `StaticAlgorithm' (`%s').", (char *)value);
    }
}

HnString
HnSRTreeFileObj::staticAlgorithmToString(HnSRTreeInfo::StaticAlgorithm value)
{
    switch ( value ) {
    case HnSRTreeInfo::NONSTATIC:
	return "NONSTATIC";
    case HnSRTreeInfo::VAM_ORIGINAL:
	return "VAM_ORIGINAL";
    case HnSRTreeInfo::VAM_CORRECTED:
	return "VAM_CORRECTED";
    default:
	HnAbort("unexpected value for `StaticAlgorithm' (%d).", value);
    }
}

HnSRTreeInfo::NonLeafFloatType
HnSRTreeFileObj::stringToNonLeafFloatType(const HnString &value)
{
    if ( value.equals("NON_LEAF_SINGLE") ) {
	return HnSRTreeInfo::NON_LEAF_SINGLE;
    }
    else if ( value.equals("NON_LEAF_DOUBLE") ) {
	return HnSRTreeInfo::NON_LEAF_DOUBLE;
    }
    else {
	HnAbort("invalid value for `NonLeafFloatType' (`%s').", (char *)value);
    }
}

HnString
HnSRTreeFileObj::nonLeafFloatTypeToString(HnSRTreeInfo::NonLeafFloatType value)
{
    switch ( value ) {
    case HnSRTreeInfo::NON_LEAF_SINGLE:
	return "NON_LEAF_SINGLE";
    case HnSRTreeInfo::NON_LEAF_DOUBLE:
	return "NON_LEAF_DOUBLE";
    default:
	HnAbort("unexpected value for `NonLeafFloatType' (%d).", value);
    }
}

HnSRTreeInfo::NeighborAlgorithm
HnSRTreeFileObj::stringToNeighborAlgorithm(const HnString &value)
{
    if ( value.equals("DEPTH_FIRST") ) {
	return HnSRTreeInfo::DEPTH_FIRST;
    }
    else if ( value.equals("BREADTH_FIRST") ) {
	return HnSRTreeInfo::BREADTH_FIRST;
    }
    else {
	HnAbort("invalid value for `NeighborAlgorithm' (`%s').",
		(char *)value);
    }
}

HnString
HnSRTreeFileObj::neighborAlgorithmToString(HnSRTreeInfo::NeighborAlgorithm
					   value)
{
    switch ( value ) {
    case HnSRTreeInfo::DEPTH_FIRST:
	return "DEPTH_FIRST";
    case HnSRTreeInfo::BREADTH_FIRST:
	return "BREADTH_FIRST";
    default:
	HnAbort("unexpected value for `NeighborAlgorithm' (%d).", value);
    }
}

/*
 * Constructor and Destructor
 */

HnSRTreeFileObj::HnSRTreeFileObj(const char *path,
				 int dimension, int dataItemSize,
				 const HnProperties &properties)
{
    int blockSize, splitFactor, reinsertFactor;
    HnSRTreeInfo::StaticAlgorithm staticAlgorithm;
    HnSRTreeInfo::NonLeafFloatType nonLeafFloatType;
    HnSRTreeInfo::NeighborAlgorithm neighborAlgorithm;
    long fileSize, freeOffset, rootOffset;
    int height;
    HnSRTreeLeaf leaf;

    initialize();

    parseProperties(getOverriddenProperties(properties),
		    dimension,
		    &blockSize, &splitFactor, &reinsertFactor,
		    &staticAlgorithm, &nonLeafFloatType,
		    &neighborAlgorithm);

    fileSize = blockSize;
    freeOffset = -1;
    rootOffset = 0;
    height = 0;

    staticAlgorithm = HnSRTreeInfo::NONSTATIC;

    info = new_HnSRTreeInfo(dimension, dataItemSize,
			    fileSize, freeOffset, rootOffset, height,
			    blockSize, splitFactor, reinsertFactor,
			    staticAlgorithm, nonLeafFloatType,
			    neighborAlgorithm);

    if ( HnSRTreeNode::getMaxCount(info) < 2 ) {
	HnAbort("the block size (%d) is too small; "
		"at least two entries should be allocated "
		"in a non-leaf node.", blockSize);
    }
    if ( HnSRTreeLeaf::getMaxCount(info) < 1 ) {
	HnAbort("the block size (%d) is too small; "
		"at least one entry should be allocated in a leaf node.",
		blockSize);
    }

    blockFile = new_HnBlockFile(path, blockSize);
    if ( blockFile == HnBlockFile::null ) {
	setConstructorFailureFlag();
	return;
    }

    leaf = allocateLeaf();
    info.setRootOffset(leaf.getOffset());
    info.setHeight(info.getHeight() + 1);

    writeLeaf(leaf);
    writeSuperBlock();
}

HnSRTreeFileObj::HnSRTreeFileObj(const char *path,
				 int dimension, int dataItemSize,
				 HnPointVector &points,
				 HnDataItemVector &dataItems,
				 const HnProperties &properties)
{
    int blockSize, splitFactor, reinsertFactor;
    HnSRTreeInfo::StaticAlgorithm staticAlgorithm;
    HnSRTreeInfo::NonLeafFloatType nonLeafFloatType;
    HnSRTreeInfo::NeighborAlgorithm neighborAlgorithm;
    long fileSize, freeOffset, rootOffset;
    int height;

    initialize();

    parseProperties(getOverriddenProperties(properties), dimension,