list.c

list is a data dtructure. this is a data structure type implemantation and it is implemented in C pr

#include <setjmp.h>
#include <stdarg.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

#include "General.h"
#include "ds/ListExtended.h"
#include "ds/ListIterator.h"

#define IT_OPERATION_NOOP 0
#define IT_OPERATION_ADD 1
#define IT_OPERATION_NEXT 2
#define IT_OPERATION_PREVIOUS 3
#define IT_OPERATION_REMOVE 4
#define IT_OPERATION_SET 5

struct LIST {
  COMPARISON_FUNC compare_component;
  COPY_FUNC copy_component;
  DESTRUCTION_FUNC destroy_component;
  unsigned int size;
  struct _LIST* head;
};

struct _LIST {
  Object info;
  struct _LIST* next;
  struct _LIST* prev;
};

typedef struct _LIST* _List;

struct LISTITERATOR {
  List underlying_list;
  _List ptr;
  int index;
  int last_op;
};

List List_Create(int type, ...) {

  int i, array_len;
  jmp_buf nxt_c;
  va_list ap;

  List_Component_Funcs funcs;
  ListIterator iterator;
  List existing_list;
  Object* from_array;

  List ret_list = (List) malloc(sizeof(struct LIST));
  if (!ret_list) {
    fprintf(stderr, "Out of memory...\n");
    return(NULL);
  } /* end of if(!ret_list) */

  ret_list->size = 0; ret_list->head = NULL;
  va_start(ap, type);
  switch(type) {
    case COPY:
      existing_list = va_arg(ap, List);
      ret_list->compare_component = existing_list->compare_component;
      ret_list->copy_component = existing_list->copy_component;
      ret_list->destroy_component = existing_list->destroy_component;
      iterator = List_ListIterator(existing_list, ITERATOR_FORWARD);
      for(; ListIterator_HasNext(iterator); )
        List_InsertAtEnd(ret_list, existing_list->copy_component(ListIterator_Next(iterator, nxt_c)));
      free(iterator);
      break;
    case DEFAULT:
      funcs = va_arg(ap, List_Component_Funcs);
      ret_list->compare_component = funcs.compare_component;
      ret_list->copy_component = funcs.copy_component;
      ret_list->destroy_component = funcs.destroy_component;
      break;
    case FROM_ARRAY:
      funcs = va_arg(ap, List_Component_Funcs);
      from_array = va_arg(ap, Object*);
      array_len = va_arg(ap, int);
      ret_list->compare_component = funcs.compare_component;
      ret_list->copy_component = funcs.copy_component;
      ret_list->destroy_component = funcs.destroy_component;
      for (i = 0; i < array_len; i++)
        List_InsertAtEnd(ret_list, ret_list->copy_component(from_array[i]));
      break;
  } /* end of switch(type) */
  va_end(ap);

  return ret_list;

} /* end of List List_Create(int, ...) */

void List_Destroy(List* this) {

  int size, i;
  jmp_buf rmv_f_c;

  if (*this == NULL) return;

  size = (*this)->size; i = 1;

  for (; i <= size; i++)
    (*this)->destroy_component(List_RemoveFromFront(*this, rmv_f_c));
  free(*this);
  *this = NULL;


  return;

} /* end of void List_Destroy(List*) */

Object List_GetFirst(const List this, jmp_buf gfc) /* throws List_Empty */ {

  if (List_IsEmpty(this)) longjmp(gfc, EXC_LIST_EMPTY);

  return this->head->info;

} /* end of Object List_GetFirst(const List, jmp_buf) */

Object List_GetLast(const List this, jmp_buf glc) /* throws List_Empty */ {

  if (List_IsEmpty(this)) longjmp(glc, EXC_LIST_EMPTY);

  return this->head->prev->info;

} /* end of Object List_GetLast(const List, jmp_buf) */

static _List create_sublist(Object info) {

  _List this = (_List) malloc(sizeof(struct _LIST));
  if (!this) return NULL;

  this->info = info;
  this->prev = this->next = this;
  
  return this;

} /* end of _List create_sublist(Object) */

void List_InsertAtEnd(const List this, Object new_item) {

  _List new_sublist = create_sublist(new_item);

  this->size++;
  if (List_IsEmpty(this)) this->head = new_sublist;
    else {
      _List tail = this->head->prev;      
      new_sublist->prev = tail;
      tail->next = new_sublist;
      new_sublist->next = this->head;
      this->head->prev = new_sublist;
    } /* end of else */

  return;

} /* end of void List_InsertAtEnd(const List, Object) */

void List_InsertInFront(const List this, Object new_item) {

  _List new_sublist = create_sublist(new_item);

  this->size++; 
  if (List_IsEmpty(this)) this->head = new_sublist;
      else {
        _List head = this->head;
        _List tail = this->head->prev;
        this->head = new_sublist;
        new_sublist->next = head;
        new_sublist->prev = tail;
        tail->next = new_sublist;
        head->prev = new_sublist;
      } /* end of else */

  return;

} /* end of void List_InsertInFront(const List, Object) */

Object List_RemoveFromEnd(const List this, jmp_buf rec) /* throws ListEmpty */ {

    _List tail;
    Object retVal;

    if (List_IsEmpty(this)) longjmp(rec, EXC_LIST_EMPTY);

    this->size--;
    tail = this->head->prev;
    retVal = tail->info;
    if (this->size != 0) {
      _List new_tail = tail->prev;
      new_tail->next = this->head;
      this->head->prev = new_tail;
    } else this->head = NULL;

    tail->next = tail->prev = NULL;
    tail->info = NULL;
    free(tail); 

    return retVal;

} /* end of Object List_RemoveFromEnd(const List, jmp_buf) */

