Initialed value lost !

[sam.barker0]

Hi there,
I am trying to develop a compressed suffix trie.
But first I want to get the trie working.
The structure of the trie is like

class trie {
private:
bool last_node;
map<char, trie> children;

//methods
.....
.....
.....
}
The problem is that after inserting one word,the values held by the
private members of the nodes(other than the root is lost).
insert is a recursive function
new node is added like this
trie new_child;
this->children[alphabet]=new_child;
new_child.insert(word.substr(1));//insert is called again.
I had stepped through to debug
this is what happened.I had a pasteing the value of this ppointer and
the data member last_node

when I insert the first waord "ca"

//for the root node
entering this pointer 0xbfe254a0
pointer 0xbfe254a0 0//last_node is false

the another node is created added into the map and in that node i set
the last_node to true
this->last_node=true;

after setting
pointer 0xbfe25430 1 //last node set to true


now i insert the word "cab"
the root node is fine

entering this pointer 0xbfe254a0
pointer 0xbfe254a0 0

but then from the map based on the letter i go to the next node(to
node a).but then the last_node member is false even though i had
set it true before
pointer 0xbfe25430 0

could anyone tell what I am doing wrong?

 

[Rolf Magnus]

Hi there,
I am trying to develop a compressed suffix trie.

Just a side node: It's called "tree".

But first I want to get the trie working.
The structure of the trie is like

class trie {
private:
bool last_node;
map<char, trie> children;

//methods
....
....
....
}
The problem is that after inserting one word,the values held by the
private members of the nodes(other than the root is lost).
insert is a recursive function
new node is added like this
trie new_child;

Ok, so you create a local instance of 'trie'.

this->children[alphabet]=new_child;

Then you copy it into your children map.

new_child.insert(word.substr(1));//insert is called again.

Now you change the local object, which doesn't affect the copy in your map
at all. At the end of the function, the local object and all the changes
you did to it will be lost.

 

[Rolf Magnus]

Hi there,
I am trying to develop a compressed suffix trie.

But first I want to get the trie working.
The structure of the trie is like

class trie {
private:
bool last_node;
map<char, trie> children;

//methods
....
....
....
}
The problem is that after inserting one word,the values held by the
private members of the nodes(other than the root is lost).
insert is a recursive function
new node is added like this
trie new_child;

Ok, so you create a local instance of 'trie'.

this->children[alphabet]=new_child;

Then you copy it into your children map.

new_child.insert(word.substr(1));//insert is called again.

Now you change the local object, which doesn't affect the copy in your map
at all. At the end of the function, the local object and all the changes
you did to it will be lost.

 

[sam.barker0]

Hi there,
I am trying to develop a compressed suffix trie.

Just a side node: It's called "tree".

But first I want to get the trie working.
The structure of the trie is like

class trie {
private:
bool last_node;
map<char, trie> children;

//methods
....
....
....
}
The problem is that after inserting one word,the values held by the
private members of the nodes(other than the root is lost).
insert is a recursive function
new node is added like this
trie new_child;

Ok, so you create a local instance of 'trie'.

this->children[alphabet]=new_child;

Then you copy it into your children map.

new_child.insert(word.substr(1));//insert is called again.

Now you change the local object, which doesn't affect the copy in your map
at all. At the end of the function, the local object and all the changes
you did to it will be lost.

Ah makes sense.I was thinking like it was a pointer.So if I
interchange the lines
trie new_child;
new_child.insert(word.substr(1));//insert is
called again.

//after inserting the nodes then connect it
back to the parent
this->children[alphabet]=new_child;
I think this should be a correct solution.Please correct me if I am
wrong.

 

[Rolf Magnus]

Now you change the local object, which doesn't affect the copy in your
map at all. At the end of the function, the local object and all the
changes you did to it will be lost.

Ah makes sense.I was thinking like it was a pointer.So if I
interchange the lines
trie new_child;
new_child.insert(word.substr(1));//insert is
called again.

//after inserting the nodes then connect it
back to the parent
this->children[alphabet]=new_child;
I think this should be a correct solution.Please correct me if I am
wrong.

Yes, this looks good. Another solution would be to let the map create a new
element and then use a reference to it. That way you can save the copying.
Something like that:

trie& new_child = this->children[alphabet];
new_child.insert(word.substr(1));//insert is called again.

The behavior of that differs from your solution if there is already an
element with that index in the map.

 

[sam.barker0]

Ah makes sense.I was thinking like it was a pointer.So if I
interchange the lines
trie new_child;
new_child.insert(word.substr(1));//insert is
called again.

//after inserting the nodes then connect it
back to the parent
this->children[alphabet]=new_child;
I think this should be a correct solution.Please correct me if I am
wrong.

Yes, this looks good. Another solution would be to let the map create a new
element and then use a reference to it. That way you can save the copying.
Something like that:

trie& new_child = this->children[alphabet];
new_child.insert(word.substr(1));//insert is called again.

The behavior of that differs from your solution if there is already an
element with that index in the map.

Yep.Thanks for your suggestion.
Cheers,
Sam

 

[James Kanze]

