tvnode.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: node.h,v 1.3 1996/04/18 21:50:24 kilin Exp kilin $ 
class TVNodeEntry;
class TVNode;
class Internal_TVNode;
class Leaf_TVNode;

class TVNodehandle {
   friend ostream& operator<<(ostream& os, const TVNodehandle& nh);

public:
  TVNodehandle();  // null handle
  TVNodehandle(TVNode* n);
  TVNodehandle(Internal_TVNode& n); // give a handle to the node
  TVNodehandle(Leaf_TVNode& n); // give a handle to the node
  TVNodehandle(const TVNodehandle&);

  TVNodehandle& operator=(const TVNodehandle&);

  // return the size of the handle (not the node)
  int bytes() const;

  TVNode* fetch() const; // fetch the node

  int write() const;  // write to secondary storage

  TVNodehandle& assign(Internal_TVNode&); // assign a handle
  TVNodehandle& assign(Leaf_TVNode&); // assign a handle
  TVNodehandle& assign(TVNode *);

  int null() const; // return TRUE if handle pts to nothing

  TVNodehandle& setnull(); // set the node handle to point to nothing

  void clearpage();

  PageNumber pagenum;

private:
  TVNode *ptr;
};





class TVBranch {
    friend ostream& operator<< (ostream&, const TVBranch&);
    friend ostream& operator<< (ostream&, const TVBranch*&);

public :
   
   TVBranch(); // Initialize an empty branch

   TVBranch(const TVRectangle&, TVNode*); // new rectangle with center and radius
   TVBranch(const TVBranch&);

   ~TVBranch();

   TVBranch& operator=(const TVBranch&); // assign the whole branch

   TVBranch& operator=(const TVRectangle&); // put in the rectangle as bound

   int Size() const;
   void ConnectChild(const TVNodehandle&);
   void DisconnectChild();
   TVRectangle GetBound() const;
   TVector GetCenter() const;
   float GetRadius() const;
   TVNode*  FetchChild();  // parameter to check whether to read from 
   TVNodehandle GetHandle() const; 


   // Update bound to accomodate all the children  
   // With requirement of minimum active dimensions
   // Note, one might need to expend more attribute from the leaves 
   TVBranch& UpdateBound(const TVector& v, int sig_dim = SIG_DIM);



   // Update bound to accomodate the rectangle
   // Given the number of active dimensions
   // Resulting bound may contract because of the new rectangle
   TVBranch& UpdateBound(const TVRectangle& d, int = SIG_DIM);


   // Set the bound to be rectangle passed in
   TVBranch& SetBound(const TVRectangle &d);

   // issue a write (child) to the disk
   void WriteChild();
   

private:
    
   TVRectangle bound;
   TVNodehandle child;

};


// A union type                                 
// Possible things that an entry of a node hold; 

enum FRType {not_defined = -1, is_branch = 0, is_leafele = 1};

class TVNodeEntry {

    friend ostream& operator<< (ostream&, TVNodeEntry&);
    friend ostream& operator<< (ostream&, TVNodeEntry*&);

public:
   TVNodeEntry();
   TVNodeEntry(TVBranch &);
   TVNodeEntry(Leaf_Element &);
   TVNodeEntry& operator=(const TVNodeEntry&);

   TVNodeEntry(const TVNodeEntry&);

   TVNodeEntry& Put(TVBranch &);
   TVNodeEntry& Put(Leaf_Element &);

   int Defined();

   FRType Type() const;

   TVRectangle GetTVRectangle();

   TVector GetTVector(int=0, VCOM_TYPE (*gfeat)(int, char*) = NULL);

   int Size();


   FRType ftype;
   union {
      TVBranch *b;
      Leaf_Element *e;
   } u;
};


// Used to compare which branch to take
   // Calculate initial value for first branch
   //
   //   The parameters used to determine which branch to take
   //      min_increase : min increase in radius
   //      max_dim      : maximum number of total dimension in new bound
   //      max_unfold_dim : maximum increase in total dimensions in new bound
   //      min_dist : minimum distance bewteen center of new rectangle and new element
   //      min_intersectcount : (similar to R*-tree)
   //                           Minimum number of new intersections with other bounds in the node
   //                           (i.e. the orginal bound does not intersect,
   //                                 but the new bound does)

class PickTVBranchCompare {

public:

   PickTVBranchCompare();

   int operator<(const PickTVBranchCompare&) const;
   int operator==(const PickTVBranchCompare&) const;

