Stuck with A Trie implementation

[RICO_BEE]

Hi guys,

Anyone can give me some help for this Trie application. I implemented an insert method and a find method in the Trie class, and in the Scrab application, I inserted 3 strings into the Trie, and then use find method to check whether the string is in the Trie. The insert method seems working fine, but the find method cannot find the string. Please give me some help guys, I haven't touched any C/C++ things for a long time(working on Java), but now I need to reactivate my C/C++ skills. So please help me with that, Guys.

The Trie class and Scrab applciation is as following:

#include "Trie.h"

Trie::Trie() {
    valid = false;
}

//inserts a word into the trie,give the entry of the first char and last one
bool Trie::insert(string::const_iterator first, string::const_iterator last) {
    Trie currentNode;
    if(first != last) {
        map<char,Trie>::iterator iter = children.find(*first);
        if(iter != children.end()) {
           currentNode = (iter->second);
           return (currentNode.insert(++first, last));
        }
        else {
           if((first == (last - 1)) && !valid) {
               children.insert(map<char,Trie>::value_type(*first,currentNode));
               cout << "last char of each word:" << *first << endl;
               cout << "insert:childrensize after last char:" << children.size() << endl;
               valid = true;
               return 1;
           }
           else {
               children.insert(map<char,Trie>::value_type(*first,currentNode));
               cout << "insert:childrensize after every insert:" << children.size() << endl;
               return currentNode.insert(++first,last);
           }
        }
    }
    return 1;
}

//checks if a word is in the trie, give the entry of the first char and last one
bool Trie::find(string::const_iterator first, string::const_iterator last) const {
    if (first != last) {
        //Checks whether it reaches the end of the
        if(children.size() == 0 && valid){
            return 1;
        }
        if (children.find(*first) != children.end()) {
            Trie* currentNode = (children.find(*first))->second;
            //cout << "find:child:" << *(first);
            //cout << "find:children size:" << currentNode.children.size() << endl;
            return currentNode.find(first+1,last);
        }
        else {
            cout << "Something wrong~~" << endl;
            return 0;
        }
    }
    return 1;
}

class Scrab {

public:
    Trie root;
    Scrab();
    ~Scrab();
};

Scrab::Scrab(){
    cout << "Initializing Scrab" << endl;
}

Scrab::~Scrab(){
    cout << "Destructing Scrab" << endl;
}

int main( int argc, const char* argv[] )
{
    int total_words = 0;
    char* charSequence;
    Scrab scrab;
    cout << "***********************" << endl;
    cout << "* Scrabbinator Helper *" << endl;
    cout << "***********************" << endl;
    if (argc != 2) {
        cerr << "Please type in file path and name."<<endl;
    }
    if (argv[1] != NULL) {
        cout<<argv[1]<<endl;
        ifstream in;
        in.open(argv[1]);
        if(!in) { // file couldn't be opened
            cerr << "Error: file could not be opened" << endl;
            exit(1);
        }
        while(!in.eof()){
            //cout << "children size:" << scrab.root.children.size() << endl;
            //cout << "found or not:" << scrab.root.find(word.begin(),word.end()) <<  endl;
            string word;
            in>>word;
            if(word.length() != 0) {
                  if(scrab.root.insert(word.begin(),word.end()))
                      total_words++;
                  cout<<"result:"<<scrab.root.find(word.begin(),word.end())<<endl;

            }
        }
       cout<<"*******************************" <<endl;
        cout<<"Read " <<total_words<<" distinct word(s) from the file \'"<<argv[1]<<"\'"<<endl;
        cout<<"Please enter letter sequence and optional match pattern:"<<endl;
        cin >> charSequence;
        in.close();
    }

[RICO_BEE]

Trie.h

#ifndef TRIE_H
#define TRIE_H

#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <map>
#include <utility>

using std::cout;
using std::endl;
using std::vector;
using std::string;
using std::map;
using std::set;
using std::pair;
using std::make_pair;

// this new interface removes the valid vector `optimisation'
// and uses a better C++ approach, with iterators and const members
// our implementation does not use [] for vector and map

// simple trie data structure
class Trie {

  // private data members
  bool valid;
  //map<char, Trie> children;

public:
  map<char, Trie> children;
  // constructor
  Trie();

  // inserts a word into the trie
  bool insert(string::const_iterator first, string::const_iterator last);
  // checks if a word is in the trie
  bool find(string::const_iterator first, string::const_iterator last) const;
  // searches for words in the trie matching letter sequence in fragments
  // stores words found in matches
  void search(set<string> &matches, vector<char> sequence, string prefix = "") const;
  // prints all words in the trie
  void print(string prefix = "") const;
  void printDebug();
  // destructor
  ~Trie();
};

[Russco]

please edit your post and repost your code within code tags.

[RICO_BEE]

sorry about the mess, it has been edited already.

[TheCPUWizard]

sorry about the mess, it has been edited already.

What happens when you step through it with the debugger? Which line gives the first "unexpected" result?

[RICO_BEE]

What happens when you step through it with the debugger? Which line gives the first "unexpected" result?

Actually it doesnt have any exceptions, but it only can get to the first level of the trie. For example, if I tried to find the word "American" in the trie, it can find the first letter 'A', but then the size of the children map of 'A' will be 0. But I cannot find why it is 0, coz I already inserted the elements in the children map when inserted the strings.

So really no idea about whats going on.

[RICO_BEE]

I suspect it could be something wrong the Trie object in the children map.

[TheCPUWizard]

Actually it doesnt have any exceptions, but it only can get to the first level of the trie. For example, if I tried to find the word "American" in the trie, it can find the first letter 'A', but then the size of the children map of 'A' will be 0. But I cannot find why it is 0, coz I already inserted the elements in the children map when inserted the strings.

So really no idea about whats going on.

Exceptions have NOTHING to do with steeping through it with the debugger.

As EACH individual line executes WRITE down the values of each variable that is used on that line.

[RICO_BEE]

Exceptions have NOTHING to do with steeping through it with the debugger.

As EACH individual line executes WRITE down the values of each variable that is used on that line.

Yep, I know what you mean. I used GDB to debug it in Linux, the problem is the 2nd level nodes don't have any child when I try to use "find" method.

For example, I inserted 4 words into the Trie, "Bob" , "Dog", "Sun", "Think" without problems. when I try to use "find" to search for "Bob", I can find 'B' without problems, and when I step into children map of 'B', it says size of children is 0. I set breakpoints in the find the value of the children.size,,, it is always 0.

I suspected that in my recursive method,, I didn't process the children properly. 'children ' is a map<char,Trie> member of Trie class.

[mahesh200910]

Hi... am planning to implement a dictionary using trie.. so i need help.. ve u implemented it in JAVA or C if so help me wit d code or tell me how to proceed

[mahesh200910]

Hi... am planning to implement a dictionary using trie for my mini project.. so i need help.. ve u implemented it in JAVA or C if so help me wit d code or tell me how to proceed

[S_M_A]

First of all you need to replace your keyboard since several keys are broken...
See this http://www.codeguru.com/forum/announcement.php?f=7 under section Your Posting

[tvranjith]

Check http://code.google.com/p/simple-trie/

[Bre45Web]

children map when inserted the strings.