C++

Forum

 
PPP2 Chapter 17 Exercise 11

Pages: 12345... 16
jlb (4973)
The exercise is asking to create a method that places its "new" element in its correct lexicographical position,

Yes, so? You need to place your "new" element (a Link*) in it's correct position.

But if I have to place an element into the "this" list, then doesn't that mean I have to pass an instance of struct God into it so I can place that into the list?

No, remember that Link has a God member variable. Look at the function signature I proposed, does it contain a "God" parameter?

But then where does the "new" keyword come in?

Why do you think I asked you to post your main() that is being used to test this part of the exercise?

I don't need the *god and I also need to change the argument from a Link to a God.

No, you need a Link* not a God*.

Even if I can compare two Links (with the logical comparison operators, right?),

Maybe. What is the key that determines if the two Links are the same? Do you understand what I mean by "key"?

how do I look for a link adjacent to the current one?

What? You have two different Link* you need to compare. Do you understand where both of these Link* are coming from. This is why you need to post your main() that is testing this part of the assignment, you seem to be missing something that should be clarified from looking at main().

By the way your main() should start similar to all of your previous main() functions in this topic. 

1
2
3
4
5
6
 
... 
int main()
{
     Link *all_mythos = new Link{ God{ "Thor", "Norse", "Chariot pulled by goats Tanngrisnir and Tanngnjostr", "Mjolnir" } };

...


This, other than the instance name and the content of the parameters, is the same every time you create a new Link. And don't confuse yourself with that "God" in the above snippet, first it is not really required, and second it is only being used to call the God constructor on the God member variable by the Link constructor.

This is basically the same as the above snippet:
1
2
3
4
5
6
 
... 
int main()
{
     Link *all_mythos = new Link{ { "Thor", "Norse", "Chariot pulled by goats Tanngrisnir and Tanngnjostr", "Mjolnir" } };

...


DragonOsman (715)
My main() is still the same as before. I was thinking of editing it after writing the add_ordered() function. So I should change main() to reflect just this exercise and take everything else out for now? And then I just use "new" in main() while adding that element into the list such that the element is in the correct position? No need to use "new" in the function itself?

And as for the "key". After reading you're post, I'm thinking the key should be the argument to the add_ordered() function, itself. The function needs to add it to its correct position, so I guess I have to compare it to the links already in the list? I'll try it for a situation where there's only one link in there, and then I'll ask again. I'm not sure what to do for a list with more in it, for now.
jlb (4973)
And as for the "key".

Well since you didn't answer the question am I to assume that you don't know?

After reading you're post, I'm thinking the key should be the argument to the add_ordered() function, itself.

Why? Again please explain what you think I mean by "key" in the content of this assignment, in English.

My main() is still the same as before.

Why, you are in the process of adding a function to your class, how do you intend to test this function?

No need to use "new" in the function itself?

Did you use new in the add or insert functions?

DragonOsman (715)
I'll edit main() after I'm done making writing first set of code in the add_ordered() function. For now, I want to focus mainly on writing the function itself.

The key should be the Link object that's passed into the function, right? Because that's the Link that needs to be inserted, and I'll have to compare that with the elements that are already there.

Something like this?
1
2
3
4
5
6
7
8
9
10
11
 
Link* Link::add_ordered(Link *n)
{
    Link *trav = this;

    // if the name of the God in n should come before the next node in the list
    if (n->m_god.name() < trav->advance()->m_god.name())
    {
        // insert *n here
        trav = trav->insert(n);
    }
}
jlb (4973)
I'll edit main() after I'm done making writing first set of code in the add_ordered() function. For now, I want to focus mainly on writing the function itself.

Then how will you know if your new function is working correctly?


The key should be the Link object that's passed into the function, right?

More specifically the "key" is, in this part of the assignment, the name of the god.

Something like this?

Does it work? Have you tested it?


DragonOsman (715)
I'll test it after I've written it. That's what I meant.
jlb (4973)
Then maybe you should wait to come back here until you've written and tested it, that's what I meant.

DragonOsman (715)
Right. First test is done. Result: Seems to be a failure. The output is a completely blank screen.

Here's the code:
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
 
// Osman Zakir
// 9 / 7 / 2017
// Bjarne Stroustrup: Programming: Principles and Practice Using C++ 2nd Edition
// Chapter 17 Exercises 11-13

#include <iostream>
#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 } { }

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

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

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

void print_all(Link *p);

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" } });
	norse_gods = norse_gods->add_ordered(new Link{ God{ "Freyja", "Norse", "Chariot pulled by two cats", "Magic called seior" } });

	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{ "Mars", "Greek", "", "A spear stained in blood" } });
	greek_gods = greek_gods->add_ordered(new Link{ God{ "Poseidon", "Greek", "", "Three-pronged spear called Trident" } });

	Link* p = greek_gods->find("Mars");
	if (p)
	{
		p->m_god.set_name("Ares");
	}

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

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

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

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

