PPP2 Chapter 17 Exercise 11

[DragonOsman]

I tried to print information within the second while-loop, but it's not printing anything. I guess it's not even running the loop for some reason.

Here (add_ordered()):

Link *Link::add_ordered(Link *n)
{
	Link *trav = this;
	if (trav)
	{
		// to make sure we start at the head
		while (trav->m_prev)
		{
			trav = trav->m_prev;
		}
	}

	std::string key;
	if (n)
	{
		key = n->m_god.name();
	}
	while (key < trav->m_god.name() && trav->m_succ)
	{
		trav = trav->add(n);
		trav = trav->m_succ;
		std::cout << "From add_ordered(), comparison loop: ";
		print_all(trav);
		std::cout << '\n';
		print_all(n);
		std::cout << '\n';
	}
	std::cout << "From add_ordered(): " << trav << ": ";
	print_all(trav);
	std::cout << '\n';
	return trav;
}

print_all():

void print_all(Link *p)
{
	std::cout << "{";
	while (p)
	{
		std::cout << "Name: " << p->m_god.name()
			<< " Myth: " << p->m_god.myth();
		if (p->m_god.vehicle() != "")
		{
			std::cout << " Vehicle: " << p->m_god.vehicle();
		}
		else
		{
			std::cout << "Vehicle: N/A";
		}
		std::cout << " Weapon: " << p->m_god.weapon();
		if ((p = p->next()))
		{
			std::cout << "\n";
		}
	}
	std::cout << "}";
}

print():

void print(const Link &current)
{
	Link trav = current;
	std::cout << "Address of *current is: " << &trav
		<< "; The name of the god is: " << trav.m_god.name()
		<< "; The previous pointer is: " << trav.previous()
		<< "; The next pointer is: " << trav.next() << '\n';
}

I also checked it in my debugger.

I changed the God class getters' signatures to what you suggested.

Edit: I'm now returning "this" in place of nullptr as a sentinel value in those functions.

[jlb]

Please explain what you think that second loop should be doing, in English. Then explain the purpose of each line in that second loop, in detail.

Why are you trying to print the entire "list" inside that loop? Wouldn't it be better just to see the values held in the single instance in question instead?

I also checked it in my debugger.

Checked what in your debugger? How? What did your debugger tell you?

[DragonOsman]

In the debugger, even after the last while-loop, the list still seemed to only have Odin in it.

As for what I think the loop should do. It should go through loop as long as the name string in the new node is less than the name string in the current node and the end of the list hasn't been reached yet. And it should insert the new node into the list before the current node if the condition is true or more on to the next node.

The purpose of the first line in the loop body is to insert the new node where it should go. The purpose of the second line is to move on to the next node in the list.

[jlb]

Okay since it seems to confuse you when I ask multiple questions from now on I'll only ask one question at a time.

In the debugger, even after the last while-loop, the list still seemed to only have Odin in it.

How can you tell using the debugger how many entries are contained in the list?

[DragonOsman]

I'm not being confused. Why do you think so?

When I run it in the debugger, both loops get skipped over completely. So I think they aren't being run. And if they aren't run, of course nothing would be in the list aside from the first node, either.

What about the other stuff I said, though?

I think it'd better to put the trav = trav->m_succ line within the loop condition so that it definitely updates it after each iteration. It's actually harder for me to tell if it'll really be updated if it's inside the loop body.

Speaking of that, though, I did this to the loop:

for (; trav->m_succ != nullptr; trav = trav->m_succ)
{
	if (key < trav->m_god.name())
	{
		trav = trav->insert(n);
	}
	else
	{
		trav = trav->add(n);
	}
}

I also want to ask about insert() and add() themselves. Like if I have them right or not. They check for whether or not m_prev (for insert()) or m_succ (for add()) is pointing nullptr or not before assigning n to it, which kind of worries me because right now the previous pointer of all of the nodes are pointing at nullptr, as are their next pointers.

Here's the code for those two functions:

Link *Link::insert(Link *n)
{
	if (n == nullptr)
	{
		return this;
	}
	n->m_succ = this;
	if (m_prev)
	{
		m_prev->m_succ = n;
	}
	n->m_prev = m_prev;
	m_prev = n;
	return n;
}

