// stack.c - a stack for common use

#include <stdio.h>
#include <stdlib.h>

#include "default_error_handling.h"
#include "default_debug.h"
#include "stack.h"
#include "stack_private.h"

//------------------------------------------------------------
// constructor for a stack
//
// triggered errors: OUT_OF_MEMORY
Stack *newStack(void (*error_handler)(int error_type,
                                      void *special))
{
  Stack *stack = (Stack*)malloc(sizeof(Stack));

  if (!error_handler)
    error_handler = defaultErrorHandler;

  if (!stack)
  {
    error_handler(OUT_OF_MEMORY,"newStack");
    return(NULL);
  }
  stack->elements = NULL;
  stack->destructors = NULL;
  stack->num_elements = 0;
  stack->num_elements_allocated = 0;
  stack->threshold_percentage = DEFAULT_THRESHOLD_PERCENTAGE;
  return(stack);
}

//------------------------------------------------------------
// destructor for a stack
//
// triggered errors: ILLEGAL_ARGUMENTS
void deleteStack(Stack *stack,
                 void (*error_handler)(int error_type,
                                       void *special))
{
  if (!error_handler)
    error_handler = defaultErrorHandler;

  if (!stack)
  {
    error_handler(ILLEGAL_ARGUMENTS,"deleteStack");
    return;
  }
      // if an error occurs go on anyway and don't return,
      // otherwise the stack structure itself is not freed!
  clear(stack,error_handler);
  free(stack);
}

//------------------------------------------------------------
// access function to set the realloc-threshold for shrinking
// the memory-block associated with the stack. The threshold
// is always given in percent and values higher than 50 percent
// are not allowed because they don't make any sense.
//
// triggered errors: ILLEGAL_ARGUMENTS
void setThresholdPercentage(Stack *stack,
                            unsigned threshold_percentage,
                            void (*error_handler)(
                              int error_type,
                              void *special))
{
  if (!error_handler)
    error_handler = defaultErrorHandler;

      // don't allow threshold percentages > 50, because
      // they don't make sense. With e.g. 100 the stack would
      // never shrink at all!
  if ((!stack) || (threshold_percentage > 50))
  {
    error_handler(ILLEGAL_ARGUMENTS,"setThresholdPercentage");
    return;
  }
  stack->threshold_percentage = threshold_percentage;
}

//------------------------------------------------------------
// access function to read the number of elements that are
// held in the stack
//
// triggered errors: ILLEGAL_ARGUMENTS
unsigned getNumElementsFromStack(Stack *stack,
                                  void (*error_handler)(
                                    int error_type,
                                    void *special))
{
  if (!error_handler)
    error_handler = defaultErrorHandler;

  if (!stack)
  {
    error_handler(ILLEGAL_ARGUMENTS,"getNumElements");
    return(0);
  }
  return(stack->num_elements);
}

//------------------------------------------------------------
// function for pushing elements on the stack
//
// triggered errors: ILLEGAL_ARGUMENTS
//                   OUT_OF_MEMORY
void push(Stack *stack,void *element,
          void (*destructor)(void *element,
                             void (*err_handler)(int error_type,
                                                 void *special)),
          void (*error_handler)(int error_type,
                                void *special))
{
  if (!error_handler)
    error_handler = defaultErrorHandler;

  if (!stack)
  {
    error_handler(ILLEGAL_ARGUMENTS,"push");
    return;
  }
  if (reallocIfNecessary(stack,stack->num_elements + 1,
                         error_handler))
    return;
  stack->elements[stack->num_elements] = element;
  stack->destructors[stack->num_elements] = destructor;
  stack->num_elements++;
}

//------------------------------------------------------------
void *pop(Stack *stack,
          void (*error_handler)(int error_type,
                                void *special))
{
  void *element = NULL;
  if (!error_handler)
    error_handler = defaultErrorHandler;

  if (!stack)
  {
    error_handler(ILLEGAL_ARGUMENTS,"pop");
    return(NULL);
  }
  if (stack->num_elements <= 0)
  {
    error_handler(INDEX_OUT_OF_BOUNDS,"pop");
    return(NULL);
  }
  element = stack->elements[--stack->num_elements];
  reallocIfNecessary(stack,stack->num_elements,error_handler);
  return(element);
}

//------------------------------------------------------------
// swap operation - swaps the last two elements on the 
// stack, if there are at least two
//
// triggered errors: ILLEGAL_ARGUMENTS
//                   INDEX_OUT_OF_BOUNDS
void swap(Stack *stack,
          void (*error_handler)(int error_type,
                                void *special))
{
  void *element = NULL;
  void (*destructor)(void *element,
                     void (*error_handler)(
                       int error_type,void*special)) = NULL;

  if (!error_handler)
    error_handler = defaultErrorHandler;

  if (!stack)
  {
    error_handler(ILLEGAL_ARGUMENTS,"swap");
    return;
  }
  if (stack->num_elements < 2)
  {
    error_handler(INDEX_OUT_OF_BOUNDS,"swap");
    return;
  }
  element = stack->elements[stack->num_elements - 1];
  destructor = stack->destructors[stack->num_elements - 1];
  stack->elements[stack->num_elements - 1] =
    stack->elements[stack->num_elements - 2];
  stack->destructors[stack->num_elements - 1] =
    stack->destructors[stack->num_elements - 2];
  stack->elements[stack->num_elements - 2] = element;
  stack->destructors[stack->num_elements - 2] = destructor;
}