Link *Link::add_ordered(Link *n)
{
	Link *trav = this;
	while (trav != nullptr)
	{
		if (trav->m_succ == nullptr && trav->m_prev == nullptr)
		{
			trav = trav->insert(n);
		}
		else
		{
			std::string key = n->m_god.name();
			if (key < trav->m_god.name())
			{
				trav = trav->insert(n);
			}
		}
		trav = trav->advance(1);
	}
	return trav;
}

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


Individually, add_ordered() is like this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
Link *Link::add_ordered(Link *n)
{
	Link *trav = this;
	while (trav != nullptr)
	{
		if (trav->m_succ == nullptr && trav->m_prev == nullptr)
		{
			trav = trav->insert(n);
		}
		else
		{
			std::string key = n->m_god.name();
			if (key < trav->m_god.name())
			{
				trav = trav->insert(n);
			}
		}
		trav = trav->advance(1);
	}
	return trav;
}


and main() is like this (only changed how the links are being added to the lists):
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
 
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" } });
	norse_gods = norse_gods->add_ordered(new Link{ God{ "Freyja", "Norse", "Chariot pulled by two cats", "Magic called seior" } });

	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{ "Mars", "Greek", "", "A spear stained in blood" } });
	greek_gods = greek_gods->add_ordered(new Link{ God{ "Poseidon", "Greek", "", "Three-pronged spear called Trident" } });

	Link* p = greek_gods->find("Mars");
	if (p)
	{
		p->m_god.set_name("Ares");
	}

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

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

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

	keep_window_open();
}
Last edited on
DragonOsman (715)
Isn't anyone replying? I have a problem here. I fixed the problem I had just now that would've made it not compile, though.

Updated code:
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
 
// Osman Zakir
// 9 / 7 / 2017
// Bjarne Stroustrup: Programming: Principles and Practice Using C++ 2nd Edition
// Chapter 17 Exercises 11-13

#include <iostream>
#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 } { }

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

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

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

void print_all(Link *p);

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" } });
	norse_gods = norse_gods->add_ordered(new Link{ God{ "Freyja", "Norse", 
		"Chariot pulled by two cats", "Magic called seior" } });

	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{ "Mars", "Greek", "", "A spear stained in blood" } });
	greek_gods = greek_gods->add_ordered(new Link{ God{ "Poseidon", "Greek", "", 
		"Three-pronged spear called Trident" } });

	Link* p = greek_gods->find("Mars");
	if (p)
	{
		p->god().set_name("Ares");
	}

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

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

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

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

Link *Link::add_ordered(Link *n)
{
	Link *trav = this;
	while (trav != nullptr)
	{
		if (trav->m_succ == nullptr && trav->m_prev == nullptr)
		{
			trav = trav->insert(n);
		}
		else
		{
			std::string key = n->m_god.name();
			if (key < trav->m_god.name())
			{
				trav = trav->insert(n);
			}
		}
		trav = trav->advance(1);
	}
	return trav;
}

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


Thanks in advance.
Last edited on
jlb (4973)
So what have you done in the last several days to troubleshoot the problem, the code looks basically the same?

