tvindex.h

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: index.h,v 1.4 1996/04/18 21:50:24 kilin Exp kilin $ 
// To return result for insertion

class LinkedList;

enum InsertReturnType {nochange = 0,
                       newele   = 1,  // new element from inserting leaf
                       newbound = 2,  // one new bound formed (adjusting child, etc)
                       newbranch = 3,
		       fromsplit = 4
                      };

// This is to store info to pass up during recursive call to insertion
// irt  : what kind of info is stored being passed up 
// branch : array storing the new branches
// bound  : array storing the new bounds 

class RecurInsertReturn{

public:
   RecurInsertReturn();
   ~RecurInsertReturn();
   RecurInsertReturn(const RecurInsertReturn&);

   RecurInsertReturn& operator=(const RecurInsertReturn&);

   RecurInsertReturn& FromSplit(const SplitReturn&);
   RecurInsertReturn& Onebound(const TVRectangle&);
   RecurInsertReturn& Twobound(const TVRectangle&, const TVRectangle&);
   RecurInsertReturn& Nbound(TVRectangle *, int n);
   RecurInsertReturn& Nbound(TVBranch *, int n); // the bounding region of the branches are the bounds 


   InsertReturnType irt ;
   int newcount;
   TVBranch *branch;
   TVRectangle *bound;
};

enum Searchcode {searchexist = 0,
		 searchall = 1,};


// The index class

class TVTree {
    friend ostream& operator<< (ostream&, TVTree&);


public:
    
    // Initalize empty index
    TVTree();          // Initialize empty index
    TVTree(istream&);     // Initialize empty index, read in all the parameters 
			 // from standard input
    TVTree(istream&, int);  // Initialize empty index, read in all the parameters 
			   // (except number of phases, which is the second paramter)
                           //  from standard input
    TVTree(ifstream&);	   // Same as above, but reading from a file
    TVTree(ifstream&, int); // Same as above, but reading from a file
    TVTree(TVTree_Para&, int);  // Empty index, with parameter given

    // Copy function
    TVTree(const TVTree&); // Note: the tree is SHARED between the 2 implementations

    // Load an index from disk:
    //   filename  : Name of file
    //   ReadData  : Read the data to be indexed. Returned as the character(byte) array
    //               The integer will store the number of bytes at the end of the
    // 		     procedure.
    TVTree(char *filename, char *(*ReadData)(ifstream&, int&), VCOM_TYPE (*gfeat)(int, char*));  //  load an index from file

    ~TVTree();

    TVTree& operator=(const TVTree&);

    float GetMinFillPercent() const;  // get min_fill_percentage
    int GetUnfolddim() const;  // get dimensions to unfold

    int GetHeight() const; // Get Height of tree-> 0 one node

    void IncrementPhase();


    // Insertion
    TVTree& Insert(char *e, int size, VCOM_TYPE (*gfeat)(int, char*));
	
    TVTree& InsertElement(Leaf_Element&, VCOM_TYPE (*gfeat)(int, char*));  // insert an element;

    TVTree& InsertTVBranch(TVBranch &b);


    // Check validity
    int TVTree::ValidityCheck();

    // Save index
    void SaveTVTree(char* filename, void(*WriteData)(ofstream&, char *, int));

    // Print index
    ostream& TVTreePrint(ostream& os, void(*PrintData)(ostream&, char *), int oneperline = FALSE);

    // Gather statistics
    void PrintStats(ostream& os);
    void RecurGatherTreeStats(TVNode *n);
    void GatherTreeStats();
    int GetIntStat(int  code);

    // All searches routines below returns number of items in the result array 

    // Search (For exact match)
    // Parameters : 
    //   e    -- pointer to the object to be searched
    //   size -- # of bytes for object e
    //   res  -- Reference to an array of pointers, each entry points to an 
    //           array storing each of the element returned
    //   GetResult -- A procedure to extract the desired bytes from those who stored
    //   gfeat     -- Feature generation function.
    //   equal     -- Function check if e is equal to an element stored
    //
    //


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


    // Range searches:
    //   The algorithm with return all the objects which feature vectors have a Hamming distance
    //    less than "dist", and than use Distance() to filter out the unwanted results.
    //    (Note that the distance between the feature vector must be an underestimate to the real
    //     distance)
    //
    // Extra Parameters 
    //   dist : the distance  	
    //   Distance( , ) : A function to calculate the real distance between the two objects,
    // 			 to do the filtering.
    int Search(float dist, char *e, int size, char**& res, char *(GetResult)(char *, int, int&), VCOM_TYPE (*gfeat)(int, char*), float (*Distance)(char *, char *), Searchcode searchcode = searchall);

    // Same Range search function, but does not do the filtering
    int Search(float dist, char *e, int size, char**& res, char *(GetResult)(char *, int, int&), VCOM_TYPE (*gfeat)(int, char*),  Searchcode searchcode = searchall);


    // Feature search:
    // User provide an array of lower/upper distance from the search element
    // for each feature 
    // The user find points that fulfill all the conditions	
    //
    // Extra parameters
    //    fdim: number of features provided for lower and upper bound
    //    lbound : array storing the lower bound for each feature
    //    ubound : array storing the upper bound for each feature

    // (to do)
    int 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);

    int Count() const; // count number of elements in the tree

    // Free the memories for the tree
    void FreeTree();

private :

    int RecurSearch(TVNode *n, Leaf_Element& le,  LinkedList *reslist, VCOM_TYPE (*gfeat)(int, char*), int (*equal)(char *, char *), Searchcode searchcode);

    int RecurSearch(TVNode *n, Leaf_Element& le,  float dis, LinkedList *reslist, VCOM_TYPE (*gfeat)(int, char*), float (*Distance)(char *, char *), Searchcode searchcode = searchall);

    int RecurSearch(TVNode *n, Leaf_Element& le,  float dis, LinkedList *reslist, VCOM_TYPE (*gfeat)(int, char*), Searchcode searchcode = searchall);

    int RecurSearch(TVNode *n, TVRectangle& testrect, LinkedList *reslist, VCOM_TYPE (*gfeat)(int, char*), Searchcode searchcode);


    RecurInsertReturn RecurInsertElement(TVNode *, Leaf_Element, const TVNodehandle& nh, ReInsertClass&, VCOM_TYPE (*gfeat)(int, char*));
    TVTree& InsertElement1(Leaf_Element& e1, ReInsertClass& reinsertd, VCOM_TYPE (*gfeat)(int, char*));

    void NewRoot(RecurInsertReturn& rir, int rootlevel, ReInsertClass&, TVRectangle* rootbound = NULL);

    RecurInsertReturn RecurInsertTVBranch(TVNode *n, TVBranch &b, int level, const TVNodehandle& nh, ReInsertClass& reinsertd);
    TVTree& InsertTVBranch1(TVBranch &b, ReInsertClass &reinsertd);

    void RecurFreeTree(TVNode *n);


    TVNode *root;
    TVTree_Para ip;
    TVTree_Stat stats;

};