and:

Link *Link::add(Link *n)
{
	if (n == nullptr)
	{
		return this;
	}
	n->m_prev = this;
	if (m_succ)
	{
		m_succ->m_prev = n;
	}
	n->m_succ = m_succ;
	m_succ = n;
	return n;
}

[DragonOsman]

Okay, never mind that change to add_ordered()'s second loop. I'll change it back to the same while loop.

Link *Link::add_ordered(Link *n)
{
	if (!n)
	{
		return this;
	}

	Link *trav = this;
	if (!trav)
	{
		return this;
	}

	// to make sure we start at head of list
	while (trav->m_prev)
	{
		trav = trav->m_prev;
	}

	std::string key = n->m_god.name();
	while (key < trav->god().name() && (trav->m_succ))
	{
		trav = trav->m_succ;
		trav = trav->insert(n);
		trav = trav->m_succ;
	}
	return trav;
}

Anyway, what am I doing wrong now?

[jlb]

I'm not being confused. Why do you think so?

Because you rarely answer all of the questions that I pose when I ask more than one question at a time.

When I run it in the debugger, both loops get skipped over completely. So I think they aren't being run. And if they aren't run, of course nothing would be in the list aside from the first node, either.

What have you done to see why the loops aren't being run?

[DragonOsman]

I don't know what to try, exactly. I'm not that good at debugging.

Are you thinking I'm confused because I answered more of your questions than you thought I would?

[Thomas1965]

Normally you would set a breakpoint at the line while (trav->m_prev) and examine the value of trav->m_prev which is most likely nullptr, same procedure at line while (key < trav->god().name() && (trav->m_succ))

There are some videos on YouTube about using the debugger in VS - I hope you still use VS.

[MikeyBoy]

I don't know what to try, exactly. I'm not that good at debugging.

An obvious thing to do would be to look at the values of the variables that control the loop, to see why the loop isn't being run, and in what way those values differ from the values you expect them to have.

Then, look at the places where you expected those values to be set, and look to see how those values are being set, or use the debugger to explore why they're not being set.

Ultimately, it's about tracking back until you find at what point the behaviour of your program deviates from what you expected the behaviour to be, and looking at the values of the data to determine why that behaviour deviates.

Are you thinking I'm confused because I answered more of your questions than you thought I would?

When someone remarks that you're not answering all their questions, it's unlikely to be because they expected you to answer even fewer of their questions.

[jlb]

I don't know what to try, exactly. I'm not that good at debugging.

Why do you think I insisted you create that simple function to print() the values contained in you Link instances? Have you even tried to use it?

Are you thinking I'm confused because I answered more of your questions than you thought I would?

Yea, right. When have you ever done that?

[jlb]

An obvious thing to do would be to look at the values of the variables that control the loop, to see why the loop isn't being run, and in what way those values differ from the values you expect them to have.

IMO, the problem is that he has no idea what the control variables should be, much less what they actually are and his way of "debugging" is just throwing random code at the issue and hoping someone else will tell him exactly what is wrong.

[DragonOsman]

Didn't I show you output from print() twice already? Or do you think I made that up?

I do think it's strange that each of the "god" instances passed to print() have the same address. Why did that happen? I wonder if it has something to do with why the loops aren't running.

@jlb: And I did answer your questions earlier, didn't I? The only ones I didn't answer from that one post were these two: (but instead of answering them, I just did what you said I should do):

Why are you trying to print the entire "list" inside that loop? Wouldn't it be better just to see the values held in the single instance in question instead?

I do that sometimes.

The variable that controls the loop, for the second one, would be trav (since trav->m_succ is being tested for nullptr to see if we can still go forward through the list). And the name of the god in the current node is being compared to the current one, so but they aren't controlling the loop. Like how, in a regular for-loop, the variable controlling the loop is the integer initialized and updated in the initialization and update parts of the loop's parentheses. And for the first one as well it's trav (->m_prev).

Edit: Could it be that the reason those loops aren't running is because trav->m_prev and trav->m_succ are never non-NULL in this case?

