searchsrtree.c

来自「R 树」· C语言 代码 · 共 325 行

/*
 * searchSRTree.c
 * 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
 *
 * 10/14/96 [e-mail]
 * $Id: searchSRTree.c,v 1.4 1997/06/02 09:35:59 katayama Exp $
 */

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include "HnSRTree.h"
#include "record.h"

static void searchNeighbors(int dimension,
			    const char *dataFileName, const char *treeFileName,
			    int maxCount, int debug, int verify,
			    int neighbors);

static void searchRange(int dimension,
			const char *dataFileName, const char *treeFileName,
			int maxCount, int debug, int verify,
			double width);

int
main(int argc, char *argv[])
{
	int dimension;
	int maxCount, debug, verify;
	int neighbors;
	double width;
	char *treeFileName, *dataFileName;

	int c, errflag;
	extern int optind;
	extern char *optarg;

	maxCount = -1;
	debug = 0;
	neighbors = 1;
	width = 0;
	verify = 0;

	errflag = 0;
	while((c = getopt(argc, argv, "c:dn:vw:")) != EOF) {
		switch(c) {
		case 'c':
			maxCount = atoi(optarg);
			break;
		case 'd':
			debug = 1;
			break;
		case 'n':
			neighbors = atoi(optarg);
			break;
		case 'v':
			verify = 1;
			break;
		case 'w':
			width = atof(optarg);
			break;
		case '?':
			errflag = 1;
			break;
		}
	}
	if(errflag || optind != argc - 3) {
		fprintf(stderr,
			"Usage: %s [options] dimension datafile treefile\n"
			"Options\n"
			"    -c count     set the count of data\n"
			"    -d           turn on the debug mode\n"
			"    -n neighbors set the number of neighbors\n"
			"    -v verify    verify data existence\n"
			"    -w width     set the width of the search range\n",
			argv[0]);
		return 1;
	}
        if(neighbors > 1 && width > 0) {
                fprintf(stderr, "%s: cannot set both `-n' and `-w' options.\n",
                        argv[0]);
                return 1;
        }

	dimension = atoi(argv[optind]);
	dataFileName = argv[optind + 1];
	treeFileName = argv[optind + 2];

	if(width == 0)
		searchNeighbors(dimension, dataFileName, treeFileName,
				maxCount, debug, verify, neighbors);
	else
		searchRange(dimension, dataFileName, treeFileName,
			    maxCount, debug, verify, width);

	return 0;
}

static void
searchNeighbors(int dimension,
		const char *dataFileName, const char *treeFileName,
		int maxCount, int debug, int verify, int neighbors)
{
	HnSRTree *srtree;
	HnSRTreeRecord *hits;
	int numHits;
	RecordPoint recordPoint;
	RecordData recordData;
	FILE *fp;
	int i, count;
	char buffer[BUFFER_SIZE];

	if((srtree = HnSRTreeOpen(treeFileName)) == NULL) {
		perror(treeFileName);
		exit(1);
	}

	if(debug)
		HnSRTreeSetDebug(srtree, 1);

	if(HnSRTreeGetDimension(srtree) != dimension) {
		fprintf(stderr, "Mismatch in dimensions. "
			"The dimension of the tree is %d.\n",
			HnSRTreeGetDimension(srtree));
		exit(1);
	}

	if((fp = fopen(dataFileName, "r")) == NULL) {
		perror(dataFileName);
		exit(1);
	}

	count = 0;

	while((maxCount < 0 || count < maxCount) &&
	      fgets(buffer, sizeof(buffer), fp) != NULL) {
		if(buffer[0] == '#' || buffer[0] == '\n')
			continue;

		getRecord(buffer, dimension, &recordPoint, &recordData);

		if(includesNANorINF(&recordPoint))
			continue;

		/* search data */
		printf("Searching %s\n", (char *)pointToString(&recordPoint));

		HnSRTreeGetNeighbors(srtree, recordPoint.coords, neighbors,
				     &hits, &numHits);

		for(i=0; i<numHits; i++) {
			char *fname = ((RecordData *)hits[i].data)->fname;
			double distance;
			int j;
			double w, sum;

			sum = 0;
			for(j=0; j<dimension; j++) {
				w = recordPoint.coords[j] - hits[i].coords[j];
				sum += w * w;
			}
			distance = sqrt(sum);

			printf("%s: %g\n", fname, distance);
		}
		printf("\n");

		if(verify) {
			int found = 0;

			for(i=0; i<numHits; i++) {
				int equal = 1;
				int j;

				for(j=0; j<dimension; j++) {
					if(recordPoint.coords[j] !=
					   hits[i].coords[j]) {
						equal = 0;
						break;
					}
				}
				if(equal && memcmp(&recordData, hits[i].data,
						   sizeof(RecordData)) == 0)
					found = 1;
			}

			if(!found) {
				fprintf(stderr, "data is not found.\n");
				exit(1);
			}
		}

		count ++;
	}

	fclose(fp);
	HnSRTreeClose(srtree);
}

static void
searchRange(int dimension, const char *dataFileName, const char *treeFileName,
	    int maxCount, int debug, int verify, double width)
{
	HnSRTree *srtree;
	HnSRTreeRange *ranges;
	HnSRTreeRecord *record;
	RecordPoint recordPoint;
	RecordData recordData;
	FILE *fp;
	int i, count;
	char buffer[BUFFER_SIZE];

	/* for verify */
	int found = 0;

	if((ranges = (HnSRTreeRange *)
	    malloc(sizeof(HnSRTreeRange) * dimension)) == NULL) {
		perror("malloc");
		exit(1);
	}

	if((srtree = HnSRTreeOpen(treeFileName)) == NULL) {
		perror(treeFileName);
		exit(1);
	}

	if(debug)
		HnSRTreeSetDebug(srtree, 1);

	if(HnSRTreeGetDimension(srtree) != dimension) {
		fprintf(stderr, "Mismatch in dimensions. "
			"The dimension of the tree is %d.\n",
			HnSRTreeGetDimension(srtree));
		exit(1);
	}

	if((fp = fopen(dataFileName, "r")) == NULL) {
		perror(dataFileName);
		exit(1);
	}

	count = 0;

	while((maxCount < 0 || count < maxCount) &&
	      fgets(buffer, sizeof(buffer), fp) != NULL) {
		if(buffer[0] == '#' || buffer[0] == '\n')
			continue;

		getRecord(buffer, dimension, &recordPoint, &recordData);

		if(includesNANorINF(&recordPoint))
			continue;

		/* extend the rectangle by the given width */
		for(i=0; i<dimension; i++) {
			double x = recordPoint.coords[i];
			ranges[i].min = x - width / 2;
			ranges[i].max = x + width / 2;
		}

		if(verify)
			found = 0;

		/* search data */
		printf("Searching %s\n", (char *)pointToString(&recordPoint));

		HnSRTreeGetFirst(srtree, ranges, &record);

		while(record != NULL) {
			char *fname = ((RecordData *)record->data)->fname;

			printf("%s\n", fname);

			if(verify) {
				int equal = 1;
				int j;

				for(j=0; j<dimension; j++) {
					if(recordPoint.coords[j] !=
					   record->coords[j]) {
						equal = 0;
						break;
					}
				}
				if(equal && memcmp(&recordData, record->data,
						   sizeof(RecordData)) == 0)
					found = 1;
			}

			HnSRTreeGetNext(srtree, &record);
		}

		printf("\n");

		if(verify) {
			if(!found) {
				fprintf(stderr, "data is not found.\n");
				exit(1);
			}
		}

		count ++;
	}

	fclose(fp);
	HnSRTreeClose(srtree);
}