/* File: piledin.c */
/* Time-stamp: "2002-05-17 00:23:56 calvanes" */
/* Scopo: rappresentazione sequenziale delle pile tramite array dinamico */

#include <stdlib.h>

/* Richiede di dichiarare il tipo bool */
/* typedef int bool; */

/* Richiede di dichiarare la dimensione iniziale della pila */
/* #define DimInizialePila 10 */

/* Richiede di dichiarare il tipo degli elementi della pila */
/* typedef int TipoElemPila; */


/* definizione del tipo pila */

struct tipoPila {
  TipoElemPila *pila;
  int pos;
  int dimCorrente;
};
typedef struct tipoPila TipoPila;


/* implementazione delle operazioni primitive sulle pile */


void InitPila(TipoPila *pp)
  /* Inizializza la pila *pp, allocando la memoria per il vettore e
     ponendo a -1 l'indice dell'elemento affiorante. */
{
  (*pp).pila = malloc(DimInizialePila * sizeof(TipoElemPila));
  (*pp).pos = -1;
  (*pp).dimCorrente = DimInizialePila;
}  /* InitPila */



bool TestPilaVuota(TipoPila p)
  /* Restituisce TRUE se la pila p e` vuota, FALSE altrimenti. */
{
  return (p.pos == -1);
}  /* TestPilaVuota */



void TopPila(TipoPila p, TipoElemPila *pv)
  /* Restituisce in *pv l'elemento affiorante della pila,
     senza modificare la pila. */
{
  if (TestPilaVuota(p))
    printf("ERRORE: PILA VUOTA\n");
  else
    *pv = p.pila[p.pos];
}  /* TopPila */



void Push(TipoPila *pp, TipoElemPila v)
  /* Inserisce l'elemento v in cima alla pila *pp e, se la pila e` piena,
     aumenta la dimensione della pila. */
{
  if ((*pp).pos == ((*pp).dimCorrente - 1)) {
               /* pila piena: raddoppia la dimensione del vettore (*pp).pila */
    (*pp).dimCorrente = (*pp).dimCorrente * 2;
    (*pp).pila = realloc((*pp).pila, (*pp).dimCorrente * sizeof(TipoElemPila));
  }
                                 /* inserisce l'elemento v in cima alla pila */
  (*pp).pos++;
  (*pp).pila[(*pp).pos] = v;
}  /* Push */



void Pop(TipoPila *pp, TipoElemPila *pv)
  /* Elimina l'elemento affiorante della pila p, restituendone il valore
     in *pv, e se necessario riduce la dimensione della pila. */
{
  if (TestPilaVuota(*pp))
    printf("ERRORE: PILA VUOTA\n");
  else {
    *pv = (*pp).pila[(*pp).pos];
    (*pp).pos--;

       /* se la pila contiene un numero di elementi maggiore di DimInizialePila
          e inferiore ad un terzo della sua dimensione corrente,
          viene dimezzata la sua dimensione */
    if ((*pp).dimCorrente > DimInizialePila &&
        (*pp).pos < (*pp).dimCorrente/3) {
      (*pp).dimCorrente = (*pp).dimCorrente / 2;
      (*pp).pila = realloc((*pp).pila,
                           (*pp).dimCorrente * sizeof(TipoElemPila));
    }
  }
}  /* Pop */