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 <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()
{
    try
    {
        Link *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" } });

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

        Link *norse_gods = Odin;
        Link *greek_gods = Zeus;
        Link *jap_gods = Amaterasu;

        while (gods->next() && gods->find_if_myth("Norse"))
        {
            move_nodes(norse_gods, gods, "Norse");
        }
        while (gods->next() && gods->find_if_myth("Greek"))
        {
            move_nodes(greek_gods, gods, "Greek");
        }
        while (gods->next() && gods->find_if_myth("Japanese"))
        {
            move_nodes(jap_gods, gods, "Japanese");
        }

        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 Odin;
        delete Zeus;
        delete Amaterasu;
        delete gods;
    }
    catch (const std::runtime_error &rte)
    {
        std::cerr << "Runtime error: " << rte.what() << '\n';
        keep_window_open();
        return 1;
    }
    catch (const std::bad_alloc &ba)
    {
        std::cerr << "Bad allocation error: " << ba.what() << '\n';
        keep_window_open();
        return 2;
    }
    catch (const std::exception &e)
    {
        std::cerr << "Exception: " << e.what() << "\n";
        keep_window_open();
        return 3;
    }
    catch (...)
    {
        std::cerr << "An unknown exception occurred\n";
        keep_window_open();
        return 4;
    }

    keep_window_open();
}

Link *Link::insert(Link *n)
{
    if (n == nullptr)
    {
        return this;
    }
    if (this == nullptr)
    {
        return n;
    }
    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;
    }
    if (this == nullptr)
    {
        return n;
    }
    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 *trav = this;
    while (trav != nullptr)
    {
        if (trav->m_god.m_name == name)
        {
            return trav;
        }
        trav = trav->m_succ;
    }
    return nullptr;
}

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

    while (trav && trav->m_succ)
    {
        if (trav->m_god.m_myth == myth)
        {
            return trav;
        }
        trav = trav->m_succ;
    }
    return nullptr;
}

const Link *Link::find_if_myth(const std::string &myth) 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.m_myth == myth)
        {
            return c_trav;
        }
        nc_trav = nc_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.m_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 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;
    }
    if (this == nullptr)
    {
        return n;
    }

    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)
    {
        if (trav == source_list)
        {
            trav = source_list->next();
        }
        trav->erase();
        if (trav->god().m_name != dest_list->god().m_name && trav->god().m_myth == myth)
        {
            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";
}