//------------------------------------------------------------
// clears the stack and frees the memory that is allocated
// by the inner structures of it.
//
// triggered errors: ILLEGAL_ARGUMENTS
void clear(Stack *stack,
           void (*error_handler)(int error_type,
                                 void *special))
{
  unsigned count = 0;
  void **elements = NULL;
  void (**destructors)(void *element,
                       void (*error_handler)(int error_type,
                                             void *special));

  if (!error_handler)
    error_handler = defaultErrorHandler;

  if (!stack)
  {
    error_handler(ILLEGAL_ARGUMENTS,"clear");
    return;
  }
  count = stack->num_elements;
  destructors = stack->destructors;
  elements = stack->elements;
  while(count--)
  {
    if (*destructors) // call destructor if given
      (*destructors++)(*elements++,error_handler);
    else
      elements++;
  }
  if (stack->elements)
    free(stack->elements);
  stack->elements = NULL;
  if (stack->destructors)
    free(stack->destructors);
  stack->destructors = NULL;
  stack->num_elements = stack->num_elements_allocated = 0;
}

//------------------------------------------------------------
// helper function to be able to have a quick look at an
// element on the stack without having to pop all elements
// "below" it. In principle this function should not be part
// of a stack implementation, but there are many cases where
// it is really needed, e.g. to show the whole stack. If
// this would have to be done with pop / push operations the
// overhead would be way too high.
//
// triggered errors: ILLEGAL_ARGUMENTS
//                   INDEX_OUT_OF_BOUNDS
void *peek(Stack *stack,unsigned index,
           void (*error_handler)(int error_type,void *special))
{
  if (!error_handler)
    error_handler = defaultErrorHandler;

  if (!stack)
  {
    error_handler(ILLEGAL_ARGUMENTS,"peek");
    return(NULL);
  }
  if (stack->num_elements <= index)
  {
    error_handler(INDEX_OUT_OF_BOUNDS,"peek");
    return(NULL);
  }
  return(stack->elements[stack->num_elements - index - 1]);
}

//------------------------------------------------------------
// helper function that implements the paradigm of exponential
// reallocation with a threshold. If there is not enough
// memory allocated then the block is doubled in size. However
// the memory is not freed immediately if there are less than
// half the elements of the allocated block on the stack.
// Rather some threshold is taken into account before the stack
// shrinks. This is very essential when doing several push / pop
// operations right on the block-boundary. Otherwise every single
// operation would cause shrinking or growing of the internal
// blocks, which is very time-consuming!
//
// triggered errors: ILLEGAL_ARGUMENTS
//                   OUT_OF_MEMORY
int reallocIfNecessary(Stack *stack,
                        unsigned num_elements,
                        void (*error_handler)(
                          int error_type,void *special))
{
  unsigned realloc_to = 0;

  if (!error_handler)
    error_handler = defaultErrorHandler;

  if (!stack)
  {
    error_handler(ILLEGAL_ARGUMENTS,"peekElementAtIndex");
    return(ILLEGAL_ARGUMENTS);
  }
      // stack is growing beyond its allocated size
  if (num_elements > stack->num_elements_allocated)
  {
    realloc_to = stack->num_elements_allocated ?
                 stack->num_elements_allocated * 2 :
                 MIN_ELEMENTS_TO_ALLOCATE;
  }
  else
  {
    unsigned threshold_limit = 0;

        // stack is growing, but not beyond its allocated size or
        // the lower limit is already reached
    if ((num_elements > stack->num_elements) ||
        (stack->num_elements_allocated <= MIN_ELEMENTS_TO_ALLOCATE))
      return(0);

        // stack is shrinking calculate threshold limit
    threshold_limit = (stack->num_elements_allocated / 2) -
                      (((stack->num_elements_allocated / 2) * 
                        stack->threshold_percentage) / 100);
        // not below threshold
    if (num_elements >= threshold_limit)
      return(0);
        // calculate new size - checking for min elements is not
        // necessary here because growth always happens by a factor
        // of 2 and it was already checked for the minimum above
    realloc_to = stack->num_elements_allocated / 2;
  }
  stack->elements = (void **)realloc(stack->elements,
                                     realloc_to * sizeof(void*));
  stack->destructors = 
    (void (**)(void*,void (*)(int,void *)))realloc(
      stack->destructors,
      realloc_to * 
      sizeof(void(*)(void*,void (*)(int,void*))));
  if ((!stack->elements) || (!stack->destructors))
  {
    error_handler(OUT_OF_MEMORY,"internal: reallocIfNecessary");
    return(OUT_OF_MEMORY);
  }
  stack->num_elements_allocated = realloc_to;
  return(0);
}
