PPP2 Chapter 17 Exercise 11

[DragonOsman]

It's not an infinite loop anymore, but I still can't get it to put the new elements into the list via add_ordered(). Are they each being overwritten by the next one entered for some reason because I'm doing the wrong checks for nullptr or am doing the wrong thing there, or something like that?

I need some sort of hint or something here. I don't mean to really be throwing code at the program expecting something to "accidentally" click here, though, I'm trying to think about what I'm doing. But, again, I need some sort of hint here.

Here's what I have now:

/**
 * This function is for use in lexicographical_compare() as a custom compare, 
 * such that the function does a case-insensitive compare of the two strings
 */
bool no_case(char a, char b)
{
	return tolower(a) < tolower(b);
}

/**
 * This function's specs are as follows:
 * Add a member function add_ordered() that places its new element in its correct lexicographical position. 
 * 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.
 */
Link *Link::add_ordered(Link *n)
{
	Link *trav = this;
	while (trav->m_prev != nullptr || trav->m_succ != nullptr)
	{
		std::string key = n->m_god.name();
		std::string name = trav->m_god.name();
		if (std::lexicographical_compare(key.begin(), key.end(), name.begin(), name.end(), no_case))
		{
			trav = trav->advance(-1);
			trav = trav->insert(n);
			if (trav->m_prev != nullptr)
			{
				if (std::lexicographical_compare(key.begin(), key.end(), name.begin(), name.end(), no_case))
				{
					trav = trav->advance(-1);
					trav = trav->insert(n);
				}
			}
			return trav;
		}
		else
		{
			trav = trav->advance(1);
			trav = trav->insert(n);
			if (trav->m_succ != nullptr)
			{
				if (!(std::lexicographical_compare(key.begin(), key.end(), name.begin(), name.end(), no_case)))
				{
					trav = trav->advance(1);
					trav = trav->insert(n);
				}
			}
			return trav;
		}
		trav = trav->m_succ;
	}
	return trav;
}

It just prints Thor's and Hera's information, in print_all(), and exits. I'm not copy-pasting everything because it make this post longer than 8192 characters.

[jlb]

To debug the problem without the debugger how can you tell what is happening if you never have any information available to help you figure out what is wrong?

Also as already pointed out no amount of debugging or rewriting will really help you until you really understand what should be happening. So please explain in plain English how you think the function should work. Be as precise as possible, no actual code required.

[jlb]

Are they each being overwritten by the next one entered for some reason because I'm doing the wrong checks for nullptr or am doing the wrong thing there, or something like that?

Probably one of the above. This is where debugging comes in, you need to somehow see what is happening inside the function. How can you do that?

Have you changed your main() in order to test this function? The main() in your last post has too much crap and it makes seeing what is actually happening way too difficult.

I suggest a main that has no more than the following:

int main()
{
	Link *norse_gods = new Link{ God{ "Thor", "Norse", 
		"Chariot pulled by goats Tanngrisnir and Tanngnjostr", "Mjolnir" } };
	norse_gods = norse_gods->add_ordered(new Link{ God{ "Odin", "Norse", 
		"Eight-legged flying horse called Sleipnir", "Spear called Gungnir" } });
	norse_gods = norse_gods->add_ordered(new Link{ God{ "Zeus", "Greek", "", "Lightning" } });

}

I also suggest you re-write your print function to print each "god" on a single line, without all the embellishments such as "Name: " and that you print the list after each line in main(). You may also want to alter you print function to only print the name of the god.

Don't forget to answer my questions from my last post.

[DragonOsman]

Okay, I'll try to explain what I think the function should do.

The way the list is written, when add_ordered() is called, there should already be at least one element in the list. If trav->m_succ or trav->m_prev is NULL, there's only one member in the list. But I'm not sure if I should allocate memory for it and then move there or just use advance() or do trav = trav->m_succ or trav = trav->m_prev to move there to insert a new element, depending on whether the name string of the God in the element I want to insert is lexicographically greater than or less than the one in the current element I'm comparing it to.

And because of the way advance() is written, since it also tests for NULL, I thought I'd have to use that if m_succ or m_prev is NULL and I want to go it.

