/**
 * @file linkedList.c
 * @ingroup collection
 *
 * Linked List module
 *
 * @author Geoff Davis <geoff@circlemudsquared.org>
 *
 * @par Copyright:
 *   Copyright (C) 2006 Geoff Davis <geoff@circlemudsquared.org><br>
 *            Greg Buxton <greg@circlemudsquared.org>
 *
 * @par
 *   Copyright (C) 1993, 94 by the Trustees of the Johns Hopkins University<br>
 *   CircleMUD is based on DikuMUD, Copyright (C) 1990, 1991.
 *
 * @par
 *   All rights reserved.  See license.doc for complete information.
 *
 * @package cs
 * @version 1.0
 */

#define __LINKEDLIST_C__

#include "base.h"
#include "linkedList.h"
#include "log.h"
#include "memory.h"

/*
 * linked list functions
 */

/**
 * Removes all elements from a linked list.
 * @param list the linked list to be cleared
 * @return none
 */
void linkedList_clear(linkedList_t *list)
{
  if (list == NULL) {
    log("linkedList_clear(): invalid 'list' linkedList_t.");
  } else {
    while (list->size) {
      /* Save off the first list entry. */
      linkedListEntry_t *entry = list->firstEntry;

      /* Unlink the linked list entry. */
      linkedListPrivate_removeEntry(list, entry, TRUE);
    }
  }
}

/**
 * Returns whether a linked list contains a particular element.
 * @param list the linked list to be tested
 * @param element the element for which to test
 * @return TRUE if the linked list contains a matching element;
 *     FALSE otherwise
 */
bool linkedList_contains(linkedList_t *list, void *element)
{
  if (list == NULL) {
    log("linkedList_contains(): invalid 'list' linkedList_t.");
  } else {
    /* Declare an iterator variable. */
    register linkedListEntry_t *entry = NULL;

    /* Search the linked list for the desired element. */
    for (entry = list->firstEntry; entry; entry = entry->nextEntry) {
      if (entry->element == element) {
        return (TRUE);
      }
    }
  }
  return (FALSE);
}

/**
 * Constructs a new linked list.
 * @param freeFunction the function to be called to free elements
 * @return a new linked list, or NULL
 */
linkedList_t *linkedList_create(freeFunction_t freeFunction)
{
  /* Allocate a new linkedList_t. */
  linkedList_t *list = CIRCLE_ALLOCN(linkedList_t, 1);

  if (list == NULL) {
    log("linkedList_create(): CIRCLE_ALLOCN() failed.");
  } else {
    /* Initialize the new linkedList_t. */
    list->firstEntry = NULL;
    list->freeFunction = freeFunction;
    list->lastEntry = NULL;
    list->size = (size_t) 0UL;   
  }
  return (list);
}

/**
 * Frees a linked list.
 * @param list the linked list to be freed
 * @return none
 */
void linkedList_free(linkedList_t *list)
{
  if (list == NULL) {
    log("linkedList_free(): invalid 'list' linkedList_t.");
  } else {
    /* Clear the linked list. */
    linkedList_clear(list);

    /* Free the linked list structure. */
    free(list);
  }
}

/**
 * Returns the size of a linked list.
 * @param list the linked list to be tested
 * @return the size of the linked list, or zero (0)
 */
size_t linkedList_getSize(linkedList_t *list)
{
  size_t retval = (size_t) 0UL;

  if (list == NULL) {
    log("linkedList_getSize(): invalid 'list' linkedList_t.");
  } else {
    retval = list->size;
  }
  return (retval);
}

/**
 * Returns whether a linked list is empty.
 * @param list the linked list to be tested
 * @return TRUE if the linked list is empty; FALSE otherwise
 */
bool linkedList_isEmpty(linkedList_t *list)
{
  return (list == NULL || list->size == (size_t) 0UL);
}

/**
 * Returns the last element in a linked list.
 * @param list the linked list whose last element is to be retreived
 * @param defaultValue the value to be returned if the linked list is empty
 * @return the last element, or NULL
 */
void *linkedList_peekBack(linkedList_t *list, void *defaultValue)
{
  void *retval = defaultValue;

  if (list == NULL) {
    log("linkedList_peekBack(): invalid 'list' linkedList_t.");
  } else {
    if (list->size && list->lastEntry) {
      retval = list->lastEntry->element;
    }
  }
  return (retval);
}

/**
 * Returns the first element in a linked list.
 * @param list the linked list whose first element is to be retreived
 * @param defaultValue the value to be returned if the linked list is empty
 * @return the first element, or NULL
 */
void *linkedList_peekFront(linkedList_t *list, void *defaultValue)
{
  void *retval = defaultValue;

  if (list == NULL) {
    log("linkedList_peekFront(): invalid 'list' linkedList_t.");
  } else {
    if (list->size && list->firstEntry) {
      retval = list->firstEntry->element;
    }
  }
  return (retval);
}