[MikeyBoy]

Could it be that the reason those loops aren't running is because trav->m_prev and trav->m_succ are never non-NULL in this case?

If only there was some kind of tool that would let you see those what those values are, as the program is running, so that you could know the answer to that question for sure?

I'm not sure what we would call such a tool, but it would be awfully useful in debugging a program...

Seriously, it's stuff like this that is frustrating the people who are trying to help you. Over and over again, people have suggested that you use a debugger to find out what values your objects have as the program runs (or to do "poor man's debugging" by printing out values at the points where it would be useful to examine them), so that you can actually know what's going on. And then you keep on posting things that make it obvious that you haven't done that.

[jlb]

@jlb: And I did answer your questions earlier, didn't I?

No.

The only ones I didn't answer from that one post were these two: (but instead of answering them, I just did what you said I should do):

But you didn't answer the questions which were: Why are you trying to print the entire "list" inside that loop? This is a very important question because you don't seem to understand what your print_all() function is actually doing. And the second question is also important but unanswered. I don't care if you change your code, I want to know your reasoning because it is your reasoning that I am questioning.

Next for this question which you only partially answered:

Please explain what you think that second loop should be doing, in English. Then explain the purpose of each line in that second loop, in detail.

As for what I think the loop should do. It should go through loop as long as the name string in the new node is less than the name string in the current node and the end of the list hasn't been reached yet. And it should insert the new node into the list before the current node if the condition is true or more on to the next node.

This at least tries to address the first part of the question. But the second part is still lacking.

The purpose of the first line in the loop body is to insert the new node where it should go. The purpose of the second line is to move on to the next node in the list.

Your definition of "detail" is extremely different than my definition of "detail". When I talk about describing something in "detail" I mean describe in the smallest possible discrete steps, using pseudo code if necessary to help with the explanation.

Here is another question you either missed or misunderstood, that contains a hint as to your problems (note this is from a post on Oct 2 at 12:28).

So then why was I told I'd have to use both insert() and add() in the same loop?

Who told you that you would need use either insert() or add() in any loop?

Do you see that hint?

Didn't I show you output from print() twice already? Or do you think I made that up?

See here you go arguing minutia again. The purpose of that function is to help you debug your program, why aren't you using it in places where you suspect the program is not functioning as you expect?

I do think it's strange that each of the "god" instances passed to print() have the same address. Why did that happen? I wonder if it has something to do with why the loops aren't running.

You're going to need to post the code showing how you called the function, the code for the function it's self and the output you got from that function. You don't necessarily need to post your whole program. Just post the print function, the function where you called the print function and the output.

The variable that controls loop, for the second one, would be trav (since trav->m_succ is being tested for nullptr to see if we can still go forward through the list).

This is half correct. The primary condition that should control the second loop is that the current name is less than the desired name, the test for nullptr is secondary.

And the name of the god in the current node is being compared to the current one, so but they aren't controlling the loop. Like how, in a regular for-loop, the variable controlling the loop is the integer initialized and updated in the initialization and update parts of the loop's parentheses.

This doesn't make any sense to me, perhaps you need to rethink and clarify what you mean.

[DragonOsman]

I did look at trav and n in the debugger, and I saw that trav's next and previous pointers are both pointing at NULL. But they're initialized to NULL in the constructor and the insert() and add() functions set them to the necessary values. If I don't do something to set them to a non-NULL value before the loops, the loops will never start. Should I call insert() in add_ordered() before the first loop to make sure that the next and previous pointers aren't pointing at NULL? I could insert the new node wherever at first and then try to place it in the correct position in the loop.

As for the hint. Did you mean to tell me I had to use one of them in the second loop? But am I not already doing that (insert() in the second loop)? Or were you trying to tell me that I'd have to call insert() or add() before the loops, too, like I just asked? And then the second loop will fix it so that it's in lexicographical order.

For what you asked me to clarify.

When I say that the name of the god in the current node is being compared to the name in the current one, I'm talking about the comparison part of the condition in the second while-loop, key < trav->god().name().

So the primary condition controlling the loop is that above comparison, and the loop control variable is trav itself because you update that to traverse the list in the loop.

