PPP2 Chapter 17 Exercise 11

[DragonOsman]

Why is it leaving only Bishamonten in the source list? What do I still need to do here?

main():

int main()
{
	try
	{
		Link *gods = new Link{ { "Odin", "Norse", "Eight-legged flying horse called Sleipnir", "Spear called Gungnir" } };
		gods = gods->add_ordered(new Link{ { "Thor", "Norse", "Chariot pulled by goats Tanngrisnir and Tanngnjostr",
			"Hammer called Mjolnir" } });
		gods = gods->add_ordered(new Link{ { "Baldr", "Norse", "A giant ship called Hringorni", "None" } });
		gods = gods->add_ordered(new Link{ { "Frejya", "Norse", "Chariot pulled by two cats", "Magic called seidr" } });
		gods = gods->add_ordered(new Link{ { "Zeus", "Greek", "A chariot pulled by the four major winds shaped as horses",
			"Thunderbolt and the shield called Aegis" } });
		gods = gods->add_ordered(new Link{ { "Hera", "Greek", "A chariot drawn by peacocks", "Her intelligence" } });
		gods = gods->add_ordered(new Link{ { "Athena", "Greek", "", "Allowed to use Zeus's Thunderbolt and the Aegis" } });
		gods = gods->add_ordered(new Link{ { "Ares", "Greek", "War chariot", "Sword and spear" } });
		gods = gods->add_ordered(new Link{ { "Amaterasu", "Japanese", "", "Sword of Kusanagi, Jewel of Yasakani, Mirror of Yata" } });
		gods = gods->add_ordered(new Link{ { "Susanoo", "Japanese", "", "Sword of Totsuka" } });
		gods = gods->add_ordered(new Link{ { "Izanagi", "Japanese", "", "Sword of Totsuka (later given to Susanoo)" } });
		gods = gods->add_ordered(new Link{ { "Bishamonten", "Japanese", "", "A spear" } });

		Link *Odin = new Link{ { "Odin", "Norse", "Eight-legged flying horse called Sleipnir", "Spear called Gungnir" } };
		Link *Zeus = new Link{ { "Zeus", "Greek", "A chariot pulled by the four major winds shaped as horses",
			"Thunderbolt and the shield called Aegis" } };
		Link *Amaterasu = new Link{ { "Amaterasu", "Japanese", "", "Sword of Kusanagi, Jewel of Yasakani, Mirror of Yata" } };

		Link *norse_gods = Odin;
		Link *greek_gods = Zeus;
		Link *jap_gods = Amaterasu;

		while (gods->find_if_myth("Norse"))
		{
			move_nodes(norse_gods, gods, "Norse");
		}
		while (gods->find_if_myth("Greek"))
		{
			move_nodes(greek_gods, gods, "Greek");
		}
		while (gods->find_if_myth("Japanese"))
		{
			move_nodes(jap_gods, gods, "Japanese");
		}

		Link *trav = gods->find("Bihamonten");
		if (trav)
		{
			trav->erase();
			jap_gods = jap_gods->add_ordered(trav);
		}

		std::cout << "\nnorse_gods list:\n";
		print_all(norse_gods);
		std::cout << "\ngreek_gods list:\n";
		print_all(greek_gods);
		std::cout << "\njap_gods list:\n";
		print_all(jap_gods);
		std::cout << "\ngods list:\n";
		print_all(gods);

		delete Odin;
		delete Zeus;
		delete Amaterasu;
		delete gods;
	}
	catch (const std::runtime_error &rte)
	{
		std::cerr << "Runtime error: " << rte.what() << '\n';
		keep_window_open();
		return 1;
	}
	catch (const std::bad_alloc &ba)
	{
		std::cerr << "Bad allocation error: " << ba.what() << '\n';
		keep_window_open();
		return 2;
	}
	catch (const std::exception &e)
	{
		std::cerr << "Exception: " << e.what() << "\n";
		keep_window_open();
		return 3;
	}
	catch (...)
	{
		std::cerr << "An unknown exception occurred\n";
		keep_window_open();
		return 4;
	}

	keep_window_open();
}

move_nodes():

void move_nodes(Link *dest_list, Link *source_list, const std::string &myth)
{
	Link *trav = source_list->find_if_myth(myth);
	if (trav)
	{
		if (trav == source_list)
		{
			trav = source_list->next();
		}
		trav->erase();
		if (trav->god().m_name != dest_list->god().m_name && trav->god().m_myth == myth)
		{
			dest_list = dest_list->add_ordered(trav);
		}
	}
}

[MikeyBoy]

What you need to do is use your debugger, and all your investigative and analytical skills, to find out where it's going wrong, and why it's going wrong at that point.

[DragonOsman]

It's not like I haven't tried doing that at all, you know.

[MikeyBoy]

OK, then. So should already have some helpful information:

- You should know on which line of your code that your program is misbehaving.
- You should be able to see the state your program's data (i.e. the values of the variables).
- You should be able to identify which of that data is in a state that you don't expect, such that it is causing your program to misbehave.

Having identified that, this is where you need to think. Using your knowledge and understanding of your own code, think about the places where that data is being set. Because it will be at one of those places that the data is being set to an unexpected value. Set breakpoints at those places, and look at that values are being stored in that data.

At the point where you see an unexpected value being stored in that data, then you have successfully identified an earlier point in your program where the misbehaviour is occurring.

Ideally, this will give a an understanding of what the real problem is. Think about why the program is doing what it's doing. Think about why it's deviating from what you want it to do.

But if it doesn't, then you repeat the steps above, but for this new line. Identify what data is wrong, identify the points at which that data could be being set, and use the debugger as described above to identify exactly where and when it's being set wrong.

Rinse, repeat, rinse, repeat, until you've found the root of the problem.

And at each stage, think. Understand the code. Understand what it really does - not in vague, general terms, but in terms of every single change that's made to every single variable.

Understand what you really want it to do - not in vague, general terms, but in terms of every single change that's made to every single variable.

[DragonOsman]

I didn't see any unexpected value being placed into a variable that I didn't want to be placed there. What I did see was one god always being skipped (Bishamonten). I also saw that Zeus remained in the source list in move_nodes() it tried to insert it into the Japanese list. It got erased from the source list, then the program saw that it doesn't belong in the Japanese list and didn't insert it there. But I don't get why it keeps skipping Bishamonten.

What do you suggest I try to do "move" code? What is the code

if (trav == source_list)
{
	trav = source_list->next();
}

actually doing? If it's skipping the head node, even when it's the node I want, how do I fix it? And if that's really what's going on, why doesn't the program crash from the next pointer being nullptr at that point?

[jlb]

I didn't see any unexpected value being placed into a variable that I didn't want to be placed there.

This is the problem, you're not "seeing" the problem. What variables are you looking at?

What I did see was one god always being skipped (Bishamonten).

Okay, is there anything special about Bishamonten?

I also saw that Zeus remained in the source list

Okay, is there anything special about Zeus?

What is the code actually doing?

This is a good question. Now, what do you think it is actually doing? How can you go about finding out what is actually happening? What do you need to look at? How?

[MikeyBoy]

What do you suggest I try to do "move" code? What is the code

if (trav == source_list)
{
	trav = source_list->next();
}

actually doing?

This is not me me being snarky, and this is not me asking a rhetorical question to disguise a criticism. It is a genuine question, designed to try and identify what is going wrong with your debugging process:

How is it possible that you don't know what that code is doing?

You wrote it. You know what you intended it to do when you wrote it. You know what each and every one of those variables is for. You know how the values of each and every one of those variables is set. It is not using any strange or obscure parts of the language.

You can see exactly what it is doing, in your debugger. You can see at every line, what it does and how the data values cause it to do what it does.

