// Chapter 17, exercise 14: complete the "list of gods" example from 17.10.1,
// but this time as a singly-linked list

#include<iostream>
using namespace std;

struct List;

class Link {
public:
    string value;

    Link(const string& v, Link* s = 0)
        : value(v), succ(s) { }

    Link* insert(List& l, Link* n);                         // insert n before this object
    Link* add(Link* n);                                     // insert n after this object
    Link* erase(List& l);                                   // remove this object from the list
    Link* find(const List& l, const string& s);             // find s in list
    const Link* find(const List& l, const string& s) const; // find s in const list

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

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

struct List {
    List() : first_link(0) { }
    List(Link* l) : first_link(l) { }
    Link* first_link;
};

// insert n before this object
Link* Link::insert(List& l, Link* n) {
    if (n==0) return this;
    if (this==0) return n;
    n->succ = this;
    if (l.first_link == this) {
        l.first_link = n;
        return n;
    }
    Link* p = l.first_link;
    while (p->succ != this)
        p = p->succ;
    p->succ = n;
    return n;
}

// insert n after this object
Link* Link::add(Link* n) {
    if (n==0) return this;
    if (this==0) return n;
    n->succ = succ;
    succ = n;
    return n;
}

// erase this object, return successor
Link* Link::erase(List& l) {
    if (this==0) return 0;
    if (l.first_link == this) {
        l.first_link = succ;
    }
    Link* p = l.first_link;
    while (p->succ != this)
        p = p->succ;
    p->succ = succ;
    return succ;
}

// find s in list; return 0 for "not found"
Link* Link::find(const List& l, const string& s) {
    Link* p = l.first_link;
    while (p) {
        if (p->value==s) return p;
        p = p->succ;
    }
    return 0;
}

// find s in const list; return 0 for "not found"
const Link* Link::find(const List& l, const string& s) const {
    const Link* p = l.first_link;
    while (p) {
        if (p->value==s) return p;
        p = p->succ;
    }
    return 0;
}

// move n positions in list, return 0 for "not found"
// positive n moves forward
Link* Link::advance(int n) const {
    if (this==0) return 0;
    Link* p = const_cast<Link*>(this);  // UGLY
    if (0 <= n) {
        while (n--) {
            if (p->succ==0) return 0;
            p = p->succ;
        }
    }
    else cerr << "must advance by a positive number";
    return p;
}

void print_all(const List& l)
{
    cout << "{ ";
    Link* p = l.first_link;
    while (p) {
        cout << p->value;
        if (p=p->next()) cout << ", ";
    }
    cout << " }";
}


int main()
try {
    Link* swiss_mathematicians = new Link("LEuler");
    List s_mathematicians(swiss_mathematicians);
    swiss_mathematicians = swiss_mathematicians->insert(s_mathematicians, new Link("Lambert"));
    swiss_mathematicians = swiss_mathematicians->insert(s_mathematicians, new Link("JBernoulli"));
    swiss_mathematicians = swiss_mathematicians->insert(s_mathematicians, new Link("DBernoulli"));

    Link* german_mathematicians = new Link("Gauss");
    List g_mathemticians(german_mathematicians);
    german_mathematicians = german_mathematicians->insert(g_mathemticians,new Link("Riemann"));
    german_mathematicians = german_mathematicians->insert(g_mathemticians,new Link("Klein"));
    german_mathematicians = german_mathematicians->insert(g_mathemticians,new Link("Frege"));

    Link* p = german_mathematicians->find(g_mathemticians,"Klein");
    if (p) p->value = "Einstein";

    Link* p2 = swiss_mathematicians->find(s_mathematicians,"Frege");
    if (p2) {
        if (p2==swiss_mathematicians) swiss_mathematicians = p2->next();
        p2->erase(s_mathematicians);
        german_mathematicians->add(p2);
        german_mathematicians = g_mathemticians.first_link;
    }

    print_all(s_mathematicians);
    cout << "\n";

    print_all(g_mathemticians);
    cout << "\n";
}
catch (exception& e) {
    cerr << "exception: " << e.what() << endl;
}
catch (...) {
    cerr << "exception\n";
}