Hi there,
I am trying to develop a compressed suffix trie.
But first I want to get the trie working.
The structure of the trie is like

class trie {
private:
bool last_node;
map<char, trie> children;

This is undefined behavior. You can't instantiate a standard
container on an incomplete type. It might work in some
implementations, but it might not.

//methods
....
....
....}

The problem is that after inserting one word,the values held by the
private members of the nodes(other than the root is lost).
insert is a recursive function
new node is added like this
trie new_child;
this->children[alphabet]=new_child;
new_child.insert(word.substr(1));//insert is called again.

Is the above supposed to be C++. Parts of it look like it,
others don't.

I'd implement a trie more or less:

class Trie
{
public:
void insert(
std::string::const_iterator begin,
std::string::const_iterator end ) ;
private:
boost::array< boost::scoped_ptr< Trie >, UCHAR_MAX + 1 >
myChildren ;
} ;

void
Trie::insert(
std::string::const_iterator begin,
std::string::const_iterator end )
{
if ( begin != end ) {
unsigned char index = *begin ;
if ( myChildren[ index ].get() == NULL ) {
myChildren[ index ].reset( new Trie ) ;
}
myChildren[ index ]->insert( begin + 1, end ) ;
}
}

Note that you need the dynamic allocation in order for the class
to contain instances of itself.

I had stepped through to debug this is what happened.I had a
pasteing the value of this ppointer and the data member
last_node

[...]

could anyone tell what I am doing wrong?

You haven't really posted enough of your own code for us to say.
But something similar to the above should work. (With regards
to the undefined behavior, I suspect that in general, if the
code compiles, it will work. But the standard still says it is
undefined, and there are implementations where it won't
compile.)

 

[James Kanze]

Just a side node: It's called "tree".

No it's not. At least not if I've correctly understood what
he's doing. A trie is a special kind of tree.

 

[Rolf Magnus]

No it's not.

Yes, I found that out right after posting. I tried canceling the post, but I
guess, it was too late already.

At least not if I've correctly understood what
he's doing. A trie is a special kind of tree.

http://en.wikipedia.org/wiki/Trie

 

[sam.barker0]

Hi again,
class trie {
private:
bool last_node;
map<char, trie> children;

//methods
.....
.....
.....
}



I had changed the implementation for recursive insert to

This code is a part of recursive function.
trie new_child
new_child.insert(word.substr(1));//insert is called again.
//after inserting the nodes then connect it back to the parent
this->children[alphabet]=new_child;
......
.....
//if the map has an entry then
Trie next_child=this->children[letter];
child.insert(word.substr(1));

Now the node correctly points to the children.The problem is that the
values held by the children are lost as I insert multiple words into
the root.
debug messages

inserting pointer 0xbf861970 0//root-- setting the last_node to 0
//create a new node and set the last node to 1
inserting pointer 0xbf861900 1
....
now I insert another 2letter word.
check root 0xbf861970 0
next node 0xbf861900 0//the last node has been changed to zero...

Even though I go to the same memory location,the value of
last_node(private variable) has been changed.
@ James
Yep the the implementation is in c++(atleast parts of it are ).I am
trying to starting off in C++.

Cheers,
Sam

 

[James Kanze]

class trie {
private:
bool last_node;
map<char, trie> children;

As I said, this is undefined behavior. For starters, change
your code to avoid it (not that I think it's the cause of the
error you're observing).

//methods
....
....
....

}

I had changed the implementation for recursive insert to

This code is a part of recursive function.
trie new_child
new_child.insert(word.substr(1));//insert is called again.
//after inserting the nodes then connect it back to the parent
this->children[alphabet]=new_child;
.....
....
//if the map has an entry then
Trie next_child=this->children[letter];
child.insert(word.substr(1));

Now the node correctly points to the children.The problem is
that the values held by the children are lost as I insert
multiple words into the root.

If you think about it, you'll realize that nodes in a trie have
identity. You're trying to use them as values, which doesn't
work. For starters, you should declare a private copy
constructor and assignment operator in Trie (which really should
be named TrieNode), and not implement them. Do this, and your
code won't compile: you've moved the error from compile time to
runtime.

I said it before: you need dynamic allocation. You're problem
can't be solved otherwise.

(That is, of course, the meta-problem. The actual symptom is
caused by the fact that you replace the node in the trie with a
new node, so any contents of the previous node are lost.)

 

[Rolf Magnus]

Hi again,
class trie {
private:
bool last_node;
map<char, trie> children;

//methods
....
....
....
}



I had changed the implementation for recursive insert to

This code is a part of recursive function.
trie new_child
new_child.insert(word.substr(1));//insert is called again.
//after inserting the nodes then connect it back to the parent
this->children[alphabet]=new_child;
.....
....
//if the map has an entry then
Trie next_child=this->children[letter];
child.insert(word.substr(1));

Now the node correctly points to the children.The problem is that the
values held by the children are lost as I insert multiple words into
the root.

Well, each time, you create a new Trie object and insert that into the map.
Your code replaces any old object with a fresh one, so the old content is
lost. You could try the alternative with the reference that I mentioned,
which won't do that.