Object List_RemoveFromFront(const List this, jmp_buf rfc) /* throws ListEmpty */ {

    _List head;
    Object retVal;

    if (List_IsEmpty(this)) longjmp(rfc, EXC_LIST_EMPTY);

    this->size--;
    head = this->head;
    retVal = head->info;
    if (this->size != 0)  {
      head->prev->next = head->next;
      head->next->prev = head->prev;
      this->head = head->next;
    } else this->head = NULL;

    head->next = head->prev = NULL;
    head->info = NULL;
    free(head); 

    return retVal;

} /* end of Object List_RemoveFromFront(const List) */

BOOL List_IsEmpty(const List this) {

  if (this->head == NULL) return TRUE;
    else return FALSE;

} /* end of BOOL List_IsEmpty(const List) */

int List_Size(const List this) {

  return this->size;

} /* end of int List_Size(const List) */

Object* List_ToArray(const List this, jmp_buf tac) /* throws ListEmpty */ {

  int size = this->size, i;

  jmp_buf nxt_c;
  ListIterator iterator;
  Object* ret_array;

  if (size == 0) longjmp(tac, EXC_LIST_EMPTY);
  
  ret_array = malloc(sizeof(Object) * size);

  i = 0; iterator = List_ListIterator(this, ITERATOR_FORWARD);
  for (; ListIterator_HasNext(iterator); i++)
    ret_array[i] = ListIterator_Next(iterator, nxt_c);

  free(iterator);

  return ret_array;

} /* end of Object[] List_ToArray(const List) */

List List_Merge(const List this, const List second_list) {

  List_Component_Funcs funcs = { this->compare_component, this->copy_component, this->destroy_component };
  List ret_list = List_Create(DEFAULT, funcs);
  List l1 = this;
  List l2 = second_list;
  jmp_buf nxt_c;
  ListIterator iterator;

  iterator = List_ListIterator(l1, ITERATOR_FORWARD);
  for(; ListIterator_HasNext(iterator);)
    List_InsertAtEnd(ret_list, ret_list->copy_component(ListIterator_Next(iterator, nxt_c)));
  free(iterator);
  
  iterator = List_ListIterator(l2, ITERATOR_FORWARD);
  for(; ListIterator_HasNext(iterator);)
    List_InsertAtEnd(ret_list, ret_list->copy_component(ListIterator_Next(iterator, nxt_c)));
  free(iterator);
  
  return ret_list;

} /* end of List List_Merge(const List, const List) */

ListIterator List_ListIterator(const List this, Iterator_type it_type) {

  ListIterator ret_iterator = (ListIterator) malloc(sizeof(struct LISTITERATOR));
  if (!ret_iterator) {
    fprintf(stderr, "Out of memory...\n");
    return(NULL);
  }

  ret_iterator->underlying_list = this;
  ret_iterator->ptr = this->head; 
  ret_iterator->last_op = IT_OPERATION_NOOP;
  if (it_type == ITERATOR_FORWARD) ret_iterator->index = 0;
    else ret_iterator->index = this->size;
  
  return ret_iterator;

} /* end of ListIterator List_ListIterator(const List, Iterator_type) */

void List_InsertAfterFirst(const List this, Object new_item, Object after, jmp_buf iafc) /* throws NoSuchItem */ {

  jmp_buf ins_a_Nth;

  if (setjmp(ins_a_Nth) != 0) longjmp(iafc, EXC_LIST_NOSUCHITEM);
  List_InsertAfterNth(this, new_item, after, 1, ins_a_Nth);

  return;

} /* end of void List_InsertAfterFirst(const List, Object, Object, jmp_buf) */

void List_InsertAfterLast(const List this, Object new_item, Object after, jmp_buf ialc) /* throws NoSuchItem */ {

  ListIterator iterator = List_ListIterator(this, ITERATOR_BACKWARD);
  jmp_buf li_a, li_n, li_p;

  for(; ListIterator_HasPrevious(iterator); ) 
    if (this->compare_component(after, ListIterator_Previous(iterator, li_p)) == 0) {
      ListIterator_Next(iterator, li_n);
      ListIterator_Add(iterator, new_item, li_a);
      free(iterator);
      return;
    }

  free(iterator);
  longjmp(ialc, EXC_LIST_NOSUCHITEM);

} /* end of void List_InsertAfterLast(const List, Object, Object, jmp_buf) */

void List_InsertAfterNth(const List this, Object new_item, Object after, int n, jmp_buf iaNc) /* throws NoSuchItem */ {

  int index = 0;
  ListIterator iterator = List_ListIterator(this, ITERATOR_FORWARD);

  jmp_buf li_a, li_n;

  for(; index < n && ListIterator_HasNext(iterator); )
    if (this->compare_component(after, ListIterator_Next(iterator, li_n)) == 0) index++;

  if (index < n) { free(iterator); longjmp(iaNc, EXC_LIST_NOSUCHITEM); }

  ListIterator_Add(iterator, new_item, li_a);
  free(iterator);

  return;

} /* end of void List_InsertAfterNth(const List this, Object, Object, int, jmp_buf) */

void List_InsertBeforeFirst(const List this, Object new_item, Object before, jmp_buf ibfc) /* throws NoSuchItem */ {