You know what trav is for, and you can see its value in the debugger every time the code is executed.

You know what source_list is for, and you can see its value in the debugger every time the code is executed.

You know what source_list->next() is for, and you can see what it does in the debugger every time the code is executed.

So, can you try and describe for me, in as specific language as possible, what it is that's causing you confusion about what the code is actually doing?

[jlb]

How is it possible that you don't know what that code is doing?

You wrote it.

No, this was supplied by the book.

[MikeyBoy]

OK, that I didn't know.

However, it is still true that:

(a) there's nothing particular about that code that is obscure. Each line should be self-explanatory. If it isn't, then of course we'll be happy to answer questions about them

(b) every aspect of what that code "actually does" can be thoroughly examined in a debugger, if anything is unclear.

But I guess I should re-word my assumptions as questions to the the OP:

Do you know what trav is for, what its value should be, and how its value should be changed?

Do you know what source_list is for, and what its value should be?

Do you know what source_list->next() is for, and what it does?

[DragonOsman]

@jlb: I was watching the variables trav, source_list, source_liist->m_succ, dest_list, and trav->m_succ. Without that part of the code that I asked about, there are nodes that aren't inserted where they should be that actually are when the code is included.

Zeus's node is already in the Greek list when control reaches the point where the nodes belonging to the Japanese list have to be moved. So I don't know why or how that node is also still there in the gods list and has to be tested to see if it belongs in the Japanese list.

What I think that code I asked about is doing is that it tests to see if trav is pointing at the correct list and then it moves to the next node if so. Is that correct? If so, could be why there's a node that keeps being skipped. Although that shouldn't happen when it's the only need left (unless Bishamonten and Zeus are both there even though Zeus isn't printed in the gods list for whatever reason, since it should be causing the program to crash from trying to access a null next pointer if Bishamonten's one is really the only node).

The variable trav is a temporary traversal pointer. The variable source_list is the original list that I'm trying to move nodes from. And source_list->next() is the function to access source_list's next pointer.

Link* p2 = norse_gods->find("Zeus");
if (p2) {
    if (p2 == norse_gods) p2 = norse_gods->next();
    p2->erase();
    greek_gods = greek_gods->insert(p2);
}

That's how Dr. Stroustrup moved Zeus from the Norse list to the Greek list in the book, to show how to correct the "mistake" he'd deliberately made.

This is a good question. Now, what do you think it is actually doing? How can you go about finding out what is actually happening? What do you need to look at? How?

Yeah, I'll try looking at that part in the debugger again.

[jlb]

I was watching the variables trav, source_list, source_liist->m_succ, dest_list, and trav->m_succ.

What about trav->prev, source_list->prev, dest_list->prev, dest_list->succ, and any others that I may have missed?

Zeus's node is already in the Greek list when control reaches the point where the nodes belonging to the Japanese list have to be moved. So I don't know why or how that node is also still there in the gods list and has to be tested to see if it belongs in the Japanese list.

This is why I asked:

Okay, is there anything special about Zeus?

which you didn't really answer. Is there something special about Zeus or Bishamonten?

What I think that code I asked about is doing is that it tests to see if trav is pointing at the correct list and then it moves to the next node if so. Is that correct?

But why do you even need to do this check?

What is the check actually checking?

Why wouldn't trav be pointing at the correct list?

That's how Dr. Stroustrup moved Zeus from the Norse list to the Greek list in the book, to show how to correct the "mistake" he'd deliberately made.

But this doesn't necessarily mean that this code will work unchanged for this application.

Yeah, I'll try looking at that part in the debugger again.

When you do you need to look at the big picture. What is happening to all the Links when you "move" one link? Are there any special cases you need to be concerned with, such as being at the "head" or the "tail" of the list?

You also should consider answering MikeyBoy's questions and concerns as well.

[DragonOsman]

