Skip to content

Instantly share code, notes, and snippets.

@DragonOsman
Last active November 5, 2017 17:15
Show Gist options
  • Save DragonOsman/c08e31b18921762fb8b156ba665dce39 to your computer and use it in GitHub Desktop.
Save DragonOsman/c08e31b18921762fb8b156ba665dce39 to your computer and use it in GitHub Desktop.
linked lists program for exercise
#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);
}
#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
// 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";
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment