I'm working on creating a BST of words provided in an input file. The input file I have is structure like so:
i apple
i bakery
i collapse
The i is a command that means the word following the command needs to be inserted into the BST. I am able to read and insert the words from an input file with 21 words, but I would like to load the words from an input file with up to 370,100 words. When I run my code on this input file it looks like the first line of the input file isn't even read but I am unable to figure out why.
class Node
{
public:
string word;
Node *left, *right, *parent;
Node() // default constructor
{
left = right = parent = NULL;
}
Node(string to_insert)
{
word = to_insert;
left = right = parent = NULL;
}
};
class BST
{
private:
Node *root;
public:
BST();
void insert(string);
void insert(Node*, Node*);
};
BST :: BST()
{
root = NULL;
}
void BST :: insert(string word)
{
Node *to_insert = new Node(word);
if (root == NULL)
root = to_insert;
else
insert(root,to_insert);
}
void BST :: insert(Node* start, Node* to_insert)
{
if (start == NULL)
return;
if (to_insert->word <= start->word)
{
if(start->left == NULL)
{
start->left = to_insert;
to_insert->parent = start;
return;
}
else // need to make recursive call
{
insert(start->left, to_insert);
return;
}
}
else // inserted node has larger key, so go right
{
if(start->right == NULL)
{
start->right = to_insert;
to_insert->parent = start;
return;
}
else
{
insert(start->right, to_insert);
return;
}
}
}
int main(int argc, char** argv)
{
if (argc < 3) // must provide two arguments as input
{
throw std::invalid_argument("Usage: ./treewrapper <INPUT FILE> <OUTPUT FILE>"); // throw error
}
ifstream input; // stream for input file
ofstream output; // stream for output file
input.open(argv[1]); // open input file
output.open(argv[2]); // open output file
string command; // to store the next command and operation
char *com, *dummy, *valstr, *op; // for using with strtok, strtol
string val = ""; // the value from the command
BST myBST;
int inserted = 0;
while(getline(input,command))
{
cout << "Checking command" << "\n";
if (command.length() == 0) // command is empty
continue;
com = strdup(command.c_str()); // annoying, first copy string into a "C-style" string
op = strtok(com, " \t"); //tokenize command on whitespace, first token is operation
valstr = strtok(NULL, " \t"); // next token is value, as string (check out documentation on strtok, to understand the parsing)
cout << valstr << "\n";
if(valstr != NULL) // first check if there is actually anything to convert into int
val = valstr; // convert initial portion of valstr into an integer val, with base 10. Check out documentation on strtol for more details.
if(strcmp(op,"i") == 0) // insert into list
{
cout << "Insert "+ val << endl;
myBST.insert(val);
inserted++;
}
}
cout << "Words inserted: " << to_string(inserted) << "\n";
input.close();
output.close();
}