PPP2 Chapter 17 Exercise 11

Pages: 1... 45678... 16
Well, yes, I didn't understand what you meant when you said that you'd noticed several problems in my code before. The reason I didn't wasn't because I didn't want to know, but more because I wasn't sure if I should ask that. I felt it was something I needed to figure out on my own.

But have you figured out why I said there were things wrong in those first 6 lines? One of the things wrong is that that pointer is not the primary "key", the primary key is the name of the god. While checking that the pointer is not a nullptr will be required it should not be the primary thing. You want to search your list from the beginning of the list for your insertion point, by the way do you know what "the beginning of the list" really means? Part of the purpose of this "challenge" is to provide you a way of "seeing" what is happening so that maybe you can answer questions like this without guessing.

As for the code of mine that you posted: is that the place you're saying I'm wrong at? Or at least one of the places I'm wrong? If so, I'm guessing the main problem is in Line 6 in that snippet. But I don't know what.

Actually line 4 is the start of the problem.

As for why I didn't make that change to main() that you suggested on Sept. 28 at 10:33 am. When I asked about whether or not I should use "new" in add_ordered(), you said there was no need because main() already does that. So I was just wondering if I'd need to use "new" in add_ordered() if I took it out of main(). But I don't think I should use regular variables (i.e. non-pointer variables) for the Link objects since all of the functions that return a Link object do so by returning a pointer to a Link. I'd have to change those functions' return values to plain Links if I were to make that change to main().

So then you don't really understand how to use pointers as I suspected. If you remove the dynamic memory there will be no need to change anything in your classes the only changes will be in main.

What I suggested was to do something like this:

1
2
3
4
5
6
7
8
9
10
Link Odin{{"Odin","","",""}};  // Only need the name of the gods for now, so leave everything else blank.
Link Zeus{{"Zeus","","",""}}; // Note that the name of the variable doesn't have to be the name of the god as I am using, the variable name could be anything.
Link Thor{{"Thor","","",""}}; // Perhaps even elements of a vector or an array. 

Link *gods; // Remember I said something like this may be useful?

// Assign memory for the first god.
gods = &Thor; // I'm separating the initialization from the definition for clarity.

// I'll leave adding the other two gods with your insert() function for you to give it a try.. 


The primary purpose of getting rid of the dynamic memory is so that you have some variables that can be individually looked at without using your class.

The reason for doing this is so that you can print the contents of the Link class variables before and after you try to insert them into your list.

