readme

R 树

=========================================================================

    HnSRTree: the SR-Tree library
    Version 1.3.1 12/02/97 [e-mail]

    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

    $Id: README,v 1.8 1997/12/04 03:30:47 katayama Exp $

=========================================================================

Tested platforms:

    (1) Hardware         : SPARCstation-20
        Operating System : SunOS 5.4, SunOS 5.5
        Compiler         : GNU C++ 2.7.2, SPARCompiler 4.0

    (2) Hardware         : SPARCstation-2
        Operating System : SunOS 4.1.3
        Compiler         : GNU C++ 2.6.3


How to compile:

    (1) run `configure' in this directory.

	% ./configure

	You can specify the initial values for variables by setting
	them in the environment. For example, you can specify the name
	of the C and C++ compilers by setting them to the variable
	`CC' and `CXX' respectively.

	    (sh)
		$ CC=cc CXX=CC ./configure

	    (csh)
		% env CC=cc CXX=CC ./configure

    (2) run `make' as follows:

	% make includes
	% make all


How to install:

	% make install


How to test:

   (0) compile source files by following the above instructions.

   (1) change the working directory to the `test' directory.

	% cd test

   (2) run the `doTest' script.

	% doTest


How to use:

    Sorry, no documentation is available. Please, refer to the
    following descriptions and the sample programs contained in
    the `c++-samples' and the `c-samples' directories.

    (1) header files

	    (C  ) HnSRTree.h

	    (C++) HnSRTreeFile.hh

	    This library has two language interfaces:
	    the C language interface and the C++ language interface.
	    The header file `HnSRTree.h' is provided for the C users
	    and `HnSRTreeFile.hh' is for the C++ users.

    (2) libraries

	    (C and C++) libHnSRTree.a

	    Although this library has the C language interface, the
	    body of this library is written in C++. Therefore, a C++
	    linker is required to link your object files with this
	    library even if your object files are compiled only with
	    the C compiler.

    (3) creating an SR-tree file
	
	    (C  ) HnSRTree *HnSRTreeCreate(const char *path,
			     	           int dimension,
			     	           int dataSize,
			     	           int blockSize,
			     	           int splitFactor,
			     	           int reinsertFactor
			     	           );

            (C++) HnSRTreeFile new_HnSRTreeFile(const char *path,
                                                int dimension,
                                                int dataSize,
                                                int blockSize,
                                                int splitFactor,
                                                int reinsertFactor
                                                );

	    These functions create an SR-tree file and return the
	    pointer to a data structure associated with that file.

	    	path           : the name of an SR-tree file
                dimension      : the dimensionality of the search space
		dataSize       : the size of an attribute associated
				 with each leaf entry
		blockSize      : the size of a block (or bucket)
				 (typically 8192)
		splitFactor    : the minimum utilization factor of a
				 block (specified in percent)
				 (typically 40)
		reinsertFactor : the percentage of entries to be reinserted
				 on a forced reinsertion
				 (typically 30)

	    The function `new_HnSRTreeFile()' of the C++ interface is
	    not equivalent to the expression `new HnSRTreeFile()' 
	    which invokes the `new' operator. `new_HnSRTreeFile()' is
	    a special function to instantiate an object of the class
	    `HnSRTreeFile'. This library takes the Java semantics for
            object instantiation. The variables are allocated only for
            referencing objects and objects are instantiated only by
            special constructors whose name starts with the string
            `new_'. The instantiated objects are automatically
            reclaimed on losing references to themselves.

    (4) opening an SR-tree for reading or updating

	    (C  ) HnSRTree *HnSRTreeUpdate(const char *path);
		  HnSRTree *HnSRTreeOpen(const char *path);      

	    (C++) HnSRTreeFile new_HnSRTreeFile(const char *path,
						const char *mode);

	    These functions open an SR-tree file for reading or updating.

		path : the name of an SR-tree file
		mode : the access mode for opening an SR-tree file

	    In the C language interface, the function `HnSRTreeUpdate()'
	    opens an SR-tree file for updating. On the other hand, the
	    function `HnSRTreeOpen()' opens an SR-tree file for reading.

	    Upon successful completion, both return the pointer to a
	    data structure associated with that file. Otherwise,
	    a null pointer is returned and errno is set to indicate
	    the error.

	    In the C++ language interface, the variable `mode'
	    specifies the access mode for opening an SR-tree file.
	    Mode "r" is for reading and mode "rw" is for updating. 

	    Upon successful completion, the function returns an object
	    of the class `HnSRTreeFile' which is associated with that
	    opened file. Otherwise, the constant `HnSRTreeFile::null'
	    is returned and errno is set to indicate the error.

    (5) closing an SR-tree file

	    (C  ) void HnSRTreeClose(HnSRTree *file);

	    (C++) void file.close(void);

	    These functions close an SR-tree file.

		file : the pointer to a data structure associated with
		       an SR-tree file

    (6) storing a point into an SR-tree file.

	    (C  ) void HnSRTreeStore(HnSRTree *file,
				     const double coords[],
				     const void *ptr,
				     int size
				     );

	    (C++) void file.store(const HnPoint &point,
				  const HnData &data
				  );

	    These functions store a point into an SR-tree file. The
	    current implementation imposes no restriction for
	    duplication. This reduces the overhead on insertion.
	    The same point-attribute pairs can be duplicated.
	    Duplication does not harm the functionality of this
	    library.

		file   : the pointer to a data structure associated with
		         an SR-tree file
		coords : the coordinates of a point to be stored
		ptr    : the pointer to an attribute to be stored
			 with a point
		size   : the size of an attribute

		point  : a point being stored
		data   : an attribute being stored

	    In the C++ language interface, the class `HnPoint' and
	    `HnData' are used. An object of the class `HnPoint' can
	    be created in the following way:

		HnPoint point;

		point = new_HnPoint(dimension);
		for (i=0; i<dimension; i++)
			point.setCoord(coords[i], i);

	    where it is supposed that the dimensionality of the object
	    is given by the variable `dimension' and its coordinates
	    are given by the array `coords[]'.

	    An object of the class `HnData' can be created in the
	    following way:

		HnData data;

	      	data = new_HnData(ptr, size);

	    where it is supposed that the content of the object is
	    given by a byte string whose location is `ptr' and whose
	    size is `size'.

    (7) removing a point from an SR-tree file.

	    (C  ) void HnSRTreeRemove(HnSRTree *file,
				      const double coords[],
				      const void *ptr,
				      int size
				      );

	    (C++) void file.remove(const HnPoint &point, const HnData &data);

	    These functions remove a point from an SR-tree file. Only
	    a point having the same coordinates and the same attribute
	    is removed. Points with different attributes are intact.

		file   : the pointer to a data structure associated with
			 an SR-tree file
		coords : the coordinates of a point to be removed
		ptr    : the pointer to an attribute to be removed
			 with a point
		size   : the size of an attribute to be removed

		point  : a point being removed
		data   : an attribute being removed

    (8) running a nearest neighbor search

	    (C  ) void HnSRTreeGetNeighbors(HnSRTree *file,
					    const double coords[],
					    int numNeighbors,
					    HnSRTreeRecord **records_return,
					    int *numRecords_return
					    );

	    (C++) void file.getNeighbors(const HnPoint &point,