A question about recursion and stacks of objects.

[JustSomeGuy]

I have a class that looks something like this (Don't try to compile it,
I haven't tested this)

class KVP
{
string key;
string value;
list<KVP> sublist;
};

class MyClass
{
private:
list<KVP> list;
public:
void parseInput(void);
};


My input looks something like.

a=b (Where a is the key and b is the value.)
c=e
d=e
b=c
f=g
h=j
k=l

So the number of tabs tells me how deeply nested I am.
I entend to implement this using a stack of KVPs.

void MyClass:arseInput(KVP & current)
{
int c;
while ((c = getchar()) != EOF)
{
if (c == '\t')
parseInput(list.front().sublist);
else
{
current.key = getkey();
current.value = getvalue();// get the key and value upto and
including the newline...
}
}
}

Of course at some point (the first call to parseInput needs 'this' as a
paramter...
Question is how do i know when to return and pop up to previous level?
When do I push_back the current to the list?
Got any tips or suggestions on how to do this?

 

[Victor Bazarov]

I have a class that looks something like this (Don't try to compile it,
I haven't tested this)

class KVP
{
string key;
string value;
list<KVP> sublist;
};

class MyClass
{
private:
list<KVP> list;
public:
void parseInput(void);
};


My input looks something like.

a=b (Where a is the key and b is the value.)
c=e
d=e
b=c
f=g
h=j
k=l

So the number of tabs tells me how deeply nested I am.
I entend to implement this using a stack of KVPs.

void MyClass:arseInput(KVP & current)
{
int c;
while ((c = getchar()) != EOF)
{
if (c == '\t')
parseInput(list.front().sublist);
else
{
current.key = getkey();
current.value = getvalue();// get the key and value upto and
including the newline...
}
}
}

Of course at some point (the first call to parseInput needs 'this' as a
paramter...
Question is how do i know when to return and pop up to previous level?
When do I push_back the current to the list?
Got any tips or suggestions on how to do this?

Honestly, I don't see a language problem here. It's a general programming
problem. The only condition that brings it closer to C++ (and similar
languages) is that the language should allow recursion. So, except for
that all you need is some pseudo-code that processes your input.

The input should read an entire line. Then count the tabs and determine
whether it should attempt to add to the sublist (if there more tabs than
the current level) or return (if the number of tabs is the same or less).

This is my attempt at pseudo-code:

void KVP:rocess_line(current_level, next_line, source)
begin
key = get_key_from_line(next_line)
value = get_value_from_line(next_line)
while (source.ok())
next_line = source.get_next_line()
new_tabs = number_of_tabs(next_line)
if (new_tabs > current_level)
new_KVP = new KVP
sublist.add(new_KVP);
new_KVP.process_line(current_level + 1, next_line, source)
else
return
endif
endwhile
end

Do criticize, please.

V

 

[JustSomeGuy]

Honestly, I don't see a language problem here. It's a general programming
problem. The only condition that brings it closer to C++ (and similar
languages) is that the language should allow recursion. So, except for
that all you need is some pseudo-code that processes your input.

The input should read an entire line. Then count the tabs and determine
whether it should attempt to add to the sublist (if there more tabs than
the current level) or return (if the number of tabs is the same or less).

This is my attempt at pseudo-code:

void KVP:rocess_line(current_level, next_line, source)
begin
key = get_key_from_line(next_line)
value = get_value_from_line(next_line)
while (source.ok())
next_line = source.get_next_line()
new_tabs = number_of_tabs(next_line)
if (new_tabs > current_level)
new_KVP = new KVP
sublist.add(new_KVP);
new_KVP.process_line(current_level + 1, next_line, source)
else
return
endif
endwhile
end

Do criticize, please.

V

Yes Of course you are right I hadn't actually thought of this and not being a
c++ problem.
Where is the 'Take back stupid OT posting' button!
Further I wish I could have edited the posting because there are a few errors.

As it stands if you return up to the very top of the 'stack' ie the lowest
recursion level
at then end of each line then you will end up back at the right level
eventually, at which
point you can simply add to the 'end' of that list. Agreed?

 

[JustSomeGuy]

Yes Of course you are right I hadn't actually thought of this and not being a
c++ problem.
Where is the 'Take back stupid OT posting' button!
Further I wish I could have edited the posting because there are a few errors.

As it stands if you return up to the very top of the 'stack' ie the lowest
recursion level
at then end of each line then you will end up back at the right level
eventually, at which
point you can simply add to the 'end' of that list. Agreed?

Which brings me to the C++ question....

If I wish to traverse the list of lists I'm getting syntax errors...

list<KVP> & listref(list); // ie at the beggining I wish to point to the 'head'
of the list.
for (i=0; i < level; ++i) listref = listref.sublist;

This is were I am getting lost now. I can't get this to compile as it doesn't
seem to like using
refrences using templates...

 

[Victor Bazarov]

[...]
Which brings me to the C++ question....

If I wish to traverse the list of lists I'm getting syntax errors...

list<KVP> & listref(list); // ie at the beggining I wish to point to the 'head'
of the list.
for (i=0; i < level; ++i) listref = listref.sublist;

This is were I am getting lost now. I can't get this to compile as it doesn't
seem to like using
refrences using templates...

Well, post the actual code, let's see where you get stuck.

For me the following works OK:

#include <list>
using std::list;

struct KVP { int i; list<KVP> sublist; KVP(int i) : i(i) {} };

#include <iostream>
#include <string>

void traverse(KVP& ref, int level) {
std::cout << std::string(level, ' ') << ref.i << std::endl;
list<KVP>::iterator it = ref.sublist.begin();
while (it != ref.sublist.end())
traverse(*it++, level + 1);
}

int main() {
KVP root(42);
KVP level1_1(4201), level1_2(4202);
KVP level2_1(420101), level2_2(420202);
level1_1.sublist.push_back(level2_1);
level1_2.sublist.push_back(level2_2);
root.sublist.push_back(level1_1);
root.sublist.push_back(level1_2);

traverse(root, 0);
}

I filled the structure manually, of course, but the traversal is
recursive as you want.

V

 

[JustSomeGuy]

[...]
Which brings me to the C++ question....

If I wish to traverse the list of lists I'm getting syntax errors...

list<KVP> & listref(list); // ie at the beggining I wish to point to the 'head'
of the list.
for (i=0; i < level; ++i) listref = listref.sublist;

This is were I am getting lost now. I can't get this to compile as it doesn't
seem to like using
refrences using templates...

Well, post the actual code, let's see where you get stuck.

For me the following works OK:

#include <list>
using std::list;

struct KVP { int i; list<KVP> sublist; KVP(int i) : i(i) {} };

#include <iostream>
#include <string>

void traverse(KVP& ref, int level) {
std::cout << std::string(level, ' ') << ref.i << std::endl;
list<KVP>::iterator it = ref.sublist.begin();
while (it != ref.sublist.end())
traverse(*it++, level + 1);
}

int main() {
KVP root(42);
KVP level1_1(4201), level1_2(4202);
KVP level2_1(420101), level2_2(420202);
level1_1.sublist.push_back(level2_1);
level1_2.sublist.push_back(level2_2);
root.sublist.push_back(level1_1);
root.sublist.push_back(level1_2);

traverse(root, 0);
}

I filled the structure manually, of course, but the traversal is
recursive as you want.

V

Ok, this is cool...
I don't know why you declared KVP as a struct and not a class.
(Other than the fact that it won't compile when its a class.)
Why doesn't this work when I declare KVP as a class?

 

[JustSomeGuy]

#include <iostream>
#include <list>

using std::list;
using std::string;

struct KVP
{
int i;
list<KVP> sublist;
KVP(int i);
};

KVP::KVP(int i) : i(i)
{
}

int main (int argc, char * const argv[])
{
int c;
KVP root;
KVP &current=root;
while ((c=getchar()) != EOF)
{
if (c == '\t')
current = current.sublist.begin(); // This doesn't
work... I assume because I don't have an appropriate operator= defined.
else if (c == '\n')
current = root;
else
current.i=c;
}
return(0);
}

I think this is close to working. Note also that the root isn't a list.
Here I am not using recursion as I have no way of knowing it's time to 'pop'
up a level in recursion.
This might be simple to overcome if I put a period '.' into the input stream
when the stack should be popped.

 

[Victor Bazarov]

#include <iostream>
#include <list>

using std::list;
using std::string;

struct KVP
{
int i;
list<KVP> sublist;
KVP(int i);
};

KVP::KVP(int i) : i(i)
{
}

int main (int argc, char * const argv[])
{
int c;
KVP root;
KVP &current=root;
while ((c=getchar()) != EOF)
{
if (c == '\t')
current = current.sublist.begin(); // This doesn't
work... I assume because I don't have an appropriate operator= defined.

'current' is a reference. If you are attempting to make it refer to
a differnt object, here is some it can't be done. You may need
to rethink 'current'.

else if (c == '\n')
current = root;
else
current.i=c;
}
return(0);
}

I think this is close to working. Note also that the root isn't a list.

Nothing _is_ a list. However, the 'root' and other KVP objects
_have_ lists.

Here I am not using recursion as I have no way of knowing it's time to
'pop'
up a level in recursion.

Take my pseudo-code, loot at it well and translate into C++. Even if
it needs fixing, it is probably fairly close to what you need as far
as recursion is concerned.

This might be simple to overcome if I put a period '.' into the input
stream
when the stack should be popped.

Whatever floats your boat.

Good luck!

V

 

[Stephan Br?nnimann]

#include <iostream>
#include <list>

using std::list;
using std::string;

struct KVP
{
int i;
list<KVP> sublist;

The definition of `sublist' is undefined behaviour because
KVP is not completly defined at this point.
It works by accident only.

KVP(int i);
};

KVP::KVP(int i) : i(i)
{
}

int main (int argc, char * const argv[])
{
int c;
KVP root;
KVP &current=root;

You are using reference here ...
.... every assignment to `current' will write to `root'!

I guess you should use
KVP* current;
instead.

while ((c=getchar()) != EOF)
{
if (c == '\t')
current = current.sublist.begin(); // This doesn't
work... I assume because I don't have an appropriate operator= defined.

BTW: what if current.sublist is empty?

current = *(current.sublist.begin());

else if (c == '\n')
current = root;

.... this is always a self-assignment, most-likley `root' is no more
what it once was!

else
current.i=c;
}
return(0);
}

[snip]

regards,
Stephan Brönnimann
(e-mail address removed)
Open source rating and billing engine for communication networks.

 

[Victor Bazarov]

The definition of `sublist' is undefined behaviour because
KVP is not completly defined at this point.
It works by accident only.

It's not a definition. It's a declaration. When the user needs to
create an object of type 'KVP' it will have been completely defined.

[..]

V