Trouble with lexicographical sorting in doubly-linked-list

[grumblesnake]

I'm currently working my way through Programming, Principles and Practice Using C++. I'm in chapter 17, which is basically an introduction to pointers and memory management. I'm at the second to last exercise, which involves creating three list of lexicographically ordered "gods", each taken from an unordered mixed list. The list is of a custom list type Link, used to help you understand the ways pointers are implemented in practice.
My method uses a myth-sorting-function that takes the unordered list and creates a lexicographically ordered list of a chosen myth string.
To a point it seems to be working as intended, but then it seems to malfunction and I can't quite figure out why.
Below is the output of something I've inserted into the name-ordering-function to determine the cause of the problem.
It basically compares the god string name of a new Link to one inserted from the unordered list, based on the greater/less than operator, to see which name should be first, and then goes back or forward in the new list, until it finds the right position, at which point it either "inserts" or "adds" depending on whether it is supposed to be before or after the current god.

I've just converted the first letter of each string name in the output below and what the result is supposed to entail.

Output:
80 < 84 insert(Poseidon) before Thor
79 < 80 insert(Odin) before Poseidon
90 > 84 add(Zeus) after Thor
84 < 90 insert(Tyr) before Zeus
77 < 79 insert(Mercury) before Odin
74 < 77 insert(Jupiter) before Mercury
76 > 77 add(Loki) after Mercury
77 > 79 add(Mars) after Odin
65 < 74 insert(Athena) before Jupiter
72 > 74 add(Hephaistos) after Jupiter


As you can see, according to my test, it sorts the names correctly until "Loki", which it for some reason "adds" after "Mercury" and hereafter every "add" is wrong.
This is in accordance with what I get when I write the list to the screen:

Name: Athena
Mythology: Greek
Vehicle:
Weapon: Spear

Name: Jupiter
Mythology: Roman
Vehicle:
Weapon: Staff

Name: Hephaistos
Mythology: Greek
Vehicle:
Weapon: Hammer

Name: Mercury
Mythology: Roman
Vehicle:
Weapon: Caduceus staff

Name: Loki
Mythology: Norse
Vehicle:
Weapon: Trickery

Name: Odin
Mythology: Norse
Vehicle: The eightlegged horse Sleipnir
Weapon: The spear Gungnir

Name: Mars
Mythology: Roman
Vehicle:
Weapon: Spear

Name: Poseidon
Mythology: Greek
Vehicle:
Weapon: Storms and earthquakes

Name: Thor
Mythology: Norse
Vehicle: Cart drawn by two goats
Weapon: The hammer Mjolnir

Name: Tyr
Mythology: Norse
Vehicle:
Weapon: Sword

Name: Zeus
Mythology: Greek
Vehicle:
Weapon: Lightning


Here is the link to the code:
https://github.com/tattermunge/PPP-myth-sorting

std_lib_facilities.h is like a catch-all header for the book, obviously not something I wrote myself.

I hope someone can help me solve this puzzle. It would be much appreciated.

[Niccolo]

For those following without the source, this is the focus of attention from the link in the OP:

...
        godlist = godlist->add_ordered(new Link{ God{ "Poseidon", "Greek", "", "Storms and earthquakes" } });
	godlist = godlist->add_ordered(new Link{ God{ "Odin", "Norse", "The eightlegged horse Sleipnir", "The spear Gungnir" } });
	godlist = godlist->add_ordered(new Link{ God{ "Zeus", "Greek", "", "Lightning" } });
	godlist = godlist->add_ordered(new Link{ God{ "Tyr", "Norse", "", "Sword" } }); 
	godlist = godlist->add_ordered(new Link{ God{ "Mercury", "Roman", "", "Caduceus staff" } });
	godlist = godlist->add_ordered(new Link{ God{ "Jupiter", "Roman", "", "Staff" } });
	godlist = godlist->add_ordered(new Link{ God{ "Loki", "Norse", "", "Trickery" } });
...	


Link* Link::add_ordered(Link* n)
{
	if (!n) return this;
	Link* p = this;
	bool before = false;
	while (n->god.name < p->god.name) {
		if (!before) before = true;
		if (!p->prev) break;
		else p = p->prev;
	}

	while (p->succ && n->god.name > p->god.name) p = p->succ;

	if (before) {
		cout << static_cast<int>(n->god.name[0]) << " < " << static_cast<int>(p->god.name[0]) << " insert(" << n->god.name << ") before " << p->god.name << "\n";
		p = p->insert(n);
	}
	else {
		cout << static_cast<int>(n->god.name[0]) << " > " << static_cast<int>(p->god.name[0]) << " add(" << n->god.name << ") after " << p->god.name << "\n";
		p = p->add(n);
	}

	return p;
}

@grumblesnake,

This is an edge case issue.

All goes well up to the point where the list contains the following:

Jupiter
Mercury
Odin
Poseidon
Thor
Tyr
Zeus

