#include <iostream>
#include <assert.h>
#include <string>
#include <algorithm> // for std::swap
using std::string;

namespace StringList
{
    // using std::string;

    struct Node
    {
        string string_;
        Node *prev_;
        Node *next_;
    } head_node, tail_node; // Start node and End node
    
    typedef Node *Cursor; // Cursor like a iterator

    void init()
    {
        head_node.prev_ = tail_node.next_ = 0;
        head_node.next_ = &tail_node;
        tail_node.prev_ = &head_node;
    }

    inline Cursor next(Cursor c)
    {
        assert(c);
        return c->next_;
    }

    inline Cursor prev(Cursor c)
    {
        assert(c);
        return c->prev_;
    }

    inline Cursor head() { return &head_node; }
    inline Cursor tail() { return &tail_node; }

    string extract(Cursor c)
    {
        assert(c != head() && c != tail());
        string s = c->string_;
        c->prev_->next_ = c->next_;
        c->next_->prev_ = c->prev_;
        delete c;
        return s;
    }

    Cursor insert_after(Cursor c, string s)
    {
        assert(c != tail());
        Node *n = new Node;
        n->string_ = s;
        n->prev_   = c;        // Before n
        n->next_   = c->next_; // After n
        c->next_   = n;        // After c;
        n->next_->prev_ = n;   // Before n->next_
        return n;
    }

    Cursor insert_before(Cursor c, string s)
    {
        assert(c != head());
        Node *n = new Node;
        n->string_ = s;
        n->prev_ = c->prev_;
        n->next_ = c;
        c->prev_ = n;
        n->prev_->next_ = n;
        return n;
    }

    void reverse() 
    {
        // First exchange the prev_ and next_ pointers
        // inside each internal node:
        for (Cursor c = next(head()); c!=tail(); c = c->prev_)
            std::swap(c->prev_, c->next_);

        // Then exchange the head and tail positions:
        tail()->prev_->prev_ = head();
        head()->next_->next_ = tail();

        std::swap(head()->next_, tail()->prev_);
    }

    namespace // unnamed namespace
    {
        void quicksort(Cursor left, Cursor right)
        {
            Cursor p = left->next_;
            Cursor l = left->next_, r = right->prev_;

            if (left == right || l == right || l == r) return;

            while (true)
            {
                while (l != r && l->string_ < p->string_)
                    l = next(l);
                while (l != r && p->string_ <= r->string_)
                    r = prev(r);
                if (l == r)
                    break;
                std::swap(l->string_, r->string_);
            }

            if (l->string_ < p->string_)
            {
                if (r->next_ != right) l = next(l);
            }
            else
            {
                if (left->next_ != r) r = prev(r);
            }

            quicksort(left, l);
            quicksort(r, right);
        }
    } // End unnamed namespace

    void sort()
    {
        if (head()->next_ != tail() && head()->next_->next_ != tail())
            quicksort(head(), tail());
    }
} // End namespace StringList

void print_stringlist()
{
    StringList::Cursor p = StringList::head();
    while ((p = StringList::next(p)) != StringList::tail())
        std::cout << p->string_ << std::endl;
}


int main()
{
   StringList::init();
   StringList::insert_before(StringList::tail(), string("Cobol"));
   StringList::insert_before(StringList::tail(), string("Fortran"));
   StringList::insert_before(StringList::tail(), string("Lisp"));
   StringList::insert_before(StringList::tail(), string("Algol 68"));
   StringList::insert_before(StringList::tail(), string("Basic"));
   StringList::insert_before(StringList::tail(), string("Pascal"));
   StringList::insert_before(StringList::tail(), string("C"));
   StringList::insert_before(StringList::tail(), string("Ada"));
   StringList::insert_before(StringList::tail(), string("Modula-2"));
   StringList::insert_before(StringList::tail(), string("C++"));
   std::cout << ">>> Original list of strings: \n";
   print_stringlist();
   std::cout << "\n>>> Reversed list of strings: \n";
   StringList::reverse();
   print_stringlist();
   std::cout << "\n>>> Sorted list of strings: \n";
   StringList::sort();
   print_stringlist();
   std::cout << "\n>>> Done.\n";

   return 0;
}