///////////////////////////////////////////////////////////////////////////////
/// @file deDynamicList.cpp
///
/// @brief Dynamic Linked List
///
/// @author Hootie
///
/// This file is the intellectual property of Novus Delta, LLC.. Usage of the
/// contents of this file is subject to the Destiny3D Member License which
/// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
///
/// This file is distributed "AS IS" without warranty of any kind.  Novus
/// Delta, LLC. does not guarantee the fitness of the contents of this file
/// for any particular purpose.
///
/// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
///
/// <hr>
///                                 Change History
/// <hr>
///
/// @date Oct 2001
/// @author Hootie
/// @remarks Rearchitecture II
///
///////////////////////////////////////////////////////////////////////////////


//=================================================================================
// Includes
//=================================================================================

#include "deShared.hpp"
#include <memory.h> // memcpy, etc



//=================================================================================
// deDynamicList::deDynamicList()
//
// Constructor 
//=================================================================================
deDynamicList::deDynamicList(const unsigned int Size,
                             const unsigned int Count,
                             const unsigned int Growth,
                             const deDynamicListClearType ClearType)
{
   CreationResult = deFALSE;
   List = NULL;
   FirstElement = NULL;
   LastElement = NULL;
   CurrentElement = NULL;
   ElementSize = 0;
   ListEntrySize = 0;
   GrowthRate = 0;
   ListSize = 0;
   CurrentElementCount = 0;
   ElementOffset = 0;
   PrevOffset = 0;
   NextOffset = 0;
   unsigned int looper = 0;
   char UnusedSlot = 'N';


   if (Size == 0 || Count == 0 || Growth == 0)
   {
      //error - Invalid parms
      return;
   }

   if (ClearType != DEDYNAMICLIST_NOCLEAR && ClearType != DEDYNAMICLIST_CLEAR)
   {
      //error - Invalid ClearType
      return;
   }

   ListEntrySize = sizeof(char) + Size + (sizeof(long *) * 2);

   List = calloc(Count, ListEntrySize);

   if (!List)
   {
      //error - List allocation failed
      return;
   }

   for(looper = 0; looper < Count; looper++)
   {
      memcpy((void *)((long)List + (ListEntrySize * looper)), &UnusedSlot, 1);
   }

   ElementSize = Size;
   GrowthRate = Growth;
   ListSize = Count;
   ElementOffset = sizeof(char);
   PrevOffset = ElementOffset + ElementSize;
   NextOffset = PrevOffset + sizeof(long *);

   CreationResult = deTRUE;

   return;
}



//=================================================================================
// deDynamicList::deDynamicList()
//
// Copy Constructor 
//=================================================================================
deDynamicList::deDynamicList(deDynamicList &deDynamicListSource)
{
   char UsedSlot = 'Y';
   int Offset = 0;
   void *NullPointer = NULL;
   long NewPointerValue = 0;
   unsigned int looper = 0;


   CreationResult = deFALSE;
   List = NULL;
   FirstElement = NULL;
   LastElement = NULL;
   CurrentElement = NULL;
   ElementSize = 0;
   ListEntrySize = 0;
   GrowthRate = 0;
   ListSize = 0;
   CurrentElementCount = 0;
   ElementOffset = 0;
   PrevOffset = 0;
   NextOffset = 0;


   List = malloc(deDynamicListSource.ListEntrySize * deDynamicListSource.ListSize);

   if (!List)
   {
      //error - List allocation failed
      return;
   }

   memcpy(List, deDynamicListSource.List, deDynamicListSource.ListEntrySize * deDynamicListSource.ListSize);

   Offset = (long)List - (long)deDynamicListSource.List;

   FirstElement = (void *)((long)deDynamicListSource.FirstElement + Offset);
   LastElement = (void *)((long)deDynamicListSource.LastElement + Offset);
   CurrentElement = (void *)((long)deDynamicListSource.CurrentElement + Offset);
   ElementSize = deDynamicListSource.ElementSize;
   ListEntrySize = deDynamicListSource.ListEntrySize;
   GrowthRate = deDynamicListSource.GrowthRate;
   ListSize = deDynamicListSource.ListSize;
   CurrentElementCount = deDynamicListSource.CurrentElementCount;
   ListClearType = deDynamicListSource.ListClearType;
   ElementOffset = deDynamicListSource.ElementOffset;
   PrevOffset = deDynamicListSource.PrevOffset;
   NextOffset = deDynamicListSource.NextOffset;

   for (looper = 0; looper < ListSize; looper++)
   {
      if (memcmp((void *)((long)List + (ListEntrySize * looper)), &UsedSlot, 1) == 0)
      {
         if (memcmp((void *)((long)List + (ListEntrySize * looper) + PrevOffset), &NullPointer, sizeof(long *)) != 0)
         {
            NewPointerValue = *((long *)((long)List + (ListEntrySize * looper) + PrevOffset)) + Offset;
            memcpy((void *)((long)List + (ListEntrySize * looper) + PrevOffset), &NewPointerValue, sizeof(long *)); 
         }

         if (memcmp((void *)((long)List + (ListEntrySize * looper) + NextOffset), &NullPointer, sizeof(long *)) != 0)
         {
            NewPointerValue = *((long *)((long)List + (ListEntrySize * looper) + NextOffset)) + Offset;
            memcpy((void *)((long)List + (ListEntrySize * looper) + NextOffset), &NewPointerValue, sizeof(long *)); 
         }
      }
   }

   CreationResult = deTRUE;

   return;
}