   int contained;
   float increase;
   int dim;
   int unfold_dim;
   float dist_from_center;
   int intersect_count;
};


// Base class for node
// Will inherit leaf node and internal node
// Enable polymorphism to simplify code

class SplitReturn;
class ReInsertClass;

class TVNode {

public :
    TVNode();          // Initialize a vector to be of no dimension
    TVNode(int);       // Initialize maxcount;
    TVNode(const TVNode&);

    virtual ~TVNode();

    TVNode& operator=(const TVNode&);

    int   MaxCount();  // return maximum count
    int   GetCount();    // return maximum count
    virtual int TVNodeType() const =0;  // type of node
    virtual int Size() const = 0;      // node size
    virtual int Put(const TVBranch&, int) = 0; // Store a branch, return NODE_FULL if full
    virtual int Put(const Leaf_Element&, int) = 0; // Store a element, return NODE_FULL if full

    virtual TVNodeEntry Fetch(int) const=0;

    virtual void WriteToDisk();
    virtual int Remove(int, float) = 0;  // remove a branch
    virtual int GetLevel() {return 0;} ;
    virtual SplitReturn Split(const TVBranch&, const TVNodehandle& nh, int = DEFAULT_PAGESIZE,   float = MIN_FILL_PERCENT, int = SIG_DIM) = 0;
    virtual SplitReturn Split(const Leaf_Element &e, const TVNodehandle& nh, VCOM_TYPE (*gfeat)(int, char*), int pagesize = DEFAULT_PAGESIZE, float min_fill_percent = MIN_FILL_PERCENT, int sig_dim = SIG_DIM) = 0;
    virtual void SetReInsert(const TVBranch&, ReInsertClass&, const TVNodehandle& nh, float = REINSERT_PERCENT, int = DEFAULT_PAGESIZE, float = MIN_FILL_PERCENT, int = SIG_DIM) = 0;
    virtual void SetReInsert(const Leaf_Element&, ReInsertClass&, const TVNodehandle& nh, float = REINSERT_PERCENT, int = DEFAULT_PAGESIZE, float = MIN_FILL_PERCENT, int = SIG_DIM) = 0;
    virtual int FixSize() = 0; // return fix size of the internal node


protected :
    int    count;      // current number of branches
    int    max_count;  // max. no of TVBranches
};


class Internal_Element;

class Internal_TVNode : public TVNode {

    friend ostream& operator<< (ostream&, const Internal_TVNode&);
    friend ostream& operator<< (ostream&, const Internal_TVNode*&);

public :
    Internal_TVNode();          // empty node
    Internal_TVNode(int, int);       // initialize node with maximum capacity
    Internal_TVNode(const Internal_TVNode&);

    ~Internal_TVNode();

    Internal_TVNode& Reinit();
    Internal_TVNode& operator=(const Internal_TVNode&);
    int TVNodeType() const;
    int Size() const;
    TVNodeEntry Fetch(int) const;
    int Put(const TVBranch&, int = DEFAULT_PAGESIZE); // Store a branch, return NODE_FULL if full
    int Put(const Leaf_Element&, int = DEFAULT_PAGESIZE) { assert(0); return 0;} ; // Store a element, return NODE_FULL if full
    int Remove(int, float);  // remove a branch
    int GetLevel() ;
    int ParentOfLeaf();
    TVRectangle MinBound(int = SIG_DIM);
    int FixSize(); // return fix size of the internal node
    SplitReturn Split(const TVBranch&, const TVNodehandle& nh, int = DEFAULT_PAGESIZE,  float = MIN_FILL_PERCENT, int = SIG_DIM);
    SplitReturn Split(const Leaf_Element &e, const TVNodehandle& nh, VCOM_TYPE (*gfeat)(int, char*), int pagesize = DEFAULT_PAGESIZE, float min_fill_percent = MIN_FILL_PERCENT, int sig_dim = SIG_DIM);
    virtual void SetReInsert(const TVBranch&, ReInsertClass&, const TVNodehandle& nh, float = REINSERT_PERCENT, int = DEFAULT_PAGESIZE, float = MIN_FILL_PERCENT, int = SIG_DIM);
    virtual void SetReInsert(const Leaf_Element&, ReInsertClass&, const TVNodehandle& nh, float = REINSERT_PERCENT, int = DEFAULT_PAGESIZE, float = MIN_FILL_PERCENT, int = SIG_DIM);

