/* listsetc.c             General routines for lists, etc */

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


/**********************************************************************/
/* lbs_init()  create and initialise a list/bag/set                   */
/*  return a pointer to the new list                                  */

LBS_PTR lbs_init()
{
  LBS_PTR newlist;                 /* pointer to new list */

  /* create the list */
  newlist = (LBS *) malloc(sizeof(LBS));
  if (newlist == NULL) {
    return(NULL);
  }

  /* initialise the list */
  FRONT(newlist) = NULL;
  BACK(newlist) = NULL;
  NELS(newlist) = 0;
  return(newlist);
}                                                     /* end LBS_INIT */
/**********************************************************************/



/**********************************************************************/
/* alloc_lbsnode()         allocate space for a (list) node           */
/*    return a pointer to the node structure                          */

LBS_NODE_PTR alloc_lbsnode()
{
  LBS_NODE_PTR newnode;

  /* create the node */
  newnode = (LBS_NODE *) malloc(sizeof(LBS_NODE));
  if (newnode == NULL) {
    return(NULL);
  }

  DATA(newnode) = NULL;
  NEXTEL(newnode) = NULL;
  return(newnode);
}                                                  /* end ALLOC_LBSNODE */
/**********************************************************************/



/**********************************************************************/
/* free_lbsnode()   free a (list) node                                */

void free_lbsnode(pN)
LBS_NODE_PTR pN;
{
  free(pN);
  pN = NULL;
}                                                   /* end FREE_LBSNODE */
/**********************************************************************/



/**********************************************************************/
/* lbs_empty(pL)    TRUE iff list is empty                           */

int lbs_empty(pL)
LBS_PTR pL;
{
  if (pL == NULL) return(TRUE);
  if (FRONT(pL) == NULL) {
    return(TRUE);
  }
  else {
    return(FALSE);
  }
}                                                   /* end LBS_EMPTY */
/**********************************************************************/



/**********************************************************************/
/* lbs_prepend()           add an element to the front of a list      */
/*   return pointer to new element node                               */

LBS_NODE_PTR lbs_prepend(pL, data)
LBS_PTR pL;
genptr data;
{
  LBS_NODE_PTR newnode;

  if (pL == NULL) return(NULL);

  /* allocate a new node */
  if ((newnode = alloc_lbsnode()) == NULL) {
    return(NULL);
  }

  /* put the data into the node */
  DATA(newnode) = data;

  if (lbs_empty(pL)) {
    FRONT(pL) = newnode;
    BACK(pL) = newnode;
  }
  else {
    NEXTEL(newnode) = FRONT(pL);
    FRONT(pL) = newnode;
  }
  NELS(pL) = NELS(pL) + 1;

  return(newnode);
}                                                      /* end LBS_PREPEND */
/**********************************************************************/



/**********************************************************************/
/* lbs_append()       add an element at the end of a list             */
/*    return pointer to new node                                      */

LBS_NODE_PTR lbs_append(pL, data)
LBS_PTR pL;
genptr data;
{
  LBS_NODE_PTR newnode;

  if (pL == NULL) return(NULL);

  /* allocate a new node */
  if ((newnode = alloc_lbsnode()) == NULL) {
    return(NULL);
  }

  /* put the data into the node */
  DATA(newnode) = data;

  if (lbs_empty(pL)) {
    FRONT(pL) = newnode;
    BACK(pL) = newnode;
  }
  else {
    NEXTEL(BACK(pL)) = newnode;
    BACK(pL) = newnode;
  }
  NELS(pL) = NELS(pL) + 1;

  return(newnode);
}                                                       /* end LBS_APPEND */
/**********************************************************************/



/**********************************************************************/
/* lbs_insert()       inserts a new element after the pos'th element  */
/*     return pointer to the new node                                 */

