tvindexsearch.c

TV-tree的c实现源码

/* 
 
                  COPYRIGHT NOTICE
 
This material was developed by Christos Faloutsos and King-Ip Lin
at the University of Maryland, College Park, Department of Computer Science.
Permission is granted to copy this software, to redistribute it
on a nonprofit basis, and to use it for any purpose, subject to
the following restrictions and understandings.
 
1. Any copy made of this software must include this copyright notice
in full.
 
2. All materials developed as a consequence of the use of this
software shall duly acknowledge such use, in accordance with the usual
standards of acknowledging credit in academic research.
 
3. The authors have made no warranty or representation that the
operation of this software will be error-free or suitable for any
application, and they are under under no obligation to provide any
services, by way of maintenance, update, or otherwise.  The software
is an experimental prototype offered on an as-is basis.
 
4. Redistribution for profit requires the express, written permission
of the authors.
 
*/

// Author : $Author$
// Date : $Date$
// Id : $Id$
// $Id: indexsearch.C,v 1.3 1996/04/18 21:50:24 kilin Exp kilin $ 
#include <iostream.h>
#include <fstream.h>
#include <assert.h>
#include <stdlib.h>
#include "TVdefine.h"
#include "TVconstants.h"
#include "TVvector.h"
#include "TVelement.h"
#include "TVrectangle.h"
#include "TVsimbuf.h"
#include "TVnode.h"
#include "TVlinkedlist.h"
#include "TVindexstat.h"
#include "TVindexpara.h"
#include "TVindex.h"
#include "TVutil.h"


extern int eletested;


// Return number of hits when search for all descendent from node n 
int TVTree::RecurSearch(TVNode *n, Leaf_Element& le,  LinkedList *reslist, VCOM_TYPE (*gfeat)(int, char*), int (*equal)(char *, char *), Searchcode searchcode)
{
  TVNodeIter nit(n);
  int result = 0;
  TVNodeEntry ne;

  if (n->TVNodeType() == INTERNAL_NODE)
     {
       stats.IncrementStat(READCOUNT);

       // not yet reached leaf
       if (searchcode == searchall)
          {
             // search all
             result = 0;
             for (ne = nit.Iter(); ne.Defined(); ne = nit.Iter())
                {
                  if (ne.u.b->GetBound().Contain(le.GetTVector(ne.u.b->GetBound().GetCenterDim(), gfeat)))
                      result += RecurSearch(ne.u.b->FetchChild(), le, reslist, gfeat, equal, searchcode);
                }
          }
       else
          {
             // search exist
             for (ne = nit.Iter(); (!result) && (ne.Defined()); ne = nit.Iter())
                {
                   if (ne.u.b->GetBound().Contain(le.GetTVector(ne.u.b->GetBound().GetCenterDim(), gfeat)))
                      result = RecurSearch(ne.u.b->FetchChild(), le, reslist, gfeat, equal, searchcode);
                }
          }
     }
  else
     {
        stats.IncrementStat(LEAFREADCOUNT);

       if (searchcode == searchall)
          {
            result = 0;
            for (ne = nit.Iter(); ne.Defined(); ne = nit.Iter())
                {
		   char *e1 = (*(ne.u.e))();
		   char *e2 = le();
          
                   int r = equal(e1, e2);
                   if (r)
                      {
                        result++;
			if (reslist)
			   reslist->Append(ne.u.e);
                      }
		   delete [] e1;
		   delete [] e2;
                 }
	     eletested += nit.Count();
          }
       else
          {
             for (ne = nit.Iter(); (!result) && (ne.Defined()); ne = nit.Iter())
                 {
		    char *e1 = (*(ne.u.e))();
		    char *e2 = le();
                    int r = equal(e1, e2);
                    if (result && reslist)
			reslist->Append(ne.u.e);
		    delete [] e1;
		    delete [] e2;
                 }
	     eletested += nit.GetLastIterInd();
          }

     }
  return result;
}

void TVStuffArray(char **result, LinkedList& reslist, char *(GetResult)(char *, int, int&))
{
   if (reslist.Count())
      {
	   reslist.ResetToHead();
	   for (int i = 0; !reslist.IsEmpty(); i++)
	       {
		  int resbytes;
		  Leaf_Element *leafele = reslist.RemoveHead()->Get();
		  result[i] = GetResult((*leafele)(), leafele->BytearraySize(), resbytes);
	       }
      }
}

int TVTree::Search(char *e, int size,  char**& res, char *(GetResult)(char *, int, int&),  VCOM_TYPE (*gfeat)(int, char*), int (*equal)(char *, char *), Searchcode searchcode = searchall)
{

   LinkedList reslist;
   int result = 0;
   Leaf_Element le(e, size);

   if (root)
      {
        result = RecurSearch(root, le, &reslist, gfeat, equal, searchcode);
        if (root->TVNodeType() == INTERNAL_NODE)
           stats.AddIntStat(READCOUNT, -1); // discount read from root
      }

   if (result)
      {
	 res = new char*[result];
	 TVStuffArray(res, reslist, GetResult);
      }
   else
      res = NULL;
	
   return(result);
}



