// ------------------------------- //
// -------- Start of File -------- //
// ------------------------------- //
// ----------------------------------------------------------- //
// C++ Source Code File Name: testprog.cpp
// Compiler Used: MSVC, BCC32, GCC, HPUX aCC, SOLARIS CC
// Produced By: DataReel Software Development Team
// File Creation Date: 11/07/1996
// Date Last Modified: 06/17/2016
// Copyright (c) 2001-2024 DataReel Software Development
// ----------------------------------------------------------- //
// ------------- 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
Test program for the generic binary search tree class.
*/
// ----------------------------------------------------------- //
#include "gxdlcode.h"
#if defined (__USE_ANSI_CPP__) // Use the ANSI Standard C++ library
#include <iostream>
using namespace std; // Use unqualified names for Standard C++ library
#else // Use the old iostream library by default
#include <iostream.h>
#endif // __USE_ANSI_CPP__
#include <stdio.h>
#include <time.h>
#include "gxbstree.h"
#include "bstreei.h"
#include "ustring.h"
#include "dfileb.h"
#ifdef __MSVC_DEBUG__
#include "leaktest.h"
#endif
void InputData(UString &sbuf)
// Input a line of text from the console
{
char buf[255];
cout << "Input Data: ";
cin.getline(buf, sizeof(buf));
sbuf = buf;
}
void ClearInputStream(istream &s)
// Used to clear istream
{
char c;
s.clear();
while(s.get(c) && c != '\n') { ; }
}
int Quit()
// Terminate the program
{
cout << "Exiting..." << "\n";
return 0;
}
void PausePrg()
// Pause the program
{
cout << "\n";
cout << "Press enter to continue..." << "\n";
cin.get();
}
void Menu(void)
// List the program options
{
cout << "(A, a) Add an item to the tree" << "\n";
cout << "(B, b) Build a tree of strings" << "\n";
cout << "(C, c) Clear the tree" << "\n";
cout << "(D, d) Delete an item from the tree" << "\n";
cout << "(E, e) Extract all the node in sort order" << "\n";
cout << "(F, f) Find an item in the tree" << "\n";
cout << "(H, h, ?) Help (prints this menu)" << "\n";
cout << "(I, i) Import a dictionary file" << "\n";
cout << "(L, l) List tree items in order" << "\n";
cout << "(Q, q) Quit this program" << "\n";
cout << "(S, s) Display the tree statistics" << "\n";
cout << "(R, r) Extract all the node in reverse order" << "\n";
cout << "(T, t) Test tree insertion/deletion times" << "\n";
}
unsigned TreeHeight(gxBStreeNode_t *node)
// Recursive function used to calculate the tree height based
// on the maximum of the height of right and left subtrees.
{
unsigned height = 0;
if(node != 0) {
unsigned left_height = TreeHeight(node->left);
unsigned right_height = TreeHeight(node->right);
if(left_height > right_height) {
height = left_height+1;
}
else {
height = right_height+1;
}
}
return height;
}
void NumNodes(gxBStreeNode_t *node, unsigned &num_nodes)
// Recursive function used to calculate the total number of nodes.
{
while(node) {
NumNodes(node->left, num_nodes);
num_nodes++;
node = node->right;
}
}
void TreeStats(gxBStree<UString> &tree)
{
cout << "\n";
cout << "----- Binary search tree statistics -----" << "\n";
cout << "\n";
if(tree.IsEmpty()) {
cout << "The tree is empty" << "\n";
return;
}
unsigned num_nodes = 0;
unsigned height = 0;
NumNodes(tree.GetRoot(), num_nodes);
height = TreeHeight(tree.GetRoot());
cout << "Number of nodes = " << num_nodes << "\n";
cout << "Height = " << height << "\n";
cout << "\n";
UString root, first, last;
cout << "Root node = " << tree.GetRoot()->data << "\n";
if(tree.FindFirst(first))
cout << "First key = " << first << "\n";
if(tree.FindLast(last))
cout << "Last key = " << last << "\n";
cout << "\n";
}
void ImportDictionaryFile(gxBStree<UString> &tree)
// Import a list of words in sort order. This function demonstrates
// how unbalanced trees are degenerated when a sort ordered list of
// items are inserted into the tree.
{
cout << "\n";
cout << "Importing a dictionary file." << "\n";
tree.Clear(); // Clear the tree before importing the file
char LineBuffer[df_MAX_LINE_LENGTH];
int status, key_count = 0;
UString key;
UString FileName;
cout << "\n";
cout << "Enter the name of the text file to import" << "\n";
InputData(FileName);
DiskFileB infile(FileName.c_str());
if(!infile) { // Could not open the istream
cout << "Could not open file: " << FileName << "\n";
return;
}
cout << "Adding words..." << "\n";
// Get CPU clock cycles before entering loop
clock_t begin = clock();
while(!infile.df_EOF()) {
if(infile.df_GetLine(LineBuffer, df_MAX_LINE_LENGTH, '\n', 1) !=
DiskFileB::df_NO_ERROR) {
break; // Error reading from the disk file
}
if(strcmp(LineBuffer, "") == 0) continue;
key = LineBuffer;
cout << key.c_str() << "\n";
status = tree.Insert(key);
if(status != 1) {
cout << "\n" << "Problem adding " << key.c_str() << "\n";
return;
}
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" << "\n";
// Rewind the file
infile.df_Rewind();
cout << "Verifying the entries..." << "\n";
begin = clock();
key_count = 0;
double search_time = 0;
while(!infile.df_EOF()) {
if(infile.df_GetLine(LineBuffer, df_MAX_LINE_LENGTH, '\n', 1) !=
DiskFileB::df_NO_ERROR) {
break; // Error reading from the disk file
}
if(strcmp(LineBuffer, "") == 0) continue;
key = LineBuffer;
clock_t begin_search = clock();
status = tree.Find(key);
clock_t end_search = clock();
search_time += (double)(end_search - begin_search) / CLOCKS_PER_SEC;
if (status != 1) {
cout << "\n" << "Problem finding " << key << "\n";
return;
}
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" << "\n";
double avg_search_time = (search_time/(double)key_count) * 1000;
cout << "Average search time = " << avg_search_time << " milliseconds"
<< "\n";
PausePrg();
// Rewind the file
infile.df_Rewind();
cout << "Deleting the entries..." << "\n";
begin = clock();
key_count = 0;
while(!infile.df_EOF()) {
if(infile.df_GetLine(LineBuffer, df_MAX_LINE_LENGTH, '\n', 1) !=
DiskFileB::df_NO_ERROR) {
break; // Error reading from the disk file
}
if(strcmp(LineBuffer, "") == 0) continue;
key = LineBuffer;
status = tree.Delete(key);
if (status != 1) {
cout << "\n" << "Problem deleting " << key << "\n";
return;
}
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" << "\n";
// Rewind the file
infile.df_Rewind();
cout << "Re-inserting all the words..." << "\n";
key_count = 0;
begin = clock();
while(!infile.df_EOF()) {
if(infile.df_GetLine(LineBuffer, df_MAX_LINE_LENGTH, '\n', 1) !=
DiskFileB::df_NO_ERROR) {
break; // Error reading from the disk file
}
if(strcmp(LineBuffer, "") == 0) continue;
key = LineBuffer;
status = tree.Insert(key);
if (status != 1) {
cout << "\n" << "Problem adding " << key << "\n";
return;
}
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" << "\n";
infile.df_Close();
return;
}
void BuildTree(gxBStree<UString> &tree)
// Build a tree of strings.
{
char *aa1 = "dog";
char *bb1 = "cat";
char *cc1 = "fish";
char *dd1 = "mouse";
char *ee1 = "bird";
char *ff1 = "pig";
char *gg1 = "horse";
char *hh1 = "lion";
char *ii1 = "snake";
char *jj1 = "cow";
char *kk1 = "armadillo";
char *ll1 = "grouper";
char *mm1 = "rat";
char *nn1 = "monkey";
char *oo1 = "zebra";
char *pp1 = "starfish";
char *qq1 = "lizard";
char *rr1 = "crab";
char *ss1 = "snail";
char *tt1 = "gorilla";
char *uu1 = "lobster";
char *vv1 = "turkey";
char *ww1 = "beetle";
char *xx1 = "shark";
char *yy1 = "clam";
char *zz1 = "oyster";
char *keys[26] = { aa1, bb1, cc1, dd1, ee1, ff1, gg1, hh1, ii1, jj1,
kk1, ll1, mm1, nn1, oo1, pp1, qq1, rr1, ss1, tt1,
uu1, vv1, ww1, xx1, yy1, zz1 };
const int INSERTIONS = 26; // Number of keys to insert
UString key;
int i, status;
tree.Clear();
cout << "Inserting " << INSERTIONS << " keys..." << "\n";
for(i = 0; i < INSERTIONS; i++) {
key = keys[i];
status = tree.Insert(key);
if(status != 1) {
cout << "\n" << "Problem adding " << keys[i] << " - " << i << "\n";
return;
}
}
TreeStats(tree);
}
void TestTree(gxBStree<UString> &tree)
// Test the tree insertion and deletion times.
{
// Adjust this number to set the number of insertions
// const unsigned long INSERTIONS = 1 * 1000; // 1K test
// const unsigned long INSERTIONS = 10 * 1000; // 10K test
const unsigned long INSERTIONS = 100 * 1000; // 100K test
// const unsigned long INSERTIONS = 1000 * 1000; // 1MEG test
// const unsigned long INSERTIONS = 10000 * 1000; // 10MEG test
// const unsigned long INSERTIONS = 100000 * 1000; // 100MEG test
// const unsigned long INSERTIONS = 1000000 * 1000; // 1GIG test
cout << "Inserting " << INSERTIONS << " keys..." << "\n";
unsigned long i, key_count = 0;
unsigned long curr_count = 0;
int status;
int verify_deletions = 0; // Set to ture to verify all deletions
double insert_time = 0;
const char *name = "Item";
char sbuf[255];
UString key;
// Get CPU clock cycles before entering loop
clock_t begin = clock();
for(i = 0; i < INSERTIONS; i++) {
sprintf(sbuf, "%s %d", name, (int)i);
key = sbuf;
clock_t begin_insert = clock();
status = tree.Insert(key);
clock_t end_insert = clock();
insert_time += (double)(end_insert - begin_insert) / CLOCKS_PER_SEC;
key_count++;
curr_count++;
if(status != 1) {
cout << "\n" << "Problem adding key - " << key << "\n";
return;
}
if(curr_count == 10000) {
curr_count = 0;
cout << "Inserted " << i << " keys in " << insert_time
<< " seconds" << "\n";
}
}
// 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 << "Inserted " << key_count << " values in "
<< elapsed_time << " seconds" << "\n";
double avg_insert_time = (insert_time/(double)key_count) * 1000;
cout << "Average insert time = " << avg_insert_time << " milliseconds"
<< "\n";
key_count = 0;
double search_time = 0;
cout << "Verifying the insertions..." << "\n";
begin = clock();
for(i = 0; i < INSERTIONS; i++) {
sprintf(sbuf, "%s %d", name, (int)i);
key = sbuf;
clock_t begin_search = clock();
status = tree.Find(key);
clock_t end_search = clock();
key_count++;
search_time += (double)(end_search - begin_search) / CLOCKS_PER_SEC;
if(status != 1) {
cout << "Error finding key - " << key << "\n";
return;
}
}
end =clock();
elapsed_time = (double)(end - begin) / CLOCKS_PER_SEC;
cout.precision(3);
cout << "Verified " << key_count << " values in "
<< elapsed_time << " seconds" << "\n";
double avg_search_time = (search_time/(double)key_count) * 1000;
cout << "Average search time = " << avg_search_time << " milliseconds"
<< "\n";
cout << "Deleting all the entries..." << "\n";
key_count = 0;
double delete_time = 0;
begin = clock();
for(i = 0; i < INSERTIONS; i++) {
sprintf(sbuf, "%s %d", name, (int)i);
key = sbuf;
clock_t begin_delete = clock();
status = tree.Delete(key);
clock_t end_delete = clock();
delete_time += (double)(end_delete - begin_delete) / CLOCKS_PER_SEC;
key_count++;
if(status != 1) {
cout << "Error deleting key - " << key << "\n";
return;
}
if(verify_deletions) { // Verify the remaining key locations
for(unsigned long j = INSERTIONS-1; j != i; j--) {
sprintf(sbuf, "%s %d", name, (int)j);
key = sbuf;
status = tree.Find(key);
if(status != 1) {
cout << "Error finding key - " << j << "\n";
cout << "After deleting key - " << i << "\n";
return;
}
}
}
}
end =clock();
cout.precision(3);
elapsed_time = (double)(end - begin) / CLOCKS_PER_SEC;
cout << "Deleted " << key_count << " values in "
<< elapsed_time << " seconds" << "\n";
double avg_delete_time = (delete_time/(double)key_count) * 1000;
cout << "Average delete time = " << avg_delete_time << " milliseconds"
<< "\n";
cout << "Re-inserting " << INSERTIONS << " keys..." << "\n";
key_count = 0;
insert_time = 0;
begin = clock();
for(i = 0; i < INSERTIONS; i++) {
sprintf(sbuf, "%s %d", name, (int)i);
key = sbuf;
clock_t begin_insert = clock();
status = tree.Insert(key);
clock_t end_insert = clock();
insert_time += (double)(end_insert - begin_insert) / CLOCKS_PER_SEC;
key_count++;
curr_count++;
if(status != 1) {
cout << "\n" << "Problem adding key - " << key << "\n";
return;
}
}
end =clock();
elapsed_time = (double)(end - begin) / CLOCKS_PER_SEC;
cout.precision(3);
cout << "Inserted " << key_count << " values in "
<< elapsed_time << " seconds" << "\n";
avg_insert_time = (insert_time/(double)key_count) * 1000;
cout << "Average insert time = " << avg_insert_time << " milliseconds"
<< "\n";
}
void ListInOrder(gxBStree<UString> &tree)
// List all the tree nodes using a tree iterator object.
{
gxBStreeNode<UString> *node = tree.GetRoot();
gxBStreeIterator tree_iterator(node);
while((node = (gxBStreeNode<UString> *)tree_iterator.GetNext()) != 0) {
cout << node->data << "\n";
}
cout << "\n";
}
void ExtractInOrder(gxBStree<UString> &tree)
// Extract all the tree nodes in sort order.
{
UString key;
while(!tree.IsEmpty()) {
tree.ExtractFirst(key);
cout << key << "\n";
}
}
void ExtractInReverseOrder(gxBStree<UString> &tree)
// Extract all the tree nodes in reverse order.
{
UString key;
while(!tree.IsEmpty()) {
tree.ExtractLast(key);
cout << key << "\n";
}
}
int main()
// Test program's main thread of execution
{
#ifdef __MSVC_DEBUG__
InitLeakTest();
#endif
Menu(); // Display the options menu
char key;
UString key_buf;
gxBStree<UString> tree;
int exists;
int rv = 1;
while(rv) {
if (!cin) {
ClearInputStream(cin);
if (!cin) {
cout << "Input stream error" << "\n";
return 0;
}
}
cout << '>';
cin >> key;
if (!cin) continue;
switch(key) {
case 'a' : case 'A' :
ClearInputStream(cin);
InputData(key_buf);
tree.Insert(key_buf, &exists);
if(exists) {
cout << "An entry for " << key_buf << " already exists" << "\n";
}
break;
case 'b' : case 'B' :
ClearInputStream(cin);
BuildTree(tree);
break;
case 'c' : case 'C' :
ClearInputStream(cin);
tree.Clear();
break;
case 'd' : case 'D' :
ClearInputStream(cin);
InputData(key_buf);
if(tree.Delete(key_buf)) {
cout << "Removed " << key_buf << "\n";
}
else {
cout << key_buf << " does not exists in the tree" << "\n";
}
break;
case 'e' : case 'E' :
ClearInputStream(cin);
ExtractInOrder(tree);
break;
case 'r' : case 'R' :
ClearInputStream(cin);
ExtractInReverseOrder(tree);
break;
case 'f' : case 'F' :
ClearInputStream(cin);
InputData(key_buf);
if(tree.Find(key_buf)) {
cout << "Found entry " << key_buf << "\n";
}
else {
cout << key_buf << " does not exists in the tree" << "\n";
}
break;
case 'l' : case 'L' :
ClearInputStream(cin);
ListInOrder(tree);
break;
case 's' : case 'S' :
ClearInputStream(cin);
TreeStats(tree);
break;
case 'i' : case 'I' :
ClearInputStream(cin);
ImportDictionaryFile(tree);
break;
case 'q' : case 'Q' :
tree.Clear();
rv = Quit();
break;
case 't' : case 'T' :
ClearInputStream(cin);
TestTree(tree);
break;
case '?' : case 'h' : case 'H' :
ClearInputStream(cin);
Menu();
break;
default:
cout << "Unrecognized command" << "\n";
}
}
return 0;
}
// ----------------------------------------------------------- //
// ------------------------------- //
// --------- End of File --------- //
// ------------------------------- //