// ------------------------------- //
// -------- 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: 06/25/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();
}
char *InputData()
// Function used to read a string from the input stream.
// Returns a null terminated string or a null value if an
// error occurs. NOTE: The calling function must free the
// memory allocated for this string.
{
char buf[255];
for(unsigned i = 0; i < 255; i++) buf[i] = 0;
cout << "Input Data: ";
cin.getline(buf, sizeof(buf));
char *s = new char[strlen(buf)+1]; // Account for null terminator
if(!s) return 0;
strcpy(s, buf);
return s;
}
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 = InputData();
#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;
delete FileName;
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) {
delete FileName;
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;
delete FileName;
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 << "Verifing 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) {
delete FileName;
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;
delete FileName;
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) {
delete FileName;
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;
delete FileName;
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) {
delete FileName;
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;
delete FileName;
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();
delete FileName;
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 --------- //
// ------------------------------- //