If it successfully moves to where it has to be to insert the new element, it should insert it there in the correct position. So in the case of the current lists, the output should be

{
Name: Freyja
Myth: Norse
Vehicle: Chariot pulled by two cats
Weapon: Magic called seior

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: Mjolnir
}
{
Name: Ares
Myth: Greek
Vehicle: N/A
Weapon: A spear stained in blood

Name: Athena
Myth: Greek
Vehicle: N/A
Weapon: Two swords and a spear; is allowed to use Zeus's thunderbolt

Name: Hera
Myth: Greek
Vehicle: N/A
Weapon: Her cleverness

Name: Poseidon
Myth: Greek
Vehicle: N/A
Weapon: Three-pronged spear called Trident

Name: Zeus
Myth: Greek
Vehicle: N/A
Weapon: Lightning
}

^If I'm not mistaken, this would be expected output if add_ordered() works.

This is the current output, when add_ordered() isn't working as intended:

{
Name: Thor
Myth: Norse
Vehicle: Chariot pulled by goats Tanngrisnir and Tanngnjostr
Weapon: Mjolnir
}
{
Name: Hera
Myth: Greek
Vehicle: N/A
Weapon: Her cleverness
}

[jlb]

The way the list is written, when add_ordered() is called, there should already be at least one element in the list.

That is correct.

If trav->m_succ or trav->m_prev is NULL, there's only one member in the list.

No, this is not quite true. Can you tell me why? Or can you prove me wrong?

But I'm not sure if I should allocate memory for it

Why would you consider allocating memory for anything? Hasn't memory already been allocated?

and then move there or just use advance() or do trav = trav->m_succ or trav = trav->m_prev to move there to insert a new element, depending on whether the name string of the God in the element I want to insert is lexicographically greater than or less than the one in the current element I'm comparing it to.

Please clarify this statement, simplify it to each specific item. You're grouping too many discrete steps in one large sentence.

And because of the way advance() is written, since it also tests for NULL, I thought I'd have to use that if m_succ or m_prev is NULL and I want to go it.

Are you sure advance() is written correctly? Have you thoroughly tested this function to insure it matches your expectations?

If it successfully moves to where it has to be to insert the new element,

True.

it should insert it there in the correct position.

True, but how does the program know the "correct" position and how are you going to place the element into the "correct" position?

^If I'm not mistaken, this would be expected output if add_ordered() works.

Maybe, but you really need to rework your main() so that all it has is a single list, and only "inserts" the elements and doesn't do anything else that may confuse the issue.

[DragonOsman]

I'm not the one who wrote that advance() function, remember? I just copied it from the book as is. I just know what it does: if you pass a negative number, it'll traverse the list in reverse by that much while decrementing the given argument. If you give it a positive value it'll do the opposite of the above. All I did was convert it into a member function of the class. Or at least try to.

No, this is not quite true. Can you tell me why? Or can you prove me wrong?

I thought it would be that way because: when there's only one element in the list, wouldn't its previous and next pointers both be pointing to NULL? Or am I misunderstanding something?

As for what you're talking about here:

Please clarify this statement, simplify it to each specific item. You're grouping too many discrete steps in one large sentence.

Basically, what I'm saying is that I'll try to traverse the list. If the name string in the new element I want to insert is lexicographically "greater" than the element already in the list that I'm looking at, I'll follow the current element's next pointer and insert the new element at that location. Otherwise, follow the previous pointer and insert the new element there.

True, but how does the program know the "correct" position and how are you going to place the element into the "correct" position?

It should be the correct position since I'm doing a lexicographical compare.

Maybe, but you really need to rework your main() so that all it has is a single list, and only "inserts" the elements and doesn't do anything else that may confuse the issue.

How about this for main(), then?

int main()
{
	Link *greek_gods = new Link{ God{ "Hera", "Greek", "", "Her cleverness" } };
	greek_gods = greek_gods->add_ordered(new Link{ God{ "Athena", "Greek", "", 
		"Two swords and a spear; is allowed to use Zeus's thunderbolt" } });
	greek_gods = greek_gods->add_ordered(new Link{ God{ "Ares", "Greek", "", "A spear stained in blood" } });
	greek_gods = greek_gods->add_ordered(new Link{ God{ "Poseidon", "Greek", "", 
		"Three-pronged spear called Trident" } });
	greek_gods = greek_gods->add_ordered(new Link{ God{ "Zeus", "Greek", "", "Lightning" } });

	print_all(greek_gods);
	std::cout << '\n';

	keep_window_open();
}

