/**********************************************************************************
*  Stack.c
*  Implementation file for Stack ADT
***********************************************************************************/

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

/************** Private Structs: not exported *************************************/

typedef struct Node{
   int data;
   struct Node* next;
} Node;

typedef Node* NodeRef;

typedef struct Stack{
   NodeRef top;
   int height;
} Stack;


/************** Constructors-Destructors ******************************************/

/*
*  newNode
*  Returns pointer to new Node struct. Initializes next field to NULL, and sets
*  data field to input parameter node_data. Private.
*/
NodeRef newNode(int node_data){
   NodeRef N = malloc(sizeof(Node));
   N->data = node_data;
   N->next = NULL;
   return(N);
}

/*
*  freeNode
*  Frees heap memory pointed to by pN. Private.
*/
void freeNode(NodeRef* pN){
   if( pN!=NULL && *pN!=NULL ){
      free(*pN);
      *pN = NULL;
   }
}

/*
*  newStack
*  Returns StackRef pointing to new StackSturct which represents an empty Stack.
*  Initializes top field to NULL, sets height field to 0.  Exported.
*/
StackRef newStack(void){
   StackRef S;
   S = malloc(sizeof(Stack));
   S->top = NULL;
   S->height = 0;
   return(S);
}

/*
*  freeStack
*  Frees all heap memory associated with the StackRef *pS, including all memory
*  in existing Nodes.  Sets *pS to NULL.  Exported.
*/
void freeStack(StackRef* pS){
   if(pS!=NULL && *pS!=NULL){
      while( !isEmpty(*pS) ) { pop(*pS); }
      free(*pS);
      *pS = NULL;
   }
}



/***************** Access functions ***********************************************/

/*
*  getTop
*  Returns the value at the top of S.
*  Pre: !isEmpty(S)
*/
int getTop(StackRef S){
   if( S==NULL ){
      printf("Stack Error: calling getTop() on NULL StackRef\n");
      exit(1);
   }
   if( isEmpty(S) ){
      printf("Stack Error: calling getTop() on an empty Stack\n");
      exit(1);
   }
   return(S->top->data);
}

/*
*  getHeight
*  Returns the height of S
*/
int getHeight(StackRef S){
   if( S==NULL ){
      printf("Stack Error: calling getHeight() on NULL StackRef\n");
      exit(1);
   }
   return(S->height);
}

/*
*  isEmpty
*  Returns True if S is empty, otherwise returns 0
*/
int isEmpty(StackRef S){
   if( S==NULL ){
      printf("Stack Error: calling isEmpty() on NULL StackRef\n");
      exit(1);
   }
   return(S->height==0);
}



/**************** Manipulation procedures ****************************************/

/*
*  push
*  Places new data element on top of S
*  Post: !isEmpty(S)
*/
void push(StackRef S, int data){
   NodeRef N = newNode(data);

   if( S==NULL ){
      printf("Stack Error: calling push() on NULL StackRef\n");
      exit(1);
   }
   if( isEmpty(S) ) { S->top = N; }
   else { N->next = S->top; S->top = N; }
   S->height++;
}

/*
*  pop
*  Deletes element on top of S
*  Pre: !isEmpty(S)
*/
void pop(StackRef S){
   NodeRef N = NULL;

   if( S==NULL ){
      printf("Stack Error: calling pop() on NULL StackRef\n");
      exit(1);
   }
   if( isEmpty(S) ){
      printf("Stack Error: calling pop() on an empty Stack\n");
      exit(1);
   }
   N = S->top;
   if( getHeight(S)>1 ) { S->top = S->top->next; }
   else { S->top = NULL; }
   S->height--;
   freeNode(&N);
}


/*************** Other Functions *************************************************/

/*
*  printStack
*  Prints data elements in S on a single line to stdout.
*/
void printStack(StackRef S){
   NodeRef N = NULL;

   if( S==NULL ){
      printf("Stack Error: calling printStack() on NULL StackRef\n");
      exit(1);
   }
   for(N = S->top; N != NULL; N = N->next){
      printf("%d ", N->data);
   }
   printf("\n");
}

/*
*  equals
*  returns 1 if Stack A is identical to Stack B, 0 otherwise
*/
int equals(StackRef A, StackRef B){
   int flag = 1;
   NodeRef N = NULL;
   NodeRef M = NULL;

   if( A==NULL || B==NULL )
   {
      printf("Stack Error: calling equals() on NULL StackRef\n");
      exit(1);
   }
   N = A->top;
   M = B->top;
   if( A->height != B->height ) { return 0; }
   while( flag && N!=NULL)
   {
      flag = (N->data==M->data);
      N = N->next;
      M = M->next;
   }
   return flag;
}