#include <stdlib.h>#include <stdio.h>#include "List.h"#include "Element.h"/* * --------------------------------------------------------- * listCreate * - Create new list initialized to empty * --------------------------------------------------------- * PRE: * void * --------------------------------------------------------- * POST: * new list is allocated and initialized; returns a * reference to new list * --------------------------------------------------------- * ERRORS: * NULL : memory allocation failure (allocation) * --------------------------------------------------------- */List *listCreate(void){ List *new = NULL; /* new list */ if (!(new = calloc(1,sizeof(List)))) return(NULL); new->element_count = 0; new->position = 0; new->elements = NULL; new->current = NULL; return(new);} /* listCreate *//* * --------------------------------------------------------- * listDelete * - De-allocate all memory associated with provided * list object * --------------------------------------------------------- * PRE: * void * --------------------------------------------------------- * POST: * this list is destroyed; returns number of elements * that were in the list * --------------------------------------------------------- * ERRORS: * void * --------------------------------------------------------- */int listDelete(List *this){ int retval = 0; /* return value */ if (this) { retval = listClear(this); free(this); } return(retval);} /* listDelete *//* * --------------------------------------------------------- * listClear * - De-allocate all memory associated with element * structures of provided list, resetting state of * list to empty * --------------------------------------------------------- * PRE: * void * --------------------------------------------------------- * POST: * this list is empty; returns number of elements that * were in the list * --------------------------------------------------------- * ERRORS: * void * --------------------------------------------------------- */int listClear(List *this){ int i; /* loop index */ int retval; /* return value */ Element *cur; /* current element - traversal */ /* * de-allocate element memory */ if (this->elements) { this->current = this->elements; for (i = 0; i < this->element_count; i++) { cur = this->current; this->current = elementGetRight(this->current); elementDelete(cur); } } /* * save number of elements in list then reset to empty */ retval = this->element_count; this->element_count = 0; this->position = 0; this->elements = NULL; this->current = NULL; return(retval);} /* listClear *//* * --------------------------------------------------------- * listHead * - Adjust position to the beginning of provided list * - NOTE: this operation is non-destructive on an * empty list * --------------------------------------------------------- * PRE: * list is non-empty * --------------------------------------------------------- * POST: * current & position reference the first element in * this list; returns a reference to this * --------------------------------------------------------- * ERRORS: * NULL : list is empty * --------------------------------------------------------- */List *listHead(List *this){ if (this->elements != NULL) { this->current = this->elements; this->position = 1; return(this); } else return(NULL);} /* listHead *//* * --------------------------------------------------------- * listTail * - Adjust position to the end of provided list * - NOTE: this operation is non-destructive on an * empty list * --------------------------------------------------------- * PRE: * list is non-empty * --------------------------------------------------------- * POST: * current & position reference the last element in * this list; returns a reference to this * --------------------------------------------------------- * ERRORS: * NULL : list is empty * --------------------------------------------------------- */List *listTail(List *this){ if (this->elements != NULL) { this->current = elementGetLeft(this->elements); this->position = this->element_count; return(this); } else return(NULL);} /* listTail *//* * --------------------------------------------------------- * listPrev * - Move the the previous element in the provided list * --------------------------------------------------------- * PRE: * list is non-empty; list is not positioned at the * first element * --------------------------------------------------------- * POST: * current & postition now reference the element * preceeding the current one in this list; returns a * reference to this * --------------------------------------------------------- * ERRORS: * NULL : list is empty * NULL : already at beginning of list * --------------------------------------------------------- */List *listPrev(List *this){ /* * note that this explicity covers "at beginning of list", and * implicitly covers "empty list", and "single element list" cases. */ if (this->current == this->elements) return(NULL); this->current = elementGetLeft(this->current); this->position--; return(this);} /* listPrev *//* * --------------------------------------------------------- * listNext * - Move the the next element in the provided list * --------------------------------------------------------- * PRE: * list is non-empty; list is not positioned at the * last element * --------------------------------------------------------- * POST: * current & position now reference the element * succeeding the current one in this list; returns * a reference to this * --------------------------------------------------------- * ERRORS: * NULL : list is empty * NULL : already at end of list * --------------------------------------------------------- */List *listNext(List *this){ /* * must explicitly cover "at end of list" as well as "empty list" * and "single element list" cases */ if ((this->position >= this->element_count) || (!this->elements) || (this->element_count < 2)) return(NULL); this->current = elementGetRight(this->current); this->position++; return(this);} /* listNext *//* * --------------------------------------------------------- * listMoveToNth * - Move to the "Nth" element in the provide dlist * - NOTE: elements are counted from 1 (not 0) * --------------------------------------------------------- * PRE: * 0 < n <= element_count * --------------------------------------------------------- * POST: * current & position now reference the "Nth" element * in this list; returns a reference to this * --------------------------------------------------------- * ERRORS: * NULL : element index out of bounds (index) * --------------------------------------------------------- */List *listMoveToNth(List *this, int n){ int i; /* loop index */ int offset; /* offset to new location from current */ int ofor; /* forward and ... */ int obak; /* ... backward offsets respectively */ /* * this should avoid ANY illegal situation (i.e. an "nth" element * exists) - excepting destructive user interference */ if ((n < 1) || (n > this->element_count)) return(NULL); /* * determine offset & direction of pointer movement from current: * (adds a couple of arithmetic operations over linear search * however may save time if movement is highly localized or a * regular progression through the list (i.e. by 2s)) */ obak = (this->position - n + this->element_count) % this->element_count; ofor = (n - this->position + this->element_count) % this->element_count; offset = (obak < ofor) ? obak : ofor; if (ofor < obak) /* move forward */ for (i = 0; i < offset; i++) this->current = elementGetRight(this->current); else /* move backward */ for (i = 0; i < offset; i++) this->current = elementGetLeft(this->current); this->position = n; return(this);} /* listMoveToNth *//* * --------------------------------------------------------- * listAddAfter * - Insert a new element containing the provided * data reference in list AFTER current element * - NOTE: current reference remains unchanged * --------------------------------------------------------- * PRE: * void * --------------------------------------------------------- * POST: * element containing data reference is inserted into * this list AFTER the current one, or is installed as * the new head of the list if it was emtpy; returns * a reference to this * --------------------------------------------------------- * ERRORS: * NULL : new_element() failure * --------------------------------------------------------- */List *listAddAfter(List *this, void *data){ Element *new; /* new element */ if (!(new = elementCreate(data))) return(NULL); /* * link into list */ if (!this->elements) { this->elements = new; this->current = this->elements; elementSetLeft(this->current,new); elementSetRight(this->current,new); this->position++; } else { elementSetLeft(elementGetRight(this->current),new); elementSetRight(new,elementGetRight(this->current)); elementSetLeft(new,this->current); elementSetRight(this->current,new); } this->element_count++; return(this);} /* listAddAfter *//* * --------------------------------------------------------- * listAddBefore * - Insert a new element containing the provided * data reference in list BEFORE current element * - NOTE: current reference remains unchanged * --------------------------------------------------------- * PRE: * void * --------------------------------------------------------- * POST: * element containing data reference is inserted into * this list BEFORE the current one, or is installed as * the new head of the list if it was emtpy; returns * a reference to this * --------------------------------------------------------- * ERRORS: * NULL : new_element() failure * --------------------------------------------------------- */List *listAddBefore(List *this, void *data){ Element *new; /* new element structure */ if (!(new = elementCreate(data))) return(NULL); /* * link into list */ if (!this->elements) { this->elements = new; this->current = this->elements; elementSetLeft(this->current,new); elementSetRight(this->current,new); } else { elementSetRight(elementGetLeft(this->current),new); elementSetLeft(new,elementGetLeft(this->current)); elementSetRight(new,this->current); elementSetLeft(this->current,new); /* * must adjust head of list if addition is at front of list */ if (this->current == this->elements) this->elements = new; } this->element_count++; this->position++; return(this);} /* listAddBefore *//* * --------------------------------------------------------- * listGetCurrent * - Obtain a reference to data from the current * element data in the provided list * --------------------------------------------------------- * PRE: * list is non-empty * --------------------------------------------------------- * POST: * returns a reference to the data in the current * element in this list * --------------------------------------------------------- * ERRORS: * NULL : list is empty * --------------------------------------------------------- */void *listGetCurrent(List *this){ if (!this->elements) return(NULL); return(elementGetData(this->current)); } /* listGetCurrent *//* * --------------------------------------------------------- * listSetCurrent * - Reassign a data reference within the current * element of the provided list * --------------------------------------------------------- * PRE: * list is non-empty * --------------------------------------------------------- * POST: * returns a reference to the previous (overwritten) * data in the current element of this list * --------------------------------------------------------- * ERRORS: * NULL : list is empty * --------------------------------------------------------- */void *listSetCurrent(List *this, void *data){ void *dval; /* reference to data value */ if (!this->elements) return(NULL); dval = elementGetData(this->current); elementSetData(this->current,data); return(dval); } /* listSetCurrent *//* * --------------------------------------------------------- * listDelCurrent * - Remove current element from the provided list and * obtain a reference to the data in the element * --------------------------------------------------------- * PRE: * list is non-empty * --------------------------------------------------------- * POST: * returns a reference to the data in the current * element in this list which no longer occurs in * the list; new current element is removed's * successor * --------------------------------------------------------- * ERRORS: * NULL : list is empty * --------------------------------------------------------- */void *listDelCurrent(List *this){ Element *el; /* reference to item to be deleted */ void *dval; /* reference to data value */ if (!this->elements) return(0); /* * note element for deletion */ el = this->current; /* * re-link list to remove current node */ elementSetRight(elementGetLeft(this->current), elementGetRight(this->current)); elementSetLeft(elementGetRight(this->current), elementGetLeft(this->current)); this->current = elementGetRight(this->current); /* * SPECIAL CASES: */ /* single element list - deleting only item */ if (this->element_count == 1) { this->elements = this->current = NULL; this->position = 0; } /* end node removed - wrapping current to first */ else if (this->elements == this->current) this->position = 1; /* first node removed - updating head of list */ else if (this->elements == el) this->elements = this->current; this->element_count--; dval = elementGetData(el); elementDelete(el); return(dval);} /* listDelCurrent *//* * --------------------------------------------------------- * listIsEmpty * - Determine if provided list is empty * --------------------------------------------------------- * PRE: * void * --------------------------------------------------------- * POST: * returns 1 if this is empty, 0 otherwise * --------------------------------------------------------- * ERRORS: * void * --------------------------------------------------------- */int listIsEmpty(List *this){ return(this->element_count == 0);} /* listIsEmpty *//* * --------------------------------------------------------- * listLength * - Determine number of elements (length) in * provided list * --------------------------------------------------------- * PRE: * void * --------------------------------------------------------- * POST: * returns value of element_count * --------------------------------------------------------- * ERRORS: * void * --------------------------------------------------------- */int listLength(List *this){ return(this->element_count);} /* listLength *//* * --------------------------------------------------------- * listPosition * - Obtain numeric value of current position in * provided list * --------------------------------------------------------- * PRE: * void * --------------------------------------------------------- * POST: * returns value of position * --------------------------------------------------------- * ERRORS: * void * --------------------------------------------------------- */int listPosition(List *this){ return(this->position);} /* listPosition */