linked lists program for exercise

cust_std_lib_facilities.cpp

#include "cust_std_lib_facilities.h"
#include <iostream>
#include <chrono>
#include <stdexcept>
#include <random>
#include <string>

int randint(int min, int max) 
{ 
	using namespace std;

	auto seed = chrono::system_clock::now().time_since_epoch().count();
	static default_random_engine ran(seed);
	return uniform_int_distribution<>{min, max}(ran); 
}

void keep_window_open()
{
	using namespace std;
	cin.clear();
	cout << "Please enter a character to exit\n";
	char ch;
	cin >> ch;
	return;
}

void keep_window_open(std::string s)
{
	using namespace std;
	if (s == "") return;
	cin.clear();
	cin.ignore(120, '\n');
	for (;;) {
		cout << "Please enter " << s << " to exit\n";
		string ss;
		while (cin >> ss && ss != s)
			cout << "Please enter " << s << " to exit\n";
		return;
	}
}

void error(const std::string& s)
{
	using namespace std;
	throw runtime_error(s);
}

void error(const std::string& s, const std::string& s2)
{
	error(s + s2);
}

cust_std_lib_facilities.h

#ifndef CUST_STD_LIB_FACILITIES_H
#define CUST_STD_LIB_FACILITIES_H

#include <iostream>
#include <string>

int randint(int min, int max);
void error(const std::string& s, const std::string& s2);
void error(const std::string& s);
void keep_window_open();
void keep_window_open(std::string s);

#endif

linked_lists.cpp

// Osman Zakir
// 9 / 7 / 2017
// Bjarne Stroustrup: Programming: Principles and Practice Using C++ 2nd Edition
// Chapter 17 Exercises 11-13

#include <iostream>
#include <fstream>
#include <stdexcept>
#include <vld.h>
#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 } { }
		God()
			: m_name{}, m_myth{}, m_vehicle{}, m_weapon{} {}

		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 *n = nullptr)
		: m_god{ god }, m_prev{ p }, m_succ{ n }
	{	
	}

	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 node matching passed in name in list
	Link *find_if_myth(const std::string &myth);                      // find node matching passed in myth in list
	const Link *find_if_myth(const std::string &myth) const;          // find node matching passed in myth in const list
	const Link *find(const std::string &name) const;                  // find node matching passed in name in const list
	Link *advance(int n) const;                                       // advance n positions in list
	Link *add_ordered(Link *n);                                       // insert n in its correct lexicographical position

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

void print_all(Link *p);
void move_nodes(Link *dest_list, Link *source_list, const std::string &myth);

int main()
{
	Link *gods;
	try
	{
		gods = new Link{ { "Odin", "Norse", "Eight-legged flying horse called Sleipnir", "Spear called Gungnir" } };
		gods = gods->add_ordered(new Link{ { "Thor", "Norse", "Chariot pulled by goats Tanngrisnir and Tanngnjostr",
			"Hammer called Mjolnir" } });
		gods = gods->add_ordered(new Link{ { "Baldr", "Norse", "A giant ship called Hringorni", "None" } });
		gods = gods->add_ordered(new Link{ { "Frejya", "Norse", "Chariot pulled by two cats", "Magic called seidr" } });
		gods = gods->add_ordered(new Link{ { "Zeus", "Greek", "A chariot pulled by the four major winds shaped as horses",
			"Thunderbolt and the shield called Aegis" } });
		gods = gods->add_ordered(new Link{ { "Hera", "Greek", "A chariot drawn by peacocks", "Her intelligence" } });
		gods = gods->add_ordered(new Link{ { "Athena", "Greek", "", "Allowed to use Zeus's Thunderbolt and the Aegis" } });
		gods = gods->add_ordered(new Link{ { "Ares", "Greek", "War chariot", "Sword and spear" } });
		gods = gods->add_ordered(new Link{ { "Amaterasu", "Japanese", "", "Sword of Kusanagi, Jewel of Yasakani, Mirror of Yata" } });
		gods = gods->add_ordered(new Link{ { "Susanoo", "Japanese", "", "Sword of Totsuka" } });
		gods = gods->add_ordered(new Link{ { "Izanagi", "Japanese", "", "Sword of Totsuka (later given to Susanoo)" } });
		gods = gods->add_ordered(new Link{ { "Bishamonten", "Japanese", "", "A spear" } });
	}
	catch (const std::bad_alloc &ba)
	{
		std::cerr << "Bad allocation error: " << ba.what() << std::endl;
	}
	catch (const std::runtime_error &rte)
	{
		std::cerr << "Runtime error: " << rte.what() << std::endl;
	}
	catch (const std::exception &e)
	{
		std::cerr << "Exception: " << e.what() << std::endl;
	}

	try
	{
		Link *norse_gods = new Link{ { "Odin", "Norse", "Eight-legged flying horse called Sleipnir", "Spear called Gungnir" } };
		Link *greek_gods = new Link{ { "Zeus", "Greek", "A chariot pulled by the four major winds shaped as horses",
			"Thunderbolt and the shield called Aegis" } };
		Link *jap_gods = new Link{ { "Amaterasu", "Japanese", "", "Sword of Kusanagi, Jewel of Yasakani, Mirror of Yata" } };

		while (gods->find_if_myth("Norse"))
		{
			move_nodes(norse_gods, gods, "Norse");
		}
		while (gods->find_if_myth("Greek"))
		{
			move_nodes(greek_gods, gods, "Greek");
		}
		while (gods->find_if_myth("Japanese"))
		{
			move_nodes(jap_gods, gods, "Japanese");
			if (jap_gods->find("Susanoo") && jap_gods->find("Izanagi") && jap_gods->find("Bishamonten"))
			{
				break;
			}
		}
		
		std::cout << "\nnorse_gods list:\n";
		print_all(norse_gods);
		std::cout << "\ngreek_gods list:\n";
		print_all(greek_gods);
		std::cout << "\njap_gods list:\n";
		print_all(jap_gods);
		std::cout << "\ngods list:\n";
		print_all(gods);

		delete gods;
		delete norse_gods;
		delete jap_gods;
		delete greek_gods;
	}
	catch (const std::runtime_error &rte)
	{
		std::cerr << "Runtime error: " << rte.what() << std::endl;
	}
	catch (const std::bad_alloc &ba)
	{
		std::cerr << "Bad allocation error: " << ba.what() << std::endl;
	}
	catch (const std::exception &e)
	{
		std::cerr << "Exception: " << e.what() << std::endl;
	}

	keep_window_open();
}