DragonOsman (715)
I know the problem should be in the new function I wrote. But I'm not sure how to troubleshoot it, even with a debugger. All I know is that, for some reason, the output is coming out blank now.

And how many days are you counting here? The recent problem of the blank console window only came up when I tried to test add_ordered().

Edit: Okay, now I at least have some output. But only Thor and Hera, because they aren't inserted into the lists via add_ordered(). The ones I'm trying to enter through add_ordered() aren't being inserted, so they aren't printed.

I'll show just the code for add_ordered() here:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
Link *Link::add_ordered(Link *n)
{
	Link *trav = this;
	while (trav)
	{
		std::string key = n->m_god.name();
		if (key < trav->m_god.name())
		{
			trav = trav->insert(n);
		}
		trav = trav->m_succ;
	}
	return trav;
}


I tried returning trav after inserting into it, in that if-condition, but that give two empty sets of curly braces in the output. Doing that while returning nullptr at the end, to indicate failure, resulted in a blank console window.
Last edited on
jlb (4973)
know the problem should be in the new function I wrote.

Duh.

But I'm not sure how to troubleshoot it, even with a debugger.

While the debugger is usually the best tool to debug your program there are other methods to aid in your debugging efforts. What have you actually tried, other than posting your code in several forums begging for someone to do the debugging for you?

All I know is that, for some reason, the output is coming out blank now.

What exactly do you mean by "coming out blank now"? And what does that tell you?

And how many days are you counting here? The recent problem of the blank console window only came up when I tried to test add_ordered().

Which was Sept 21 this is Sept 24 you do the math.

DragonOsman (715)
After thinking about it a bit more, I noticed I probably had to compare the first two letters in the name strings (individually, of course) first to see if the strings are the same or if one should come before or after the other. I followed the "next" and "previous" pointers of the current element and inserted n there accordingly. But it still didn't work (I still have two pairs of blank curly braces and then "Please enter a character to exit").

I think the problem I'm having is either where to put the return statement or how many characters to compare and what to exactly in each case. Or maybe both.

Here's the code for 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
 
Link *Link::add_ordered(Link *n)
{
	Link *trav = this;
	while (trav != nullptr)
	{
		const std::string key = n->m_god.name();	// string being used to compare; is the name string of the "god" to be inserted
		std::size_t i = 0;

		// if the current element in the list is the only element
		if (trav->m_prev != nullptr && trav->m_succ != nullptr)
		{
			// if the first letter of both name strings are not the same
			if (key[i] != trav->m_god.name()[i] && i == 0)
			{
				// if the first character in the key is "less" than the first letter in the name string of the current element
				if (key[i] < trav->m_god.name()[i] && i == 0)
				{
					// go to the previous pointer of the current element and insert n at that location
					trav = trav->m_prev;
					trav = trav->insert(n);
					//return trav;
				}
				// else if the first letter in the key is "greater" than the first letter in the name string of the current element
				else if (key[i] > trav->m_god.name()[i] && i == 0)
				{
					// go to the next pointer of the current element and insert n at that location
					trav = trav->m_succ;
					trav = trav->insert(n);
					//return trav;
				}
			}
			// else if the first letters in each name string are the same
			else if (key[i] == trav->m_god.name()[i] && i == 0)
			{
				// if the second letter in the key is "less" than the first letter in the name string of the current element
				if (key[i] < trav->m_god.name()[i] && i == 1)
				{
					// go to the previous pointer of the current element and insert n at that location
					trav = trav->m_prev;
					trav = trav->insert(n);
					//return trav;
				}
				// else if the second letter in the key is "greater" than the first letter in the name string of the current element
				else if (key[i] > trav->m_god.name()[i] && i == 1)
				{
					// go the next pointer of the current element and insert n at that location
					trav = trav->m_succ;
					trav = trav->insert(n);
					//return trav;
				}
			}
			// if the key string is shorter than the string compared to
			if (key.length() < trav->m_god.name().length() && key[i] == key.at(key.length() - 1))
			{
				// exit the loop
				break;
			}
			// if the key string is greater than the string being compared to
			else if (key.length() > trav->m_god.name().length() && 
				trav->m_god.name()[i] == trav->m_god.name().at(trav->m_god.name().length() - 1))
			{
				// exit the loop
				break;
			}
			++i;
		}
		trav = trav->m_succ;
	}
	return trav;
}
Last edited on
jlb (4973)
After thinking about it a bit more, I noticed I probably had to compare the first two letters in the name strings (individually, of course) first to see if the strings are the same or if one should come before or after the other.