LBS_NODE_PTR lbs_insert(pL, data, pos)
LBS_PTR pL;                        /* the list */
genptr data;                     /* the data */
int pos;                         /* the position, starting from 1 */
{
  LBS_NODE_PTR nod, previous, next;
  LBS_NODE_PTR newnode;
  int i;
  int loc = pos;

  if (pL == NULL) return(NULL);

  if (pos <= 0) loc = 0;

  /* allocate a new node */
  if ((newnode = alloc_lbsnode()) == NULL) {
    return(NULL);
  }
  /* put the data into the node */
  DATA(newnode) = data;

  if (lbs_empty(pL)) {    /* easy */
    FRONT(pL) = newnode;
    BACK(pL) = newnode;
    NELS(pL) = NELS(pL) + 1;
    return(newnode);
  }

  if (loc == 0) {          /* easy */
    NEXTEL(newnode) = FRONT(pL);
    FRONT(pL) = newnode;
    NELS(pL) = NELS(pL) + 1;
    return(newnode);
  }

  if (loc >= NELS(pL)) {  /* add at end */
    NEXTEL(BACK(pL)) = newnode;
    BACK(pL) = newnode;
    NELS(pL) = NELS(pL) + 1;
    return(newnode);
  }

  nod = FRONT(pL);
  previous = nod;
  for (i = 1; i <= pos; i++) {  /* traverse the list */
    if (NEXTEL(nod) == NULL) {    /* going past end of the list */
      break;
    }
    previous = nod;
    nod = NEXTEL(previous);
  }  
  /* previous is the node to be added after */

  if (previous == BACK(pL)) {    /* at the end */
    NEXTEL(previous) = newnode;
    BACK(pL) = newnode;
  }
  else {                         /* in the middle */
    NEXTEL(newnode) = NEXTEL(previous);
    NEXTEL(previous) = newnode;
  }
  NELS(pL) = NELS(pL) + 1;
  return(newnode);

}                                                       /* end LBS_INSERT */
/**********************************************************************/



/**********************************************************************/
/* lbs_remove()       deletes the pos'th element from a list          */
/*    returns pointer to removed node                                 */

LBS_NODE_PTR lbs_remove(pL, pos)
LBS_PTR pL;                        /* the list */
int pos;                         /* the position, starting from 1 */
{
  LBS_NODE_PTR nod, previous, next;
  int i;

  if (pL == NULL) return(NULL);
  if (lbs_empty(pL)) {  /* nothing to delete */
    return(NULL);
  }

  nod = FRONT(pL);
  previous = nod;
  for (i = 1; i < pos; i++) {  /* traverse the list */
    if (NEXTEL(nod) == NULL) {    /* going past end of the list */
      return(NULL);
    }
    previous = nod;
    nod = NEXTEL(previous);
  }  
  /* nod is the node to be removed */

  if (nod == FRONT(pL)) {    /* deleting first in the list */
    if (nod == BACK(pL)) {    /* deleting the only member */
      FRONT(pL) = NULL;
      BACK(pL) = NULL;
    }
    else {
      FRONT(pL) = NEXTEL(nod);
    }
  }
  else if (nod == BACK(pL)) {  /* deleting last element */
    NEXTEL(previous) = NULL;
    BACK(pL) = previous;
  }
  else {                       /* deleting in the middle */
    NEXTEL(previous) = NEXTEL(nod);
  }
  NELS(pL) = NELS(pL) - 1;
  return(nod);
}                                                       /* end LBS_REMOVE */
/**********************************************************************/



/**********************************************************************/
/* lbs_get_first       get first element                              */
/*     returns pointer to the node                                    */

LBS_NODE_PTR lbs_get_first(pL)
LBS_PTR pL;
{
  if (pL == NULL) return(NULL);
  return(FRONT(pL));
}                                                    /* end LBS_GET_FIRST */
/**********************************************************************/



/**********************************************************************/
/* lbs_get_last       get last element                                */
/*     returns pointer to the node                                    */

LBS_NODE_PTR get_last(pL)
LBS_PTR pL;
{
  if (pL == NULL) return(NULL);
  return(BACK(pL));
}                                                     /* end LBS_GET_LAST */
/**********************************************************************/



/**********************************************************************/
/* lbs_get_nth       get n'th element                                 */
/*     returns pointer to the node                                    */

LBS_NODE_PTR lbs_get_nth(pL, n)
LBS_PTR pL;
int n;
{
  LBS_NODE_PTR nth;
  int i;

  if (pL == NULL) return(NULL);
  if (n <= 0) return(NULL);
  if (n == 1) return(FRONT(pL));
  if (n == NELS(pL)) return(BACK(pL));

  nth = FRONT(pL);
  for (i = 1; i < n; i++) {
    nth = NEXTEL(nth);
    if (nth == NULL) {           /* past the end */
      return(NULL);
    }
  }

  return(nth);
}                                                      /* end LBS_GET_NTH */
/**********************************************************************/



/**********************************************************************/
/* lbs_get_next_el       get next element                             */
/*     returns pointer to the node                                    */

LBS_NODE_PTR lbs_get_next_el(pL, this)
LBS_PTR pL;
LBS_NODE_PTR this;     /* current node, NULL to start off */
{

  if (pL == NULL) return(NULL);
  if (this == NULL) return(FRONT(pL));

  return(NEXTEL(this));
}                                                  /* end LBS_GET_NEXT_EL */
/**********************************************************************/