/*------------------------------------------------------------------*/
/* dynarray.c                                                       */
/*------------------------------------------------------------------*/

#include "dynarray.h"
#include <assert.h>
#include <stdlib.h>

#define MIN_PHYS_LENGTH 2

struct DynArray
{
   int iLength;
   int iPhysLength;
   const void **ppvArray;
};

/*------------------------------------------------------------------*/

static int DynArray_isValid(DynArray_T oDynArray)

/* Return 1 (TRUE) iff *oDynArray is in a valid state. */

{
   if (oDynArray->iLength < 0) return 0;
   if (oDynArray->iPhysLength < MIN_PHYS_LENGTH) return 0;
   if (oDynArray->iLength > oDynArray->iPhysLength) return 0;
   if (oDynArray->ppvArray == NULL) return 0;
   return 1;
}

/*------------------------------------------------------------------*/

DynArray_T DynArray_new(int iLength)

/* Return a new DynArray_T whose length is iLength.
   It is a checked runtime error for iLength to be negative. */

{
   DynArray_T oDynArray;

   assert(iLength >= 0);

   oDynArray = (struct DynArray*)malloc(sizeof(*oDynArray));
   assert(oDynArray != NULL);
   oDynArray->iLength = iLength;
   if (iLength > MIN_PHYS_LENGTH)      
      oDynArray->iPhysLength = iLength;
   else
      oDynArray->iPhysLength = MIN_PHYS_LENGTH;
   oDynArray->ppvArray = 
      (const void**)calloc(oDynArray->iPhysLength, sizeof(void*));
   assert(oDynArray->ppvArray != NULL);

   return oDynArray;
}

/*------------------------------------------------------------------*/

void DynArray_free(DynArray_T oDynArray)

/* Free oDynArray. */

{
   if (oDynArray == NULL)
      return;

   free(oDynArray->ppvArray);
   free(oDynArray);
}

/*------------------------------------------------------------------*/

int DynArray_getLength(DynArray_T oDynArray)

/* Return the length of oDynArray.
   It is a checked runtime error for oDynArray to be NULL. */

{
   assert(oDynArray != NULL);
   assert(DynArray_isValid(oDynArray));

   return oDynArray->iLength;
}

/*------------------------------------------------------------------*/

void *DynArray_get(DynArray_T oDynArray, int iIndex)

/* Return the iIndex'th element of oDynArray.
   It is a checked runtime error for oDynArray to be NULL or empty.
   It is a checked runtime error for iIndex to be less than 0 or
   greater than or equal to the length of oDynArray. */

{
   assert(oDynArray != NULL);
   assert(DynArray_isValid(oDynArray));
   assert(iIndex >= 0);
   assert(iIndex < oDynArray->iLength);

   return (void*)(oDynArray->ppvArray)[iIndex];
}

/*------------------------------------------------------------------*/

void DynArray_put(DynArray_T oDynArray, int iIndex, const void *pvItem)

/* Assign pvItem to the iIndex'th element of oDynArray.
   It is a checked runtime error for oDynArray to be NULL or empty.
   It is a checked runtime error for iIndex to be less than 0 or
   greater than or equal to the length of oDynArray. */

{
   assert(oDynArray != NULL);
   assert(DynArray_isValid(oDynArray));
   assert(iIndex >= 0);
   assert(iIndex < oDynArray->iLength);

   oDynArray->ppvArray[iIndex] = pvItem;
}

/*------------------------------------------------------------------*/

static void DynArray_grow(DynArray_T oDynArray)

/* Double the physical length of oDynArray. */

{
   assert(oDynArray != NULL);
   assert(DynArray_isValid(oDynArray));

   oDynArray->iPhysLength *= 2;
   oDynArray->ppvArray = 
      (const void**)realloc(oDynArray->ppvArray, 
                      sizeof(void*) * oDynArray->iPhysLength);
   assert(oDynArray->ppvArray != NULL);
}

/*------------------------------------------------------------------*/

void DynArray_add(DynArray_T oDynArray, const void *pvItem)

/* Add pvItem to the end of oDynArray, thus incrementing its length.
   It is a checked runtime error for oDynArray to be NULL. */

{
   assert(oDynArray != NULL);
   assert(DynArray_isValid(oDynArray));

   if (oDynArray->iLength == oDynArray->iPhysLength)
      DynArray_grow(oDynArray);
   
   oDynArray->ppvArray[oDynArray->iLength] = pvItem;
   oDynArray->iLength++;
}

/*------------------------------------------------------------------*/

void DynArray_toArray(DynArray_T oDynArray, void **ppvArray)

