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