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

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.