Why just the first two letters? What happens if there are three or more characters that are the same?

I followed the "next" and "previous" pointers of the current element and inserted n there accordingly. But it still didn't work (I still have two pairs of blank curly braces and then "Please enter a character to exit").

How can you follow both the "next" and "previous" pointers at the same time?
Last edited on
DragonOsman (715)
Didn't you read the code? I didn't do it at the same time. One if-condition for the previous pointer, and one for the next pointer. I did also say, "individually, of course" in the parentheses in my post before posting the code, didn't I? I meant I didn't try to follow both at the same time.

I didn't try to compare the other characters because I'm not sure what I should do about the sizes of the strings. Isn't there some way I could compare each character without going out of bounds and correctly position the link objects as needed? Right now, what am I going to do if one string is 4 letters and the other is 7 or something (or whatever other combination of sizes - the point is, I don't know what the sizes are at any given time and I also won't try to assume anything). I don't want to hard-code string indices beyond the first two or three characters because of that.

I wonder if just something like this would be fine?
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
 
if (key[i] == trav->m_god.name()[i])
{
    if (key[i + 1] < trav->m_god.name()[i + 1])
    {
        trav = trav->m_prev;
        trav = trav->insert(n);
        return trav;
    }
    else if (key[i + 1] > trav->m_god.name()[i + 1])
    {
        trav = trav->m_succ;
        trav = trav->insert(n);
        return trav;
    }
}
else
{
    if (key[i] < trav->m_god.name()[i])
    {
        trav = trav->m_prev;
        trav = trav->insert(n);
        return trav;
    }
    else if (key[i] > trav->m_god.name()[i])
    {
        trav = trav->m_succ;
        trav = trav->insert(n);
        return trav;
    }
}
return nullptr;


I'll try do it in a similar to this (might switch (==) or (!=) in the first outer if-condition, like how I have it in the actual code right now). Wait a bit.

Edit: Okay, I still have the same result as before. Am I doing the wrong thing by breaking out of the loop if one of the name strings is shorter than the other, and/or is it that the logic in the earlier if-else-if chain where I'm comparing the characters in the name strings is still wrong?

Here's the code:
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
 
Link *Link::add_ordered(Link *n)
{
	Link *trav = this;
	while (trav != nullptr)
	{
		const std::string key = n->m_god.name();	// string being used to compare; is the name string of the "god" to be inserted
		std::size_t i = 0;

		// if the current element in the list is the only element
		if (trav->m_prev != nullptr && trav->m_succ != nullptr)
		{
			// if the curren char in one name string is not the same as the current char in the other name string
			if (key[i] != trav->m_god.name()[i])
			{
				// if the current char in the key is "less" than the current char in the name string of the current element
				if (key[i] < trav->m_god.name()[i])
				{
					// go to the previous pointer of the current element and insert n at that location
					trav = trav->m_prev;
					trav = trav->insert(n);
					return trav;
				}
				// else if the current char in the key is "greater" than the current char in the name string of the current element
				else if (key[i] > trav->m_god.name()[i])
				{
					// go to the next pointer of the current element and insert n at that location
					trav = trav->m_succ;
					trav = trav->insert(n);
					return trav;
				}
			}
			// else if the current chars in each name string are the same
			else if (key[i] == trav->m_god.name()[i] && i == 0)
			{
				// if the char adjacent to the current char in the key is "less" than the one in the name string of the current element
				if (key[i + 1] < trav->m_god.name()[i + 1])
				{
					// go to the previous pointer of the current element and insert n at that location
					trav = trav->m_prev;
					trav = trav->insert(n);
					return trav;
				}
				// else if the char adjacent to the current char in the key is "greater" than the one in the name string of the current element
				else if (key[i + 1] > trav->m_god.name()[i + 1])
				{
					// go the next pointer of the current element and insert n at that location
					trav = trav->m_succ;
					trav = trav->insert(n);
					return trav;
				}
			}
			// if the key string is shorter than the string compared to
			if (key.length() < trav->m_god.name().length() && key[i] == key.at(key.length() - 1))
			{
				// exit the loop
				break;
			}
			// if the key string is greater than the string being compared to
			else if (key.length() > trav->m_god.name().length() && 
				trav->m_god.name()[i] == trav->m_god.name().at(trav->m_god.name().length() - 1))
			{
				// exit the loop
				break;
			}
			++i;
		}
		trav = trav->m_succ;
	}
	return nullptr;
}