// Return number of hits when search for all descendent from node n 
int TVTree::RecurSearch(TVNode *n, Leaf_Element& le,  float radius, LinkedList *reslist, VCOM_TYPE (*gfeat)(int, char*), float (*Distance)(char *, char *), Searchcode searchcode)
{
  TVNodeIter nit(n);
  int result = 0;
  TVNodeEntry ne;

  if (n->TVNodeType() == INTERNAL_NODE)
     {
       stats.IncrementStat(READCOUNT);
	

       // not yet reached leaf
       if (searchcode == searchall)
          {
             // search all
             result = 0;
             for (ne = nit.Iter(); ne.Defined(); ne = nit.Iter())
                {
                  if (ne.u.b->GetBound().MinDist(le.GetTVector(ne.u.b->GetBound().GetCenterDim(), gfeat)) <= radius)
                      result += RecurSearch(ne.u.b->FetchChild(), le, radius, reslist, gfeat, Distance, searchcode);
                }
          }
       else
          {
            // search exist
            for (ne = nit.Iter(); (!result) && (ne.Defined()); ne = nit.Iter())
                {
                  if (ne.u.b->GetBound().MinDist(le.GetTVector(ne.u.b->GetBound().GetCenterDim(), gfeat)) <= radius)
                     result = RecurSearch(ne.u.b->FetchChild(), le, radius, reslist, gfeat, Distance, searchcode);
                }
          }
     }
  else
     {
        stats.IncrementStat(LEAFREADCOUNT);

       if (searchcode == searchall)
          {
            result = 0;
            for (ne = nit.Iter(); ne.Defined(); ne = nit.Iter())
                {
		   char *e1 = (*(ne.u.e))();
		   char *e2 = le();
          
                   float r = Distance(e1, e2);
                   if (r <= radius)
                      {
                        result++;
			if (reslist)
			   reslist->Append(ne.u.e);
                      }
		   delete [] e1;
		   delete [] e2;
                 }
	     eletested += nit.Count();
          }
       else
          {
             for (ne = nit.Iter(); (!result) && (ne.Defined()); ne = nit.Iter())
                 {
		    char *e1 = (*(ne.u.e))();
		    char *e2 = le();
                    float r = Distance(e1, e2);
		    result = (r <= radius); 
                    if (result && reslist)
		       reslist->Append(ne.u.e);
		    delete [] e1;
		    delete [] e2;
                 }
	    eletested += nit.GetLastIterInd();
          }

     }
  return result;
}

int TVTree::Search(float dis, char *e, int size, char** &res, char *(GetResult)(char *, int, int&),  VCOM_TYPE (*gfeat)(int, char*), float (*Distance)(char *, char *), Searchcode searchcode)
{
   LinkedList reslist;
   int result = 0;
   Leaf_Element le(e, size);

   if (root)
      {
        result = RecurSearch(root, le, dis, &reslist, gfeat, Distance, searchcode);
        if (root->TVNodeType() == INTERNAL_NODE)
           stats.AddIntStat(READCOUNT, -1); // discount read from root
      }
   if (result)
      {
	 res = new char*[result];
	 TVStuffArray(res, reslist, GetResult);
      }
   else
      res = NULL;
	
   return(result);
}


// Return number of hits when search for all descendent from node n 
int TVTree::RecurSearch(TVNode *n, Leaf_Element& le,  float radius, LinkedList *reslist, VCOM_TYPE (*gfeat)(int, char*), Searchcode searchcode)
{
  TVNodeIter nit(n);
  int result = 0;
  TVNodeEntry ne;

  if (n->TVNodeType() == INTERNAL_NODE)
     {
       stats.IncrementStat(READCOUNT);
	

       // not yet reached leaf
       if (searchcode == searchall)
          {
             // search all
             result = 0;
             for (ne = nit.Iter(); ne.Defined(); ne = nit.Iter())
                {
                  if (ne.u.b->GetBound().MinDist(le.GetTVector(ne.u.b->GetBound().GetCenterDim(), gfeat)) <= radius)
                      result += RecurSearch(ne.u.b->FetchChild(), le, radius, reslist, gfeat, searchcode);
                }
          }
       else
          {
            // search exist
            for (ne = nit.Iter(); (!result) && (ne.Defined()); ne = nit.Iter())
                {
                  if (ne.u.b->GetBound().MinDist(le.GetTVector(ne.u.b->GetBound().GetCenterDim(), gfeat)) <= radius)
                     result = RecurSearch(ne.u.b->FetchChild(), le, radius, reslist, gfeat, searchcode);
                }
          }
     }
  else
     {
        stats.IncrementStat(LEAFREADCOUNT);

       if (searchcode == searchall)
          {
            result = 0;
            for (ne = nit.Iter(); ne.Defined(); ne = nit.Iter())
                {
		   int dim = min(le.GetTVector().GetDim(), ne.u.e->GetTVector().GetDim());
		   float r = le.GetTVector().ProjectFront(dim).Distance(ne.u.e->GetTVector().ProjectFront(dim));
		   if (r < 0.0)
			r = -r;
          
                   if (r <= radius)
                      {
                        result++;
			if (reslist)
			   reslist->Append(ne.u.e);
                      }
                 }
	     eletested += nit.Count();
          }
       else
          {
             for (ne = nit.Iter(); (!result) && (ne.Defined()); ne = nit.Iter())
                 {
		   int dim = min(le.GetTVector().GetDim(), ne.u.e->GetTVector().GetDim());
		   float r = le.GetTVector().ProjectFront(dim).Distance(ne.u.e->GetTVector().ProjectFront(dim));
		   if (r < 0.0)
			r = -r;
		    result = (r <= radius); 
                    if (result && reslist)
		       reslist->Append(ne.u.e);
                 }
	    eletested += nit.GetLastIterInd();
          }

     }
  return result;
}