//=================================================================================
// deDynamicList::~deDynamicList()
//
// Destructor
//=================================================================================
deDynamicList::~deDynamicList()
{
   if (List)
   {
      free(List);
      List = NULL;
   }
} 



//=================================================================================
// deDynamicList::AddElement()
//
// Add a new element to end of list
//=================================================================================
deBoolean deDynamicList::AddElement(void *Element)
{
   char UsedSlot = 'Y';
   void *Pointer = NULL;


   if (!Element)
   {
      //error - Null pointer
      return deFALSE;
   }

   if (CurrentElementCount == ListSize)
   {
      if (!GrowList(GrowthRate))
      {
         //error - GrowList failed
         return deFALSE;
      }
   }

   if (CurrentElementCount == 0)
   {
      memcpy(List, &UsedSlot, 1);
      memcpy((void *)((long)List + ElementOffset), Element, ElementSize);
      memcpy((void *)((long)List + PrevOffset), &Pointer, sizeof(long *));
      memcpy((void *)((long)List + NextOffset), &Pointer, sizeof(long *));

      CurrentElementCount++;
      FirstElement = List;
      LastElement = List;
      CurrentElement = List;

      return deTRUE;
   }
      
   CurrentElement = LastElement;

   if (!InsertElementAfter(Element))
   {
      //error - Add Failed
      return deFALSE;
   }

   return deTRUE;
}



//=================================================================================
// deDynamicList::InsertElementBefore()
//
// Add a new element before the current one
//=================================================================================
deBoolean deDynamicList::InsertElementBefore(void *Element)
{
   char UsedSlot = 'Y';
   void *Pointer = NULL;
   void *NullPointer = NULL;
   void *PrevPointer = NULL;


   if (!Element)
   {
      //error - Null pointer
      return deFALSE;
   }

   if (CurrentElementCount == ListSize)
   {
      if (!GrowList(GrowthRate))
      {
         //error - GrowList failed
         return deFALSE;
      }
   }

   if (CurrentElementCount == 0)
   {
      memcpy(List, &UsedSlot, 1);
      memcpy((void *)((long)List + ElementOffset), Element, ElementSize);
      memcpy((void *)((long)List + PrevOffset), &Pointer, sizeof(long *));
      memcpy((void *)((long)List + NextOffset), &Pointer, sizeof(long *));

      CurrentElementCount++;
      FirstElement = List;
      LastElement = List;
      CurrentElement = List;

      return deTRUE;
   }

   Pointer = FindOpenSlot();

   if (!Pointer)
   {
      //error - FindOpenSlot failed
      return deFALSE;
   }

   memcpy(Pointer, &UsedSlot, 1);
   memcpy((void *)((long)Pointer + ElementOffset), Element, ElementSize);
   memcpy((void *)((long)Pointer + NextOffset), &CurrentElement, sizeof(long *));

   if (memcmp((void *)((long)CurrentElement + PrevOffset), &NullPointer, sizeof(long *)) == 0)
   {
      memcpy((void *)((long)CurrentElement + PrevOffset), &Pointer, sizeof(long *));
      memcpy((void *)((long)Pointer + PrevOffset), &NullPointer, sizeof(long *));
      FirstElement = Pointer;
   }
   else
   {
      memcpy((void *)((long)Pointer + PrevOffset), (void *)((long)CurrentElement + PrevOffset), sizeof(long *));
      memcpy((void *)((long)CurrentElement + PrevOffset), &Pointer, sizeof(long *));

      memcpy(&PrevPointer, (void *)((long)Pointer + PrevOffset), sizeof(long *));
      memcpy((void *)((long)PrevPointer + NextOffset), &Pointer, sizeof(long *));
   }

   CurrentElement = Pointer;
   CurrentElementCount++;

   return deTRUE;
}