What I did to make it easier on myself was to create a function that can be easily called to print the information of interest. The signature of this function is something like: void print(const Link& current);, notice the parameter is not a pointer, but a reference to a single instance of the Link class. It will be able to be called from anywhere in your program to print out the variables of interest (the god's name, the previous pointer, and the next pointer). This will be used to help you debug your program without needing to rely on your debugger.



Here's another massive hint:

I reckon we only need two comparisons: NextPtr with nullptr ; and a less than . They both form the condition for the while loop. If either of them is true, insert the item after the current pointer, otherwise move to the next item. There we go, 1 line of pseudo code. Only a few lines of actual code. Note I didn't actually have any if statements. And even that can be reduced - what's another way of saying a pointer isn't a nullptr? Hint, the answer is already there in the code you were given.

Seen as we are using std::string, we can use the < operator, it does the same thing as lexicographic_compare .

I don't think we need a greater than ; or two insert functions.


Thomas1965 wrote:
Somehow I have the suspect that you overthink this problem. When adding the node there are two options. If the name of the insert god is greater than the current god insert it after. If the name of the insert god is smaller than the current god insert it before.
I assume ascending order.


Can i disagree with the underlined part? If we were talking numbers, and already had {1,2,5} and wanted to insert 8 we would have {1,8,2,5} and would reiterate that this is why the OP's code has never worked.

I certainly agree, The OP is massively overthinking this, IMO it's like this recipe for Damper:

Make a dough from flour and water. Bake.

Compared to a recipe for a Michelin Star quality bread with lots of ingredients.

@OP

Here is another way to trace the program without pieces of paper - use your editor ! For a given sequence of input numbers, type in what the list will look like after each number is inserted. So for this input: {9, -1,3,8,5} , we have:

9
-1, 9
-1, 3, 9
-1,3,8,9
-1,3,5,8,9

Now what happens when you trace through your code with it's logic? If you get to a point where the list is not sorted, ask yourself why the program put that item there?
@TheIdeasMan
If the name of the insert god is greater than the current god insert it after.
Can i disagree with the underlined part? If we were talking numbers, and already had {1,2,5} and wanted to insert 8 we would have {1,8,2,5} and would reiterate that this is why the OP's code has never worked.

You are absolutely right. I was not precise enough. I meant he needs then only to find the right place after the current node, not somewhere before.

@Thomas1965

At the risk of being pedantic, consider if the first node is 3, the value to be inserted is 2, it has to go before ......

I think of it in terms of a comparison with the next node, if we start at the head, the comparison can always be less than, and the insertion is always before the next node. The only other consideration is encountering the end of the list: that test is made first to handle the empty list.

@OP

Note that less than was a clue given by jlb a long way back ......
Okay, wait. If I only have to insert before the next node, what about a case where the node I want to insert is greater than the next node?

@jlb: You misunderstood, and so did I. I thought you meant to take away pointers altogether and use plain variables. That's why I asked that. I know you can still use pointers even without dynamic memory allocation.

And why did you read my code as saying I'm assigning the node itself to the std::string key? I was assigning the name of the god to it like I'm supposed to. It clearly says std::string key = n->m_god.name();. That's the name of the god in the node to be inserted.

As for the while-loop condition. Should be like this?
1
2
3
4
while (trav->m_succ != nullptr || key < trav->m_god.name())
{
    // insert before the next node
}


How do I find the head of the list, though? Would that be whatever the "this" pointer is pointing at when add_ordered() starts? And am I going to tell it to keep going until it finds the right place to insert the node when there's no if-condition? Wouldn't I still need to say "if the right place hasn't been found yet, traverse the next pointer to get to the next node"?

Edit: This is what I have right now:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Link *Link::add_ordered(Link *n)
{
	if (n == nullptr)
	{
		return nullptr;
	}

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

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


Good so far? Or is there still a mistake in the while loop and/or condition?

I just used the debugger and, apparently, "this" was NULL. And that "while" might also be an infinite loop.
Last edited on
@TheIdeasMan,
At the risk of being pedantic, consider if the first node is 3, the value to be inserted is 2, it has to go before ......

Yes certainly. I meant to find the right location, either before or after the current node.
I am thinking about a simple way like this.

If the new node is greater than the current node then
find the right location after the current node and insert it there
Else if the new node is smaller than the current node then
find the right location before the current node and insert it there
Else handle duplicate case
Okay, wait. If I only have to insert before the next node, what about a case where the node I want to insert is greater than the next node?

You will definitely need both your add and insert functions.


And why did you read my code as saying I'm assigning the node itself to the std::string key? I was assigning the name of the god to it like I'm supposed to. It clearly says std::string key = n->m_god.name();. That's the name of the god in the node to be inserted.

What? I said the pointers were not the primary key. Your code seems to be using the condition of the pointers as the primary key not the the desired name.


As for the while-loop condition. Should be like this?

No, where is your primary key?

How do I find the head of the list, though?

What makes the head of the list the head of the list? What conditions? This is why I suggested the changes to main() have you started doing that challenge?

Would that be whatever the "this" pointer is pointing at when add_ordered() starts?

Not necessarily, again have you even started that challenge I gave you? It will only be guaranteed to be the head of the list the first time add ordered is called.

And am I going to tell it to keep going until it finds the right place to insert the node when there's no if-condition?

Well if your loop is constructed properly you won't need an if() statement to stop. This is part of why your current code (the code before the horrible edit) will only properly insert one or two elements into the Link.

Now about the edited code:
I just used the debugger and, apparently, "this" was NULL.

If you're doing things correctly *this should never be null.

Good so far? Or is there still a mistake in the while loop and/or condition?


while ((trav = trav->m_succ) || key < trav->m_god.name())
First your "Key" should be first, that's why it's the key. Second modifying trav in the while loop body will just confuse you, the assignment would be better to be done separately in the loop body, not the loop condition. Third the you're using the improper operator, both conditions must be met. Fourth, did you try the code? Did it work? Fifth, answer no it didn't work. Why are you try to insert() something into the list every time the loop executes?

Have you finished the challenge I suggested? You can use the code in that challenge to help you see what is going on.

Please don't edit the code you post, just add a new post.
Last edited on
I made this the signature of the new print function: void print(Link *gods) because I don't know how to get the address of the object that a reference is referring to. Anyway, I made the suggested changes to main() and tried to fix add_ordered() (no change in the output of the latter, though).

Here's the new main() (I commented out the other stuff from before because I'll need it later and I didn't want to look up the information again):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
int main()
{
	/*
	    Link *norse_gods = new Link{ God{ "Thor", "Norse",
		"Chariot pulled by goats Tanngrisnir and Tanngnjostr", "Mjolnir" } };
		
		if (norse_gods)
		{
			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{ "Frejya", "Norse", "", "Magic called seidr" } });

			print_all(norse_gods);
			std::cout << '\n';
		}
	*/
	
	try
	{
		Link Odin{ God{"Odin", "", "", ""} };
		Link Zeus{ God{"Zeus", "", "", ""} };
		Link Thor{ God{"Thor", "", "", ""} };

		Link *gods;

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

		print(gods);
	}
	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();
}


Here's add_ordered():
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Link *Link::add_ordered(Link *n)
{
	if (n == nullptr)
	{
		return nullptr;
	}

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

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


The node isn't being inserted at all. The current output from print() is as follows:
Address of *gods is: 003FF624
The name of the god is: Odin
The previous pointer is: 00000000
The next pointer is: 00000000
Please enter a character to exit
k
Press any key to continue . . .


Anyway, for the head: Isn't that the first node in the list? It should be the node that the pointer variable "gods" in main() is pointing at before add_ordered() is called.
Last edited on
Anyway, for the head: Isn't that the first node in the list?

But what makes a node the "first" node in the list?

The node isn't being inserted at all.

Why would it? In that while loop how can key ever be greater than the name?



Last edited on
I made this the signature of the new print function: void print(Link *gods) because I don't know how to get the address of the object that a reference is referring to

Why not? You said you know how pointers work. But anyway where is your code for that function? Have you tried to use it? By the way I made it a const Link& for a reason, the reason being you won't need to worry about getting the pointer notation correct.

I suggested inserting the gods out of order for a reason, Try inserting as Thor, Odin, Zeus.

Also I suggest you use insert() instead of add_ordered to insure that this redone main is actually working as expected.



The first node in the list is the one whose previous pointer is pointing at NULL.

And yeah, key can't be greater than the name in that loop. But I still need to check for that, right? So what should I do?
The first node in the list is the one whose previous pointer is pointing at NULL.

That is correct.

But I still need to check for that, right?

Why do you think you need to check if one name is greater than the other? Especially inside the loop.

So I don't need to worry about a case where the key is greater than the name in the current node? So then why was I told I'd have to use both insert() and add() in the same loop?

Anyway, here's print():
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void print(const Link &gods)
{
	Link *trav = &const_cast<Link&>(gods);
	while (trav)
	{
		std::cout << "Address of *gods is: " << &trav << '\n'
			<< "The name of the god is: " << trav->m_god.name() << '\n'
			<< "The previous pointer is: " << trav->previous() << '\n'
			<< "The next pointer is: " << trav->next() << '\n';
		if ((trav = trav->next()))
		{
			std::cout << "\n";
		}
	}
}


And here's add_ordered():
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Link *Link::add_ordered(Link *n)
{
	if (n == nullptr)
	{
		return nullptr;
	}

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

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

	/*while (key > trav->m_god.name() && trav->m_prev)
	{
		trav = trav->add(n);
		trav = trav->m_prev;
	}*/
	return trav;
}
Okay, I tried adding code for traversing backwards as much as possible until finding the head.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Link *Link::add_ordered(Link *n)
{
	if (n == nullptr)
	{
		return nullptr;
	}

	Link *trav = this;
	if (trav == nullptr)
	{
		return nullptr;
	}
	else
	{
		// to make sure we start at the head
		while (trav->m_prev)
		{
			trav = trav->m_prev;
		}
	}
	
	std::string key = n->m_god.name();
	while (key < trav->m_god.name() && trav->m_succ)
	{
		trav = trav->insert(n);
		trav = trav->m_succ;
	}

	while (key > trav->m_god.name() && trav->m_succ)
	{
		trav = trav->add(n);
		trav = trav->m_succ;
	}
        return trav;
}


Still not actually adding anything, though.
Last edited on
So I don't need to worry about a case where the key is greater than the name in the current node?

If you're doing things correctly, no. Everything is based on less than.

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?

Be very careful about returning a nullptr from any of your functions. The way you're trying to use most of your functions returning a nullptr will have dire consequences.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void print(const Link &gods)
{
	Link *trav = &const_cast<Link&>(gods);
	while (trav)
	{
		std::cout << "Address of *gods is: " << &trav << '\n'
			<< "The name of the god is: " << trav->m_god.name() << '\n'
			<< "The previous pointer is: " << trav->previous() << '\n'
			<< "The next pointer is: " << trav->next() << '\n';
		if ((trav = trav->next()))
		{
			std::cout << "\n";
		}
	}
}

You don't need any loops or any pointers in this function, you're just printing one god, not the entire list.

Still not actually adding anything, though.

It probably is adding something, what is the question. Which is why I recommended getting rid of the dynamic memory in main() so you could print() each of the gods in main() by printing each instance of the class you created using the print() function. Edit: It would be nice if you showed how you tried to use this function in main() as well.


By the way you are getting closer to a correct solution for add_ordered() but not quite there yet.



Last edited on
So I also don't need two loops, with the second testing for greater than? I just need the one checking for less than, and it has to somehow see where to insert the node if it has to go after the current or next node? If so, what am I still missing?

And I know you said I shouldn't return nullptr, but there are some situations where I have to, right? So could you suggest something to better to return in places where I'm returning nullptr but shouldn't be?

The function insert() is for inserting before "this" object and the function add() is for inserting after "this" object.

How am I going to print each instance of the class when I only have one in main()? And print() takes a reference to a Link object, not a God object. A God is used to initialize a Link, as one of the arguments to the constructor.

I'll just post the whole thing here again:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
// Osman Zakir
// 9 / 7 / 2017
// Bjarne Stroustrup: Programming: Principles and Practice Using C++ 2nd Edition
// Chapter 17 Exercises 11-13

#include <cctype>
#include <iostream>
#include <iterator>
#include <algorithm>
#include "../../cust_std_lib_facilities.h"

struct God
{
	God(const std::string &name, const std::string &myth, const std::string &vehicle, const std::string &weapon)
		: m_name{ name }, m_myth{ myth }, m_vehicle{ vehicle }, m_weapon{ weapon } { }

	const std::string &name() const { return m_name; }
	const std::string &myth() const { return m_myth; }
	const std::string &vehicle() const { return m_vehicle; }
	const std::string &weapon() const { return m_weapon; }

	void set_name(const std::string name) { m_name = name; }
	void set_myth(const std::string myth) { m_myth = myth; }
	void set_vehicle(const std::string vehicle) { m_vehicle = vehicle; }
	void set_weapon(const std::string weapon) { m_weapon = weapon; }
private:
	std::string m_name;
	std::string m_myth;
	std::string m_vehicle;
	std::string m_weapon;
};

class Link
{
public:
	Link(const God &god, Link *p = nullptr, Link *s = nullptr)
		: m_god{ god }, m_prev{ p }, m_succ{ s } { }

	God m_god;
	Link *insert(Link *n);                              // insert n before this object
	Link *add(Link *n);                                 // insert n after this object
	Link *erase();                                      // remove this object from list
	Link *find(const std::string &name);                // find values in list
	const Link *find(const std::string &name) const;    // find values in const list
	Link *advance(int n) const;                         // advance n positions in list
	Link *add_ordered(Link *n);
	int element_count();

	Link *next() const { return m_succ; }
	Link *previous() const { return m_prev; }

private:
	Link *m_prev;
	Link *m_succ;
};

void print_all(Link *p);
void print(const Link &gods);

int main()
{
	/*
	    Link *norse_gods = new Link{ God{ "Thor", "Norse",
		"Chariot pulled by goats Tanngrisnir and Tanngnjostr", "Mjolnir" } };
		
		if (norse_gods)
		{
			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{ "Frejya", "Norse", "", "Magic called seidr" } });

			print_all(norse_gods);
			std::cout << '\n';
		}
	*/
	
	try
	{
		Link Odin{ God{"Odin", "", "", ""} };
		Link Zeus{ God{"Zeus", "", "", ""} };
		Link Thor{ God{"Thor", "", "", ""} };

		Link *gods;

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

		print(*gods);
		std::cout << "Number 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();
}

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;
}

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;
}

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

Link *Link::find(const std::string &name)
{
	Link *trav = this;
	while (trav != nullptr)
	{
		if (trav->m_god.name() == name)
		{
			return trav;
		}
		trav = trav->m_succ;
	}
	return nullptr;
}

const Link *Link::find(const std::string &name) const
{
	const Link *c_trav = this;                    // const pointer
	Link *nc_trav = const_cast<Link*>(c_trav);    // non-const pointer
	while (c_trav != nullptr && nc_trav != nullptr)
	{
		if (c_trav->m_god.name() == name)
		{
			return c_trav;
		}
		nc_trav = nc_trav->m_succ;
	}
	return nullptr;
}

Link *Link::advance(int n) const
{
	Link *trav = const_cast<Link *>(this);
	if (trav == nullptr)
	{
		return nullptr;
	}
	if (n > 0)
	{
		while (n--)
		{
			if (trav->m_succ == nullptr)
			{
				return nullptr;
			}
			trav = trav->m_succ;
		}
	}
	else if (n < 0)
	{
		while (n++)
		{
			if (trav->m_prev == nullptr)
			{
				return nullptr;
			}
			trav = trav->m_prev;
		}
	}
	return trav;
}

/**
 * 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;
	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->insert(n);
		trav = trav->m_succ;
	}

	while (key > trav->m_god.name() && trav->m_succ)
	{
		trav = trav->add(n);
		trav = trav->m_succ;
	}
	return trav;
}

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;
}

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

void print(const Link &gods)
{
	Link *trav = &const_cast<Link&>(gods);
	while (trav)
	{
		std::cout << "Address of *gods is: " << &trav << '\n'
			<< "The name of the god is: " << trav->m_god.name() << '\n'
			<< "The previous pointer is: " << trav->previous() << '\n'
			<< "The next pointer is: " << trav->next() << '\n';
		if ((trav = trav->next()))
		{
			std::cout << "\n";
		}
	}
}
Last edited on
Okay, let's try this again. I'll print each individual god's stuff in print() now.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
// Osman Zakir
// 9 / 7 / 2017
// Bjarne Stroustrup: Programming: Principles and Practice Using C++ 2nd Edition
// Chapter 17 Exercises 11-13

#include <cctype>
#include <iostream>
#include <iterator>
#include <algorithm>
#include "../../cust_std_lib_facilities.h"

struct God
{
	God(const std::string &name, const std::string &myth, const std::string &vehicle, const std::string &weapon)
		: m_name{ name }, m_myth{ myth }, m_vehicle{ vehicle }, m_weapon{ weapon } { }

	const std::string &name() const { return m_name; }
	const std::string &myth() const { return m_myth; }
	const std::string &vehicle() const { return m_vehicle; }
	const std::string &weapon() const { return m_weapon; }

	void set_name(const std::string name) { m_name = name; }
	void set_myth(const std::string myth) { m_myth = myth; }
	void set_vehicle(const std::string vehicle) { m_vehicle = vehicle; }
	void set_weapon(const std::string weapon) { m_weapon = weapon; }
private:
	std::string m_name;
	std::string m_myth;
	std::string m_vehicle;
	std::string m_weapon;
};

class Link
{
public:
	Link(const God &god, Link *p = nullptr, Link *s = nullptr)
		: m_god{ god }, m_prev{ p }, m_succ{ s } { }

	God m_god;
	Link *insert(Link *n);                              // insert n before this object
	Link *add(Link *n);                                 // insert n after this object
	Link *erase();                                      // remove this object from list
	Link *find(const std::string &name);                // find values in list
	const Link *find(const std::string &name) const;    // find values in const list
	Link *advance(int n) const;                         // advance n positions in list
	Link *add_ordered(Link *n);
	int element_count();

	Link *next() const { return m_succ; }
	Link *previous() const { return m_prev; }

private:
	Link *m_prev;
	Link *m_succ;
};

void print_all(Link *p);
void print(const Link &gods);

int main()
{
	/*
	    Link *norse_gods = new Link{ God{ "Thor", "Norse",
		"Chariot pulled by goats Tanngrisnir and Tanngnjostr", "Mjolnir" } };
		
		if (norse_gods)
		{
			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{ "Frejya", "Norse", "", "Magic called seidr" } });

			print_all(norse_gods);
			std::cout << '\n';
		}
	*/
	
	try
	{
		Link Odin{ God{"Odin", "", "", ""} };
		Link Zeus{ God{"Zeus", "", "", ""} };
		Link Thor{ God{"Thor", "", "", ""} };

		Link *gods;

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

		print(Odin);
		print(Zeus);
		print(Thor);
		std::cout << "Number 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();
}

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;
}

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;
}

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

