/*===========================================================================
 *
 * DblList.CPP - Dave Humphrey (uesp@m0use.net), 1 December 2000
 *
 * Implements a doubly linked list class.
 *
 *=========================================================================*/

	/* Include Files */
#include "dbllist.h"

 
#undef  __FUNC__
#define __FUNC__ "CDblEntry::CDblEntry()"
/*===========================================================================
 *
 * Class CDblEntry Constructor
 *
 *=========================================================================*/
CDblEntry::CDblEntry (void) {
  pPrev = pNext = NULL;
  Size = 0;
  pBody = NULL;
 }
/*===========================================================================
 *		End of Class CDblEntry Constructor
 *=========================================================================*/


#undef  __FUNC__
#define __FUNC__ "CDblEntry::~CDblEntry()"
/*===========================================================================
 *
 * Class CDblEntry Destructor
 *
 *=========================================================================*/
CDblEntry::~CDblEntry (void) {

	/* Don't want to mess with a NULL pointer */
  ASSERT(this != NULL);	

	/* Delete the main list entry data if present */
  if (pBody) delete pBody;

	/* Rearrange the list */
  if (pPrev) pPrev->SetNext(pNext);
  if (pNext) pNext->SetPrev(pPrev);
 }
/*===========================================================================
 *		End of Class CDblEntry Destructor
 *=========================================================================*/


#undef  __FUNC__
#define __FUNC__ "CDblEntry::CreateBody()"
/*===========================================================================
 *
 * Class CDblEntry Method - void CreateBody (const void* pData, const uint NewSize)
 *
 * Creates the new body for the entry.
 *
 *=========================================================================*/
void CDblEntry::CreateBody (const void* pData, const uint NewSize) {

	/* Only create a new body if required */
  if (NewSize != Size || pBody == NULL) {

		/* Create the new body */
    CreatePointerArray(pBody, byte, NewSize);
   }
  
	/* Copy data to new data entry */
  memmove (pBody, pData, NewSize);
  Size = NewSize;
 }
/*===========================================================================
 *		End of Class Method CDblEntry::CreateBody()
 *=========================================================================*/


#undef  __FUNC__
#define __FUNC__ "CDblList::CDblList()"
/*===========================================================================
 *
 * Class CDblList Constructor
 *
 *=========================================================================*/
CDblList::CDblList (void) {

	/* Add the custom class errors only once */
  static boolean InitErrors = AddClassErrors();

  pCurrent = pHead = pTail = pHold = NULL;
  CompareProc = NULL;
  NumEntries = 0;
 }
/*===========================================================================
 *		End of Class CDblList Constructor
 *=========================================================================*/


#undef  __FUNC__
#define __FUNC__ "CDblList::AddClassErrors()"
/*===========================================================================
 *
 * Class CDblList Method - boolean AddClassErrors (void)
 *
 * Static function which adds the custom class errors to the error handler.
 *
 *=========================================================================*/
boolean CDblList::AddClassErrors (void) {
  ErrorHandler.AddError(ERRDBLLIST_NOCURRENT, "No current pointer in list!", EL_WARNING);
  ErrorHandler.AddError(ERRDBLLIST_NOCOMPAREPROC, "No compare procedure set!", EL_ERROR);
  return (TRUE);
 }
/*===========================================================================
 *		End of Class Method CDblList::AddClassErrors()
 *=========================================================================*/


#undef  __FUNC__
#define __FUNC__ "CDblList::AddHead()"
/*===========================================================================
 *
 * Class CDblList Method - void* AddHead (pData, Size);
 *
 * Adds a new list node to the start of the list.  Returns the list body
 * or NULL on any error.
 *
 *=========================================================================*/
void* CDblList::AddHead (const void* pData, const uint Size) {

	/* Create a new list node */
  pHold = Create(pData, Size);

	/* Create new tail and list if one doesn't presently exist */
  if (pHead == NULL) {
    pTail = pHead = pCurrent = pHold;
   }
  else {	/* Add to the head */
    pHead->SetPrev(pHold);
    pHold->SetNext(pHead);
    pHead = pHold;
   }

  return (pHead->GetBody());
 }
/*===========================================================================
 *		End of Class Method CDblList::AddHead()
 *=========================================================================*/


#undef  __FUNC__
#define __FUNC__ "CDblList::AddSort()"
/*===========================================================================
 *
 * Class CDblList Method - void* AddSort (const void* pData, const uint Size)
 *
 * Adds the data to the list in a sorted manner.  The CompareProc function
 * must be previously defined, otherwise the data will be added to the end
 * of the list.  The new data body is returned on success, or NULL on any
 * error.
 *
 *=========================================================================*/
void* CDblList::AddSort (const void* pData, const uint Size) {
  CDblEntry* pSort;

	/* Default to AddTail() if no compare function defined */
  if (CompareProc == NULL) {
    SET_EXT_ERROR(ERRDBLLIST_NOCOMPAREPROC);
    return AddTail(pData, Size);
   }

  	/* Create a new list node */
  pHold = Create(pData, Size);

	/* Find the position to the add the new data */
  pSort = FindSortNode(pData);

	/* Create new tail and list if one doesn't presently exist */
  if (pTail == NULL) {
    pTail = pHead = pCurrent = pHold;
   }
	/* Add entry to the end of the list */
  else if (pSort == NULL) {
    pTail->SetNext(pHold);
    pHold->SetPrev(pTail);
    pTail = pHold;
   }
	/* Add element somewhere from the head to the end */
  else {

		/* Check if adding entry at the head */
    if (pSort->GetPrev())
      pSort->GetPrev()->SetNext(pHold);
    else
      pHead = pHold;	/* New head of list */

    pHold->SetNext(pSort);
    pHold->SetPrev(pSort->GetPrev());
    pSort->SetPrev(pHold);
   }

  return (pHold->GetBody());
 }
/*===========================================================================
 *		End of Class Method CDblList::AddSort()
 *=========================================================================*/


#undef  __FUNC__
#define __FUNC__ "CDblList::AddTail()"
/*===========================================================================
 *
 * Class CDblList Method - void* AddTail (pData, Size);
 *
 * Adds a new list node to the end of the list.  Returns the list body
 * or NULL on any error.
 *
 *=========================================================================*/
void* CDblList::AddTail (const void* pData, const uint Size) {

	/* Create a new list element */
  pHold = Create(pData, Size);

	/* Create new tail and list if one doesn't presently exist */
  if (pTail == NULL) {
    pTail = pHead = pCurrent = pHold;
   }
  else {	/* Add to the tail */
    pTail->SetNext(pHold);
    pHold->SetPrev(pTail);
    pTail = pHold;
   }

  return (pTail->GetBody());
 }
/*===========================================================================
 *		End of Class Method CDblList::AddTail()
 *=========================================================================*/ 


#undef  __FUNC__
#define __FUNC__ "CDblList::AddCurrent()"
/*===========================================================================
 *
 * Class CDblList Method - void* AddCurrent (pData, Size);
 *
 * Adds a new list node to the current position in the list.  Returns the
 * list body or NULL on any error.
 *
 *=========================================================================*/
void* CDblList::AddCurrent (const void* pData, const uint Size) {
  
	/* Create a new list element */
  pHold = Create(pData, Size);

	/* Add to end of list if current undefined */
  if (pCurrent == NULL) {
    void* pResult = AddTail(pData, Size);
    pCurrent = pTail;
    return (pResult);
   }

	/* Create new tail and list if one doesn't presently exist */
  if (pTail == NULL) {
    pTail = pHead = pCurrent = pHold;
   }
  else {	/* Add somewhere in middle */

    if (pCurrent->GetPrev())
      pCurrent->GetPrev()->SetNext(pHold);
    else
      pHead = pHold;	/* New head of list */

    pHold->SetNext(pCurrent);
    pHold->SetPrev(pCurrent->GetPrev());
    pCurrent->SetPrev(pHold);
   }

  return (pCurrent->GetBody());
 }
/*===========================================================================
 *		End of Class Method CDBlList::AddCurrent()
 *=========================================================================*/


#undef  __FUNC__
#define __FUNC__ "CDblList::AddList()"
/*===========================================================================
 *
 * Class CDblList Method - void AddList (NewList);
 *
 * Adds a new list to the end of the current list.  The source list is 
 * cleared.
 *
 *=========================================================================*/
void CDblList::AddList (CDblList& NewList) {

	/* Does the current list exist or not? */
  if (pTail != NULL) {
    pTail->SetNext(NewList.GetHead());
    pTail = NewList.GetTail();
    NumEntries += NewList.Count();
   }
  else {
    pHead = NewList.GetHead();
    pTail = NewList.GetTail();
    NumEntries = NewList.Count();
   }

	/* Reset the source list contents */
  NewList.ClearList();
 }
/*===========================================================================
 *		End of Class Method CDblList::AddList()
 *=========================================================================*/


#undef  __FUNC__
#define __FUNC__ "CDblList::ClearList()"
/*===========================================================================
 *
 * Class CDblList Method - void ClearList (void)
 *
 * Clears the list without deleting anything.
 *
 *=========================================================================*/
void CDblList::ClearList (void) {
  pHead = pTail = pCurrent = pHold = NULL;
  NumEntries = 0;
 }
/*===========================================================================
 *		End of Class Method CDblList::ClearList()
 *=========================================================================*/


#undef  __FUNC__
#define __FUNC__ "CDblList::Create()"
/*===========================================================================
 *
 * Class CDblList Method - CDblEntry* Create (pData, Size);
 *
 * Protected class method which creates a new linked list node with the
 * given size and data.  Does not rearrange the list.
 *
 *=========================================================================*/
CDblEntry *CDblList::Create (const void *pData, const uint Size) {

	/* Attempt to create new list pointer */
  CreatePointer(pHold, CDblEntry);

	/* Attempt to create data entry in new list pointer */
  pHold->CreateBody(pData, Size);

	/* Add one more entry to the total number */
  NumEntries++;
  return (pHold);
 }
/*===========================================================================
 *		End of Class Method CDblList::Create()
 *=========================================================================*/


#undef  __FUNC__
#define __FUNC__ "CDblList::DeleteEntry()"
/*===========================================================================
 *
 * Class CDblList Method - boolean DeleteEntry (void);
 *
 * Deletes the current list node from the list, if any.  Returns TRUE on
 * success.
 *
 *=========================================================================*/
boolean CDblList::DeleteEntry (void) {

	/* Don't want to delete a NULL pointer now do we? */
  if (pCurrent == NULL) {
    SET_EXT_ERROR(ERRDBLLIST_NOCURRENT);
    return (FALSE);
   }
  
	/* Is the current pointer the tail? Move Tail */
  if (pCurrent == pTail) {
    pTail = pTail->GetPrev();
    if (pTail != NULL) pTail->SetNext(NULL);
   }

	/* Is the current pointer the head? Move Head */
  if (pCurrent == pHead) {
    pHead = pHead->GetNext();
    if (pHead != NULL) pHead->SetPrev(NULL);
   }

	/* Special case for nothing left in the list */
  if (pHead == pTail && pHead == NULL) {
    pHead->SetNext(NULL);
    pTail->SetPrev(NULL);
   }

	/* Delete and reset the current list pointer */
  delete pCurrent;
  pCurrent = NULL;
  NumEntries--;

  return (TRUE);
 }
/*===========================================================================
 *		End of Class Method CDblList::DeleteEntry()
 *=========================================================================*/


#undef  __FUNC__
#define __FUNC__ "CDblList::DeleteList()"
/*===========================================================================
 *
 * Class CDblList Method - boolean DeleteList (void);
 *
 * Deletes all nodes from the list, if any.  
 *
 *=========================================================================*/
void CDblList::DeleteList (void) {

	/* Does list exist at all? */
  if (pHead == NULL) {
    pCurrent = pHead = pTail = pHold = NULL;
    NumEntries = 0;
    return;
   }

	/* Delete each component of the list. Point rearranging is done
	 * automatically by the CDblEntry destructor function */
  while (pHead->GetNext()) {
    delete pHead->GetNext();
   }

	/* Delete the head of list */
  delete pHead;
  pCurrent = pHead = pTail = pHold = NULL;
  NumEntries = 0;
 }
/*===========================================================================
 *		End of Class Method CDblList::DeleteList()
 *=========================================================================*/


#undef  __FUNC__
#define __FUNC__ "CDblList::FindSortNode()"
/*===========================================================================
 *
 * Class CDblList Method - CDblEntry* FindSortNode (const void* pData)
 *
 * Find the node to insert the given data at using the user defined
 * compare function.  Returns the node or NULL if the item should be
 * added to the end of the list.  Protected class method.
 *
 *=========================================================================*/
CDblEntry* CDblList::FindSortNode (const void* pData) {
  CDblEntry* pEntry = pHead; 
  int	     Result;

	/* Ensure valid input */
  ASSERT(pData != NULL);
  ASSERT(CompareProc != NULL);

	/* Look through list for a position to add data */
  while (pEntry != NULL) {
    Result = CompareProc(pEntry->GetBody(), pData);
    if (Result >= 0) return (pEntry);
    pEntry = pEntry->GetNext();
   }

	/* No matching entry found, add to end of list */
  return (NULL); 
 }
/*===========================================================================
 *		End of Class Method CDblList::FindSortNode()
 *=========================================================================*/


#undef  __FUNC__
#define __FUNC__ "CDblList::GotoHead()"
/*===========================================================================
 *
 * Class CDblList Method - void* GotoHead (void);
 *
 * Moves the current pointer to the list head and returns the head body.
 * Returns NULL on any error.
 *
 *=========================================================================*/
void* CDblList::GotoHead (void) {

  if (pHead) {
    pCurrent = pHead;
    return (pCurrent->GetBody());
   }
  else
    return (NULL);

 }
/*===========================================================================
 *		End of Class Method CDblList::GotoHead()
 *=========================================================================*/


#undef  __FUNC__
#define __FUNC__ "CDblList::GotoTail()"
/*===========================================================================
 *
 * Class CDblList Method - void* GotoTail (void);
 *
 * Moves the current pointer to the list tail and returns the head body.
 * Returns NULL on any error.
 *
 *=========================================================================*/
void* CDblList::GotoTail (void) {

  if (pTail) {
    pCurrent = pTail;
    return (pCurrent->GetBody());
   }
  else
    return (NULL);

 }
/*===========================================================================
 *		End of Class Method CDblList::GotoTail()
 *=========================================================================*/


#undef  __FUNC__
#define __FUNC__ "CDblList::MoveEntry()"
/*===========================================================================
 *
 * Class CDblList Method - void MoveEntry (NewList);
 *
 * Moves the current list node in the given list to the end of the current
 * list.  The element is removed from the source list. 
 *
 *=========================================================================*/
void CDblList::MoveEntry (CDblList& NewList) {
  CDblEntry* pSourceNode = NewList.GetCurrentPtr();

	/* Can't do anything with NULL node pointer */
  if (pSourceNode == NULL) { 
    SET_EXT_ERROR(ERRDBLLIST_NOCURRENT);
    return;
   }

	/* Repoint the src list */
  NewList.RemoveCurrent();
  
	/* Does the current list exist or not? */
  if (pTail != NULL) {
    pTail->SetNext(pSourceNode);
    pSourceNode->SetPrev(pTail);
    pSourceNode->SetNext(NULL);
    pTail = pSourceNode;
    NumEntries++;
   }
	/* Create a new list */
  else {
    pHead = pTail = pCurrent = pSourceNode;
    pHead->SetNext(NULL);
    pHead->SetPrev(NULL);
    NumEntries = 1;
   }

 }
/*===========================================================================
 *		End of Class Method CDblList::MoveEntry()
 *=========================================================================*/


#undef  __FUNC__
#define __FUNC__ "CDblList::RemoveCurrent()"
/*===========================================================================
 *
 * Class CDblList Method - void RemoveCurrent (void)
 *
 * Removes the current list pointer from the list without deleting it.
 *
 *=========================================================================*/
void CDblList::RemoveCurrent (void) {

	/* Ignore if no current node */
  if (pCurrent == NULL) {
    SET_EXT_ERROR(ERRDBLLIST_NOCURRENT);
    return;
   }

	/* Special case where current is the head of list */
  if (pCurrent == pHead) pHead = pHead->GetNext();

	/* Special case where current is the tail of list */
  if (pCurrent == pTail) pTail = pTail->GetPrev();

	/* Rearrange the list to remove the current node */
  if (pCurrent->GetNext() != NULL) pCurrent->GetNext()->SetPrev(pCurrent->GetPrev());
  if (pCurrent->GetPrev() != NULL) pCurrent->GetPrev()->SetNext(pCurrent->GetNext());
  NumEntries--;
 }
/*===========================================================================
 *		End of Class Method CDblList::RemoveCurrent()
 *=========================================================================*/


#undef  __FUNC__
#define __FUNC__ "CDblList::Sort()"
/*===========================================================================
 *
 * Class CDblList Method - boolean Sort (void)
 *
 * Uses the current compare proc to sort the linked list.  Returns FALSE
 * on any error.
 *
 *=========================================================================*/
boolean CDblList::Sort (void) {
  CDblList   NewList;
  CDblEntry* pEntry;
  CDblEntry* pSortEntry;

	/* Ensure there's a compare proc to use */
  if (CompareProc == NULL) {
    SET_EXT_ERROR(ERRDBLLIST_NOCOMPAREPROC);
    return (FALSE);
   }

  pCurrent = pHead;
  NewList.SetCompareProc(CompareProc);

  while (pCurrent != NULL) { 
    pSortEntry = NewList.FindSortNode(pCurrent->GetBody());
    pEntry = pCurrent;

		/* Remove the current pointer from list */
    RemoveCurrent();

		/* Add to the end of the new list */
    if (pSortEntry == NULL) {

		/* Create a new list */
      if (NewList.pTail == NULL) {
        NewList.pHead = NewList.pTail = NewList.pCurrent = pCurrent;
	pCurrent->SetNext(NULL);
	pCurrent->SetPrev(NULL);
       }
      else {
        pCurrent->SetNext(NULL);
	pCurrent->SetPrev(NewList.pTail);
	NewList.pTail->SetNext(pCurrent);
	NewList.pTail = pCurrent;
       }
     }
		/* Add the entry to the head of the new list */	
    else if (pSortEntry == NewList.pHead) {
      pSortEntry->SetPrev(pCurrent);
      pCurrent->SetNext(pSortEntry);
      pCurrent->SetPrev(NULL);
      NewList.pHead = pCurrent;
     }
		/* Add the element somewhere in the middle of the new list */
    else {
      pCurrent->SetNext(pSortEntry);
      pCurrent->SetPrev(pSortEntry->GetPrev());
      (pSortEntry->GetPrev())->SetNext(pCurrent);
      pSortEntry->SetPrev(pCurrent);
     }

    pCurrent = pHead;
   }

	/* Copy the new, sorted list, to our list */
  pHead = NewList.pHead;
  pTail = NewList.pTail;
  pCurrent = NULL;

	/* Clear the new list without deleting nodes */
  NewList.ClearList();
  return (TRUE);
 }
/*===========================================================================
 *		End of Class Method CDblList::Sort()
 *=========================================================================*/