Notice that "add_ordered" returns "p", which itself is returned from either "insert" or "add", which will be the new node in each case.

This means, for example, that when "add_ordered" for "Odin" returned, "godlist" in the calling code pointed to the link for "Odin", and when "add_ordered" for "Jupiter" returned, "godlist" pointed to "Jupiter" in the calling code.

This is the key point in the code which is an edge case situation. At this point, "godlist" in the calling code points to the link for "Jupiter", which at that moment is the top of the linked list. It may seem odd, but "godlist" may point to any link in the doubly linked list upon return. To this point in the execution, this edge case situation has not yet happened.

The edge case, specifically, is that "add_ordered" is now to be called for a new link "Loki", where "god_list" is the instance for which "add_ordered" is called, and so within that function "this" is the "Jupiter" link, the top of the list, and the new link is supposed to be inserted just after the "Jupiter" link, but before the "Mercury" link.

Here is where things go wrong, at the top of "add_ordered"

	Link* p = this;
	bool before = false;
	while (n->god.name < p->god.name) {
		if (!before) before = true;
		if (!p->prev) break;
		else p = p->prev;
	}

The while loop will never execute its bracketed code, because the "n" link is "Loki", while the "p" link is "Jupiter", and since "Loki" is not less than "Jupiter", the loop will not execute.

The next code to execute is this:

while (p->succ && n->god.name > p->god.name) p = p->succ;

Here, since p->succ is not nullptr, and n->god.name is greater than p->god.name (being "Loki" is greater than "Jupiter", the loop does execute

p = p->succ;

It does this once, because p becomes the link for "Mercury", and thus stops the loop, with "p" pointing to "Mercury".

The requirement, at this point, is that "Loki" must be inserted before "Mercury".

The problem at this moment is that "before", a bool, is false.

It is false because the only place it can be made true is inside the loop at the top of this function, but that loop never executed. That left "before" false, when, under these circumstances, it would have to be true in order for the following to execute correctly

	if (before) {
		cout << static_cast<int>(n->god.name[0]) << " < " << static_cast<int>(p->god.name[0]) << " insert(" << n->god.name << ") before " << p->god.name << "\n";
		p = p->insert(n);
	}
	else {
		cout << static_cast<int>(n->god.name[0]) << " > " << static_cast<int>(p->god.name[0]) << " add(" << n->god.name << ") after " << p->god.name << "\n";
		p = p->add(n);
	}

This section, just after the loop that moved "p" to "Mercury", chooses how to apply the new node, either before or after the node "p".

As a result, it incorrectly executes the "after" clause, not the "before" clause as required.

There could be many "cures" for this.

One might be something like:

	while (p->succ && n->god.name > p->god.name) p = p->succ;

        if ( n->god.name < p->god.name ) before = true;

Alternatively, the entire theory of the algorithm could be adjusted so as not to depend upon the "before" flag in the first place (which, at this point, it really doesn't if the above change is applied).

[dhayden]

You're doing something I've never seen before: representing the list itself by a pointer to any old item in the list. Usually we keep a pointer to the head (and possibly the tail also).

[Niccolo]

@dhayden, it is odd, but it is also part of Stoustrup's walk through on the subject, so the OP is following the book's "plan" - one I'm not sure I get, either.

At first, I thought - this is wrong. Like you, I've always started with the top link as the container's member, but factually I can see that in a double linked list it actually does not matter so much, as any link would be a valid hold onto the structure. It's just an odd viewpoint.

It does "happen" to mean, though, that as often as not, the search point is near the position of the new entry, partly because the data is ordered so. I suspect he intends debugging to proceed with just a few loops, occasionally, instead of starting at the top only to have to sequence through to the bottom to append.

It really looks weird, though, and indeed - as Stroustrup has pointed out in lecture - this is a study on low level development strictly for the training of such things, and to generate appreciation for why we use the STL containers instead of making these things ourselves. Yet, as he appends, some engineers must be able to make them or there won't be any good ones.

[grumblesnake]

@Niccolo, I think I just made the mistake of not really thinking it through and thus completely overlooking that edge case. It just once again goes to show that it is never to late to go through your code again with new eyes.

So I guess a position in a list is referred to as a "node"? That is actually quite a helpful way for me to think about it, as the idea that any point in the list essentially contains the whole list was a bit confusing to me at first.

It probably isn't the most efficient way to do it, and I since writing it, I've come up with a few other methods, but as it is mainly a learning exercise, I decided to just change if (before) to
if (before || n->god.name < p->god.name) and move on.

@dhayden, I'll keep that in mind, my thought was that it would be restrictive in some way. But since I've yet to use an actual list in any way, that is purely conjecture with no basis in fact. As @Niccolo rightly assumed, my idea was also to theoretically reduce the number of loops. But since my understanding has grown since then, I'm not really sure that ever made sense.

In any case, you've solved the problem Niccolo, for which I've very thankful.
Have a nice day everyone.