What should I do when one name string is shorter than the other? Or do I not have to worry about that (although in this case, the iterator variable would be liable to go out of bounds)?

Edit2: I thought maybe the problem was that I was only checking whether the current element in the only element (and even doing it wrong (signs flipped)), so I tried to fix that, but now I'm back to the situation where I get nothing in the console window (except for a blinking prompt).
Last edited on
jlb (4973)
Didn't you read the code?

Not really, I just skimmed the code. I don't see a reason to thoroughly study the code if you're describing it wrong. Besides after about a half dozen lines I had already noticed several problems.

I didn't try to compare the other characters because I'm not sure what I should do about the sizes of the strings.

Why are you even trying to compare characters?

What should I do when one name string is shorter than the other?

Again why do you care if one string is larger than the other?

but now I'm back to the situation where I get nothing in the console window (except for a blinking prompt).

Do you understand what that "blinking prompt" is really telling you?

You really really need to learn to debug your own programs. Remember that the debugger isn't the only way to debug a program. What have you tried? Just throwing code at a problem you don't understand will only work if you're lucky, you don't seem that "lucky".

DragonOsman (715)
I care if one is shorter than the other so that I don't go out of bounds in the shorter one. That and, for the lexicographical compare, I have to check the characters themselves as well, don't I? Or can I just compare them normally as strings and insert n before or after the current element depending on that?

I've already told you what I've tried and I've also showed it. Why do you need to ask? And yeah, I'm not sure what the "blinking prompt with no output" means. I think it might be something to do with a NULL pointer somewhere since the program seems to be freeze, but that's all I get.

I'm going to try comparing as C-strings using the version of strcomp() where the case doesn't matter. Before that, though, 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
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
 
// Osman Zakir
// 9 / 7 / 2017
// Bjarne Stroustrup: Programming: Principles and Practice Using C++ 2nd Edition
// Chapter 17 Exercises 11-13

#include <iostream>
#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 } { }

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

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

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

void print_all(Link *p);

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" } });
	norse_gods = norse_gods->add_ordered(new Link{ God{ "Freyja", "Norse", 
		"Chariot pulled by two cats", "Magic called seior" } });

	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{ "Mars", "Greek", "", "A spear stained in blood" } });
	greek_gods = greek_gods->add_ordered(new Link{ God{ "Poseidon", "Greek", "", 
		"Three-pronged spear called Trident" } });

	Link* p = greek_gods->find("Mars");
	if (p)
	{
		p->god().set_name("Ares");
	}

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

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

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

	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;
	while (trav != nullptr)
	{
		const std::string key = n->m_god.name();

		if (key < trav->m_god.name())
		{
			trav = trav->advance(-1);
			trav = trav->insert(n);
			return trav;
		}
		else if (key > trav->m_god.name())
		{
			trav = trav->advance(1);
			trav = trav->insert(n);
			return trav;
		}
		
		trav = trav->m_succ;
	}
	return nullptr;
}

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


Edit: Here's another try:
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
 