Link *Link::find(const std::string &name)
{
	Link *trav = this;
	while (trav != nullptr)
	{
		if (trav->m_god.name() == name)
		{
			return trav;
		}
		trav = trav->m_succ;
	}
	return nullptr;
}

const Link *Link::find(const std::string &name) const
{
	const Link *c_trav = this;                    // const pointer
	Link *nc_trav = const_cast<Link*>(c_trav);    // non-const pointer
	while (c_trav != nullptr && nc_trav != nullptr)
	{
		if (c_trav->m_god.name() == name)
		{
			return c_trav;
		}
		nc_trav = nc_trav->m_succ;
	}
	return nullptr;
}

Link *Link::advance(int n) const
{
	Link *trav = const_cast<Link *>(this);
	if (trav == nullptr)
	{
		return nullptr;
	}
	if (n > 0)
	{
		while (n--)
		{
			if (trav->m_succ == nullptr)
			{
				return nullptr;
			}
			trav = trav->m_succ;
		}
	}
	else if (n < 0)
	{
		while (n++)
		{
			if (trav->m_prev == nullptr)
			{
				return nullptr;
			}
			trav = trav->m_prev;
		}
	}
	return trav;
}

/**
 * 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;
	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->insert(n);
		trav = trav->m_succ;
	}

	while (key > trav->m_god.name() && trav->m_succ)
	{
		trav = trav->add(n);
		trav = trav->m_succ;
	}
	return trav;
}

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;
}

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

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


It seems they each have the same address? How?

And I know you said I shouldn't return nullptr, but there are some situations where I have to, right? So could you suggest something to better to return in places where I'm returning nullptr but shouldn't be?

IMO, you would be better off throwing an exception instead of returning a nullptr in this program since it is exceptional if either *this or the parameter was ever a nullptr. By the way why did you all of a sudden start using exceptions in this program? You keep changing your programming style which makes it look like you're getting help somewhere else.

But note neither of the pointers should really ever be a nullptr unless you made a mistake in your coding.

By the way these functions should not be returning a reference:
1
2
3
4
	const std::string &name() const { return m_name; }
	const std::string &myth() const { return m_myth; }
	const std::string &vehicle() const { return m_vehicle; }
	const std::string &weapon() const { return m_weapon; }


None of these functions should be returning a nullptr:
1
2
3
4
5
6
7
	Link *insert(Link *n);                              // insert n before this object
	Link *add(Link *n);                                 // insert n after this object
	Link *erase();                                      // remove this object from list
	Link *find(const std::string &name);                // find values in list
	const Link *find(const std::string &name) const;    // find values in const list
	Link *advance(int n) const;                         // advance n positions in list
	Link *add_ordered(Link *n);

You would be better off just returning *this instead.

How can you really test add_ordered() if you are always putting the elements into your Link in order in the first place? I've already mentioned this in an earlier post.

Look at this snippet:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void print(const Link &gods)
{
	Link *trav = &const_cast<Link&>(gods);
	while (trav)
	{
		std::cout << "Address of *gods is: " << &trav << '\n'
			<< "The name of the god is: " << trav->m_god.name() << '\n'
			<< "The previous pointer is: " << trav->previous() << '\n'
			<< "The next pointer is: " << trav->next() << '\n';
		if ((trav = trav->next()))
		{
			std::cout << "\n";
		}
	}
}

I've already told you you don't need any pointers or loops in this function so why haven't you changed anything?

Your print_all() function is still not following the directions provided in the instructions, I've already mentioned that as well. Why haven't you fixed this issue as well?
Write a print_all() function that lists gods with their attributes one per line.

Also note this function is also incorrect. Didn't you thoroughly test this function using your different insertion methods?


The function insert() is for inserting before "this" object and the function add() is for inserting after "this" object.

I'm glad you know this, I've know this since the very beginning. The trick is knowing when to use which.

So I also don't need two loops, with the second testing for greater than? I just need the one checking for less than, and it has to somehow see where to insert the node if it has to go after the current or next node? If so, what am I still missing?

Well this function will need two loops, not the three you presently have. One loop to pre-position the list to the beginning, one to find the correct place to put the "new" record. By the way don't forget to check for edge cases.

I made another post where I took the loop out of print(). But about print_all(), am I not already printing out each god's attribute one per line? I thought it was asking for each god's attribute one per line with each god's information also separated by a new line, like I have now.

I included exceptions because I felt like I needed to. Though it was mainly when I used error() in the case that the names in both the new node and the current node are equal. I took out that check, but forgot to take out the exception handling code in main(). I think I should bring that check back in, but I don't know how.

As for the functions that return nullptr. find(), advance, erase() and insert() all return nullptr originally; that's how I got them from the book. I think I know why you're saying it's bad, but I don't want to change code I got from the book that much.

So anyway, if I don't need another loop to check for where to put the new node, then what am I still missing?

The getters in the God class shouldn't be returning const references? So I shouldn't make them return a const string, either? But I thought getters in classes had to return a const reference if they return a big object like a string or a vector?

Here's my current output:
From print():
Address of *current is: 008FF608
The name of the god is: Odin
The previous pointer is: 00000000
The next pointer is: 00000000
Address of *current is: 008FF608
The name of the god is: Zeus
The previous pointer is: 00000000
The next pointer is: 00000000
Address of *current is: 008FF608
The name of the god is: Thor
The previous pointer is: 00000000
The next pointer is: 00000000


From print_all():
{
Name: Odin
Myth:
Vehicle: N/A
Weapon:
}
Number of nodes in list is: 1
Please enter a character to exit
l
Press any key to continue . . .


main():
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
int main()
{
	/*
	    Link *norse_gods = new Link{ God{ "Thor", "Norse",
		"Chariot pulled by goats Tanngrisnir and Tanngnjostr", "Mjolnir" } };
		
		if (norse_gods)
		{
			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{ "Frejya", "Norse", "", "Magic called seidr" } });

			print_all(norse_gods);
			std::cout << '\n';
		}
	*/
	
	try
	{
		Link Odin{ God{"Odin", "", "", ""} };
		Link Zeus{ God{"Zeus", "", "", ""} };
		Link Thor{ God{"Thor", "", "", ""} };

		Link *gods;

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

		std::cout << "From print():\n";
		print(Odin);
		print(Zeus);
		print(Thor);

		std::cout << "\n\nFrom print_all():\n";
		print_all(gods);
		std::cout << "\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():
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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->insert(n);
		trav = trav->m_succ;
	}
	return trav;
}