/**  
 * Removes and returns the last element in a linked list.
 * @param list the linked list whose last element is to be popped   
 * @param defaultValue the value to be returned if the linked list is empty
 * @return the last element, or NULL   
 */ 
void *linkedList_popBack(linkedList_t *list, void *defaultValue)
{
  void *retval = defaultValue;

  if (list == NULL) {
    log("linkedList_popBack(): invalid 'list' linkedList_t.");
  } else {
    if (list->size && list->lastEntry) {
      /* Save off the last list entry. */
      linkedListEntry_t *entry = list->lastEntry;

      /* Save off the last element. */
      retval = entry->element;

      /* Unlink the linked list entry. */
      linkedListPrivate_removeEntry(list, entry, FALSE);
    }
  }
  return (retval);
}

/**  
 * Removes and returns the first element in a linked list.
 * @param list the linked list whose first element is to be popped   
 * @param defaultValue the value to be returned if the linked list is empty
 * @return the first element, or NULL   
 */ 
void *linkedList_popFront(linkedList_t *list, void *defaultValue)
{
  void *retval = defaultValue;

  if (list == NULL) {
    log("linkedList_popFront(): invalid 'list' linkedList_t.");
  } else {
    if (list->size && list->firstEntry) {
      /* Save off the first list entry. */
      linkedListEntry_t *entry = list->firstEntry;

      /* Save off the first element. */
      retval = entry->element;

      /* Unlink the linked list entry. */
      linkedListPrivate_removeEntry(list, entry, FALSE);
    }
  }
  return (retval);
}

/**
 * Adds an element at the end of a linked list.
 * @param list the linked list into which an element is to be inserted
 * @param element the element to be inserted
 * @return TRUE if the size of the linked list was changed by this function;
 *     FALSE otherwise
 */
bool linkedList_pushBack(linkedList_t *list, void *element)
{
  bool retval = FALSE;

  if (list == NULL) {
    log("linkedList_pushBack(): invalid 'list' linkedList_t.");
  } else {
    /* Allocate a new linkedListEntry_t. */
    linkedListEntry_t *entry = CIRCLE_ALLOCN(linkedListEntry_t, 1);

    if (entry == NULL) {
      log("linkedList_pushBack(): CIRCLE_ALLOCN() failed.");
    } else {
      /* At this point, we know the operation will succeed. */
      retval = TRUE;

      /* Initialize the new entry. */
      entry->element = element;
      entry->nextEntry = NULL;
      entry->previousEntry = list->lastEntry;

      /*
       * Link the new entry into the linked list.
       */
      if (list->lastEntry) {
        list->lastEntry->nextEntry = entry;
      }
      if (list->firstEntry == NULL) {
        list->firstEntry = entry;
      }
      list->lastEntry = entry;

      /* Increment the size of the linked list by one (1). */
      list->size++;
    }
  }
  return (retval);
}

/**
 * Adds an element at the beginning of a linked list.
 * @param list the linked list into which an element is to be inserted
 * @param element the element to be inserted
 * @return TRUE if the size of the linked list was changed by this function;
 *     FALSE otherwise
 */
bool linkedList_pushFront(linkedList_t *list, void *element)
{
  bool retval = FALSE;

  if (list == NULL) {
    log("linkedList_pushFront(): invalid 'list' linkedList_t.");
  } else {
    /* Allocate a new linkedListEntry_t. */
    linkedListEntry_t *entry = CIRCLE_ALLOCN(linkedListEntry_t, 1);

    if (entry == NULL) {
      log("linkedList_pushFront(): CIRCLE_ALLOCN() failed.");
    } else {
      /* At this point, we know the operation will succeed. */
      retval = TRUE;

      /* Initialize the new entry. */
      entry->element = element;
      entry->nextEntry = list->firstEntry;
      entry->previousEntry = NULL;

      /*
       * Link the new entry into the linked list.
       */
      if (list->firstEntry) {
        list->firstEntry->previousEntry = entry;
      }
      if (list->lastEntry == NULL) {
        list->lastEntry = entry;
      }
      list->firstEntry = entry;

      /* Increment the size of the linked list by one (1). */
      list->size++;
    }
  }
  return (retval);
}

/**
 * Removes an element from a linked list.
 * @param list the linked list from which to remove an element
 * @param element the element to be removed
 * @return TRUE if the size of the linked list was changed by this function;
 *     FALSE otherwise
 */
bool linkedList_remove(linkedList_t *list, void *element)
{
  bool retval = FALSE;

  if (list == NULL) {
    log("linkedList_remove(): invalid 'list' linkedList_t.");
  } else {
    /* Declare an iterator variable. */
    register linkedListEntry_t *entry = NULL;

    /* Search for the element in the linked list. */
    for (entry = list->firstEntry; entry && entry->element != element;
       entry = entry->nextEntry);

    if (entry) {
      /* If we made it this far, we've succeeded. */
      retval = TRUE;

      /* Unlink the entry from the linked list. */
      linkedListPrivate_removeEntry(list, entry, TRUE);
    }
  }
  return (retval);
}

