PRINT whats in the THREE

what function do i call in my MAIN() ??

or better
how do i call these function in my main()
print_words(??,??);

or how i do it

#include <iostream>

using namespace std;

....other stuff....

int main()
{
   char buf[256];

   print_words(cout,buf);
}

Another alternative is to put the buffer in print_words:

void print_words(ostream & os)
{
   char buf[256];
   root -> print_words_r(os,buf,0,'A');
}

In this case you just write:

print_words(cout);

in your main when you want to print out if you want to print out to stdout.

If you want to print to file you do this:

int main()
{
   ofstream file("words.txt");
   print_words(file);
}

or if you keep the variation with buf in main then you do that:

int main()
{
   char buf[256];
   ofstream file("words.txt");
   print_words(file,buf);
}

either way works.

Alf

Alf:
here is the code :
#include "stdafx.h"
#include <iostream>
#include <stdlib.h>
#include <string>
#include <fstream>
#include <stdio.h>



using namespace std ;



class Dictio {
private:
 Dictio * a[26];
 bool FlagEndWord;

public:
  Dictio();
  ~Dictio();

  // This function follow from the current node
  // the letters given by word. The word is assumed
  // to be len characters.
  // On output plen will have the length of characters
  // leading to the returned entry.
  // The function searches from the given node
  // for a continuation using the first letter of
  // word and so on until it either find a complete
  // plen == len on output it means the whole word
  // has been read to reach the returned node, otherwise
  // the search stopped at some node because there is
  // no continuation present for the given leters.
  // len == plen and returned node has FlagEndWord
  // it means the input word was in the dictionary and
  // is a complete word.
  // if len == plen but the returned node do not have
  // FlagEndWord it means the 'word' contains a valid
  // prefix but is not in itself a complete word.
  // iF plen < len then not all the characters in word
  // could be followed because the word is not in the
  // dictionary, the plen indicate how many letters make
  // up a prefix that IS in the dictionary.
  // The functions VerifyWord and VerifyList can easily
  // be implemented in terms of this function.
  // also, insertion into the dictionary can be made
  // using this function as this function return the
  // leaf node that represent a prefix.
  Dictio * follow(const char * word, // the word
                  int len, // length of word
                  int & plen); // OUT: Length of prefix.

  bool IsFullWord() const { return FlagEndWord; }
 

  static void InsertDictionary(const char * word, int len);
  void print_words_r(ostream & os, char buf[], int n, char base);
};

Dictio * root = new Dictio;

bool VerifyWord(const char * word, int len)
{
  int plen;
  Dictio * n = root -> follow(word,len,plen);
  return (plen == len && n -> IsFullWord());
}

// insert the word into dictionary.
void Dictio::InsertDictionary(const char * word, int len)
{
  int plen;
  Dictio * n = root -> follow(word,len,plen);
  if (plen == len) {
     n -> FlagEndWord = true;
     return;
  }
  // need to add more nodes to the tree.
  do {
     char c = word[plen++];
     if (c >= 'A' && c <= 'Z')
       c = c - 'A' + 'a';
     if (c < 'a' || c > 'z') {
        // Not a word letter.
        // Now if you want to allow for - or other
        // letters in words you can always arrange for
        // that by allow for 27 or more letters in that
        // array, but then the waste becomes even more
        // appearant as every node will have those extra
        // pointers.
        // throw some error if you want here.
        return;
     }
     Dictio * & next = n -> a[c - 'a'];
     if (next != 0) {
        // follow() didn't do what it's supposed to do.
        // fatal error, throw error or something if you
        // want here.
        return;
     }
     next = n = new Dictio;
  } while (plen < len);
}






// read the file and add words to dictionary.
void AppendDictionary(const char * file)
{
 
      ifstream f(file);
  char buf[100];

  // each line is one word.
  while (f.getline(buf,sizeof(buf),'\n')) {
     
        // skip the newline at end of line if any.
     f.ignore(1024,'\n');

     Dictio::InsertDictionary(buf,strlen(buf));
  }
}