But this doesn't necessarily mean that this code will work unchanged for this application.

Yeah, I figured as much. But taking it out also causes problems, so I need to find good code to put there where taking that part out won't create problems.

I tried to answer some of MikeyBoy's questions here:

What I think that code I asked about is doing is that it tests to see if trav is pointing at the correct list and then it moves to the next node if so. Is that correct? If so, could be why there's a node that keeps being skipped. Although that shouldn't happen when it's the only need left (unless Bishamonten and Zeus are both there even though Zeus isn't printed in the gods list for whatever reason, since it should be causing the program to crash from trying to access a null next pointer if Bishamonten's one is really the only node).

The variable trav is a temporary traversal pointer. The variable source_list is the original list that I'm trying to move nodes from. And source_list->next() is the function to access source_list's next pointer.

Anyway, I'll try to look at the big picture as you suggested.

[DragonOsman]

I'll show the code right now as well:

int main()
{
	Link *gods;
	try
	{
		gods = new Link{ { "Odin", "Norse", "Eight-legged flying horse called Sleipnir", "Spear called Gungnir" } };
		gods = gods->add_ordered(new Link{ { "Thor", "Norse", "Chariot pulled by goats Tanngrisnir and Tanngnjostr",
			"Hammer called Mjolnir" } });
		gods = gods->add_ordered(new Link{ { "Baldr", "Norse", "A giant ship called Hringorni", "None" } });
		gods = gods->add_ordered(new Link{ { "Frejya", "Norse", "Chariot pulled by two cats", "Magic called seidr" } });
		gods = gods->add_ordered(new Link{ { "Zeus", "Greek", "A chariot pulled by the four major winds shaped as horses",
			"Thunderbolt and the shield called Aegis" } });
		gods = gods->add_ordered(new Link{ { "Hera", "Greek", "A chariot drawn by peacocks", "Her intelligence" } });
		gods = gods->add_ordered(new Link{ { "Athena", "Greek", "", "Allowed to use Zeus's Thunderbolt and the Aegis" } });
		gods = gods->add_ordered(new Link{ { "Ares", "Greek", "War chariot", "Sword and spear" } });
		gods = gods->add_ordered(new Link{ { "Amaterasu", "Japanese", "", "Sword of Kusanagi, Jewel of Yasakani, Mirror of Yata" } });
		gods = gods->add_ordered(new Link{ { "Susanoo", "Japanese", "", "Sword of Totsuka" } });
		gods = gods->add_ordered(new Link{ { "Izanagi", "Japanese", "", "Sword of Totsuka (later given to Susanoo)" } });
		gods = gods->add_ordered(new Link{ { "Bishamonten", "Japanese", "", "A spear" } });
	}
	catch (const std::bad_alloc &ba)
	{
		std::cerr << "Bad allocation error: " << ba.what() << std::endl;
	}
	catch (const std::runtime_error &rte)
	{
		std::cerr << "Runtime error: " << rte.what() << std::endl;
	}
	catch (const std::exception &e)
	{
		std::cerr << "Exception: " << e.what() << std::endl;
	}

	try
	{
		Link *norse_gods = new Link{ {} };
		Link *greek_gods = new Link{ {} };
		Link *jap_gods = new Link{ {} };

		while (gods->find_if_myth("Norse"))
		{
			move_nodes(norse_gods, gods, "Norse");
		}
		while (gods->find_if_myth("Greek"))
		{
			move_nodes(greek_gods, gods, "Greek");
		}
		while (gods->find_if_myth("Japanese"))
		{
			move_nodes(jap_gods, gods, "Japanese");
		}

		std::cout << "\nnorse_gods list:\n";
		print_all(norse_gods);
		std::cout << "\ngreek_gods list:\n";
		print_all(greek_gods);
		std::cout << "\njap_gods list:\n";
		print_all(jap_gods);
		std::cout << "\ngods list:\n";
		print_all(gods);

		delete gods;
		delete norse_gods;
		delete jap_gods;
		delete greek_gods;
	}
	catch (const std::runtime_error &rte)
	{
		std::cerr << "Runtime error: " << rte.what() << std::endl;
	}
	catch (const std::bad_alloc &ba)
	{
		std::cerr << "Bad allocation error: " << ba.what() << std::endl;
	}
	catch (const std::exception &e)
	{
		std::cerr << "Exception: " << e.what() << std::endl;
	}

	keep_window_open();
}