But I'm having trouble moving the node from where it was to the correct position.

Here's the code for add_ordered():

Link *Link::add_ordered(Link *n)
{
	if (!n)
	{
		return this;
	}

	Link *trav = this;
	if (!trav)
	{
		return this;
	}

	trav = trav->insert(n);
	std::cout << "In add_ordered(), after the first call to insert():\n";
	print(*trav);

	// to make sure we start at head of list
	while (trav->m_prev)
	{
		trav = trav->m_prev;
	}
	std::cout << "In add_ordered(), after the first while-loop:\n";
	print(*trav);

	std::string key = n->m_god.name();
	while (key < trav->m_god.name() && trav->m_succ)
	{
		trav = n->erase();
		trav = trav->m_succ;
		trav = trav->add(n);
		std::cout << "In add_ordered(), inside the second while-loop, after the call to add():\n";
		print(*trav);
		trav = trav->m_succ;
	}
	return trav;
}

Output:

In add_ordered(), after the first call to insert():
Address of *current is: 0133F5E4; The name of the god is: Zeus; The previous pointer is: 00000000; The next pointer is: 0133F71C
In add_ordered(), after the first while-loop:
Address of *current is: 0133F5E4; The name of the god is: Zeus; The previous pointer is: 00000000; The next pointer is: 0133F71C
In add_ordered(), after the first call to insert():
Address of *current is: 0133F5E4; The name of the god is: Thor; The previous pointer is: 00000000; The next pointer is: 0133F794
In add_ordered(), after the first while-loop:
Address of *current is: 0133F5E4; The name of the god is: Thor; The previous pointer is: 00000000; The next pointer is: 0133F794
In add_ordered(), after the first call to insert():
Address of *current is: 0133F5E4; The name of the god is: Frejya; The previous pointer is: 00000000; The next pointer is: 0133F80C
In add_ordered(), after the first while-loop:
Address of *current is: 0133F5E4; The name of the god is: Frejya; The previous pointer is: 00000000; The next pointer is: 0133F80C

{
Name: Frejya Myth: Norse Vehicle: N/A Weapon: Magic called seidr
Name: Thor Myth: Norse Vehicle: Chariot pulled by goats Tanngrisnir and Tanngnjostr Weapon: Hammer called Mjolnir
Name: Zeus Myth: Greek Vehicle: N/A Weapon: Thunderbolt
Name: Odin Myth: Norse Vehicle: Eight-legged flying horse called Sleipnir Weapon: Spear called Gungnir
}


Number of nodes in list is: 4

Odin should've been inserted before Thor. How do I move it there after insert()ing it, though? I tried to erase() it first.

[jlb]

I did look at trav and n in the debugger, and I saw that trav's next and previous pointers are both pointing at NULL.

Okay and is there something wrong with that?

f I don't do something to set them to a non-NULL value before the loops, the loops will never start.

Why would you think this? Where are you accessing "n" except to try to "add" n to the list?

As for the hint. Did you mean to tell me I had to use one of them in the second loop?

Nope. Carefully read the sentence.

Who told you that you would need use either insert() or add() in any loop?

But am I not already doing that (insert() in the second loop)?

That's a big part of the problem. What is the purpose of this loop, be specific.

Or were you trying to tell me that I'd have to call insert() or add() before the loops, too, like I just asked?

Nope, not before and not inside. Again what exactly is the purpose of that loop?

When I say that the name of the god in the current node is being compared to the name in the current one, I'm talking about the comparison part of the condition in the second while-loop, key < trav->god().name().

But is that the correct comparison?

The primary condition that should control the second loop is that the current name is less than the desired name

What is the current name (trav or n)? What is the desired name (trav or n).

But I'm having trouble moving the node from where it was to the correct position.

Yes I know that. This is because you haven't figured out what is the purpose of the second loop.

You need to print() the trav and n at the beginning of the function print() trav anywhere you try to use it to add or insert into the list.

I really recommend you get print() to print everything on one line with minimum labeling so that the outputs are easier to compare.

[DragonOsman]