[jlb]

I'm not the one who wrote that advance() function, remember?

No.

All I did was convert it into a member function of the class. Or at least try to.

That last bit is why I'm asking if you thoroughly tested the function.

I thought it would be that way because: when there's only one element in the list, wouldn't its previous and next pointers both be pointing to NULL? Or am I misunderstanding something?

Well there is a big difference between this statement and the statement I pointed out:

If trav->m_succ or trav->m_prev is NULL, there's only one member in the list.

Can you see the difference? The latter is correct, if both pointers are nullptr then only one element is in the list. However when one or both of the pointers are not nullptr then you have more than one element in the list.

Basically, what I'm saying is that I'll try to traverse the list. If the name string in the new element I want to insert is lexicographically "greater" than the element already in the list that I'm looking at, I'll follow the current element's next pointer and insert the new element at that location. Otherwise, follow the previous pointer and insert the new element there.

You need to break this huge statement into discreet steps. As worded the above statement is not totally correct, and the parts that are wrong are why you're having so much trouble.

It should be the correct position since I'm doing a lexicographical compare.

You're assuming something that may not be true at this point. You should be able to see the problem after you properly break out that big statement to it's discreet steps.

How about this for main(), then?

How about this:

int main()
{
	Link *greek_gods = new Link{ God{ "Hera", "Greek", "", "Her cleverness" } };
	print_all(greek_gods);

	greek_gods = greek_gods->add_ordered(new Link{ God{ "Athena", "Greek", "", 
		"Two swords and a spear; is allowed to use Zeus's thunderbolt" } });
	print_all(greek_gods);

	greek_gods = greek_gods->add_ordered(new Link{ God{ "Ares", "Greek", "", "A spear stained in blood" } });
	print_all(greek_gods);

	greek_gods = greek_gods->add_ordered(new Link{ God{ "Zeus", "Greek", "", "Lightning" } });

	print_all(greek_gods);
	std::cout << '\n';

	keep_window_open();
}

And with these changes, what is happening?


Did you modify your print statement to either print out the information for each god on a single line, or to only print out the name of the god?

[DragonOsman]

I just tested advance() and found that it does work.

Proof:

p is pointing to: Zeus
p is pointing to: Poseidon
p is pointing to: Ares
p is pointing to: Athena
p is pointing to: Hera

The code that generated it is:

        Link *greek_gods = new Link{ God{ "Hera", "Greek", "", "Her cleverness" } };

	greek_gods = greek_gods->insert(new Link{ God{ "Athena", "Greek", "", 
		"Two swords and a spear; is allowed to use Zeus's thunderbolt" } });

	greek_gods = greek_gods->insert(new Link{ God{ "Ares", "Greek", "", "A spear stained in blood" } });

	greek_gods = greek_gods->insert(new Link{ God{ "Poseidon", "Greek", "", 
		"Three-pronged spear called Trident" } });

	greek_gods = greek_gods->insert(new Link{ God{ "Zeus", "Greek", "", "Lightning" } });

	Link *p = greek_gods;
	while (p)
	{
		std::cout << "p is pointing to: " << p->m_god.name() << std::endl;
		p = p->advance(1);
	}

Anyways. I get that if one or both pointers are not pointing to nullptr, there is more than one element in the list. What if-condition would work for that? "if trav->m_succ is not nullptr OR trav->m_prev is not nullptr"?

And I think part of the problem I'm having is also to do with the fact that I can't tell how to not overwrite stuff when there's more than one element in the list. How should I take care of it in that case? Or is that a stupid question?

As for the statement you're saying to break into discreet steps. I'll try to break it down further later, but right now as well it's not exactly one huge statement. It's three statements, isn't it?