/*
 * list iterator functions
 */

/**
 * @ingroup collection
 * @example linkedListIterator_example.c
 */

/**
 * Constructs a new linked list iterator.
 * @param list the linked list to be iterated
 * @return a new linked list iterator, or NULL
 */
linkedListIterator_t *linkedListIterator_create(linkedList_t *list)
{
  linkedListIterator_t *iter = NULL;

  if (list == NULL) {
    log("linkedListIterator_create(): invalid 'list' linkedList_t.");
  } else {
    /* Allocate a new linked list iterator. */
    iter = CIRCLE_ALLOCN(linkedListIterator_t, 1);

    if (iter == NULL) {
      log("linkedListIterator_create(): CIRCLE_ALLOCN() failed.");
    } else {
      /* Initialize the new linked list iterator. */
      iter->currentEntry = list->firstEntry;
      iter->lastReturned = NULL;
      iter->list = list;
    }
  }
  return (iter);
}

/**
 * Frees a linked list iterator.
 * @param iter the linked list iterator to be freed
 * @return none
 */
void linkedListIterator_free(linkedListIterator_t *iter)
{
  if (iter == NULL) {
    log("linkedListIterator_free(): invalid 'iter' linkedListIterator_t.");
  } else {
    free(iter);
  }
}

/**
 * Returns whether a linked list iterator has more elements.
 * @param iter the linked list iterator to be tested
 * @return TRUE if there are more elements to be iterated;
 *     FALSE otherwise
 */
bool linkedListIterator_hasNext(linkedListIterator_t *iter)
{
  bool retval = FALSE;

  if (iter == NULL) {
    log("linkedListIterator_hasNext(): invalid 'iter' linkedListIterator_t.");
  } else {
    if (iter->currentEntry) {
      retval = TRUE;
    }
  }
  return (retval);
}

/**
 * Returns the current element and advances the linked list iterator.
 * @param iter the linked list iterator
 * @return the current element, or NULL
 */
void *linkedListIterator_next(linkedListIterator_t *iter)
{
  void *element = NULL;

  if (iter == NULL) {
    log("linkedListIterator_next(): invalid 'iter' linkedListIterator_t.");
  } else if (iter->currentEntry) {
    /* Save off the current element. */
    element = iter->currentEntry->element;

    /* Save off the last entry. */
    iter->lastReturned = iter->currentEntry;

    /* Advance the linked list iterator to the next entry. */
    iter->currentEntry = iter->currentEntry->nextEntry;
  }
  return (element);
}

/**
 * Removes the last element returned by a linked list iterator.
 * @param iter the linked list iterator from which to remove an element
 * @return none
 */
void linkedListIterator_remove(linkedListIterator_t *iter)
{
  if (iter == NULL) {
    log("linkedListIterator_remove(): invalid 'iter' linkedListIterator_t.");
  } else if (iter->lastReturned == NULL) {
    log("linkedListIterator_remove(): iterator has no last entry.");
  } else {
    /* Save off the last returned entry's next entry. */
    linkedListEntry_t *lastNext = iter->lastReturned->nextEntry;

    /* Unlink the last returned entry. */
    linkedListPrivate_removeEntry(iter->list, iter->lastReturned, TRUE);

    /* And now, a quick fix up. */
    if (iter->currentEntry == iter->lastReturned) {
      iter->currentEntry = lastNext;
    }

    /* Reset the iterator's last entry. */
    iter->lastReturned = NULL;
  }
}

/**
 * Removes a linked list entry from a linked list and updates the linked list size.
 * @param list the linked list whose entry is to be unlinked
 * @param entry the entry to be removed
 * @param freeIt if the linked list entry element is to be freed
 * @return none
 */                    
void linkedListPrivate_removeEntry(linkedList_t *list,
  linkedListEntry_t *entry, bool freeIt) {
  if (list == NULL) {
    log("linkedListPrivate_removeEntry(): invalid 'list' linkedList_t.");
  } else if (entry == NULL) {
    log("linkedListPrivate_removeEntry(): invalid 'entry' linkedListEntry_t.");
  } else {
    /* Relink the previous entry. */
    if (entry->previousEntry) {
      entry->previousEntry->nextEntry = entry->nextEntry;
    } else {
      list->firstEntry = entry->nextEntry;
    }

    /* Relink the next entry. */
    if (entry->nextEntry) {
      entry->nextEntry->previousEntry = entry->previousEntry;
    } else {
      list->lastEntry = entry->previousEntry;
    }

    /* Free the linked list entry element. */
    if (freeIt && list->freeFunction) {
      list->freeFunction(entry->element);
    }

    /* Free the linked list entry. */
    free(entry);

    /* Decrement the linked list size by one (1). */
    list->size--;
  }
}