Link *Link::insert(Link *n)
{
	if (n == nullptr)
	{
		return this;
	}
	n->m_succ = this;    // this object comes after n
	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 this;
	}
	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 *head = this;
	while (head->m_prev)
	{
		head = head->m_prev;
	}

	Link *tail = this;
	while (tail->m_succ)
	{
		tail = tail->m_succ;
	}

	Link *trav = tail;
	while (trav->m_prev)
	{
		if (trav->god().m_name == name)
		{
			return trav;
		}
		trav = trav->m_prev;
	}
	return nullptr;
}

Link *Link::find_if_myth(const std::string &myth)
{
	Link *head = this;
	while (head->m_prev)
	{
		head = head->m_prev;
	}

	Link *tail = this;
	while (tail->m_succ)
	{
		tail = tail->m_succ;
	}

	Link *trav = tail;
	while (trav != head)
	{
		if (trav->god().m_myth == myth)
		{
			return trav;
		}
		trav = trav->m_prev;
	}
	return nullptr;
}

const Link *Link::find_if_myth(const std::string &myth) const
{
	const Link *head = this;
	while (head->m_prev)
	{
		head = head->m_prev;
	}

	const Link *tail = this;
	while (tail->m_succ)
	{
		tail = tail->m_succ;
	}

	const Link *trav = tail;
	while (trav != head)
	{
		if (trav->god().m_myth == myth)
		{
			return trav;
		}
		trav = trav->m_prev;
	}
	return nullptr;
}

const Link *Link::find(const std::string &name) const
{
	const Link *head = this;
	while (head->m_prev)
	{
		head = head->m_prev;
	}

	const Link *tail = this;
	while (tail->m_succ)
	{
		tail = tail->m_succ;
	}

	const Link *trav = tail;
	while (trav->m_prev)
	{
		if (trav->god().m_name == name)
		{
			return trav;
		}
		trav = trav->m_prev;
	}
	return nullptr;
}

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

Link *Link::add_ordered(Link *n)
{
	if (n == nullptr)
	{
		return this;
	}
	
	Link *trav = this;
	if (!trav)
	{
		return n;
	}

	// to make sure to start at head of the list
	while (trav->m_prev != nullptr)
	{
		trav = trav->m_prev;
	}

	while (trav->m_god.m_name < n->m_god.m_name && trav->m_succ)
	{
		trav = trav->m_succ;
	}

	if (n->m_god.m_name < trav->m_god.m_name)
	{
		trav = trav->insert(n);
	}
	else if (!(n->m_god.m_name < trav->m_god.m_name))
	{
		trav = trav->add(n);
	}
	return trav;
}

void move_nodes(Link *dest_list, Link *source_list, const std::string &myth)
{
	Link *trav = source_list->find_if_myth(myth);
	if (trav)
	{
		trav->erase();
		if (trav->god().m_name != dest_list->god().m_name)
		{
			dest_list = dest_list->add_ordered(trav);
		}
	}
}

void print_all(Link *p)
{
	while (p->previous() != nullptr && p != nullptr)
	{
		p = p->previous();
	}

	std::cout << "{\n";
	while (p)
	{
		std::cout << "Name: " << p->god().m_name
			<< "; Myth: " << p->god().m_myth;
		if (p->god().m_vehicle != "")
		{
			std::cout << "; Vehicle: " << p->god().m_vehicle;
		}
		else
		{
			std::cout << "; Vehicle: N/A";
		}
		if (p->god().m_weapon != "")
		{
			std::cout << "; Weapon: " << p->god().m_weapon;
		}
		else
		{
			std::cout << "; Weapon: N/A";
		}
		if ((p = p->next()))
		{
			std::cout << "\n";
		}
	}
	std::cout << "\n}\n";
}