print():
1
2
3
4
5
6
7
8
9
10
11
void print(const Link &current)
{
	Link *trav = &const_cast<Link&>(current);
	if (trav)
	{
		std::cout << "Address of *current is: " << &trav << '\n'
			<< "The name of the god is: " << trav->m_god.name() << '\n'
			<< "The previous pointer is: " << trav->previous() << '\n'
			<< "The next pointer is: " << trav->next() << '\n';
	}
}

But about print_all(), am I not already printing out each god's attribute one per line? I thought it was asking for each god's attribute one per line with each god's information also separated by a new line, like I have now.

No, look at this snippet:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void print_all(Link *p)
{
	std::cout << "{\n";
	while (p)
	{
		std::cout << "Name: " << p->m_god.name() << '\n'
			<< "Myth: " << p->m_god.myth() << '\n';
		if (p->m_god.vehicle() != "")
		{
			std::cout << "Vehicle: " << p->m_god.vehicle() << '\n';
		}
		else
		{
			std::cout << "Vehicle: N/A\n";
		}
		std::cout << "Weapon: " << p->m_god.weapon() << '\n';
		if ((p = p->next()))
		{
			std::cout << "\n";
		}
	}
	std::cout << "}";
}

Look closely at all of those '\n' (new line character) that your printing. Does the following look like all the information is on one line?
1
2
3
4
5
6
7
From print_all():
{
Name: Odin
Myth:
Vehicle: N/A
Weapon:
}