void move_nodes(Link *dest_list, Link *source_list, const std::string &myth)
{
	Link *trav = source_list->find_if_myth(myth);
	if (trav)
	{
		trav->erase();
		if (trav->god().m_myth == myth)
		{
			dest_list = dest_list->add_ordered(trav);
		}
		trav = source_list->next();
	}
}

I initialized the destination lists with dummy nodes. That way I can see what list gets a node inserted and which doesn't, when it comes to Zeus, Amaterasu and Odin.

Anyway, right now I have an infinite loop again.

[jlb]

Yeah, I figured as much. But taking it out also causes problems, so I need to find good code to put there where taking that part out won't create problems.

No, you need to write good code, not find it. You can't write good code until you really understand the problem.

I initialized the destination lists with dummy nodes.

Are you sure that this is a good idea? What is going to happen to those "dummy nodes"? Do you expect them to magically disappear?



Edit:

I tried to answer some of MikeyBoy's questions here:

Looks like a bunch of gibberish to me. That code in question contains only two lines of code, why do you need a book to describe what they're doing.

Also you still haven't answered my questions about Zeus and Bis.

Edit 2:

Anyway, I'll try to look at the big picture as you suggested.

You do realize that to look at the big picture you need to know the values of the each of the "nodes"? By values I mean every pointer, the pointer to the actual "node" and that "nodes" next() and previous() pointers, the actual god names and myths are of little importance but may be nice to know.

[DragonOsman]

Well, for one thing, there are times when trav's m_succ is different from the source_list one. Also times when both were NULL.

I put those dummy nodes in there because I wasn't sure what else to do there. Initializing the nodes to nullptr makes the code crash when I try to put a valid pointer in there later. As for "finding good code to put in there," I didn't mean going on to the Internet and finding code to copy-paste. What I meant was figuring out what would be good to put there.

I don't know what to say about Zeus and Bishamonten because I don't know yet what's so special about them in this scenario. All I know is that they stay in the original list for longer than I want them to, with the latter staying in there until the end of the program.

You say the god's name is of little importance, but if I don't know the name, how do I know what nodes are staying in the original list that shouldn't be or whatnot?

What should I replace if (trav == source_list) trav = source_list->next(); with? Could I have at least a hint? If there's something I should replace it rather than just taking it out, which does seem to be the case.

Now excuse me; I need to find out why there's an infinite loop again.

[DragonOsman]

The reason for the infinite loop is that it gets stuck on Amaterasu when myth == "Japanese". It seems like it happens after Bishamonten is inserted into the Japanese list. But I don't know why it won't identify Zeus as a Greek god since it always goes into the while loop for the Japanese list just after inserting Hera into the Greek list. Zeus is still in there, but apparently it doesn't see it. I did this in main():

while (gods->find_if_myth("Norse"))
{
	move_nodes(norse_gods, gods, "Norse");
}
while (gods->find_if_myth("Greek"))
{
	move_nodes(greek_gods, gods, "Greek");
}
if (gods->find_if_myth("Greek"))
{
	move_nodes(greek_gods, gods, "Greek");
}
while (gods->find_if_myth("Japanese"))
{
	move_nodes(jap_gods, gods, "Japanese");
}

But the check for a node with the "GreeK' myth string still being left in the original list is somehow being evaluated as false.