/**
 * 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 != nullptr)
	{
		std::string key = n->m_god.name();
		std::string name = trav->m_god.name();
		std::size_t key_length = key.length();
		std::size_t name_length = name.length();

		if (std::lexicographical_compare(key.c_str(), key.c_str() + key_length, name.c_str(), name.c_str() + name_length))
		{
			trav = trav->advance(-1);
			trav = trav->insert(n);
			return trav;
		}
		else
		{
			trav = trav->advance(1);
			trav = trav->insert(n);
			return trav;
		}
		trav = trav->m_succ;
	}
	return nullptr;
}


Same overall result, but std::lexicographical_compare should be better than me trying to do it manually at least.
Last edited on
jlb (4973)
I care if one is shorter than the other so that I don't go out of bounds in the shorter one. That and, for the lexicographical compare, I have to check the characters themselves as well, don't I?

No, you don't really need to compare each character.

Or can I just compare them normally as strings and insert n before or after the current element depending on that?

Did you try? How are you going to insert before or after the current element? And remember you can't advance past the last record and you can't retreat past the first element.

I've already told you what I've tried and I've also showed it. Why do you need to ask?

No you haven't said what you've done to try to debug your program all you've shown is throwing code at the problem to try to solve the issue. You need to understand why the program is not working before you can truly solve the problem.

And yeah, I'm not sure what the "blinking prompt with no output" means.

In this case it means that the program is not ending because you have an endless loop somewhere.

I think it might be something to do with a NULL pointer somewhere since the program seems to be freeze, but that's all I get.

It might be because of a nullptr somewhere, but until you do some debugging you're just shooting in the dark.


I'm going to try comparing as C-strings using the version of strcomp() where the case doesn't matter. Before that, though, this is what I have right now:

Why would you step back into the dark ages of C-strings and try to use a non-standard version of strcmp(). You're already using std::string stick with them. 

1
2
3
4
5
6
 
		std::string key = n->m_god.name();
		std::string name = trav->m_god.name();
		std::size_t key_length = key.length();
		std::size_t name_length = name.length();

		if (std::lexicographical_compare(key.c_str(), key.c_str() + key_length, name.c_str(), name.c_str() + name_length))


This is really a waste. Why not:

1
2
3
4
5
6
7
8
 
bool no_case(char a, char b)
{
    return toupper(a) < toupper(b);
}
...
    string name = trav->m_god.name();
    if(std::lexicongraphical_compare(key.begin(), key.end(), name.begin(), name.end(), no_case))
...


DragonOsman (715)
An infinite loop due to trav never being NULL, maybe? If that's the case, I've really goofed.

Anyway, yeah, I'll use begin() and end() and a custom compare function like you suggested.

I remember there was a version of the function Thor and Hera's information was printed while add_ordered() still didn't manage to add anything to the list. I'll try to go back to that version while using std::lexicographical_compare(). I'd have to find out why nothing was being added to the list with add_ordered(), though. Any suggestions/hints/ideas for that? Thanks in advance.

I changed my mind about comparing them as actual strings normally because I found an actual function in the standard library to lexicographically compare strings.

It just seems like that function requires a C-string with input iterators for the start and end of the strings. That's why I converted them to C-strings. It's how it's used in cplusplus.com's reference pages.

Edit: Okay, I still seem to have an infinite loop there with the while. Should I exit the loop after the list has been edited? How do I check for that?

Here is the code for the two functions:
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
 
/**
 * 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 != 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->m_prev;
			trav = trav->insert(n);
		}
		else
		{
			trav = trav->m_succ;
			trav = trav->insert(n);
		}
		trav = trav->m_succ;
	}
	return trav;
}
Last edited on
MikeyBoy (5631)
Okay, I still seem to have an infinite loop there with the while. Should I exit the loop after the list has been edited?


Wouldn't you be better off figuring out why the loop is infinite? Presumably, you're expecting trav to be null at some point. If it's never null, then your code isn't working the way you intended it to work. If you simply change the conditions on which you exit the loop, you haven't actually fixed the problem of your code not doing what you intended, have you?

I can only re-iterate what jlb said: if you want to write decent code, you have to understand why it's not working, and fix that problem, rather than just randomly rewriting code in the hope that you'll accidentally come up with something that appears to work.

There's a reason we use software developers to write code, rather than infinite monkeys...
Last edited on
Pages: 12345... 16