PPP2 Chapter 17 Exercise 11

[DragonOsman]

I sense sarcasm in that last line. Well, actually, I'll define a print function later. It's just, sometimes it's easier to type that out right in the function you need it in. :P [besides, I copy-pasted it and altered slightly as needed after typing it once, anyway.]

add_ordered():

Link *Link::add_ordered(Link *n)
{
	Link *trav = this;

	std::cout << "Before loop:\n";
	std::cout << "*trav:\n";
	print(*trav);
	std::cout << "*n:\n";
	print(*n);

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

	std::cout << "\nAfter loop:\n";
	std::cout << "*trav:\n";
	print(*trav);
	std::cout << "*n:\n";
	print(*n);

	if (n->m_god.name() < trav->m_god.name())
	{
		std::cout << "Inside first conditional check, before insertion:\n";
		std::cout << "*trav:\n";
		print(*trav);
		std::cout << "*n:\n";
		print(*n);
		trav = trav->insert(n);
		std::cout << "Inside first conditional check, after insertion:\n";
		std::cout << "*trav:\n";
		print(*trav);
		std::cout << "*n:\n";
		print(*n);
	}
	else if (!(n->m_god.name() < trav->m_god.name()))
	{
		std::cout << "Inside first else-if conditional check, before insertion:\n";
		std::cout << "*trav:\n";
		print(*trav);
		std::cout << "*n:\n";
		print(*n);
		trav = trav->add(n);
		std::cout << "Inside first else-if conditional check, after insertion:\n";
		std::cout << "*trav:\n";
		print(*trav);
		std::cout << "*n:\n";
		print(*n);
	}
	else if (n->m_god.name() == trav->m_god.name())
	{
		error("Name of God to insert cannot be the same as one already in the list");
	}

	std::cout << "After conditional for adding n to list:\n";
	std::cout << "*trav:\n";
	print(*trav);
	std::cout << "*n:\n";
	print(*n);

	return trav;
}

print():

void print(const Link &link)
{
	std::cout << "current Link object: " << &link << '\n'
		<< link.god().name() << '\n'
		<< link.previous() << '\n'
		<< link.next() << '\n';
}

output:

Before loop:
*trav:
current Link object: 00061088
Odin
00000000
00000000
*n:
current Link object: 00061130
Baldr
00000000
00000000

After loop:
*trav:
current Link object: 00061088
Odin
00000000
00000000
*n:
current Link object: 00061130
Baldr
00000000
00000000
Inside first conditional check, before insertion:
*trav:
current Link object: 00061088
Odin
00000000
00000000
*n:
current Link object: 00061130
Baldr
00000000
00000000
Inside first conditional check, after insertion:
*trav:
current Link object: 00061130
Baldr
00000000
00061088
*n:
current Link object: 00061130
Baldr
00000000
00061088
After conditional for adding n to list:
*trav:
current Link object: 00061130
Baldr
00000000
00061088
*n:
current Link object: 00061130
Baldr
00000000
00061088
Before loop:
*trav:
current Link object: 00061130
Baldr
00000000
00061088
*n:
current Link object: 0005F4D0
Thor
00000000
00000000

After loop:
*trav:
current Link object: 00061130
Baldr
00000000
00061088
*n:
current Link object: 0005F4D0
Thor
00000000
00000000
Inside first else-if conditional check, before insertion:
*trav:
current Link object: 00061130
Baldr
00000000
00061088
*n:
current Link object: 0005F4D0
Thor
00000000
00000000
Inside first else-if conditional check, after insertion:
*trav:
current Link object: 0005F4D0
Thor
00061130
00061088
*n:
current Link object: 0005F4D0
Thor
00061130
00061088
After conditional for adding n to list:
*trav:
current Link object: 0005F4D0
Thor
00061130
00061088
*n:
current Link object: 0005F4D0
Thor
00061130
00061088
Before loop:
*trav:
current Link object: 0005F4D0
Thor
00061130
00061088
*n:
current Link object: 000611D8
Frejya
00000000
00000000