//=================================================================================
// deDynamicList::InsertElementAfter()
//
// Add a new element after the current one
//=================================================================================
deBoolean deDynamicList::InsertElementAfter(void *Element)
{
   char UsedSlot = 'Y';
   void *Pointer = NULL;
   void *NullPointer = NULL;
   void *NextPointer = NULL;


   if (!Element)
   {
      //error - Null pointer
      return deFALSE;
   }

   if (CurrentElementCount == ListSize)
   {
      if (!GrowList(GrowthRate))
      {
         //error - GrowList failed
         return deFALSE;
      }
   }

   if (CurrentElementCount == 0)
   {
      memcpy(List, &UsedSlot, 1);
      memcpy((void *)((long)List + ElementOffset), Element, ElementSize);
      memcpy((void *)((long)List + PrevOffset), &Pointer, sizeof(long *));
      memcpy((void *)((long)List + NextOffset), &Pointer, sizeof(long *));

      CurrentElementCount++;
      FirstElement = List;
      LastElement = List;
      CurrentElement = List;

      return deTRUE;
   }

   Pointer = FindOpenSlot();

   if (!Pointer)
   {
      //error - FindOpenSlot failed
      return deFALSE;
   }

   memcpy(Pointer, &UsedSlot, 1);
   memcpy((void *)((long)Pointer + ElementOffset), Element, ElementSize);
   memcpy((void *)((long)Pointer + PrevOffset), &CurrentElement, sizeof(long *));

   if (memcmp((void *)((long)CurrentElement + NextOffset), &NullPointer, sizeof(long *)) == 0)
   {
      memcpy((void *)((long)CurrentElement + NextOffset), &Pointer, sizeof(long *));
      memcpy((void *)((long)Pointer + NextOffset), &NullPointer, sizeof(long *));
      LastElement = Pointer;
   }
   else
   {
      memcpy((void *)((long)Pointer + NextOffset), (void *)((long)CurrentElement + NextOffset), sizeof(long *));
      memcpy((void *)((long)CurrentElement + NextOffset), &Pointer, sizeof(long *));

      memcpy(&NextPointer, (void *)((long)Pointer + NextOffset), sizeof(long *));
      memcpy((void *)((long)NextPointer + PrevOffset), &Pointer, sizeof(long *));
   }

   CurrentElement = Pointer;
   CurrentElementCount++;

   return deTRUE;
}



//=================================================================================
// deDynamicList::DeleteElement()
//
// Delete the current element
//=================================================================================
deBoolean deDynamicList::DeleteElement(void)
{
   char UnusedSlot = 'N';
   void *NullPointer = NULL;
   void *PrevPointer = NULL;
   void *NextPointer = NULL;


   if (CurrentElementCount == 0)
   {
      //error - No elements exist
      return deFALSE;
   }

   CurrentElementCount--;

   memcpy(CurrentElement, &UnusedSlot, 1);
   memcpy(&PrevPointer, (void *)((long)CurrentElement + PrevOffset), sizeof(long *));
   memcpy(&NextPointer, (void *)((long)CurrentElement + NextOffset), sizeof(long *));

   if (PrevPointer == NULL)
   {
      if (NextPointer == NULL)
      {
         FirstElement = NULL;
         LastElement = NULL;
         CurrentElement = NULL;
         return deTRUE;
      }
      else
      {
         FirstElement = NextPointer;
         CurrentElement = NextPointer;
         memcpy((void *)((long)NextPointer + PrevOffset), &NullPointer, sizeof(long *));
         return deTRUE;
      }
   }
   else
   {
      if (NextPointer == NULL)
      {
         LastElement = PrevPointer;
         CurrentElement = PrevPointer;
         memcpy((void *)((long)PrevPointer + NextOffset), &NullPointer, sizeof(long *));
         return deTRUE;
      }
      else
      {
         CurrentElement = PrevPointer;
         memcpy((void *)((long)PrevPointer + NextOffset), &NextPointer, sizeof(long *));
         memcpy((void *)((long)NextPointer + PrevOffset), &PrevPointer, sizeof(long *));
         return deTRUE;
      }
   }
}



//=================================================================================
// deDynamicList::GetFirstElement()
//
// Get the first element
//=================================================================================
void *deDynamicList::GetFirstElement(void)
{
   if (CurrentElementCount == 0)
   {
      //error - No elements exist
      return NULL;
   }

   CurrentElement = FirstElement;

   return (void *)((long)FirstElement + ElementOffset);
}