int TVTree::Search(float dis, char *e, int size, char**& res, char *(GetResult)(char *, int, int&),  VCOM_TYPE (*gfeat)(int, char*), Searchcode searchcode)
{
   LinkedList reslist;
   int result = 0;
   Leaf_Element le(e, size);

   if (root)
      {
        result = RecurSearch(root, le, dis, &reslist, gfeat, searchcode);
        if (root->TVNodeType() == INTERNAL_NODE)
           stats.AddIntStat(READCOUNT, -1); // discount read from root
      }
   if (result)
      {
	 res = new char*[result];
	 TVStuffArray(res, reslist, GetResult);
      }
   else
      res = NULL;
	
   return(result);
}


// Don't eliminate false hits (i.e. don't call the distance function) 
int TVTree::RecurSearch(TVNode *n, TVRectangle& testrect, LinkedList *reslist, VCOM_TYPE (*gfeat)(int, char*), Searchcode searchcode)
{
  TVNodeIter nit(n);
  int result = 0;
  TVNodeEntry ne;

  if (n->TVNodeType() == INTERNAL_NODE)
     {
       stats.IncrementStat(READCOUNT);
	

       // not yet reached leaf
       if (searchcode == searchall)
          {
             // search all
             result = 0;
             for (ne = nit.Iter(); ne.Defined(); ne = nit.Iter())
                {
// cout << "Search internal node : " << ne.u.b->GetBound() << "  vs. " << testrect << endl;
                  if (ne.u.b->GetBound().Intersect(testrect))
                      result += RecurSearch(ne.u.b->FetchChild(), testrect, reslist, gfeat, searchcode);
                }
          }
       else
          {
            // search exist
            for (ne = nit.Iter(); (!result) && (ne.Defined()); ne = nit.Iter())
                {
                  if (ne.u.b->GetBound().Intersect(testrect))
                      result = RecurSearch(ne.u.b->FetchChild(), testrect, reslist, gfeat, searchcode);
                }
          }
     }
  else
     {
        stats.IncrementStat(LEAFREADCOUNT);

       if (searchcode == searchall)
          {
            result = 0;
            for (ne = nit.Iter(); ne.Defined(); ne = nit.Iter())
                {
		   TVector v1 = ne.u.e->GetTVector(testrect.GetCenterDim(), gfeat, FALSE);
		  
		   if (testrect.Contain(v1))
                      {
// cout << "  HITS";
                        result++;
			if (reslist)
			   reslist->Append(ne.u.e);
                      }
// cout <<  endl;
                 }
	     eletested += nit.Count();
          }
       else
          {
             for (ne = nit.Iter(); (!result) && (ne.Defined()); ne = nit.Iter())
                 {
		    TVector v1 = ne.u.e->GetTVector(testrect.GetCenterDim(), gfeat, FALSE);
		    result = testrect.Contain(v1);
                    if (result && reslist)
			 reslist->Append(ne.u.e);
                 }
	    eletested += nit.GetLastIterInd();
          }

     }
  return result;
}



int TVTree::Search(char *e, int size, int fdim, float *lbound, float *ubound, char**& res, char *(GetResult)(char *, int, int&), VCOM_TYPE (*gfeat)(int, char*),  Searchcode searchcode = searchall)
{
 
   LinkedList reslist;
   int result = 0;
   Leaf_Element le(e, size);
   TVector lower(fdim), upper(fdim);

   for (int i = 0; i < fdim; i++)
	{
	  lower[i] = lbound[i];
	  upper[i] = ubound[i];
	}

   TVRectangle trec(lower, upper);

   if (root)
      {
        result = RecurSearch(root, trec, &reslist, gfeat, searchcode);
        if (root->TVNodeType() == INTERNAL_NODE)
           stats.AddIntStat(READCOUNT, -1); // discount read from root
      }
   if (result)
      {
	 res = new char*[result];
	 TVStuffArray(res, reslist, GetResult);
      }
   else
      res = NULL;
	
   return(result);
}