So I'm not supposed to insert() or add() anything into the list into the second loop? If I compare n's name string with trav's in that loop, why would I not want to insert n into the list in that loop as well? And where and how will I put n in the list where I want to if I don't call insert() or add() inside the second loop?

print():

void print(const Link &current)
{
	Link trav = current;
	std::cout << "*current's address: " << &trav
		<< "; god's name: " << trav.god().name()
		<< "; previous pointer: " << trav.previous()
		<< "; next pointer: " << trav.next() << '\n';
}

add_ordered():

Link *Link::add_ordered(Link *n)
{
	if (!n)
	{
		return this;
	}

	Link *trav = this;
	if (!trav)
	{
		return this;
	}

	trav = trav->insert(n);
	std::cout << "In add_ordered(), after the first call to insert():\n";
	print(*trav);

	// to make sure we start at head of list
	while (trav->m_prev)
	{
		trav = trav->m_prev;
	}
	std::cout << "In add_ordered(), after the first while-loop:\n";
	print(*trav);

	std::string key = n->m_god.name();
	while (trav->m_god.name() < key && trav->m_succ)
	{
		trav = n->erase();
		trav = trav->m_succ;
		trav = trav->add(n);
		std::cout << "In add_ordered(), inside the second while-loop, after the call to add():\n";
		print(*trav);
		trav = trav->m_succ;
	}
	return trav;
}

output:

In add_ordered(), after the first call to insert():
*current's address: 009EF22C; god's name: Zeus; previous pointer: 00000000; next pointer: 009EF364
In add_ordered(), after the first while-loop:
*current's address: 009EF22C; god's name: Zeus; previous pointer: 00000000; next pointer: 009EF364
In add_ordered(), after the first call to insert():
*current's address: 009EF22C; god's name: Thor; previous pointer: 00000000; next pointer: 009EF3DC
In add_ordered(), after the first while-loop:
*current's address: 009EF22C; god's name: Thor; previous pointer: 00000000; next pointer: 009EF3DC
In add_ordered(), after the first call to insert():
*current's address: 009EF22C; god's name: Frejya; previous pointer: 00000000; next pointer: 009EF454
In add_ordered(), after the first while-loop:
*current's address: 009EF22C; god's name: Frejya; previous pointer: 00000000; next pointer: 009EF454

{
Name: Frejya Myth: Norse Vehicle: N/A Weapon: Magic called seidr
Name: Thor Myth: Norse Vehicle: Chariot pulled by goats Tanngrisnir and Tanngnjostr Weapon: Hammer called Mjolnir
Name: Zeus Myth: Greek Vehicle: N/A Weapon: Thunderbolt
Name: Odin Myth: Norse Vehicle: Eight-legged flying horse called Sleipnir Weapon: Spear called Gungnir
}


Number of nodes in list is: 4

Is the purpose of the second loop supposed to be to reorder the nodes after putting them in outside the loop?

[jlb]

Please post your main() function.

Your main problem is that you don't understand what is happening, throwing more random code at the problem will not solve anything.

The purpose of the second loop is to find the location where you need to insert your new record, nothing else!

By the way your output from print() with the "current" address doesn't surprise me since trying to print the value of the pointer in that function is meaningless since it's a copy.

Do you not understand what your insert function is actually doing and what it is returning to the calling function?

[DragonOsman]

It inserts its argument before this object and then returns its argument to the calling function.

Anyway, basically, I have to make an if-else chain before the second loop that would compare the current node's name string to that of the one to be inserted and use insert() or add() accordingly, or else print an error if both strings are equal (I'll use error(), since I'm already catching a runtime error in main()). Is that good? I just need to see how to get the user to give add_ordered() a non-NULL and otherwise correct argument after catching the exception.

And the second loop is just meant to traverse the list as long as a NULL next pointer hasn't been found? So that's what you meant when you asked who ever told me to use insert() or add() in either loop.

Edit: Okay, I got it. Here's main():