    int PickTVBranch(Leaf_Element& d0, VCOM_TYPE (*gfeat)(int, char*), int pbcc= DEFAULT_PICKBRANCH_COMPARE_COUNT, int sig_dim = SIG_DIM);
    int PickTVBranch(const TVRectangle& d0, int= DEFAULT_PICKBRANCH_COMPARE_COUNT, int sig_dim = SIG_DIM);


private :
    Internal_TVNode& ReDistribute(SplitReturn& sret, TVBranch *larray, int pagesize);
    PickTVBranchCompare PickTVBranchCal(Leaf_Element& le, int ent, VCOM_TYPE (*gfeat)(int, char *), int checkintersectcount, int sig_dim = SIG_DIM);
    PickTVBranchCompare PickTVBranchCal(const TVRectangle& d0, int ent, int checkintersectcount, int sig_dim = SIG_DIM);

    TVBranch *entry;    // array of branches
    int    level;     // level of the node in tree
                      // 0 = leaf, counting upwards

};


class Leaf_TVNode : public TVNode {

    friend ostream& operator<< (ostream&, const Leaf_TVNode&);
    friend ostream& operator<< (ostream&, const Leaf_TVNode*&);

public :
    Leaf_TVNode();          // empty node
    Leaf_TVNode(int);       // initialize node with maximum capacity
    Leaf_TVNode(const Leaf_TVNode&);

    ~Leaf_TVNode();

    Leaf_TVNode& Reinit();
    Leaf_TVNode& operator=(const Leaf_TVNode&);
    int TVNodeType() const;
    int Size() const;
    TVNodeEntry Fetch(int) const;
    int Put(const Leaf_Element&, int = DEFAULT_PAGESIZE); // Store a element, return NODE_FULL if full
    int Put(const TVBranch&, int = DEFAULT_PAGESIZE) {assert(0); return 0;} ; // Store a branch, return NODE_FULL if full
    int Remove(int, float = MIN_FILL_PERCENT);  // remove a branch
    int FixSize(); // return fix size of the leaf node

    // Find the minimum bounding region
    // Must have sig_dim number of active dimensions
    TVRectangle MinBound(VCOM_TYPE (*gfeat)(int, char*), int sig_dim = SIG_DIM);

    // Split
    SplitReturn Split(const TVBranch&, const TVNodehandle& nh, int = DEFAULT_PAGESIZE,  float = MIN_FILL_PERCENT, int = SIG_DIM);
    SplitReturn Split(const Leaf_Element &e, const TVNodehandle& nh, VCOM_TYPE (*gfeat)(int, char*), int pagesize = DEFAULT_PAGESIZE, float min_fill_percent = MIN_FILL_PERCENT, int sig_dim = SIG_DIM);

    // Select objects to reinsert
    virtual void SetReInsert(const TVBranch&, ReInsertClass&, const TVNodehandle& nh, float = REINSERT_PERCENT, int = DEFAULT_PAGESIZE, float = MIN_FILL_PERCENT, int = SIG_DIM);
    virtual void SetReInsert(const Leaf_Element&, ReInsertClass&, const TVNodehandle& nh, float = REINSERT_PERCENT, int = DEFAULT_PAGESIZE, float = MIN_FILL_PERCENT, int = SIG_DIM);

    // Print Leaf TVNode
    ostream& PrintLeaf(ostream& os,  void(*PrintData)(ostream&, char *), int oneperline = FALSE);

private :
    Leaf_TVNode& ReDistribute(SplitReturn& sret, Leaf_Element *larray, int pagesize);
   
    Leaf_Element *entry;    // array of branches
};


// This is a structure to store the stuff returned from
// the splitting procedures
// (pointer to the newly created node), pre-calculated bounds

class SplitReturn {

public:
  SplitReturn(int ent);
  SplitReturn(const SplitReturn&);

  SplitReturn& operator=(const SplitReturn&);

  int HasBound();
 
  ~SplitReturn();


  int entrycount; // number of entries

  int *distribute; // how the entries are to be distributed after splitting
		   // 0 = original node

  int parts;  // Parts that has been splitted (counting the original part)

  TVNode **newnode; // (thus if split into 3 parts, will consists of 2 new nodes)

  TVRectangle *bound; // ALL the new bounds (bound[0] = bound for original node)  

};


// Used to iterate all entries of a node

class TVNodeIter{

public:
    TVNodeIter();
    TVNodeIter(TVNode *);
    TVNodeIter(TVNode&);
    TVNodeIter(const TVNodeIter &);

    int GetLastIterInd();
    TVNodeEntry Iter();
    void Reset();
    int Count(); // return number of element of the node

private:
     TVNode *n;
     int  count;
};