/* Fill ppvArray with the elements of oDynArray.
   It is a checked runtime error for oDynArray or ppvArray to be NULL.
   It is an unchecked runtime error for *ppvArray to be too small
   to hold all elements of oDynArray.  */

{
   int i;

   assert(oDynArray != NULL);
   assert(DynArray_isValid(oDynArray));
   assert(ppvArray != NULL);
   
   for (i = 0; i < oDynArray->iLength; i++)
      ppvArray[i] = (void*)oDynArray->ppvArray[i];
}

/*------------------------------------------------------------------*/

void DynArray_map(DynArray_T oDynArray, 
              void (*pfApply)(void *pvItem, void *pvExtra),
              const void *pvExtra)

/* Apply function *pfApply to each element of oDynArray, passing 
   pvExtra as an extra argument.  That is, for each element pvItem
   of oDynArray, call (*pfApply)(pvItem, pvExtra).
   It is a checked runtime error for oDynArray or pfApply to be 
   NULL. */

{
   int i;

   assert(oDynArray != NULL);
   assert(DynArray_isValid(oDynArray));
   assert(pfApply != NULL);
      
   for (i = 0; i < oDynArray->iLength; i++)
      (*pfApply)((void*)oDynArray->ppvArray[i], (void*)pvExtra);
}

/*------------------------------------------------------------------*/

void DynArray_sort(DynArray_T oDynArray,
   int (*pfCompare)(const void *pvItem1, const void *pvItem2))

/* Sort oDynArray in the order determined by *pfCompare.  
   *pfCompare should return <0, 0, or >0 depending upon whether *pvItem1 
   is less than, equal to, or greater than *pvItem2, respectively.
   It is a checked runtime error for oDynArray or pfCompare to be NULL. */

{
   int iOuter;
   int iInner;
   int iCompare;
   const void *pvTemp;

   assert(oDynArray != NULL);
   assert(DynArray_isValid(oDynArray));
   assert(pfCompare != NULL);

   for (iOuter = 1; iOuter < oDynArray->iLength; iOuter++)
      for (iInner = iOuter; iInner > 0; iInner--)
      {
         iCompare = (*pfCompare)(oDynArray->ppvArray[iInner], 
                                 oDynArray->ppvArray[iInner-1]);
         if (iCompare < 0)
         {
            pvTemp = oDynArray->ppvArray[iInner];
            oDynArray->ppvArray[iInner] = oDynArray->ppvArray[iInner-1];
            oDynArray->ppvArray[iInner-1] = pvTemp;
         }
      }
}

/*------------------------------------------------------------------*/

int DynArray_search(DynArray_T oDynArray, void *pvSoughtItem,
   int (*pfCompare)(const void *pvItem1, const void *pvItem2))

/* Linear search oDynArray for *pvSoughtItem using *pfCompare to 
   determine equality.  Return the index at which *pvSoughtItem
   is found, or -1 if there is no such index.
   *pfCompare should return 0 if *pvItem1 is equal to pvItem2, 
   and non-0 otherwise.
   It is a checked runtime error for oDynArray or pfCompare to be 
   NULL. */

{
   int i;

   assert(oDynArray != NULL);
   assert(DynArray_isValid(oDynArray));
   assert(pfCompare != NULL);

   for (i = 0; i < oDynArray->iLength; i++)
      if ((*pfCompare)(oDynArray->ppvArray[i], pvSoughtItem) == 0)
         return i;
   return -1;
}

/*------------------------------------------------------------------*/

int DynArray_bsearch(DynArray_T oDynArray, void *pvSoughtItem,
   int (*pfCompare)(const void *pvItem1, const void *pvItem2))

/* Binary search oDynArray for *pvSoughtItem using *pfCompare to 
   determine equality.  Return the index at which *pvSoughtItem
   is found, or -1 if there is no such index.
   *pfCompare should return <0, 0, or >0 depending upon whether *pvItem1 
   is less than, equal to, or greater than *pvItem2, respectively.
   It is a checked runtime error for oDynArray or pfCompare to be 
   NULL. 
   It is an unchecked runtime error for oDynArray not to be sorted
   as determined by *pfCompare. */

{
   int iLeft = 0;
   int iRight = oDynArray->iLength - 1;
   int iMid;
   int iCompare;

   assert(oDynArray != NULL);
   assert(DynArray_isValid(oDynArray));
   assert(pfCompare != NULL);

   while (iLeft <= iRight)
   {
      iMid = (iLeft + iRight) / 2;
      iCompare = (*pfCompare)(pvSoughtItem, oDynArray->ppvArray[iMid]);
      if (iCompare == 0)
         return iMid;
      if (iCompare < 0)
         iRight = iMid - 1;
      else
         iLeft = iMid + 1;
   }

   return -1;
}