#include <stdlib.h>
#include <string.h>
#include "llist.h"

typedef struct _record {
  char *name;			/*key*/
  struct _record *prev, *next;	/*forward and backward links*/
  } record;

/*pointers to dummy head and tail elements initialised by init()*/
static record *tailptr, *headptr;

/*constructor*/
static record *new(name, prev, next)
char *name;
record *prev, *next;
  {
  record *new_record;
  new_record = (record *)malloc(sizeof(*new_record));
  if(new_record == (record *)0)
    perror("new");
  else
    {
    new_record->name = name;
    new_record->prev = prev;
    new_record->next = next;
    }
  return(new_record);
  }

/*destructor*/
static void delete(old_record)
record *old_record;
  {
  old_record->prev->next = old_record->next;
  old_record->next->prev = old_record->prev;
  free(old_record);
  }

/*create an empty list, with dummy head and tail elements that point back to
  themselves*/
void init()
  {
  headptr = new((char *)0, (record *)0, (record *)0);
  tailptr = new((char *)0, headptr, (record *)0);
  headptr->prev = headptr;
  headptr->next = tailptr;
  tailptr->next = tailptr;
  }

/*return the address of the element that contains the given name, or null if
  the name doesn't occur in the list*/
static record *find(target)
char *target;
  {
  register record *p;
  for(p = headptr->next; (p->name != (char *)0) && (strcmp(p->name, target) != 0); p = p->next)
    ;
  return((p->name==(char *)0)? (record *)0: p);
  }

/*return a count of the number of occurrences of the target string in the list*/
int occur(target)
char *target;
  {
  register record *p;
  register int num_occurrences;
  for(p = headptr->next, num_occurrences = 0; (p->name != (char *)0); p = p->next)
    if(strcmp(p->name, target) == 0)
      num_occurrences++;
  return num_occurrences;
  }

/*insert an element immediately following the given element*/
static void add_following(element, prev)
char *element;
record *prev;
  {
  record *new_node;
  new_node = new(element, prev, prev->next);
  prev->next->prev = new_node;
  prev->next = new_node;
  }

/*insert an element immediately preceding the given element*/
static void add_preceding(element, next)
char *element;
record *next;
  {
  record *new_node;
  new_node = new(element, next->prev, next);
  next->prev->next = new_node;
  next->prev = new_node;
  }

void insert_at_head(element)
char *element;
  {
  add_following(element, headptr);
  }

void insert_at_tail(element)
char *element;
  {
  add_preceding(element, tailptr);
  }

/*Use the given insertion function to place the given string into the list
  either preceding or following the leftmost occurrence of the target
  element.  If the target element doesn't occur at all, leave the list
  unchanged and return 1.  Otherwise, return 0.*/
static int insert(target, element, insert_fn)
char *target, *element;
int (*insert_fn)(char *, record *);
  {
  record *target_node;
  target_node = find(target);
  if(target_node == (record *)0)
    return 1;
  (*insert_fn)(element, target_node);
  return 0;
  }

/*insert the given string into the list immediately following the leftmost
  occurrence of the target element.  If the target element doesn't occur at
  all, leave the list unchanged and return 1.  Otherwise, return 0.*/
int insertr(target, element)
char *target, *element;
  {
  return(insert(target, element, add_following));
  }

/*Insert the given string into the list immediately preceding the leftmost
  occurrence of the target element.  If the target element doesn't occur at
  all, leave the list unchanged and return 1.  Otherwise, return 0.*/
int insertl(target, element)
char *target, *element;
  {
  return(insert(target, element, add_preceding));
  }

/*Delete the leftmost occurrence of the target element.  If the target element
  doesn't occur at all, leave the list unchanged and return 1.  Otherwise,
  return 0.*/
int remove(target)
char *target;
  {
  record *target_node;
  target_node = find(target);
  if(target_node == (record *)0)
    return 1;
  delete(target_node);
  return 0;
  }

void traverse()
  {
  register record *node;
  for(node = headptr->next; node != tailptr; node = node->next)
    printf("%s\n", node->name);
  }