/* tcslll_.cpp
 *
 * a generic templated circular singly linked list using
 * classes and overloading <
 *
 */
#include 
using namespace std;


template 
struct ListNode
  {
    ListNode  *next;
    T          info;

    ListNode() { next = this; }
    ListNode(T newinfo) { next = this; info = newinfo; }
    bool operator < (const ListNode item);
  };

  template 
  bool ListNode::operator < (const ListNode item)
    { int t;

      t = info < item.info;  // compare 2 items of type T
      return  t;
    }

// Templated Circular Singly Linked List
//
template 
class List
  {
  public:
    List () {}
   ~List () {}

    /*
     * Insert a single node on to the front of a (circular singly linked ) list
     */
    void Insert_Left (T* & tail, T* p)
      {
        if (!tail)
          { /* insert into an empty list */
            tail = p;
            p->next = p;
          }
        else
          { /* insert into a non-empty list */
            p->next = tail->next;
            tail->next = p;
          }
      }


    /* Insert a single node onto the end of a (circular singly linked) list */
    void Insert_Right(T* &tail, T* p)
      {
        Insert_Left(tail,p);
        tail = p;
      }


    /*
     *  Remove the node pointed to by tail->next
     *  (i.e. remove the first node from the list, and set the link
     *  of that node to point to that node)
     */
    void Remove_Left(T*& tail, T* &p)
      {
        if(!tail) p = tail;
        else
          {
            if (tail->next==tail)
              { /* 1 node left */
                p = tail;
                tail = NULL;
              }
            else
              { /* > 1 node left */
                p = (T *)tail->next;
                tail->next = p->next;
              }
            p->next = p;
          }
      }


    /*
     * Remove the node pointed to by tail
     *  (i.e. remove the last node from the list)
     */
    void Remove_Right(T*& tail,T* &p)
      {
        p = tail;
        while (p->next != tail) p = p->next;    /*  MAY SLOW IT DOWN */
        tail = p;
        Remove_Left(tail,p);
      }


    /* returns the ADDRESS of the first node in the list */
    T *First_Node(T* tail)
      {
        if (tail) return (T *)tail->next;
        else return NULL;
      }


    /* returns the ADDRESS of the last node in the list */
    T *Last_Node(T* tail)
      {
        return tail;
      }


    /* returns the ADDRESS of p->next (unless p points to the last one). */
    T *Next_Node (T* &tail, T* &p)
      {
        if (p == tail) return NULL;
        else return (T *) p->next;
      }


    /*
     * Traverse the csll - when visiting each node invoke '<<'.
     * The user is required to write << for the type being processed.
     * 
     */
    void Traverse(T* tail)
      {
        T *p = First_Node(tail);
        while (p)
          {
            cout << p->info ;
            p = Next_Node (tail, p);
          }
      }

    /*
     * Sort items in a (Circular Singly Linked) List using the comparator <.
     * The last item in the list is referenced by the parameter 'tail'.
     *
     * The user is required to overload the "<" operator for the record type
     * being sorted.
     *
     */
    void Sort(T* & tail)
      {
        int i, t1, t2, outindex, Res;
        long int count[2];
        T *p, *in[2], *out[2], First0, First1, Last;

        /* set both input lists and both output lists to NULL */
        for (i = 0; i < 2; i++) in[i] = out[i] = NULL;

        /* point out[0] to the list to be sorted */
        out[0] = tail;

        /* this loop will sort the list until the 2nd output list is empty */
        do
          {
            /* move the output list pointers to the input list pointers
             * set the output list pointers to NULL
             * set the counts to 0
             */
            for (i=0; i<2; i++)
              {
                in[i] = out[i];
                out[i] = NULL;
                count[i] = 0;
              }

            /* Move the first item over */
            /* if there is only 1 list - grab the first one from that list  */
            if (!in[1]) Remove_Left(in[0],p);
            else
              {
               /* if there are 2 lists, get the smaller one from the 2 lists */
               Remove_Left(in[!(*First_Node(in[0]) < *First_Node(in[1]))],p);
              }
            /* now, insert the node into the output list */
            Insert_Right(out[0],p);
            count[0]++;

            /* this loop moves the rest of the items over,
               from the 2 input lists to the 2 output lists */
            outindex = 0;
            while (in[0] || in[1])
              { /* figure out which node to remove then remove it */
                if (!in[0] || !in[1])
                  /* one of the lists is empty */
                  /* remove an item from the only non-empty list */
                  Remove_Left(in[!!in[1]],p);
                else
                  { /* both the input lists are non-empty */
                    First0 = *First_Node(in[0]);
                    First1 = *First_Node(in[1]);
                    Last   = *Last_Node(out[outindex]);
                    Res    = First0 < First1;
                    t1     = First0 < Last;
                    t2     = First1 < Last;
                    Remove_Left(in[(t1 && t2 || !t1 && !t2 ? !Res : Res)],p);
                  }
                /* determine which output list to send the node to */
                First0 = *p;
                First1 = *Last_Node(out[outindex]);
                if (First0 < First1)
                    outindex ^= 1;
                /* send the node to the appropriate output list */
                Insert_Right(out[outindex],p);
                count[outindex]++;
              }
            cout << count[0] << "  " << count[1] << endl;  /* watch the passes */

          } while (out[1]);
        tail = out[0];
      } /* end of function Sort */
  }; /* end of class List */