// ------------------------------- // // -------- Start of File -------- // // ------------------------------- // // ----------------------------------------------------------- // // C++ Source Code File Name: gxbtree.cpp // Compiler Used: MSVC, BCC32, GCC, HPUX aCC, SOLARIS CC // Produced By: glNET Software // File Creation Date: 08/22/2000 // Date Last Modified: 08/27/2001 // Copyright (c) 2001 glNET Software // ----------------------------------------------------------- // // ------------- Program Description and Details ------------- // // ----------------------------------------------------------- // /* This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA Dictionary example using the balanced multiway tree class. */ // ----------------------------------------------------------- // #include <iostream.h> #include <fstream.h> #include <string.h> #include <time.h> #include "gxbtree.h" const BtreeNodeOrder_t MyKeyClassOrder = 27; const __WORD__ MyKeyNameSize = 26; class MyKeyClass : public DatabaseKeyB { public: MyKeyClass(); MyKeyClass(const char *name); void operator=(const char *name); ~MyKeyClass() { } public: // Base class interface size_t KeySize() { return sizeof(key_name); } int operator==(const DatabaseKeyB& key) const; int operator>(const DatabaseKeyB& key) const; public: // Persistent data member char key_name[MyKeyNameSize]; }; MyKeyClass::MyKeyClass() : DatabaseKeyB((char *)key_name) { for(int i = 0; i < MyKeyNameSize; i++) key_name[i] = 0; } MyKeyClass::MyKeyClass(const char *name) : DatabaseKeyB((char *)key_name) { strncpy(key_name, name, MyKeyNameSize); key_name[ MyKeyNameSize-1] = 0; // Ensure null termination } void MyKeyClass::operator=(const char *name) { strncpy(key_name, name, MyKeyNameSize); key_name[ MyKeyNameSize-1] = 0; // Ensure null termination } int MyKeyClass::operator==(const DatabaseKeyB& key) const { const MyKeyClass *kptr = (const MyKeyClass *)(&key); return (strcmp(key_name, (char *)kptr->db_key) == 0); } int MyKeyClass::operator>(const DatabaseKeyB& key) const { const MyKeyClass *kptr = (const MyKeyClass *)(&key); return (strcmp(key_name, (char *)kptr->db_key) > 0); } void PausePrg() { cout << endl; cout << "Press enter to continue..." << endl; cin.get(); } void BtreeStatus(gxBtree &btx) { cout << endl; cout << "Root address = " << btx.Root() << endl; cout << "Number of entries = " << btx.NumKeys() << endl; cout << "Number of nodes = " << btx.NumNodes() << endl; cout << "Btree order = " << btx.NodeOrder() << endl; cout << "Btree height = " << btx.BtreeHeight() << endl; PausePrg(); } int ParseString(char *string, char words[255][255], int*numwords, char sepchar) // General purpose string parser { int i = 0; char newword[255]; *numwords = 0; // First skip over leading blanks. Stop if an ASCII NULL is seen while (1) { if (*string == '\0') return 0; if (*string != ' ') break; string++; } while(1) { // Check to see if there is room for another word in the array if(*numwords == 255) return 1; i = 0; while (i < 255) { if(*string == 0 || *string == sepchar) break; newword[i] = *string; string++; i++; } newword[i] = 0; // Ensure an ASCII null at end of newword. strcpy (words[*numwords], newword); // Install into array (*numwords)++; // If stopped by an ASCII NULL above, exit loop if(*string == 0) break; string++; if(*string == 0) break; } return 0; } int ImportTextFile(gxBtree &btx) { cout << endl; cout << "Importing a dictionary file." << endl; cout << "NOTE: Words must be delimited by a space or forward slash (/)" << endl; int status, num, i, key_count = 0; char words[255][255]; const int MaxLine = 255; char LineBuffer[MaxLine]; const char dchar = '/'; // Text delimiter cout << endl; cout << "Enter the name of the text file to import" << endl; char *FileName = "amerdict.txt"; #ifdef __BCC32__ // The BCC 32 ios class does not have an enumeration for "nocreate" ifstream istream(FileName, ios::in); #else ifstream istream(FileName, ios::in|ios::nocreate); #endif if(!istream) { // Could not open the istream cout << "Could not open file: " << FileName << endl; return 1; } cout << "Adding words..." << endl; // Get CPU clock cycles before entering loop clock_t begin = clock(); MyKeyClass key; MyKeyClass compare_key; while(1) { for(i = 0; i < MaxLine; i++) LineBuffer[i] = 0; // Clear the line buffer // Read in file line by line istream.getline(LineBuffer, MaxLine); if(ParseString(LineBuffer, words, &num, dchar) == 1) { return 1; } if(istream.eof()) break; // Exit loop at EOF if(strcmp(LineBuffer, "") == 0) continue; key = LineBuffer; status = btx.Insert(key, compare_key, 0); if (status != 1) { cout << endl << "Problem adding " << words[0] << endl; return 1; } else { key_count++; } } // Get CPU clock cycles after loop is completed clock_t end =clock(); // Calculate the elapsed time in seconds. double elapsed_time = (double)(end - begin) / CLOCKS_PER_SEC; cout.precision(3); cout << "Added " << key_count << " words in " << elapsed_time << " seconds" << endl; BtreeStatus(btx); // Rewind the file #ifdef __BCC32__ istream.close(); istream.open(FileName, ios::in); #else istream.seekg(0, ios::beg); istream.clear(); #endif cout << "Verifying the entries..." << endl; begin = clock(); key_count = 0; double search_time = 0; while(1) { for(i = 0; i < MaxLine; i++) LineBuffer[i] = 0; // Clear the line buffer // Read in file line by line istream.getline(LineBuffer, MaxLine); if(ParseString(LineBuffer, words, &num, dchar) == 1) { return 1; } if(istream.eof()) break; // Exit loop at EOF if(strcmp(LineBuffer, "") == 0) continue; key = LineBuffer; clock_t begin_search = clock(); status = btx.Find(key, compare_key, 0); clock_t end_search = clock(); search_time += (double)(end_search - begin_search) / CLOCKS_PER_SEC; if (status != 1) { cout << endl << "Problem finding " << words[0] << endl; return 1; } else { key_count++; } } end =clock(); elapsed_time = (double)(end - begin) / CLOCKS_PER_SEC; cout.precision(3); cout << "Verified " << key_count << " words in " << elapsed_time << " seconds" << endl; double avg_search_time = (search_time/(double)key_count) * 1000; cout << "Average search time = " << avg_search_time << " milliseconds" << endl; PausePrg(); // Rewind the file #ifdef __BCC32__ istream.close(); istream.open(FileName, ios::in); #else istream.seekg(0, ios::beg); istream.clear(); #endif cout << "Deleting the entries..." << endl; begin = clock(); key_count = 0; while(1) { for(i = 0; i < MaxLine; i++) LineBuffer[i] = 0; // Clear the line buffer // Read in file line by line istream.getline(LineBuffer, MaxLine); if(ParseString(LineBuffer, words, &num, dchar) == 1) { return 1; } if(istream.eof()) break; // Exit loop at EOF if(strcmp(LineBuffer, "") == 0) continue; key = LineBuffer; status = btx.Delete(key, compare_key, 0); // status = btx.LazyDelete(key, compare_key, 0); if (status != 1) { cout << endl << "Problem deleting " << words[0] << endl; return 1; } else { key_count++; } } end =clock(); cout.precision(3); elapsed_time = (double)(end - begin) / CLOCKS_PER_SEC; cout << "Deleted " << key_count << " words in " << elapsed_time << " seconds" << endl; BtreeStatus(btx); // Rewind the file #ifdef __BCC32__ istream.close(); istream.open(FileName, ios::in); #else istream.seekg(0, ios::beg); istream.clear(); #endif cout << "Re-inserting all the words..." << endl; key_count = 0; begin = clock(); while(1) { for(i = 0; i < MaxLine; i++) LineBuffer[i] = 0; // Clear the line buffer // Read in file line by line istream.getline(LineBuffer, MaxLine); if(ParseString(LineBuffer, words, &num, dchar) == 1) { return 1; } if(istream.eof()) break; // Exit loop at EOF if(strcmp(LineBuffer, "") == 0) continue; key = LineBuffer; status = btx.Insert(key, compare_key, 0); if (status != 1) { cout << endl << "Problem adding " << words[0] << endl; return 1; } else { key_count++; } } end =clock(); cout.precision(3); elapsed_time = (double)(end - begin) / CLOCKS_PER_SEC; cout << "Added " << key_count << " words in " << elapsed_time << " seconds" << endl; BtreeStatus(btx); istream.close(); return 0; } int main() { const char *fname = "testfile.btx"; MyKeyClass key, kbuf; gxBtree btx(key, MyKeyClassOrder); // Create a new tree btx.Create(fname); ImportTextFile(btx); cout << "Exiting..." << endl; return 0; } // ----------------------------------------------------------- // // ------------------------------- // // --------- End of File --------- // // ------------------------------- //