/*
 * CSLL_.C
 *
 * Implementation of a Circular Singly Linked List with a single tail pointer.
 * Copyright (c) 1999 Bill McDaniel  www.comsc.uco.edu/~mcdaniel.
 *
 * This file includes the following routines:
 *
 *   Init_List    (void **  tail)
 *   Fetch_A_Node (long int size)
 *   Insert_Left  (void  *  p, void **tail)
 *   Insert_Right (void  *  p, void **tail)
 *   Remove_Left  (void **  tail)
 *   Remove_Right (void **  tail)
 *   First_Node   (void  *  tail)
 *   Last_Node    (void  *  tail)
 *   Next_Node    (void  *  p, void *tail)
 *   Traverse     (void  *  tail_pointer, void (*Visit) (void *))
 *   Sort         (void **  tail_pointer, int (*comp) (void *, void *))
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include "csll_.h"


/*
 * initialize the list to empty
 */
void Init_List(void **tail)
  {
    *tail = NULL;
  }


/*
 * Allocate and initialize a node.
 */
void *Fetch_A_Node(long int size)
  { struct SllNode *p;
    p = (struct SllNode *) malloc(size);
    if (!p) { printf("Out of Memory\n"); exit(0); }
    p->next = p;
    return p;
  }


/*
 * Insert a single node on to the front of a ( circular, singly linked ) list
 */
void Insert_Left (void *p_, void **tail_)
  { struct SllNode  *p    = (struct SllNode  *)p_;
    struct SllNode **tail = (struct SllNode **)tail_;
    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(void *p, void **tail)
  {
    Insert_Left(p,tail);
    *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(void **tail_)
  { struct SllNode *p, **tail = (struct SllNode **)tail_;
    if(!*tail) p = *tail;
    else
      { /* non-empty list */
        if ((*tail)->next==*tail)
          { /* only 1 item left */
            p = *tail;
            *tail = NULL;
          }
        else
          { /* more than 1 item left */
            p = (*tail)->next;
            (*tail)->next = p->next;
          }
        p->next = p;
      }
    return p;
  }


/*
 * Remove the node pointed to by *tail
 *  (i.e. remove the last node from the list)
 */
void *Remove_Right(void **tail)
  { struct SllNode *p;
    p = (SllNode *) *tail;
    while (p->next != *tail) p = p->next;    /*  may slow it down, A LOT */
    *tail = p;
    p = (SllNode *) Remove_Left(tail);
    return p;
  }


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


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


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


/*
 * Traverse the csll - when visiting each node invoke 'Visit'.
 * The user is required to write (and pass the address of) 'Visit' (which is
 * the code the user wants executed when this node is processed).
 */
void Traverse(void *tail_pointer, void (*Visit) (void *))
  {
    SllNode *p = (SllNode *)First_Node(tail_pointer);
    while (p)
      {
        Visit(p);
        p = (SllNode *)Next_Node (p,tail_pointer);
      }
  }


/*
 * Sort items in a ( Circular, Singly Linked ) List using the comparator 'comp'.
 * The last item in the list is referenced by the parameter 'tail_pointer'.
 *
 * The user is required to write (and pass the address of) 'comp' (which is
 * probably a  less_than  test which returns true if the item pointed to by
 * the first parameter is  less than  the item pointed to by the second
 * parameter).  The parameters are void pointers because this code has no
 * idea what they will point to.  The 'comp' routine will have to make
 * the necessary type changes so the appropriate fields will be compared.
 * comp returns either a 0 (FALSE) or a 1 (TRUE).
 */
void Sort(void ** tail_pointer, int (*comp) (void *, void *))
  {
    void *p;
    int i, t1, t2, outindex, Res;
    void *in[2], *out[2], *First0, *First1, *Last;
    long int count[2];

    /* 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_pointer;

    /* 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]) p = Remove_Left(&in[0]);
        else
        /* if there are 2 lists, get the smaller one from the 2 lists */
           p = Remove_Left(&in[!comp(First_Node(in[0]),First_Node(in[1]))]);
        /* now, insert the node into the output list */
        Insert_Right(p,&out[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 */
              p = Remove_Left(&in[!!in[1]]);
            else
              { /* both the input lists are non-empty */
                First0 = First_Node(in[0]);
                First1 = First_Node(in[1]);
                Last   = Last_Node(out[outindex]);
                Res    = comp(First0, First1);
                t1     = comp(First0, Last);
                t2     = comp(First1, Last);
                p = Remove_Left(&in[(t1 && t2 || !t1 && !t2 ? !Res : Res)]);
              }
            /* determine which output list to send the node to */
            if (comp(p, Last_Node(out[outindex]))) outindex ^= 1;

            /* send the node to the appropriate output list */
            Insert_Right(p,&out[outindex]);
            count[outindex]++;
          }
        printf("%8ld %8ld\n",count[0],count[1]);  /* To watch the passes */
      } while (out[1]);
    *tail_pointer = out[0];
  }