TV.tar.gz_The Tree_tv tree_tv-tree source code

/* 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.C,v 1.3 1996/04/18 21:50:24 kilin Exp kilin $ // Please change sig_dim to active_dim #include <iostream.h> #include <assert.h> #include <stdlib.h> #include <fstream.h> #include "TVdefine.h" #include "TVconstants.h" #include "TVvector.h" #include "TVrectangle.h" //#include "TVrectangle.h" #include "TVelement.h" #include "TVsimbuf.h" #include "TVnode.h" #include "TVutil.h" #include "TVsplit.h" #include "TVreinsert.h" extern Storage *globstorage; TVNodehandle::TVNodehandle() { ptr = NULL; pagenum = -1; } TVNodehandle::TVNodehandle(Internal_TVNode& n) { ptr = (TVNode *)&n; pagenum = globstorage->newpage(); } TVNodehandle::TVNodehandle(TVNode* n) { ptr = n; pagenum = globstorage->newpage(); } TVNodehandle::TVNodehandle(Leaf_TVNode& n) { ptr = (TVNode *)&n; pagenum = globstorage->newpage(); } TVNodehandle::TVNodehandle(const TVNodehandle& nh) { ptr = nh.ptr; pagenum = nh.pagenum; } TVNodehandle& TVNodehandle::operator=(const TVNodehandle& nh) { ptr = nh.ptr; pagenum = nh.pagenum; return *this; } // return the size of the handle (not the node) // Assume all pointer have the same size int TVNodehandle::bytes() const { return sizeof(TVNode *); } TVNode* TVNodehandle::fetch() const { globstorage->fetch(pagenum); return ptr; } // return FALSE when write fail int TVNodehandle::write() const { if (pagenum > -1) globstorage->writepage(pagenum); return TRUE; } TVNodehandle& TVNodehandle::assign(Internal_TVNode& n) { ptr = (TVNode *)&n; pagenum = globstorage->newpage(); return *this; } TVNodehandle& TVNodehandle::assign(Leaf_TVNode& d) { ptr = (TVNode *)&d; pagenum = globstorage->newpage(); return *this; } TVNodehandle& TVNodehandle::assign(TVNode* d) { ptr = d; pagenum = globstorage->newpage(); return *this; } int TVNodehandle::null() const { return !ptr; } TVNodehandle& TVNodehandle::setnull() { ptr = NULL; if (pagenum > 0) { globstorage->clearpage(pagenum); pagenum = -1; } return *this; } void TVNodehandle::clearpage() { globstorage->clearpage(pagenum); } ostream& operator<<(ostream& os, const TVNodehandle& nh) { if (nh.ptr) os << "TVNode ptr : " << nh.ptr; os << " Page number : " << nh.pagenum; return os; } TVNode::TVNode() { count = 0; max_count = 0; } TVNode::TVNode(int maxc) { count = 0; max_count = maxc; } TVNode::TVNode(const TVNode &n) { count = n.count; max_count = n.max_count; } TVNode::~TVNode() { } TVNode& TVNode::operator=(const TVNode& n) { count = n.count; max_count = n.max_count; return *this; } int TVNode::MaxCount() { return max_count; } int TVNode::GetCount() { return count; } void TVNode::WriteToDisk() { // increase statistics } Internal_TVNode::Internal_TVNode() { level = -1; entry = NULL; } Internal_TVNode::Internal_TVNode(int l, int maxc) : TVNode(maxc) { level = l; entry = NULL; entry = new TVBranch[maxc]; } Internal_TVNode::Internal_TVNode(const Internal_TVNode &n) { count = n.count; max_count = n.max_count; level = n.level; entry = new TVBranch[n.max_count]; for (int i = 0; i < n.count; i++) entry[i] = n.entry[i]; } Internal_TVNode::~Internal_TVNode() { if (max_count > 0) { for (int j = 0; j < count ; j++) entry[j].TVBranch::~TVBranch(); delete [] entry; } } Internal_TVNode& Internal_TVNode::Reinit() { if (max_count > 0) { for (int j = 0; j < count ; j++) entry[j].TVBranch::~TVBranch(); delete [] entry; } entry = new TVBranch[max_count]; count = 0; return *this; } Internal_TVNode& Internal_TVNode::operator=(const Internal_TVNode& n) { if (max_count > 0) { for (int j = 0; j < count ; j++) entry[j].TVBranch::~TVBranch(); delete [] entry; } count = n.count; max_count = n.max_count; level = n.level; entry = new TVBranch[n.max_count]; for (int i = 0; i < n.count; i++) entry[i] = n.entry[i]; return *this; } int Internal_TVNode::TVNodeType() const { return INTERNAL_NODE; } int Internal_TVNode::Size() const { int bsize=0; for (int i=0; i < count; i++) bsize += entry[i].Size(); return sizeof(count) + sizeof(max_count) + sizeof(level) + bsize; } int Internal_TVNode::GetLevel() { return level; } int Internal_TVNode::ParentOfLeaf() { return level == PARENT_OF_LEAF; } TVNodeEntry Internal_TVNode::Fetch(int i) const { assert (i < max_count); TVNodeEntry f(entry[i]); return f; } int Internal_TVNode::Put(const TVBranch& b, int pagesize) { int result; // cout << "B.size, Size : " << b.Size() << ", " << Size() << "\n"; if (b.Size() + Size() <= pagesize) { if (count >= max_count) { // current array not big enough, create new one TVBranch *newentry = new TVBranch[max_count * 2]; max_count = max_count * 2; for (int i = 0; i < count ; i++) newentry[i] = entry[i]; newentry[count++] = b; delete [] entry; entry = newentry; } else { entry[count++] = b; result = NODE_NOT_FULL; } } else result = NODE_FULL; return result; } int Internal_TVNode::Remove(int bno, float min_fill_percent) { assert((bno < count) && (bno >= 0)); assert(min_fill_percent > 0); entry[bno] = entry[count - 1]; if (--(count) < min_fill_percent * max_count / 100.0) return(NODE_EMPTY); else return(NODE_NOT_EMPTY); } TVRectangle Internal_TVNode::MinBound(int sig_dim) { TVRectangle *darray = new TVRectangle[count]; for (int i = 0; i < count; i++) darray[i] = entry[i].GetBound(); delete [] darray; return (MinBoundTVRectangle(darray, count, sig_dim)); } int Internal_TVNode::FixSize() { return sizeof(int) * 3; } // Redistribute the nodes from the split return entries Internal_TVNode& Internal_TVNode::ReDistribute(SplitReturn& sret, TVBranch *barray, int pagesize) { Reinit(); if (sret.newnode) delete [] sret.newnode; if (sret.parts > 1) sret.newnode = new TVNode*[sret.parts - 1]; for (int i = 0; i < sret.parts - 1; i++) sret.newnode[i] = new Internal_TVNode(level, max(max_count, CONSERVE_MAX_BRANCH_FACTOR)); for (int j = 0; j < sret.entrycount; j++) { if (sret.distribute[j]) sret.newnode[sret.distribute[j] - 1]->Put(barray[j], pagesize); else Put(barray[j], pagesize); } return *this; } SplitReturn Internal_TVNode::Split(const TVBranch &b, const TVNodehandle& thishandle, int pagesize, float min_fill_percent, int sig_dim) { // cout << "----------\n"; // cout << "Splitting :\n"; // for (int xyy = 0; xyy < count