Wouldn't on one line mean? {Name: Odin Myth: Vehicle: N/A Weapon:}


As for the functions that return nullptr. find(), advance, erase() and insert() all return nullptr originally; that's how I got them from the book. I think I know why you're saying it's bad, but I don't want to change code I got from the book that much.

Do you realize that the book can be wrong? What do you think happens to the rest of the program if you return a nullptr from any of those functions.

1
2
3
4
5
6
7
8
9
10
11
void print(const Link &current)
{
	Link *trav = &const_cast<Link&>(current);
	if (trav)
	{
		std::cout << "Address of *current is: " << &trav << '\n'
			<< "The name of the god is: " << trav->m_god.name() << '\n'
			<< "The previous pointer is: " << trav->previous() << '\n'
			<< "The next pointer is: " << trav->next() << '\n';
	}
}

Why do you still have a pointer in that code, it's not needed. Just print the Link without the pointer using normal non-pointer syntax. You also don't need that if statement, a reference parameter can never be a nullptr. And I recommend that you print this information all on one line.


The getters in the God class shouldn't be returning const references? So I shouldn't make them return a const string, either? But I thought getters in classes had to return a const reference if they return a big object like a string or a vector?


No, and no. The getters should just be returning the strings not const strings and not const references. Just something like: std::string name() const { return m_name; } The remaining const is telling the compiler that this function doesn't modify the class in any way.

So anyway, if I don't need another loop to check for where to put the new node, then what am I still missing?

It looks like your missing the point of that last loop. Why don't you try printing some information inside the various loops to try to see what is happening.



Pages: 1... 45678... 16