/** G. Hagopian
4. Modify class Link from §17.9.3 to be a template with the type
of value as the template argument. Then redo exercise 13 from
Chapter 17 with Link<God>.

13. Modify the Link class from §17.10.1 to hold a value of a
struct God. struct God should have members of type string: name,
mythology, vehicle, and weapon. For example,
God{"Zeus", "Greek", "", "lightning"} and
God{"Odin", "Norse", "Eight-legged flying horse called Sleipner", "Spear called Gungnir"}.
Write a print_all() function that lists gods with their attributes
one per line. 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.
*/

/** template<typename T>
class Link {
public:
    T value;

    Link(const T& v, Link* p = 0, Link* s = 0)
        : value(v), prev(p), 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 T& s);    // find s in list
    const Link* find(const string& s) const; // find s in list

    Link* advance(int n) const;     // move n positions in list

    Link* next() const { return succ; }
    Link* previous() const { return prev; }
private:
    Link* prev;
    Link* succ;
};*/

#include<iostream>
#include<string>
using namespace std;

template<class T> struct Link {
    T value;
    Link<T>* prev;
    Link<T>* succ;
    Link<T>(const T& v, Link<T>* p = 0, Link* s = 0)
        : value(v), prev(p), succ(s) { }
    Link<T>* erase() ;// remove this object from list
    Link<T>* find(const T& s);    // find s in list
    Link<T>* add_ordered(Link<T>* p, Link<T>* n)
    {
        if (n==0) return p;
        if (p==0) return n;
        while (n->value > p->value && p->succ) {
            p = p->succ;
        }
        /// p points now to first element with value bigger than value of n or the
        /// last element of the list
        if (n->value > p->value) p = add(p,n);
        else p = insert(p,n);

        // traverse list to return first element
        while (p->prev) p = p->prev;
        return p;
    }
    Link<T>* move(Link<T>* from, Link<T>* to, const T& d)
    {
        Link<T>* temp = find(from,d);
        erase(temp);
        return add_ordered(to,temp);
    }
    Link<T>* next() const { return succ; }
    Link<T>* previous() const { return prev; }
};

//------------------------------------------------------------------------------
///from https://github.com/bewuethr/stroustrup_ppp/blob/master/chapter19/chapter19_ex04.cpp
struct God {
    God(const string& n, const string& m, const string& v, const string& w)
        : name(n), mythology(m), vehicle(v), weapon(w) { }
    string name;
    string mythology;
    string vehicle;
    string weapon;
};
//------------------------------------------------------------------------------

ostream& operator<<(ostream& os, const God& g)
{
    os << g.name << ": " << g.mythology << ", "
        << g.vehicle << ", " << g.weapon;
    return os;
}
//------------------------------------------------------------------------------

/**template<class T>
struct Link {
    T value;
    Link* prev;
    Link* succ;
    Link(const T& v, Link* p = 0, Link* s = 0)
        : value(v), prev(p), succ(s) { }
};*/

// insert n before p; return n
template<class T>
Link<T>* insert(Link<T>* p, Link<T>* n)
{
    if (n==nullptr) return p;
    if (p==nullptr) return n;
    n->succ = p;
    if (p->prev) p->prev->succ = n;
    n->prev = p->prev;
    p->prev = n;
    return n;
}

//------------------------------------------------------------------------------

template<typename T>
Link<T>* Link<T>::erase()          // remove this object from the list; return this's successor
{
    if (this==0) return 0;
    if (succ) succ->prev = prev;
    if (prev) prev->succ = succ;
    return succ;
}

//------------------------------------------------------------------------------
template<typename T>
Link<T>* Link<T>::find(const T& s) // find s in list;
/// return 0 for "not found"
{
    Link* p = this;
    while(p) {
        if (p->value == s) return p;
        p = p->succ;
    }
    return 0;
}

//------------------------------------------------------------------------------

template<typename T>
void print_all(Link<T>* p)
{
    cout << "{ ";
    while (p) {
        cout << p->value;
        if (p=p->next()) cout <<  ", ";
    }
    cout << " }";
}


int main() {
    Link<God>* all_gods = new Link<God>(God("Thor","Norse",
        "Pinzgauer","Hammer"));
    all_gods = insert(all_gods,new Link<God>(God("Odin","Norse",
        "Eight-legged horse","")));
    all_gods = insert(all_gods,new Link<God>(God("Zeus","Greek",
        "","Lightning")));
    all_gods = insert(all_gods,new Link<God>(God("Freia","Norse",
        "F-transport","F-weapon")));
    all_gods = insert(all_gods,new Link<God>(God("Hera","Greek",
        "H-transport","Spear")));
    all_gods = insert(all_gods,new Link<God>(God("Athena","Greek",
        "A-transport","A-weapon")));
    all_gods = insert(all_gods,new Link<God>(God("Mars","Roman",
        "M-transport","M-weapon")));
    all_gods = insert(all_gods,new Link<God>(God("Poseidon","Greek",
        "Seahorse","Trident")));
    all_gods = insert(all_gods,new Link<God>(God("Ares","Greek",
        "A-transport","A-weapon")));
    all_gods = insert(all_gods,new Link<God>(God("Vesuvius","Roman",
        "V-transport","Volcano")));
    all_gods = insert(all_gods,new Link<God>(God("Bacchus","Roman",
        "Stretcher","Wine goblet")));

    print_all(all_gods);

    Link<God>* norse_gods = nullptr;
    norse_gods = move(all_gods,norse_gods,
        God("Odin","Norse","Eight-legged horse",""));
    norse_gods = move(all_gods,norse_gods,God("Thor","Norse",
        "Pinzgauer","Hammer"));
    norse_gods = move(all_gods,norse_gods,God("Freia","Norse",
        "F-transport","F-weapon"));

    Link<God>* greek_gods = 0;
    greek_gods = move(all_gods,greek_gods,God("Hera","Greek",
        "H-transport","Spear"));
    greek_gods = move(all_gods,greek_gods,God("Athena","Greek",
        "A-transport","A-weapon"));
    greek_gods = move(all_gods,greek_gods,God("Poseidon","Greek",
        "Seahorse","Trident"));
    greek_gods = move(all_gods,greek_gods,God("Zeus","Greek",
        "","Lightning"));
    greek_gods = move(all_gods,greek_gods,God("Ares","Greek",
        "A-transport","A-weapon"));

    Link<God>* roman_gods = 0;
    roman_gods = move(all_gods,roman_gods,God("Mars","Roman",
        "M-transport","M-weapon"));
    roman_gods = move(all_gods,roman_gods,God("Vesuvius","Roman",
        "V-transport","Volcano"));
    roman_gods = move(all_gods,roman_gods,God("Bacchus","Roman",
        "Stretcher","Wine goblet"));

    // all_gods is now empty - this should probably be part of the erase
    // function
    all_gods = 0;

    cout << "\nAll gods:\n";
    print_all(all_gods);
    cout << "\nNorse gods:\n";
    print_all(norse_gods);
    cout << "\nGreek gods:\n";
    print_all(greek_gods);
    cout << "\nRoman gods:\n";
    print_all(roman_gods);
}