Inside loop (before "trav = trav->m_prev":
*trav:
current Link object: 0005F4D0
Thor
00061130
00061088
*n:
current Link object: 000611D8
Frejya
00000000
00000000

Inside loop (after "trav = trav->m_prev":
*trav:
current Link object: 00061130
Baldr
00000000
0005F4D0
*n:
current Link object: 000611D8
Frejya
00000000
00000000

After loop:
*trav:
current Link object: 00061130
Baldr
00000000
0005F4D0
*n:
current Link object: 000611D8
Frejya
00000000
00000000
Inside first else-if conditional check, before insertion:
*trav:
current Link object: 00061130
Baldr
00000000
0005F4D0
*n:
current Link object: 000611D8
Frejya
00000000
00000000
Inside first else-if conditional check, after insertion:
*trav:
current Link object: 000611D8
Frejya
00061130
0005F4D0
*n:
current Link object: 000611D8
Frejya
00061130
0005F4D0
After conditional for adding n to list:
*trav:
current Link object: 000611D8
Frejya
00061130
0005F4D0
*n:
current Link object: 000611D8
Frejya
00061130
0005F4D0

I can already see the same problem as before. Odin is inserted after Thor.

I can't see how I can get it to find its position given either case for whether n has to go before or after the current node. It does it fine up to the point of figuring out if n should go before the current node or after, but I think I need it to keep looking until it finds the best place to insert n. I don't know how to say that in code, though. And where should I put the loop for having it do that? Should I put in a variable that increments for however many times I need to keep advancing either forward or backward?

I saw in earlier posts that Thomas or someone else had said that I'd have to find where to put n whether it's less than or greater than the current node. It's because it just inserts it immediately after seeing "before" or "after", instead of traversing the list in either direction to see where would be best to insert it before, or where would be best to insert after the current node.

But yeah, I don't know how to make it do that. Just that I might need to.

Maybe I should put the if-else-if-else chain inside a loop that traverses the list in either direction to look for the correct place to insert n, and have "outer condition" that traverses the list forward as long as n is less than the current node.

[jlb]

I sense sarcasm in that last line.

I'm glad you sensing something that is correct at last.

It would be much easier to see what is going on if every print() statement printed everything on one line. Something like:

void print(Link& c)
{
    using std::cout;
    using std::endl;
    using std::setw;
    using std::left;
    using std::right;
    cout << &c << " " << setw(10) << left <<  c.god.name
         << " prev: " << setw(15) << c.previous()
         << " succ: " << setw(15) << c.next() << endl;

}

You can also get rid of the print() of n, except for the first one.

Now to the new code. Note I removed all but the required logic for clarity.

	if (n->m_god.name() < trav->m_god.name())
	{
		trav = trav->insert(n);
	}
	else if (!(n->m_god.name() < trav->m_god.name()))
	{
		trav = trav->add(n);
	}
	else if (n->m_god.name() == trav->m_god.name())
	{
		error("Name of God to insert cannot be the same as one already in the list");
	}

Now some questions:

What is the order of the gods you're trying to add?

How many elements are added before there are problems?

NOTE: Don't make any logic changes to our code until you are told to try something else.

[DragonOsman]

What is the order of the gods you're trying to add?

Current order is Baldr, Thor, Frejya. Desired order is Baldr, Frejya, Thor. It seems that current logic right now inserts the node incorrectly when it has to add it after the current node. It's inserting Thor before Odin, for example. So it's fine when it has to insert n before the current node, but not when it has to insert it after.

How many elements are added before there are problems?

2 elements.

I'm thinking that the purpose of that second loop may have been to try to find the right place to insert the new node. The initial if-statement checks if trav is (not) less than n. The while loop's condition checks if trav is less than n and traverses the loop as long as it is and as long as trav's next pointer is not nullptr.

But I wonder if both of those have to meshed into one. It won't even run the loop if there's only one (or zero) node(s) in the list, but if I put that if-statement before the loop, it'll be out of order and I'll have to rearrange it in the loop. That's too much work.

[DragonOsman]

Should I wait until someone replies before I edit my code again? I think I should, but I just want to make sure.

Edit: And I'm returning n instead of trav now, so that add_ordered() will always start at the head of the list when called.

[jlb]

Current order is Baldr, Thor, Frejya.

What? Looking at the output of the program Odin appears to be first followed by Baldr then Thor then Frejya.

Can you verify my assumptions?

Edit: And I'm returning n instead of trav now, so that add_ordered() will always start at the head of the list when called.

What? Why do you think that returning n in trav will magically insure that you are at the head of the list.

I'm thinking that the purpose of that second loop may have been to try to find the right place to insert the new node. The initial if-statement checks if trav is (not) less than n. The while loop's condition checks if trav is less than n and traverses the loop as long as it is and as long as trav's next pointer is not nullptr.

You're close but the initial if statement has nothing to do with the second while loop. Stop worrying about that while loop for now.

Should I wait until someone replies before I edit my code again? I think I should, but I just want to make sure.

That would be best, just throwing code at the problem without understanding what is wrong won't do any good.

For now answer the new questions posed above. And note both questions are important but the first most important.

[DragonOsman]

I thought you meant just the nodes being added via add_ordered(). I would've said, "Odin, Baldr, Thor, Frejya" if I'd known that you meant "all of them".

As for why I think returning n would ensure that the function starts at the head. If I return trav, it'll start at what trav was when the function returned last time, right? With this, I might not need the loop that goes backwards until it hits a NULL previous pointer.

I think I just don't understand the "why" of what's wrong at this point. I think already get the "what". The "what" is that it's inserting n before the current node no matter what (right?).

[jlb]

If I return trav, it'll start at what trav was when the function returned last time, right?

Will it? Manually follow the logic with two gods, make sure you reverse the order of these two gods and do it again. This requires no modifications to your code or even running the program. Do it manually. Lastly try with both names the same. Then tell me your conclusions about the return value and why.

I thought you meant just the nodes being added via add_ordered(). I would've said, "Odin, Baldr, Thor, Frejya" if I'd known that you meant "all of them".

Of course I meant all of them. How else can I tell what is happening.

Now after verifying the actual order of input can you verify, looking at your program output, if Baldr is actually being added correctly?

[DragonOsman]

I created and printed trav in main(). Saw that it's pointing at the last node inserted. So I made another loop that will point trav at the head before the return statement and then changed the return statement back to "return trav;". Now it's fine.

Anyway, looking at the program output it seems like Baldr is being added correctly. I may have to change the order again to verify. Should I? I'll do that all of them, actually. I don't want to take any chances if possible.

Edit: Basically what I think I should try to do to verify is to put them in reverse order compared to what the order would be if add_ordered() was correct. So if the correct would be "Baldr, Frejya, Odin, Thor" (if add_ordered() worked correctly), I'll put them into the list in reverse ordered compared to that. So in other words, "Thor, Odin, Frejya, Baldr".

By the way, it seems like I need to hurry up and get done with learning C++ and then try to do something to start making money fast. I'm already 27 and I've been at this for 2-3 years, maybe more. So I need to get a mentor to help me learn. I'm thinking of talking to the mentor over a Discord channel if I can't go to them in person.

It may sound like I'm rushing, but actually I don't want to rush if I can help it.

If the mentor can also help me with learning Boost (especially Boost.Asio) and Wt, that'll be a great help. I want to make web apps in Wt, but first I need to learn Wt.

I'd prefer it if the mentor would be willing to help for free. I'm scared that if I had to pay, I might not be able to afford it.

[jlb]

I created and printed trav in main(). Saw that it's pointing at the last node inserted. So I made another loop that will point trav at the head before the return statement and then changed the return statement back to "return trav;". Now it's fine.

Why do all this extra work? What is the purpose of that first loop?

By the way if you're just going to keep throwing random code at the problem we might as well stop right now and not waste any more time.

Anyway, looking at the program output it seems like Baldr is being added correctly.

The it appears that your if() logic is about right.

However you don't need that last else statement and the else if() should just be an else.

[DragonOsman]

So I don't need trav to be pointing at the head when returning?

And my plan isn't to keep throwing random code at the problem. I'll go back to waiting now, then. But I do think I should verify if the other nodes are being added correctly first.

This:

Basically what I think I should try to do to verify is to put them in reverse order compared to what the order would be if add_ordered() was correct. So if the correct would be "Baldr, Frejya, Odin, Thor" (if add_ordered() worked correctly), I'll put them into the list in reverse ordered compared to that. So in other words, "Thor, Odin, Frejya, Baldr".

What do you think?

Also, I'll post this again as well:

By the way, it seems like I need to hurry up and get done with learning C++ and then try to do something to start making money fast. I'm already 27 and I've been at this for 2-3 years, maybe more. So I need to get a mentor to help me learn. I'm thinking of talking to the mentor over a Discord channel if I can't go to them in person.

It may sound like I'm rushing, but actually I don't want to rush if I can help it.

If the mentor can also help me with learning Boost (especially Boost.Asio) and Wt, that'll be a great help. I want to make web apps in Wt, but first I need to learn Wt.

I'd prefer it if the mentor would be willing to help for free. I'm scared that if I had to pay, I might not be able to afford it.

Who are the three people on this site who do mentoring for free? I'll just talk to one of them if they're also good with Wt and Boost.

[jlb]

And my plan isn't to keep throwing random code at the problem. I'll go back to waiting now, then. But I do think I should verify if the other nodes are being added correctly first.

You already know it's not working.

Current order is Baldr, Thor, Frejya. Desired order is Baldr, Frejya, Thor. It seems that current logic right now inserts the node incorrectly when it has to add it after the current node.

Right now you need to figure out is when it is failing. For example

By the way, it seems like I need to hurry up and get done with learning C++ and then try to do something to start making money fast. I'm already 27 and I've been at this for 2-3 years, maybe more. So I need to get a mentor to help me learn.

Hurrying up won't help, if you can't debug you will be of little value to any employer. If you intend to find a mentor you need to find a mentor that can personally mentor you in person, I doubt internet mentoring is going to speed anything up.

And my plan isn't to keep throwing random code at the problem.

But that's exactly what you're doing and it is the very problem that has gotten you so confused.

That is why is explicitly said:

Manually follow the logic with two gods, make sure you reverse the order of these two gods and do it again. This requires no modifications to your code or even running the program. Do it manually. Lastly try with both names the same. Then tell me your conclusions about the return value and why.

Which it seems that you haven't yet done. That manual part is very important, it should make you think not just react.

Right now you need to focus on the first call to add_ordered(). Is it always placing the 'n' in the proper order? Making sure the first record is always placed correctly will tell you your logic is basically correct.

So for now take Odin as the first (only) record then insert only Thor. Does it get put into the proper order (this is using your code from the first post on this page)? Note the results.

Next have Thor as the first (only) record then insert only Odin. Does it get put into the proper order? Note the results.

After you've done these two tests, come back with the results. If both these tests work you will be ready to go to the next phase.

[DragonOsman]

One question, though:

However you don't need that last else statement and the else if() should just be an else.

Here, are you saying I don't need the check for the names being the same? The other part is easy to understand if that's the case (as in, change the remaining else-if () to just else).

Edit: I tried it with each possible set of two gods. Works fine. Adding all of them in reverse order also works fine.

Current code in add_ordered():

Link *Link::add_ordered(Link *n)
{
	Link *trav = this;

	std::cout << "Before loop:\n";
	std::cout << "*trav:\n";
	print(*trav);
	std::cout << "*n:\n";
	print(*n);

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

	std::cout << "\nAfter loop:\n";
	std::cout << "*trav:\n";
	print(*trav);

	if (n->m_god.name() < trav->m_god.name())
	{
		std::cout << "Inside first conditional check, before insertion:\n";
		std::cout << "*trav:\n";
		print(*trav);
		trav = trav->insert(n);
		std::cout << "Inside first conditional check, after insertion:\n";
		std::cout << "*trav:\n";
		print(*trav);
	}
	else
	{
		std::cout << "Inside first else-if conditional check, before insertion:\n";
		std::cout << "*trav:\n";
		print(*trav);
		trav = trav->add(n);
		std::cout << "Inside first else-if conditional check, after insertion:\n";
		std::cout << "*trav:\n";
		print(*trav);
	}

	std::cout << "After conditional for adding n to list:\n";
	std::cout << "*trav:\n";
	print(*trav);

	return trav;
}

In my current situation, I can't actually receive mentoring in person. My only choice right now is online mentoring. Even if it won't speed anything up, it's all I have. So the only thing I can do is work at it diligently.

[jlb]

Here, are you saying I don't need the check for the names being the same?

Yes. You should be checking only for less than.

I tried it with each possible set of two gods. Works fine. Adding all of them in reverse order also works fine.

Okay then, since we now know that the program is working for two gods the next logical step would be to see if it works with three gods.

So using the gods Apollo and Odin for the first two gods try to insert Zeus. Does your program work properly?

[DragonOsman]

Okay, I need some clarification here. Is there any restriction on whether I should use insert() or add_ordered() to insert them into the list? I'll use one of them to initialize the list, but what I'm asking is if it'd be okay to insert the nodes using insert() or if I have to insert each node using add_ordered().

[jlb]

When I said "insert" in my last post I wasn't talking about using a particular function I was using "insert" as a verb.

in·sert
verb
verb: insert; 3rd person present: inserts; past tense: inserted; past participle: inserted; gerund or present participle: inserting
inˈsərt/

1.place, fit, or thrust (something) into another thing, especially with care.
"a steel rod was inserted into the small hole"
synonyms: put, place, push, thrust, slide, slip, load, fit, slot, lodge, install;

but what I'm asking is if it'd be okay to insert the nodes using insert() or if I have to insert each node using add_ordered().

Is this a trick question?

What function are you working on at the present time?

[DragonOsman]

Okay, so one node to initialize the list and then two inserted through add_ordered(). I just wanted to confirm that.

Edit: Problems detected at three. The original order matters, but it's possible to get the resulting order to come out wrong with three nodes.

[jlb]

Okay is there any pattern when add_ordered() fails to properly place the elements in the proper order?

For example what was the beginning order of the elements when the function failed to properly place the elements in order?

What was the beginning order of the elements when the function properly placed the elements in the proper order?

[DragonOsman]

Strangely enough, it failed when the initial order was "Apollo, Odin, Zeus". And it was correct when the order was "Apollo, Zeus, Odin", "Odin, Zeus, Apollo", or "Zeus, Odin, Apollo".

By the way, is there a way to avoid a memory leak in a situation like this?

char *strdup(const char *src)
{
	if (src == nullptr)
	{
		error("source string cannot be null");
	}
	char *dup = new char[str_len(src)];
	str_cpy(dup, src);
	return dup;
}

And while we're at it, since this is for an exercise where the subscript operator isn't allowed, is it possible to allocate memory using new with just the dereference operator?

And if avoiding a memory leak isn't possible, how do I do it without dynamic memory (note: standard library functions aren't allowed)? Do I need to create a function identical to strcpy()?

I tried to write one myself:

void str_cpy(char *dst, const char *src)
{
	for (int i = 0; *(src + i) != '\0'; ++i)
	{
		*(dst + i) = *(src + i);
	}
	int length = str_len(src);
	*(dst + length) = '\0';
}

[jlb]

By the way, is there a way to avoid a memory leak in a situation like this?

What does this have to do with the current problem?

Strangely enough, it failed when the initial order was "Apollo, Odin, Zeus".

Why is that strange?

And does that tell you anything?

[DragonOsman]

I thought it was strange because it actually failed when I deliberately put them in the correct order. If it was working correctly, that would be the simplest way to make sure I got the correct output.

I think it's possible that what's happening is that it puts the string that's greater than the one before it before the other string when they're in the correct order and side-by-side like that. Though I could be wrong.

I know my other question has nothing to do with this, but I was trying to do that exercise and thought I'd ask about it here. So I'd be better making a different for it, after all?