//=================================================================================
// deDynamicList::GetNextElement()
//
// Get the next element
//=================================================================================
void *deDynamicList::GetNextElement(void)
{
   void *NullPointer = NULL;

   if (CurrentElementCount == 0)
   {
      //error - No elements exist
      return NULL;
   }

   if (memcmp((void *)((long)CurrentElement + NextOffset), &NullPointer, sizeof(long *)) == 0)
   {
      return NULL;
   }

   memcpy(&CurrentElement, (void *)((long)CurrentElement + NextOffset), sizeof(long *));

   return (void *)((long)CurrentElement + ElementOffset);
}



//=================================================================================
// deDynamicList::GetPreviousElement()
//
// Get the previous element
//=================================================================================
void *deDynamicList::GetPreviousElement(void)
{
   void *NullPointer = NULL;

   if (CurrentElementCount == 0)
   {
      //error - No elements exist
      return NULL;
   }

   if (memcmp((void *)((long)CurrentElement + PrevOffset), &NullPointer, sizeof(long *)) == 0)
   {
      return NULL;
   }

   memcpy(&CurrentElement, (void *)((long)CurrentElement + PrevOffset), sizeof(long *));

   return (void *)((long)CurrentElement + ElementOffset);
}



//=================================================================================
// deDynamicList::GetLastElement()
//
// Get the last element
//=================================================================================
void *deDynamicList::GetLastElement(void)
{
   if (CurrentElementCount == 0)
   {
      //error - No elements exist
      return NULL;
   }

   CurrentElement = LastElement;

   return (void *)((long)LastElement + ElementOffset);
}



//=================================================================================
// deDynamicList::FindOpenSlot()
//
// Find an open slot in the list
//=================================================================================
void *deDynamicList::FindOpenSlot(void)
{
   unsigned int looper = 0;
   char UnusedSlot = 'N';
   void *Pointer = NULL;


   for (looper = 0; looper < ListSize; looper++)
   {
      if (memcmp((void *)((long)List + (ListEntrySize * looper)), &UnusedSlot, 1) == 0)
      {
         Pointer = (void *)((long)List + (ListEntrySize * looper));
         break;
      }
   }

   return Pointer;
}



//=================================================================================
// deDynamicList::GrowList()
//
// Increase the list size
//=================================================================================
deBoolean deDynamicList::GrowList(unsigned int SizeIncrease)
{
   void *NewList = NULL;
   char UnusedSlot = 'N';
   char UsedSlot = 'Y';
   int Offset = 0;
   void *NullPointer = NULL;
   long NewPointerValue = 0;
   unsigned int looper = 0;


   NewList = realloc(List, (ListSize + SizeIncrease) * ListEntrySize);

   if (!NewList)
   {
      //error - Realloc failed
      return deFALSE;
   }

   for(looper = ListSize; looper < (ListSize + SizeIncrease); looper++)
   {
      memcpy((void *)((long)NewList + (ListEntrySize * looper)), &UnusedSlot, 1);
   }

   ListSize += SizeIncrease;

   if (NewList != List)
   {
      Offset = (long)NewList - (long)List;
      FirstElement = (void *)((long)FirstElement + Offset);
      LastElement = (void *)((long)LastElement + Offset);
      CurrentElement = (void *)((long)CurrentElement + Offset);
      
      for (looper = 0; looper < ListSize; looper++)
      {
         if (memcmp((void*)((long)NewList + (ListEntrySize * looper)), &UsedSlot, 1) == 0)
         {
            if (memcmp((void *)((long)NewList + (ListEntrySize * looper) + PrevOffset), &NullPointer, sizeof(long *)) != 0)
            {
               NewPointerValue = *((long *)((long)NewList + (ListEntrySize * looper) + PrevOffset)) + Offset;
               memcpy((void *)((long)NewList + (ListEntrySize * looper) + PrevOffset), &NewPointerValue, sizeof(long *)); 
            }

            if (memcmp((void *)((long)NewList + (ListEntrySize * looper) + NextOffset), &NullPointer, sizeof(long *)) != 0)
            {
               NewPointerValue = *((long *)((long)NewList + (ListEntrySize * looper) + NextOffset)) + Offset;
               memcpy((void *)((long)NewList + (ListEntrySize * looper) + NextOffset), &NewPointerValue, sizeof(long *)); 
            }
         }
      }
   }

   List = NewList;

   return deTRUE;
}