It seems like part of the reason for it might be that I go back to the head node each time in my "find" functions. It goes back to the head node, but then it isn't able to get through to all of the nodes until it reaches the last one, perhaps due to some next pointers in the route being NULL. But I don't have it go back to the head node, most of the nodes that should go into the destination lists aren't inserted into the correct lists. So I'm confused.

Edit: current output:

norse_gods list:
{
Name: Baldr; Myth: Norse; Vehicle: A giant ship called Hringorni; Weapon: None
Name: Frejya; Myth: Norse; Vehicle: Chariot pulled by two cats; 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
}

greek_gods list:
{
Name: Ares; Myth: Greek; Vehicle: War chariot; Weapon: Sword and spear
Name: Athena; Myth: Greek; Vehicle: N/A; Weapon: Allowed to use Zeus's Thunderbolt and the Aegis
Name: Hera; Myth: Greek; Vehicle: A chariot drawn by peacocks; Weapon: Her intelligence
Name: Zeus; Myth: Greek; Vehicle: A chariot pulled by the four major winds shaped as horses; Weapon: Thunderbolt and the shield called Aegis
}

jap_gods list:
{
Name: Amaterasu; Myth: Japanese; Vehicle: N/A; Weapon: Sword of Kusanagi, Jewel of Yasakani, Mirror of Yata
Name: Bishamonten; Myth: Japanese; Vehicle: N/A; Weapon: A spear
}

gods list:
{
Name: Bishamonten; Myth: Japanese; Vehicle: N/A; Weapon: A spear
}

I took out the dummy nodes and did this instead:

Link *norse_gods = new Link{ { "Odin", "Norse", "Eight-legged flying horse called Sleipnir", "Spear called Gungnir" } };
Link *greek_gods = new Link{ { "Zeus", "Greek", "A chariot pulled by the four major winds shaped as horses",
			"Thunderbolt and the shield called Aegis" } };
Link *jap_gods = new Link{ { "Amaterasu", "Japanese", "", "Sword of Kusanagi, Jewel of Yasakani, Mirror of Yata" } };

[jlb]

You say the god's name is of little importance, but if I don't know the name, how do I know what nodes are staying in the original list that shouldn't be or whatnot?

Yes I said that the name is of little importance, I did not say "no importance". I said this because you seem to be so focused on the name that you appear to be missing the important information buried in that class, namely the pointers.

Could I have at least a hint? If there's something I should replace it rather than just taking it out, which does seem to be the case.

Before you do anything with this code you need to really understand what that code is actually doing.

Do you realize that in the following ramblings you have possible answers to some of your problems.

It seems like part of the reason for it might be that I go back to the head node each time in my "find" functions. It goes back to the head node, but then it isn't able to get through to all of the nodes until it reaches the last one, perhaps due to some next pointers in the route being NULL. But I don't have it go back to the head node, most of the nodes that should go into the destination lists aren't inserted into the correct lists.

I took out the dummy nodes and did this instead:

Why?

I put those dummy nodes in there because I wasn't sure what else to do there. Initializing the nodes to nullptr makes the code crash when I try to put a valid pointer in there later.

Why and where does the program crash? Perhaps you need to fix this issue before you continue?

[DragonOsman]

I changed the finding code such that it'd go to the tail and search from there. But now it gets stuck on a certain area in the source and dest lists when working on the Japanese gods.

I've put my code up on Gist. Would it be okay to just post a link to that here (it includes all of the code, including the custom .h and .cpp file I'm using)?

[jlb]

I changed the finding code such that it'd go to the tail and search from there. But now it gets stuck on a certain area in the source and dest lists when working on the Japanese gods.

So what does that tell you? It tells me nothing, because your problem description is too vague.

[DragonOsman]

It seems to do the Norse and Greek parts just fine, but gets into an infinite loop on the Japanese part. It looks like it's stuck on Susanoo. Of course, Amaterasu is already in there. I'm going backwards through the original list, so Susanoo is the first one it's trying to insert.