#ifndef Stack_c_
#define Stack_c_

#include "PickObject.c"

/**
 * This class represents a stack as defined by the which algorithm.
 **/

/**
 * This structure will represent one node in the Stack.
 * @menber mData The actual data the user interacts with and is concerned about.
 * @member mPrev A pointer to the previous node in the Stack.
 * @member mNext A pointer to the next node in the Stack.
 **/
struct StackNodeStruct
{
  void *mData;
  struct StackNodeStruct *mPrev, *mNext;
};
typedef struct StackNodeStruct StackNode;


/**
 * This structure will represent the Stack.
 * @member mSize The current size of the stack.
 * @member mMaxSize The maximums size the stack can be.  If this is -1, the stack is infinite in size.
 * @member mTop The top of the stack( last element inserted ).
 * @member mBottom The bottom of the stack( first element inserted ).
 * @member mDeleteData A pointer to the function that handles deleting the node's data.
 * @member mSetNodeData A pointer to the function that handles setting up a node.
 **/
struct StackStruct
{
  int mSize;
  int mMaxSize;
  StackNode *mTop, *mBottom;
  void (*mDeleteData)( void* );
  void *(*mSetNodeData)( void* );
};
typedef struct StackStruct Stack;

Stack *newStack( int maxSize, void (*deleteData)( void* ), void *(*setNodeData)( void* ) )
{
  Stack *stack = (Stack*)malloc( sizeof( Stack ) );
  stack->mSize = 0;
  stack->mMaxSize = maxSize;
  stack->mTop = NULL;
  stack->mBottom = NULL;
  stack->mDeleteData = deleteData;
  stack->mSetNodeData = setNodeData;
    
  return stack;
}

void delStack( Stack *stack )
{
  StackNode *curPtr = stack->mBottom;
  while ( curPtr != NULL )
  {
    StackNode *tmp = curPtr->mNext;

    stack->mDeleteData( curPtr->mData );
    free( curPtr );

    curPtr = tmp;
  }
  stack->mTop = stack->mBottom = NULL;
}

int push( void *data, Stack *stack )
{
  StackNode *node = (StackNode*)malloc( sizeof( StackNode ) );
  node->mPrev = node->mNext = NULL;
  node->mData = stack->mSetNodeData( data );

  // Two cases, the stack is empty, the stack has elements.
  if ( stack->mSize == 0 )
  {
    stack->mTop = node;
    stack->mBottom = node;
    stack->mSize++;
  }
  else
  {
    // If the stack is not full, or infinite, add the item.
    if ( stack->mSize < stack->mMaxSize || stack->mMaxSize == -1 )
    {
      node->mPrev = stack->mTop;
      stack->mTop->mNext = node;
      stack->mTop = node;
      stack->mSize++;
    }
    else
    {
      return -1;
    }
  }
  return 0;
}

/**
 * This method acts similiarly to push but with a caveat.  It will push the new data into the
 * stack iff it compares better than some node currently in the stack.  In the event that it
 * does score better, the lowest node in the stack, mBottom, will be removed.
 * @param compare The method of comparison.
 * @param data The data to add to the stack.
 * @param stack The stack to add the data to.
 *
 **/
int pushWithScore( float (*compare)(void*, void*), void *data, Stack *stack )
{
  // We are definately going to be added, so create the node here.
  // Set its pointers to the links as NULL.
  StackNode *node = (StackNode*)malloc( sizeof( StackNode ) );
  node->mNext = node->mPrev = NULL;
  node->mData = data;
 
  // Two cases: The stack is empty or the stack has elements.
  if ( stack->mSize == 0 )
  {
    stack->mTop = node;
    stack->mBottom = node;
  }
  // In this case, we must see how this new data compares with the current data and put it in its place.
  // If the data is less than the worst and the stack has a size, we don't add it.  If the data is better
  // than the worst, the current worst( the bottom ) gets removed.
  else
  {
    // If it is worse than the worst, and the stack isn't full, add the node to the bottom, else ignore it.
    if ( compare( node->mData, stack->mBottom->mData ) <= 0 )
    {
      if ( stack->mSize >= stack->mMaxSize && stack->mMaxSize != -1 )
      {
	printf( "\n\n\nI am here\n\n\n" );
	stack->mDeleteData( node->mData );
	free( node );
	return -1;
      }
      node->mNext = stack->mBottom;
      stack->mBottom->mPrev = node;
      node->mPrev = NULL;
      stack->mBottom = node;
    }
    // If we are better than the best, no need to search.
    else if ( compare( node->mData, stack->mTop->mData ) > 0 )
    {
      node->mPrev = stack->mTop;
      node->mNext = NULL;
      stack->mTop->mNext = node;
      stack->mTop = node;

    }
    // Here, we need to bubble down until we get the right spot for it.
    else
    {
      StackNode *curPtr = stack->mTop;
      
      // While we are not at the bottom AND our new data scored lower than the current node, bubble down.
      while ( curPtr != NULL && compare( node->mData, curPtr->mData ) <= 0 )
	curPtr = curPtr->mPrev;

      // Now we are at the score spot we need to be.  However, there may be several with the same score. Place this
      // node in the spot that is score based on the score.  IE sort the Stack on two dimensions,
      // first the score in descending order, then sort the equal-scoring rules by size in ascending order.
      while ( curPtr != NULL && compare( node->mData, curPtr->mData ) == 0 &&
	      ((PickObject*)node->mData)->mSize > ((PickObject*)curPtr->mData)->mSize )
	curPtr = curPtr->mPrev;


      node->mPrev = curPtr;
      node->mNext = curPtr->mNext;
      node->mNext->mPrev = node;
      node->mPrev->mNext = node;
    }
  }

  // Now that we have added the next element, check to see if the last element needs to go.
  if ( stack->mSize == stack->mMaxSize )
  {
    StackNode *tmp = stack->mBottom;
    stack->mBottom = tmp->mNext;
    tmp->mNext->mPrev = NULL;
    stack->mDeleteData( tmp->mData );
    free( tmp );
  }
  // Otherwise, we simply add one to the stack size.
  else
  {
    stack->mSize++;
  }
  
  return 0;
}      
  
#endif