linked_lists.cpp

// 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);
bool no_case(char a, char b);

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

    print_all(norse_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 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)
{
    if (n == nullptr)
    {
        return nullptr;
    }

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

    std::string key = n->m_god.name();
    while (trav->m_succ)
    {
        if (std::lexicographical_compare(key.begin(), key.end(), trav->m_god.name().begin(), trav->m_god.name().end(), no_case))
        {
            trav = trav->insert(n);
        }
        else
        {
            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_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 << "}";
}