Dictio * Dictio::follow(const char * word, int len, int & plen)
{
  int x = 0;

  Dictio * n = this;
  while (x < len) {
     char c = word[x++];
     if (c >= 'A' && c <= 'Z')
        c = c - 'A' + 'a';
     if (c < 'a' || c > 'z') {
        // again not a legal letter....
        break;
     }
     Dictio * & next = n -> a[c - 'a'];
     if (next == 0) {
        // continuation not in dictionary.
        break;
     }
     n = next;
  }
  plen = x;
  return n;
}

Dictio::Dictio()
{
  for (int i = 0; i < 26; ++i)
     a[i] = 0;
  FlagEndWord = false;
}

Dictio::~Dictio()
{
  for (int i = 0; i < 26; ++i)
     delete a[i];
}


void Dictio::print_words_r(ostream & os, char buf[], int n, char base)
{
 // os is ostream to print out the words to.
 // buf[0..n-1] holds the first initial characters of word.
 // n is length of initial prefix.
 // base is 'a' or 'A' depending on upper/lowercase output.
 if (FlagEndWord) {
    buf[n] = '\0'; // terminating null byte.
    os << buf << endl;
 }
 for (int i = 0; i < 26; ++i) {
    if (a[i] != 0) {
       buf[n] = base + i;
       a[i] -> print_words_r(os,buf,n+1,'a');
    }
 }
}

void print_words(ostream & os)
{
  char buf[256];
  root -> print_words_r(os,buf,0,'A');
}


int main()
{
  string prefix;
  Dictio D;
 


      AppendDictionary("dict.txt");
     print_words(cout);
  // use it as you like.
  // if you have a word in a buffer and the length of it
  // you can check if it is in the dictionary by calling
  // follow or VerifyWord.

      
}

no errors, nothing, but it dosent print anything
it tells me : Press Any Key To Continue...

in my folder of the program i got a dict.txt with  3 words in it, 1 per line, but nothing appears.
can u tell me how come, where is the mistake ??

thx

Hard to say off hand, have you tried to debug your program? what platform are you using? What compiler?

If you use gcc or g++ you can use the gdb debugger to inspect your code.

If you use Visual C++ it has a built in debugger you can use.

If you use Borland C++ builder it also has a built in debugger you can use.

The first thing I want to know is if there is data in the tree at all or not.

If you have three words and they are like:

a
ab
bc

Then you should have a tree structure like this:

root -> a Dictio object.

root -> FlagEndWord == false.
root -> a[0] == obja (some Dictio object)
root -> a[1] == objb (another Dictio object).
root -> a[x] == 0 for all others.

obja -> FlagEndWord == true.
obja -> a[0] == 0
obja -> a[1] == objab (some Dictio object).
obja -> a[x] == 0 for all others.

objb -> FlagEndWord == false.
objb -> a[0] == 0
objb -> a[1] == 0
objb -> a[2] == objbc (some Dictio object).
objb -> a[x] == 0 for all others.

objab -> FlagEndWord == true.
objab -> a[x] == 0 for all x.

objbc -> FlagEndWord == true.
objbc -> a[x] == 0 for all x.

So you have a total of five Dictio objects:

root
obja
objb
objab
objbc

If this is the structure then it is the writing function that has bug, if you do not have that structure the it is the reading function that has error.

I would say the first step is to determine which of these two has the error.

For example if root -> a[x] == 0 for all x after reading that file with 3 words then it won't print anything but we also know that the reading function has error and we can start to look deeper into that reading function. But if root looks ok and the other nodes in the tree also look ok it is an error.

Also, if no node has the FlagEndWord set to true then that is a good hint that something is wrong. In this case there won't be any output either.

Alf

Hey Alf
before i read your text, i had a .txt file with 10 words, nothing appeared. I had an other .txt file with lots and lots of word, and it worked.
You know this can be ???????

and other thing.

how can i do this :
an other function :
i type un a word ; cin << word ;
and i see if the word exist in the tree

thx

The best way to find out what is happening is if you can use a debugger.

what platform are you using? GCC, G++, Visual C++ or Borland C++ or some other platform?

Alf

Visual C++

how can i do a function
that the User taps in a word and see if its in the tree
like this i can find out if they at least put the word in the tree

Salte
thats the last function i need
to type in a word : cin and check if it exist in the tree

thx
Ital

Ok, Visual C++ has a built in debugger, try to run your program in a debugger and stop it after it has read the data structure and before it is about to print and see what it has. If it has the proper datastructure then you know it is the printing function that is wrong, if it is something wrong then it is the reading function that is wrong.

You can check if a word is in the tree by using the following form:

// word is word and len is length of that word.
bool IsWordInTree(const char * word, int len)
{
   int plen;
   Dictio * n = root -> followIsWordInTree(word,len,0);
   return n != 0 && plen == len && n -> FlagEndWord;
}

if (IsWordInTree("foo",3)) {
   // "foo" is in tree.
} else {
   // "foo" is not in tree.
}

Alf

i dont get what your doing.
the function is ok
its more :

if (IsWordInTree("foo",3)) {
  // "foo" is in tree.
} else {
  // "foo" is not in tree.
}

if i replace foo with TypeWord
and i do a
cin>> TypeWord
it dosent work
whats the 3 for, the lent of the word

the only thing i need is i type in the word and see if its in the tree

thats all
i'm sorry to bust, but im really greatfull for your help
thats the last questions, if it works, ill stop bugging you
lol
ital

the thing is the lent of the word
its changes evrytime, thats the thing

Alf
i made it work

but the thing is again, it dosent had all the words in it
if u can help , let me know ?

Alf
if u come back here
can u put comments here, explain a bit what i does :
void Dictio::InsertDictionary(const char * word, int len)
{
  int plen;
  Dictio * n = root -> follow(word,len,plen);
  if (plen == len) {
     n -> FlagEndWord = true;
     return;
  }
  // need to add more nodes to the tree.
  do {
     char c = word[plen++];
     if (c >= 'A' && c <= 'Z')
       c = c - 'A' + 'a';
     if (c < 'a' || c > 'z') {
       
        return;
     }
     Dictio * & next = n -> a[c - 'a'];
     if (next != 0) {
        // follow() didn't do what it's supposed to do.
        // fatal error, throw error or something if you
        // want here.
        return;
     }
     next = n = new Dictio;
  } while (plen < len);
}

and here :
Dictio * Dictio::follow(const char * word, int len, int & plen)
{
  int x = 0;

  Dictio * n = this;
  while (x < len) {
     char c = word[x++];
     if (c >= 'A' && c <= 'Z')
        c = c - 'A' + 'a';
     if (c < 'a' || c > 'z') {
        // again not a legal letter....
        break;
     }
     Dictio * & next = n -> a[c - 'a'];
     if (next == 0) {
        // continuation not in dictionary.
        break;
     }
     n = next;
  }
  plen = x;
  return n;
}

...

...

im confused

simpsons
this is a program that takes a file and had the Words into a dictionnairye

thats what it does

Alf
if u come back here
can u put comments here, explain a bit what i does :

I am here.

void Dictio::InsertDictionary(const char * word, int len)
{
 int plen;
 Dictio * n = root -> follow(word,len,plen);

/*
  Follow is a function that tries to find a node that represent the longest prefix found in the tree.
  If "pre" is stored in the tree and you do
  Dictio * n = follow("prefix",6,plen);

  n will be the node representing the 'e' of "pre". plen will have the value 3 indicating that the length of this prefix is of length 3.

 The function follow never inserts new node in the tree but tries to follow the nodes as long as it find a valid continuation.

  It follows that if n != 0 (it should always be) and
  plen == len then the node represent the full word.
*/

 if (plen == len) {
    /* Here we know that the node n represent the full
       word so we just set FlagEndWord to true.
       The word is complete.
     */
    n -> FlagEndWord = true;
    return;
 }
 /* Here we know that the prefix was incomplete, since
    we want to insert this word that means we have to
    insert nodes for the missing letters after the prefix.
  */
 // need to add more nodes to the tree.
 do {
    char c = word[plen++];
    /* The next char is c and so we need to add a node
       for c. */
    if (c >= 'A' && c <= 'Z')
      c = c - 'A' + 'a'; /* Uppercase letter, convert to lowercase */
    if (c < 'a' || c > 'z') {
       /* Not a letter! You should probably throw an
          error here instead of simply returning */
       return;
    }
    Dictio * & next = n -> a[c - 'a'];
    if (next != 0) {
       /* Here it says that the next node is non-zero
          but this indicates that follow didn't go as
          far as it could, so we have an internal error.
          This should definitely throw an exception */
       // follow() didn't do what it's supposed to do.
       // fatal error, throw error or something if you
       // want here.
       return;
    }
    /* Add the new node and continue */
    next = n = new Dictio;
 } while (plen < len);
  /* The new word is complete, however, I see a bug here,
     FlagEndWord should be set since we have a complete
     word */
  n -> FlagEndWord = true; /* NEW FIX NEW FIX */
}

