Thanks for the reply, Lesshardtofind.
I changed to trie code by adding a block that reads from a text file, but it errors out. Here is the new code:
Code:
/* trie.cc - short and sweet data storage API :-)
* Implementation of TRIE data structure, a bare bone.
* Fri Oct 9 22:49:25 IST 2009
* Author: Shamail Tayyab [[email protected]]
* Creative Commons BY-NC-ND.
* Insertion: O(n). Searching: O(n).
*/
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <fstream>
#define MAXDICTELEMENTS 227 /* Using a-z and space */
#define MAXDEPTH 220 /* Supporting 20 character depth of dictionary */
using namespace::std;
/* Start open file block */
ifstream::pos_type size;
char * memblock;
int main () {
ifstream file ("words.txt", ios::in|ios::ate);
if (file.is_open())
{
size = file.tellg();
memblock = new char [size];
file.seekg (0, ios::beg);
file.read (memblock, size);
file.close();
cout << "\n+++++++++++++++++++\nFile is in memory\n+++++++++++++++++++\n\n";
delete[] memblock;
}
else cout << "Unable to open file";
/* End open file block */
/* Our dictionary node */
struct Node {
int wordEnd; /* Represents that a word is ending here also */
Node *next[MAXDICTELEMENTS];
};
/* Trie represented as class */
class Trie {
private:
Node *start; /* Our start pointer */
char dict[MAXDICTELEMENTS]; /* Our char dictionary or supported characters in TRIE */
Node *createNode (); /* Create and mallocs a node */
int printThisNode ( Node * ); /* Debugging function */
int isEmpty ( Node *, char ); /* Detects if we have an empty node at given depth */
int getIndexForChar ( char ); /* Returns ith position from dict array */
public:
Trie (); /* Constructor function to initialize the TRIE */
~Trie (); /* FREEing up of memory. FIXME required */
int insert ( char * ); /* Insert a word in TRIE */
void reportSearch ( char *word ); /* Searches and reports on stderr the result in printed form */
int search ( char *word ); /* API to search */
};
Trie::Trie () {
start = (Node *)malloc ( sizeof ( Node ) );
strcpy ( dict, "abcdefghijklmnopqrstuvwxyz " ); /* Add here for any other word list, also update MAXDICTELEMENTS*/
}
Trie::~Trie () {
free (start);
}
/*
* Array index for TRIE's next.
*/
int Trie::getIndexForChar ( char c ) {
for ( int i = 0 ; i < MAXDICTELEMENTS ; i++ ) {
if ( dict[i] == c ) {
return i;
}
}
return ( -1 );
}
/*
* For debugging, prints which all nodes are free in a given level of TRIE.
*/
int Trie::printThisNode ( Node * treeNode ) {
if ( treeNode == NULL ) {
return EXIT_FAILURE;
}
for ( int i = 0 ; i < MAXDICTELEMENTS ; i++ ) {
if ( treeNode -> next[i] == NULL ) {
cout << "Empty(" << i << ")\t";
}
else {
cout << "Filled(" << i << ")\t";
}
cout << endl;
}
}
/*
* If the TRIE has an empty node at this treeNode at cth position?
*/
int Trie::isEmpty ( Node *treeNode, char ch ) {
if ( treeNode -> next[getIndexForChar(ch)] == NULL )
return (1);
else
return (0);
}
/*
* Brings one node from the memory.
*/
Node *Trie::createNode () {
Node *created = (Node *) malloc ( sizeof ( Node ) );
created -> wordEnd = 0;
return (created);
}
/*
* Insert a word into the TRIE.
* Quick Algo: Traverse to the right depth, insert.. O(n).
*/
int Trie::insert ( char *word ) {
if ( strlen ( word ) > MAXDEPTH ) {
cerr << "MAXDEPTH Exceeded! Cannot insert(" << word << ")" << endl;
return EXIT_FAILURE;
}
cerr << "Adding word " << word << " to the dictionary..." << endl;
Node *operatingOn = start;
for ( int i = 0 ; i < strlen ( word ) ; i++ ) {
if ( isEmpty ( operatingOn, word[i] ) ) {
Node *childHere = createNode ();
operatingOn -> next[getIndexForChar(word[i])] = childHere;
operatingOn = childHere;
}
}
operatingOn -> wordEnd = 1;
return EXIT_SUCCESS;
}
/* Searches in a TRIE the given word.
* Quick Algo: Iterate on chars, if the pointer is null anywhere, its not found. else accent into one level on this character.
* If even all pointers are fixed and last pointer has 0 in its wordEnd, still not found.
* Else found.
*/
int Trie::search ( char *word ) {
Node *iterator = start;
if ( iterator == NULL )
return (EXIT_FAILURE);
if ( strlen ( word ) > MAXDEPTH ) {
cerr << "MAXDEPTH Exceeded!" << endl;
return (EXIT_FAILURE);
}
for ( int i = 0 ; i < strlen(word) ; i++ ) {
if ( iterator -> next[getIndexForChar(word[i])] == NULL )
return EXIT_FAILURE;
iterator = iterator -> next[getIndexForChar(word[i])];
}
if ( iterator -> wordEnd == 0 ) {
return EXIT_FAILURE;
}
else {
return EXIT_SUCCESS;
}
}
/*
* Perform search and print result on STDERR.
*/
void Trie::reportSearch ( char *word ) {
if ( search ( word ) ) {
cerr << "Not Found!" << endl;
}
else
cerr << "Found!" << endl;
}
/*
* Test case
*/
int main ( int argc, char *argv[] ) {
Trie t;
t.insert ( (char *)"545645645645645645645677777777777777776567567567567567567567567567567" );
t.insert ( (char *)"45645645656r456456456" );
t.insert ( (char *)"789789789789789789789" );
t.insert ( (char *)"4564565633453455" );
t.insert ( (char *)"45456456456" );
t.insert ( (char *)"456456456456" );
t.insert ( (char *)"5886456456456456456" );
t.insert ( (char *)"45645645656r456489789789789" );
t.insert ( (char *)"4564565883453455" );
t.insert ( (char *)"45457878787878456" );
t.insert ( (char *)"4578787878788786456" );
t.insert ( (char *)"5456456456456456456456" );
t.insert ( (char *)"45645645656r456456456" );
t.insert ( (char *)"789789789789789789789" );
t.insert ( (char *)"4564565633453455" );
t.insert ( (char *)"45456456456" );
t.insert ( (char *)"456456456456" );
t.insert ( (char *)"5886456456456456456" );
t.insert ( (char *)"45645645656r456489789789789" );
t.insert ( (char *)"4564565883453455" );
t.insert ( (char *)"45457878787878456" );
t.insert ( (char *)"4578787878788786456" );
t.insert ( (char *)"5456456456456456456456" );
t.insert ( (char *)"45645645656r456456456" );
t.insert ( (char *)"789789789789789789789" );
t.insert ( (char *)"4564565633453455" );
t.insert ( (char *)"45456456456" );
t.insert ( (char *)"456456456456" );
t.insert ( (char *)"5886456456456456456" );
t.insert ( (char *)"45645645656r456489789789789" );
t.insert ( (char *)"4564565883453455" );
t.insert ( (char *)"45457878787878456" );
t.insert ( (char *)"4578787878788786456" );
t.insert ( (char *)"5456456456456456456456" );
t.insert ( (char *)"45645645656r456456456" );
t.insert ( (char *)"789789789789789789789" );
t.insert ( (char *)"4564565633453455" );
t.insert ( (char *)"45456456456" );
t.insert ( (char *)"456456456456" );
t.insert ( (char *)"5886456456456456456" );
t.insert ( (char *)"45645645656r456489789789789" );
t.insert ( (char *)"4564565883453455" );
t.insert ( (char *)"45457878787878456" );
t.insert ( (char *)"4578787878788786456" );
t.insert ( (char *)"5456456456456456456456" );
t.insert ( (char *)"45645645656r456456456" );
t.insert ( (char *)"789789789789789789789" );
t.insert ( (char *)"4564565633453455" );
t.insert ( (char *)"45456456456" );
t.insert ( (char *)"456456456456" );
t.insert ( (char *)"5886456456456456456" );
t.insert ( (char *)"45645645656r456489789789789" );
t.insert ( (char *)"4564565883453455" );
t.insert ( (char *)"45457878787878456" );
t.insert ( (char *)"4578787878788786456" );
system ("pause");
return 0;
}
How do I change it so it actually reads words.txt and passes the lines from it instead of using the /* Test cases */ block?
Thanks to all who replied.