Basically, what I'm saying is that I'll try to traverse the list.(1) If the name string in the new element I want to insert is lexicographically "greater" than the element already in the list that I'm looking at, I'll follow the current element's next pointer and insert the new element at that location.(2) Otherwise, follow the previous pointer and insert the new element there.(3)

What are the problems in those statements?

[jlb]

What are the problems in those statements?

Which problem do you want to talk about first?

Basically, what I'm saying is that I'll try to traverse the list.(1)

This is too broad of a statement. How will you traverse the list?

If the name string in the new element I want to insert is lexicographically "greater" than the element already in the list that I'm looking at, I'll follow the current element's next pointer and insert the new element at that location.

Again not specific enough, and incorrect.

Also you really should be thinking in terms of "less than" since that's how most of the standard library works.

Otherwise, follow the previous pointer and insert the new element there.(3)

Again not specific enough, and incorrect.

You need to realize that since your code is broken there is some misunderstanding in your approach, so don't rely on your code when trying to thoroughly describe the process.

And I think part of the problem I'm having is also to do with the fact that I can't tell how to not overwrite stuff when there's more than one element in the list.

What do you mean by "overwrite stuff"? What "stuff" are you talking about?

[DragonOsman]

I'm traversing the list by following the next and previous pointers. To go forward, use next pointer. To backward, follow the previous pointer.

I did test for "less than" in the code when I used std::lexicographical_compare(). I read the documentation, so I know that it returns true if the first string is "less than" the second. So when I want to test for "greater than", I either do an "else" or I use the ! operator on the "if" checking the function's return value.

But how is what I said there incorrect? Are you saying I shouldn't insert *n into the list before the current element if it's "less than" the current element and after if it's "greater"? Or do you mean I'm doing it wrong since you said I should rely on my code to describe the process?

I need to see what the misunderstanding in my approach exactly is, in that case.

As for overwriting stuff, I was thinking that maybe the reason there's nothing in the list except for Hera and her information for Greek list isn't was entered at all, but more because what did get entered got overwritten by whatever got entered after it. If that's not what's happening, then maybe I did get the if-condition checking for whether there's one or more element(s) in the list correct. In that case, the problem is in how I'm trying to insert an element in the list.

[jlb]

I'm traversing the list by following the next and previous pointers. To go forward, use next pointer. To backward, follow the previous pointer.

Okay, how do you know which pointer to traverse? Where do you make this decision?

I did test for "less than" in the code when I used std::lexicographical_compare(). I read the documentation, so I know that it returns true if the first string is "less than" the second. So when I want to test for "greater than", I either do an "else" or I use the ! operator on the "if" checking the function's return value.

I didn't say that you didn't test for "less than" I said you need to start thinking in terms of less than.

But how is what I said there incorrect? Are you saying I shouldn't insert *n into the list before the current element if it's "less than" the current element and after if it's "greater"?

I'm saying two things, first your statement as a whole is incorrect, and two you have more than one discreet step in those statements. You need to break those statements down in much more detail.

As for overwriting stuff,

What is this "stuff" you keep talking about, be specific?

but more because what did get entered got overwritten by whatever got entered after it.

What exactly got overwritten, be specific?

But most of all how can you determine if your suspicions are correct or not? What do you need to do in order to "see" what is happening?

[TheIdeasMan]

Basically, what I'm saying is that I'll try to traverse the list.(1) If the name string in the new element I want to insert is lexicographically "greater" than the element already in the list that I'm looking at, I'll follow the current element's next pointer and insert the new element at that location.(2) Otherwise, follow the previous pointer and insert the new element there.(3)

Hi,

Could I suggest at this point that the OP do an old school thing? It's probably seems really boring to actually write something on real paper, with a real pencil, but I think you will find it very instructive.

Get some small pieces of paper (about sticky note size) and a pencil. Each piece of paper represents an item in the list, and will have written on it GodName , thisPtr, NextPtr, PrevPtr. But don't write any values just yet. The reason I have only included GodName is because that is sufficient to identify which item we are talking about, and that is the value on which we are sorting by.

Now for the first step in the program: insert 1 item. Fill in the values on the paper, use simple numbers: this =10 ; next = 0, prev = 0.

Now insert a second item: What is the process for doing that? You have a comparison to make ; A decision ; then actual steps for placing the item where it has to go. What are each of these things in code or pseudo code? Update the values on the paper for each item, they will have changed. That's why I suggest using a pencil :+)

Now insert a 3rd item: A big clue here, it's slightly different to the previous step . Do you know why? Actually, follow the instructions for inserting the second item: does it produce the correct results? It might do, depending on what the values are. OTOH it might not be for this or successive insertions, depending on the values. What do you need to do to make it work? Once you figure out why, you can generalize what an insertion looks like for any amount of the values already in the container. This is where you are going wrong at the moment.


This methodology an be used in 2 ways: To see where the current thinking goes wrong ; and what actually happens when it is done correctly. The first part leads to the realization of how to do the second part in practise (That is, in code), not just in the sense of knowing intuitively what the answer should be.

When you use a debugger, what you are doing is seeing how the current program goes wrong. You know what the results should be, but the results you see are different. I am not talking about the output, rather more like: The program inserted the item here, is that correct? No. Why not?

Good Luck, I hope this has helped you how to see what is going on :+)

[DragonOsman]

Okay, how do you know which pointer to traverse? Where do you make this decision?

If I want to go back, I go to where the previous pointer (trav->m_prev) is pointing; next pointer to go forward (trav->m_succ).

Let me just say first that I'm not sure what loop condition to use in the while-loop that I'll have in the following pseudocode.

if both m_succ and m_prev pointers of the current element are pointing to NULL (there is only one element):
    if element n is lexicographically less than the current element:
        follow m_prev to go backward one; insert element n at that location
        return updated list
    else
        follow m_succ to go forward one; insert element n at that location
        return updated list
else (there is more than one element in the list)
    while (/*what condition (such that the loop will stop when an element has been successfully inserted)?*/
        if element n is lexicographically less than the current element:
            follow m_prev to go backward one; insert element n at that location
            return updated list
        else
            follow m_succ to go forward one; insert element n at that location
            return updated list
        (somehow find a way to detect that an element was inserted; break out of loop if so)
return nullptr on failure

Two things I don't know here;
1. What could be a good looping condition to use?
2. How do I detect that an element was inserted?

Or do you see more problems in there?

What is this "stuff" you keep talking about, be specific?

I mean if there was an element there and I'm accidentally overwriting it. Although it does seem unlikely since there might not be anything being inserted in the first place. How can I tell? Use the debugger and watch the list?

Maybe I should make a counter variable that would be updated whenever an element was successfully inserted (make the counter a member of the class and create a member function to update it as needed). Then in the debugger, I could tell whether an element was inserted or not by watching that counter. The problem is that I don't know how I'll detect whether an element was inserted or not.

I was also thinking of maybe having the counter be decremented whenever an element is inserted. I'd assign to the counter in main(), with the same value as the number of elements I want to insert. In add_ordered(), once the counter hits 0, all of the elements I wanted to insert should've been inserted. I'd have a different counter for each mythology list, of course, so I'd have to have a separate initializer for each instance of the counter.

[TheIdeasMan]

Hi,

Your logic is still wrong, I strongly suggest you follow my advice in my last post. I realize you may have only just seen it :+)

[DragonOsman]

There's something I have to do differently when there are three or more elements in the list? So does that mean I need another condition in the while loop's if-else chain?

[jlb]

What makes you think you have to do something differently when there are three or more elements in the list?

[TheIdeasMan]

@Osman

Did you do the exercise I mentioned? I don't think that you have, you shouldn't have come to that conclusion. If you had done it, I am sure you might have learned something.

About doing something different: At the moment your logic is wrong, and works the first two times you insert something, but probably does not work for subsequent inserts. The exercise I mentioned was supposed to highlight this. If the logic is correct, then it will be the same logic no matter how many items are in the list. That is why I said this:

TheIdeasMan wrote:

Now insert a 3rd item: A big clue here, it's slightly different to the previous step . Do you know why? Actually, follow the instructions for inserting the second item: does it produce the correct results? It might do, depending on what the values are. OTOH it might not be for this or successive insertions, depending on the values. What do you need to do to make it work? Once you figure out why, you can generalize what an insertion looks like for any amount of the values already in the container. This is where you are going wrong at the moment.

I also said this:

TheIdeasMan wrote:

This methodology an be used in 2 ways: To see where the current thinking goes wrong ; and what actually happens when it is done correctly. The first part leads to the realization of how to do the second part in practise (That is, in code), not just in the sense of knowing intuitively what the answer should be.

Lets look at a number list, and follow your logic:

Inserting the first number is trivial, the list is this: {5}
The second number is trivial too: {5,6}
the 3rd number: {5,8,6} Bam, we have a problem Houston !! The same problem exists when the number to be inserted is less than the number at the beginning. You can discover these problems in code with the debugger - why did the program put that item there? What can I do to fix it?

I think we have now proved that your logic is wrong, so throw it away and start again. Delete the code from your add_ordered function. Btw, why isn't it named insert_ordered ?

Concentrate on this part:

Now consider this list: {5, 6, 9} we want to insert 8. What is the logic now?
Or even this list: {5,6,nullptr} we want to insert 8.

The thing about this whole question is that it is so easy that it is hard :+)

[DragonOsman]

Keep following the next or previous pointers as needed until we hit a nullptr, while comparing the element(s) against n. If we find an element with a name string that n is "less than", we go behind that element and insert n there. Otherwise, we go to the front of that element and insert n there.

I could make a counter for the number of non-NULL m_succ and m_prev pointers. I've noticed that the number of elements in the list is that number + 1.

Could I find that number and also insert n into the list in a for-loop? Or should I keep using a while-loop? And can both operations be done in a single loop, or should I use two different loops? If I use for-loop for the insertion operation, I should be able use a nested loop. Outer loop for going forward, inner loop for going backward. So in the outer loop, I'll write an if-condition to see if n is not lexicographically less than the current one, and in the inner loop I'll write an if-condition to check for the opposite.

Is that logic correct?

[jlb]

Is that logic correct?

It's not specific enough.

I could make a counter for the number of non-NULL m_succ and m_prev pointers. I've noticed that the number of elements in the list is that number + 1.

Why throw more logic into the process than necessary?

Or should I keep using a while-loop?

Yes stick to loops and if()/else statements.

And can both operations be done in a single loop, or should I use two different loops?

Have you done the task set by TheIdeasMan?

I'm going to suggest you make a few further changes to main() so that maybe you can see what is going on.

First, let's get rid of the dynamic memory and just use plain non-pointer instances of the three gods, in the following order, Thor, Odin, Zeus. Once you do that print out the following information (you may want to create a function to make this easier) the address of the instance, the name of the god, the previous pointer and the next pointer. This print should turn out something like the following:

0x7fff7dc8dde0
0x7fff7dc8df00 Thor m_prev:               0 m_next:               0
0x7fff7dc8de70 Odin m_prev:               0 m_next:               0
0x7fff7dc8dde0 Zeus m_prev:               0 m_next:               0

By the way that first number is your norse_gods pointer (The current start of the list).

And after you're finished you should end up with something like:

Using add_ordered:

Odin
Thor
Zeus

0x7fff7dc8dde0
0x7fff7dc8df00 Thor m_prev:  0x7fff7dc8de70 m_next:  0x7fff7dc8dde0
0x7fff7dc8de70 Odin m_prev:               0 m_next:  0x7fff7dc8df00
0x7fff7dc8dde0 Zeus m_prev:  0x7fff7dc8df00 m_next:               0

Again the numbers will probably be different but where the pointer points should be the same. Ie, Zeus previous points to Thor, and Zeus next is a nullptr.

As you should be able to see I'm only printing out the god names, the rest of the god structure can be blank.

Since you should know how to create a non-pointer instance of your Link class and how to assign and pass these non-pointer classes to your Link I'll leave the implementation to you.

[DragonOsman]

I was asking whether I should keep using a while-loop or switch to a for-loop (if it'll work), not whether or not I should continue using loops. I know I'll need a loop for this either way.

If I don't try that with the m_succ and m_prev pointers, how will I know how many elements there are in the list?

I want to do what TheIdeasMan suggested, but I don't really have a pen and paper to use near me. There should be some in the house, but I'll ask someone to give it to me. I do know the "pen and paper" method can help.