and here :
Dictio * Dictio::follow(const char * word, int len, int & plen)
{
 int x = 0;

 Dictio * n = this;
 /* To start with we set n to this, so we start from
    current node */

 while (x < len) {
    char c = word[x++];
    /* Pick up the next character to insepct */
    if (c >= 'A' && c <= 'Z')
       c = c - 'A' + 'a';
    if (c < 'a' || c > 'z') {
       // again not a legal letter....
       break;
    }
    Dictio * & next = n -> a[c - 'a'];
    if (next == 0) {
       // continuation not in dictionary.
       /* We have run out of nodes to follow so we return
          the last node we saw (n). This is the node
          which we will append new nodes to if we want to
          insert the word */
       
       break;
    }
    n = next;
 }
 /* plen is the prefix we have followed so far, the value
    is such that 0 <= plen <= x and if plen == x then
    the word is in the dictionary already - possibly not as
    a separate word but the word is in the dictionary.
    for example if the word "prefix" is in the dictionary
    then we have "pre" in - perhaps not as separate word
    but it is there and that is what we return, so
    follow("pre",3,plen) will return with the node for
    'pre' and a plen value of 3.
 */

 plen = x;
 return n;
}


Hope this explains, also please correct the bug I discovered. It failed to set FlagEndWord at the end of a word in the Insert function.

Note that follow is used both by insertDictionary and by lookups.

Alf

hey ALF
if u see this message, reply and i have to ask you something

when i Insert, i dosent insert the first LETTER or so
can u see why ?

if i take this out, it dosent print alot of word
so maybe the mistake is there
what u suggest me to do


if (next != 0) {
      /* Here it says that the next node is non-zero
         but this indicates that follow didn't go as
         far as it could, so we have an internal error.
         This should definitely throw an exception */
     
       
        // follow() didn't do what it's supposed to do.
      // fatal error, throw error or something if you
      // want here.
      return;
   }

I have suggested you use the debugger functionality of Visual C++. Visual C++ has a debugger, use it.

It is the best tool to find errors in a program.

The

if (next != 0) { ... }

indicate that there is a next node at the next letter. But follow should have followed that path to the node that next is pointing to in this condition. So if this is true (next != 0) then there is a bug in follow(). You should throw some error in this condition and you should check with the debugger and try to step through the code where insert works here.

follow() is supposed to follow the path in the tree along the letters.

If you insert the word "foobar" and the word "foo" is already in the tree then follow() will follow the nodes f, o and o and then it will return because there is no 'b' node after that 'o'. In this case next will be 0.

I see one more bug though in follow and this may be the cause.

Dictio * Dictio::follow(const char * word, int len, int & plen)
{
 int x = 0;

 Dictio * n = this;
 while (x < len) {
    char c = word[x]; // FIX: remove the ++
    if (c >= 'A' && c <= 'Z')
       c = c - 'A' + 'a';
    if (c < 'a' || c > 'z') {
       // again not a legal letter....
       break;
    }
    Dictio * & next = n -> a[c - 'a'];
    if (next == 0) {
       // continuation not in dictionary.
       break;
    }
    n = next;
    ++x; // FIX: Do the ++ here.
 }
 plen = x;
 return n;
}

The problem was that the code moved x past the character before checking to see if that character was in the word. It should only move to next character if the character is found in a node from node n.

Alf

hey alf
you find something good. it helps
not it shows the entire word
now one problem
it puts in 1 out of 2 words.
so if i have

Eat
Allo
Food
Good
Bad

it will had :

eat
food
bad

thats it. if u can figure something out before me, let me know

Alf
i found the ERROR
thx again
your a good man
thx
Ital