int main()
{
	try
	{
		Link Odin{ God{"Odin", "Norse", "Eight-legged flying horse called Sleipnir", "Spear called Gungnir"} };
		Link Zeus{ God{"Zeus", "Greek", "", "Thunderbolt"} };
		Link Thor{ God{"Thor", "Norse", "Chariot pulled by goats Tanngrisnir and Tanngnjostr", "Hammer called Mjolnir"} };
		Link Frejya{ God{"Frejya", "Norse", "", "Magic called seidr"} };

		Link *gods;

		gods = &Odin;
		gods = gods->add_ordered(&Zeus);
		gods = gods->add_ordered(&Thor);
		gods = gods->add_ordered(&Frejya);

		std::cout << '\n';
		print_all(gods);
		std::cout << "\n\nNumber of nodes in list is: " << gods->element_count() << '\n';
	}
	catch (const std::runtime_error &rte)
	{
		std::cerr << "Runtime error: " << rte.what() << '\n';
		keep_window_open();
		return 2;
	}
	catch (const std::exception &e)
	{
		std::cerr << "Exception: " << e.what() << "\n";
		keep_window_open();
		return 2;
	}
	catch (...)
	{
		std::cerr << "An unknown exception occurred\n";
		keep_window_open();
		return 3;
	}

	keep_window_open();
}

add_ordered():

Link *Link::add_ordered(Link *n)
{
	if (!n)
	{
		return this;
	}

	Link *trav = this;
	if (!trav)
	{
		return this;
	}

	// to make sure we start at head of list
	while (trav->m_prev)
	{
		trav = trav->m_prev;
	}

	std::string key = n->m_god.name();
	if (trav->m_god.name() < key)
	{
		trav = trav->add(n);
	}
	else if (trav->m_god.name() > key)
	{
		trav = trav->insert(n);
	}
	else if (trav->m_god.name() == key)
	{
		error("Name of god to be inserted can't be the same as the name of a god already in the list");
	}

	std::cout << "In add_ordered(), after the if-else chain:\n";
	print(*trav);

	
	while (trav->m_god.name() < key && trav->m_succ)
	{
		std::cout << "In add_ordered(), inside the second while-loop, after the call to add():\n";
		print(*trav);
		print(*n);
		trav = trav->m_succ;
	}
	return trav;
}

output:

In add_ordered(), after the if-else chain:
*current's address: 004FF028; god's name: Zeus; previous pointer: 004FF1F0; next pointer: 00000000
In add_ordered(), after the if-else chain:
*current's address: 004FF028; god's name: Thor; previous pointer: 004FF1F0; next pointer: 004FF268
In add_ordered(), after the if-else chain:
*current's address: 004FF028; god's name: Frejya; previous pointer: 00000000; next pointer: 004FF1F0

{
Name: Frejya Myth: Norse Vehicle: N/A Weapon: Magic called seidr
Name: Odin Myth: Norse Vehicle: Eight-legged flying horse called Sleipnir Weapon: Spear called Gungnir
Name: Thor Myth: Norse Vehicle: Chariot pulled by goats Tanngrisnir and Tanngnjostr Weapon: Hammer called Mjolnir
Name: Zeus Myth: Greek Vehicle: N/A Weapon: Thunderbolt
}


Number of nodes in list is: 4

By the way, here's the function where I get the size of the list:

int Link::element_count()
{
	Link *trav = this;
	int size = 0;
	if (trav)
	{
		while (trav->m_prev)
		{
			trav = trav->m_prev;
		}

		while (trav->m_succ)
		{
			size++;
			trav = trav->m_succ;
		}
	}
	return size + 1;
}

I'd like to know how to define an actual iterator (std::iterator) for a custom type, since I also need it for the custom vector class in Chapters 17 and 18. There's a code listing in the book that I can't get to compile without it (in the copy constructor, std::copy(arg, arg + sz, elem);). The arg + sz part also won't compile without overloading an operator+, but I ended up getting a function that was recursive in all control paths when I tried to do it. I need help on this, too. Should I make a new thread for that?

Edit: Never mind about the iterator for now, since there's another part of this exercise to go still. I don't understand what it's asking for, exactly, either.

Using the Links with the values of type God, make a list of gods from three mythologies; then move the elements (gods) from that list to three lexicographically ordered lists — one for each mythology.

I get that it's asking to create three lists from three mythologies, but how it's saying to do that is what I don't get.