#ifndef BTREE_H #define BTREE_H #define LNEG -100000000 #include #include using namespace std; namespace iret { const int order = 5; //Half the order of the Btree that we build. const int height_limit =12; //Limit on the height of the Btree. const int ord2 = order*2; //The order of the Btree. int stc_my(int &,int &,const char *,const char *); //Function used to compare //two strings. The first two arguments hold information about how much the //string can be ignored in the comparison. class Page; //forward declaration class Btree; //forward declaration class Partial_match; //forward declaration class Node { friend int stc_my(int &,int &,const char *,const char *); friend class Page; friend class Btree; friend class List; friend class Count; friend class FCount; friend class DCount; template friend class BCount; friend class Partial_match; friend class Thes; public: Node(void); //Sets all points to NULL. Node(const char * ); //Argument is the string for this node. Node(const char * ,void *); //Arguments are first the string and then the //data pointer. ~Node(); void debug(); //Prints out the node in simple format. private: char *str; //String pointer. void *rel; //Data pointer. Page *pdn; //Points down to the page below or to NULL. }; class Page { friend int stc_my(int &,int &,const char *,const char *); friend class Btree; friend class Partial_match; friend class FCount; friend class DCount; public: Page(); //Constructs a new empty page. Only happens at the root. Page(Page * const pz,Page * const pn,const int n); //Constructs a page that //holds the right half of a full page. The full page is pointed at by the //pz. The new pages downward pointer is set to pn. //n tells how much of the full page is to remain or where to begin removal. ~Page(); void clean(void); //Used to delete without touching search keys in the nodes //which were created with addp functions and do not belong to the tree. void insert(const int n,Node * const nd,const int j); //inserts in partially empty //page. n is insertion point, j is number of nodes on page that are viable. int search(int &a,int &b,const char *,int &p); //searches for string on //the page. Returns 1 if found, 0 otherwise. If found p is the index, otherwise //if p is 0 then the page downward pointer is to next page to search, but if //p is positive then p-1 is number of node that has the downward pointer to //next page to search. int search(int &a,int &b,char *,int &p,Partial_match *btr); //Looks for longest //partial match. void debug(); //Prints out the page for debugging purposes. private: char ndnm; //Indicates the number of Nodes on the page. Page *pdn; //Pointer that points to the page below and also lexically below. //May be NULL. Node *pnd[ord2]; //Pointers to the nodes on the page. Some may be NULL. }; class Btree { friend class Page; public: Btree(void); Btree(ifstream &); //Reads in a Btree in form of list written out by //list_write() from disc. String arguments mark the path in proj file. Btree( const Btree & btree ) {copy = true; root = btree.root;} // Actually // creates another reference to the same tree. Take great care to // avoid simultaneously modifying both copies. ~Btree(void); int search(const char *); //Searches for a string and sets the path to that //string or its insertion point. int insert(Node *);//Only to be called after a search has failed to find the //string. void node_first();//Finds the first node in the tree and sets the path to it. int node_next(); //Given the path is already set to a node, this function //finds the next node in lexicographic order. char *show_str();//Used to show the string after a call to next is successful. void *give_ptr();//Used to give the data pointer in the current node. void set_ptr(void *); //Used to set the data pointer after a call to search //has found string. int add(Node *); //Only to be used to construct a tree from a lexical list //as written out by list_write(); void next_empty(); //Only used to reset the pointer arrays when the root is //split. Used in add(). long list_write(ofstream &); //Writes out a lexical list of the strings in //the tree. int iclean; //Default 0, but set to 1 if want to have destructor run without //touching key strings (if addp used in making tree). protected: int depth; //Tells the depth in the tree that marks the current location. Page *root; //Points at the root page of the tree. Page *pg[height_limit]; //Descending list of pointers that mark the pages. int cnd[height_limit]; //Mark the positions of the nodes just above the //downard page pointer at each level. Thus 0 marks the page's downward //pointer, but a nonzero value must have 1 subtracted and then it gives //the node whose downward pointer is the correct downward pointer. bool copy; //flags copies of a tree with true. }; class List : public Btree { public: List(); List(const List & list) : Btree(list) {} ~List(); void add_key(const char *str); //Adds the string *str to the tree if not already in list void add_key_count(const char *str); //Adds the string *str to the tree if //not already in list and counts it. void addp_key_count(char *str); //Adds the string *str to the tree if //not already in list and counts it. Uses the actual string pointer instead //of making a copy long cnt_key; //Used to count the number of keys. }; class Count : public List { public: Count(); Count(const Count & Ct) : List(Ct){} ~Count(); void add_count(const char *str,long n); //Adds the string *str with its count //to the tree if not already in list. String is key and count is data. //If string is already a key the count is incremented by n. void add_countz(const char *str,long n); //Adds the string *str with its count //just as add_count, but also counts number of unique keys in count. //Does not add count to the total variable, unlike add_count2. void add_count2(const char *str,long n); //Adds the string *str with its count //just as add_count, but also counts number of unique keys in count. void addp_count2(char *str,long n); //Adds the string *str with its count //just as add_count, but also counts number of unique keys in count. //Does not make copy of string, but uses the pointer str as key pointer. void correct(const char *str,long n); //If str is in the tree the count is //changed to n. Otherwise nothing is done. //Functions for maximum calculation void max_count(const char *str,long n); //Adds the string *str with its count //to the tree if not already in list. String is key and count is data. //If string is already a key the count is max of n and prior value. void max_count2(const char *str,long n); //Adds the string *str with its count //just as max_count, but also counts number of unique keys in count. void maxp_count2(char *str,long n); //Adds the string *str with its count //just as max_count, but also counts number of unique keys in count. //Does not make copy of string, but uses the pointer str as key pointer. //Functions for minium calculation void min_count(const char *str,long n); //Adds the string *str with its count //to the tree if not already in list. String is key and count is data. //If string is already a key the count is min of n and prior value. void min_count2(const char *str,long n); //Adds the string *str with its count //just as min_count, but also counts number of unique keys in count. void minp_count2(char *str,long n); //Adds the string *str with its count //just as min_count, but also counts number of unique keys in count. //Does not make copy of string, but uses the pointer str as key pointer. long count(const char *str); //Returns the count if a key (in list) otherwise //returns 0. long count(void); //Returns the count of the current string. Assumes the //pointers have already been set by a search or node_next call. long total; //Holds the total of all counts added for all keys. }; class FCount : public List { public: FCount(); FCount(const FCount & Ct) : List(Ct){} ~FCount(); void Copy(FCount &Dc); //Makes a copy of the tree Dc in the current tree. void add_count(const char *str,float z); //Adds the string *str with its count //to the tree if not already in list. String is key and count is data. //If string is already a key the count is incremented by z. void add_count2(const char *str,float z); //Adds the string *str with its count //just as add_count, but also counts number of unique keys in count. void addp_count2(char *str,float z); //Adds the string *str with its count //just as add_count, but also counts number of unique keys in count. //Does not make copy of string, but uses the pointer str as key pointer. float count(const char *str); //Returns the count if a key (in list) otherwise //returns 0. float count(void); //Returns the count of the current string. Assumes the //pointers have already been set by a search or node_next call. float total; //Holds the total of all counts added for all keys. }; class DCount : public List { public: DCount(); DCount(const DCount & Ct) : List(Ct){} ~DCount(); void Copy(DCount &Dc); //Makes a copy of the tree Dc in the current tree. void add_count(const char *str,double z); //Adds the string *str with its count //to the tree if not already in list. String is key and count is data. //If string is already a key the count is incremented by z. void add_count2(const char *str,double z); //Adds the string *str with its count //just as add_count, but also counts number of unique keys in count. void addp_count2(char *str,double z); //Adds the string *str with its count //just as add_count, but also counts number of unique keys in count. //Does not make copy of string, but uses the pointer str as key pointer. double count(const char *str); //Returns the count if a key (in list) otherwise //returns 0. double count(void); //Returns the count of the current string. Assumes the //pointers have already been set by a search or node_next call. //Functions for maximum calculation void max_count(const char *str,double z); //Adds the string *str with its count //to the tree if not already in list. String is key and count is data. //If string is already a key the count is max of z and prior value. void max_count2(const char *str,double z); //Adds the string *str with its count //just as max_count, but also counts number of unique keys in count. void maxp_count2(char *str,double z); //Adds the string *str with its count //just as max_count, but also counts number of unique keys in count. //Does not make copy of string, but uses the pointer str as key pointer. //Functions for minium calculation void min_count(const char *str,double z); //Adds the string *str with its count //to the tree if not already in list. String is key and count is data. //If string is already a key the count is min of z and prior value. void min_count2(const char *str,double z); //Adds the string *str with its count //just as min_count, but also counts number of unique keys in count. void minp_count2(char *str,double z); //Adds the string *str with its count //just as min_count, but also counts number of unique keys in count. //Does not make copy of string, but uses the pointer str as key pointer. void debug(void); //Prints to stdout a list "i str[i]" double total; //Holds the total of all counts added for all keys. }; class Partial_match : public Count { friend class Page; public: Partial_match(); Partial_match(const Partial_match & Par_mat) : Count(Par_mat){} ~Partial_match(); void long_match(char *,List &); //Finds the longest matches for all word //starts in the string and adds them to the list. void local_match(char *,List &); //Finds all matches that start at //beginning of the string and adds them to the list. void all_match(char *,List &); //Finds all matches within the string and //adds them to the list. void long_match(char *,Count &,long n); //Finds the longest matches for all word //starts in the string and adds them to the list in Count. void local_match(char *,Count &,long n); //Finds all matches that start at //beginning of string and adds them to the list in Count. void all_match(char *,Count &,long n); //Finds all matches within the string and //adds them to the list in Count. int search_long(char *); //Searches for longest partial match to an initial //segment of a string that ends at a word boundary and //sets the path to that string or its insertion point. private: int stc_my_long(int &,int &,char *,const char *,int); //Function used to compare //two strings. The first two arguments hold information about how much the //string can be ignored in the comparison. The last argument holds the index //or number of the string's node on the page. int step_one(int &,int &,char *); //Looks for partial or complete match and //returns 1 if complete found. Partial is reflected in parameters. //Special parameters used in partial matching. int depth_o; //Depth of longest partial match thus far. int index_o; //index of longest partial match thus far. int cln_o; //String length of longest partial match thus far. int len; //Length of query string. int cln; //Current null position in string. }; class Str_str : public Btree { public: Str_str(); Str_str(const Str_str & Stst) : Btree(Stst){} ~Str_str(); void add_pair(const char *one,const char *two); //Adds the string *one to the tree and stores //the string *two at that node. char *match(const char *one); //Returns pointer to the string stored under string *one. }; class Num_num : public Btree { public: Num_num(); Num_num(const Num_num & Nmnm) : Btree(Nmnm){} ~Num_num(); void add_pair(long i, long j); //Adds the string for i to the tree and //stores the number j at that node. long match(long i); //Returns the number stored under the string for i. }; template class BCount : public List { public: BCount(); BCount(const BCount & Ct) : List(Ct){} ~BCount(); void add_count(const char *str,Z n); //Adds the string *str with its count //to the tree if not already in list. String is key and count is data. //If string is already a key the count is incremented by n. void add_count2(const char *str,Z n); //Adds the string *str with its count //just as add_count, but also counts number of unique keys in count. void addp_count2(char *str,Z n); //Adds the string *str with its count //just as add_count, but also counts number of unique keys in count. //Does not make copy of string, but uses the pointer str as key pointer. void correct(const char *str,Z n); //If str is in the tree the count is //changed to n. Otherwise nothing is done. //Functions for maximum calculation void max_count(const char *str,Z n); //Adds the string *str with its count //to the tree if not already in list. String is key and count is data. //If string is already a key the count is max of n and prior value. void max_count2(const char *str,Z n); //Adds the string *str with its count //just as max_count, but also counts number of unique keys in count. void maxp_count2(char *str,Z n); //Adds the string *str with its count //just as max_count, but also counts number of unique keys in count. //Does not make copy of string, but uses the pointer str as key pointer. //Functions for minium calculation void min_count(const char *str,Z n); //Adds the string *str with its count //to the tree if not already in list. String is key and count is data. //If string is already a key the count is min of n and prior value. void min_count2(const char *str,Z n); //Adds the string *str with its count //just as min_count, but also counts number of unique keys in count. void minp_count2(char *str,Z n); //Adds the string *str with its count //just as min_count, but also counts number of unique keys in count. //Does not make copy of string, but uses the pointer str as key pointer. Z count(const char *str); //Returns the count if a key (in list) otherwise //returns 0. Z count(void); //Returns the count of the current string. Assumes the //pointers have already been set by a search or node_next call. Z total; //Holds the total of all counts added for all keys. }; template BCount::BCount() : List() { total=0; } template BCount::~BCount(){ if(copy)return; Z *pk; this->node_first(); while(this->node_next()){ pk=(Z *)(this->give_ptr()); if(pk)delete pk; } } template void BCount::add_count(const char *pch,Z n){ Z *ppt; Node *np; total+=n; if(this->search(pch)==0){ ppt = new Z; (*ppt) =n; np=new Node(pch,(void*)ppt); this->insert(np); } else { (*(Z *) this->give_ptr())+=n; } } template void BCount::add_count2(const char *pch,Z n){ Z *ppt; Node *np; total+=n; if(this->search(pch)==0){ ppt = new Z; (*ppt) =n; np=new Node(pch,(void*)ppt); this->insert(np); cnt_key++; } else { (*(Z *) this->give_ptr())+=n; } } template void BCount::addp_count2(char *pch,Z n){ Z *ppt; Node *np; total+=n; if(this->search(pch)==0){ ppt = new Z; (*ppt) =n; np=new Node; np->str=pch; np->rel=ppt; this->insert(np); cnt_key++; } else { (*(Z *) this->give_ptr())+=n; } } template void BCount::correct(const char *pch,Z n){ if(this->search(pch)){ (*(Z *) this->give_ptr())=n; } } template Z BCount::count(const char *pch){ if(this->search(pch)==0){ return(0); } else { return(*((Z *) this->give_ptr())); } } template Z BCount::count(void){ return(*((Z *) this->give_ptr())); } template void BCount::max_count(const char *pch,Z n){ Z *ppt,i; Node *np; total+=n; if(!search(pch)){ ppt = new Z; (*ppt) =n; np=new Node(pch,(void*)ppt); this->insert(np); } else { ppt=(Z *)give_ptr(); if(*ppt void BCount::max_count2(const char *pch,Z n){ Z *ppt,i; Node *np; total+=n; if(!search(pch)){ ppt = new Z; (*ppt) =n; np=new Node(pch,(void*)ppt); this->insert(np); cnt_key++; } else { ppt=(Z *)give_ptr(); if(*ppt void BCount::maxp_count2(char *pch,Z n){ Z *ppt,i; Node *np; total+=n; if(!search(pch)){ ppt = new Z; (*ppt) =n; np=new Node; np->str=pch; np->rel=ppt; this->insert(np); cnt_key++; } else { ppt=(Z *)give_ptr(); if(*ppt void BCount::min_count(const char *pch,Z n){ Z *ppt,i; Node *np; total+=n; if(!search(pch)){ ppt = new Z; (*ppt) =n; np=new Node(pch,(void*)ppt); this->insert(np); } else { ppt=(Z *)give_ptr(); if(*ppt>n)*ppt=n; } } template void BCount::min_count2(const char *pch,Z n){ Z *ppt,i; Node *np; total+=n; if(!search(pch)){ ppt = new Z; (*ppt) =n; np=new Node(pch,(void*)ppt); this->insert(np); cnt_key++; } else { ppt=(Z *)give_ptr(); if(*ppt>n)*ppt=n; } } template void BCount::minp_count2(char *pch,Z n){ Z *ppt,i; Node *np; total+=n; if(!search(pch)){ ppt = new Z; (*ppt) =n; np=new Node; np->str=pch; np->rel=ppt; this->insert(np); cnt_key++; } else { ppt=(Z *)give_ptr(); if(*ppt>n)*ppt=n; } } } #endif