PI 2016/2017 Parte B

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

int MAXc = 3;

typedef struct chunk {
	int vs[3];
	struct chunk *prox;
} *CList;

typedef struct stackC {
	CList valores;
	int sp;
} StackC;

/* NOTA INICIAL: A forma C da stack suscitou-me algumas dúvidas quanto à ordem na stack. Vou deixar aqui a forma que entendi que funciona, que é a
* forma que tive sempre em consideração durante a implementação dos exercícios:
*
* Ordem pela qual os valores foram inseridos : 1 -> 12 -> 23 -> 34 -> 45 -> 56 -> 67
* Fazendo pop, retira o último inserido: 67. Fazendo pop outra vez, o valor retirado seria 56.
* Fazendo reverse, o resultado seria o mesmo que se obteria caso a inserção fosse feita da seguinte forma: 67 -> 56 -> 45 -> 34 -> 23 -> 12 -> 1
*/


/* Pergunta 1
* Esta função vai introduzir um valor novo na stack. Recebe um apontador para a stack e o valor a ser introduzido
*/
int push(StackC *stack, int value){

	// Se o valor armazenado em 'sp' é igual a MAXc, entao o array em stack->valores está cheio. É preciso entao criar um novo
	// e ligar esse novo ao array no topo da lista, sem perder a continuidade das listas ligadas
	if(stack->sp == MAXc){

		// O novo valor de sp vai ser 1, já que o novo array terá 1 elemento
		stack->sp = 1;
		// Reserva espaço na memória para alocar um novo CList
		CList newCList = malloc(sizeof(struct chunk));

		// Insere o valor no novo CList
		newCList->vs[0] = value;
		//  Liga o nov CList à cabeça da lista
		newCList->prox = stack->valores;
		// Actualiza o apontador da stack para a nova cabeça da lista ligada
		stack->valores = newCList;
	} else {
		// Se o valor em 'sp' é menor que MAXc, então o array na cabeça da lista não está cheio. Vai então colocar o valor nesse
		// array, e incrementar o valor de 'sp'
		stack->valores->vs[stack->sp++] = value;
	}

	return 0;
}


/* Pergunta 2
* Esta função vai retirar o último valor adicionado à stack. Recebe um apontador para a stack, e um apontador para um inteiro,
* que irá armazenar o valor retirado da stack
*/
int pop(StackC *stack, int *value){
	// Primeiro coloca em 'value' o último valor da stack
	*value = stack->valores->vs[stack->sp - 1];

	// Agora vai efectivamente retirar esse valor da stack. Se o valor de 'sp' for igual a 1, então significa que o array na cabeça da
	// lista apenas tem um valor, que vai ser retirado. Significa que basta apontar 'stack->valores' para o próximo array da lista ligada
	// e fazer free à cabeça da lista
	if(stack->sp == 1){
		// Actualiza o valor de 'sp' para MAXc
		stack->sp = MAXc;

		// Guarda a cabeça da lista, para se fazer free mais tarde
		CList toRemove = stack->valores;

		// Actaliza a cabeça da lista para o próximo array da lista
		stack->valores = stack->valores->prox;
		// Faz free à antiga cabeça da lista
		free(toRemove);
	} else {
		// Se o valor de 'sp' for maior que 1, então basta colcar o último valor do array da cabeça da lista a NULL e decrementar o valor de 'sp'
		stack->valores->vs[--stack->sp] = NULL;
	}

	return 0;
}


// Funcao auxiliar para popular a stack com os valores dados no teste
void initializeStack(StackC *stack){
	push(stack, 1);
	push(stack, 12);
	push(stack, 23);
	push(stack, 34);
	push(stack, 45);
	push(stack, 56);
	push(stack, 67);
}


// Funcao auxiliar para imprimir os valores na stack
void printStack(StackC *stack){
	int first = 1;
	CList currentArray = stack->valores;

	while(currentArray != NULL){
		int i = 0;
		int size = first ? stack->sp : MAXc;

		while(i < size){
			printf("%d\n", currentArray->vs[i++]);
		}
		printf("--------\n");

		currentArray = currentArray->prox;
		first = 0;
	}
}


/* Pergunta 3
* Esta função recebe a stack, e conta quantos elementos tem.
*/
int size(StackC stack){
	// Primeiro conta quantos arrays completos tem na lista ligada
	int numberOfLinkedCLists = 0;

	CList nextCList = stack.valores->prox;

	while(nextCList != NULL){
		numberOfLinkedCLists++;
		nextCList = nextCList->prox;
	}

	// Esses arrays completos têm MAXc elementos cada um, portanto basta retornar a seguinte conta
	return numberOfLinkedCLists * MAXc + stack.sp;
}


/* Pergunta 4
* Esta função faz o reverse à stack utilizando as funções push e pop implementadas.
*/
void reverse(StackC *stack){
	int stackSize = size(*stack);
	int popdedValues[stackSize];

	// Primeiro vamos retirar todos os elementos da stack, e armazená-los num array
	for(int i = 0; i < stackSize; i++){
		pop(stack, &popdedValues[i]);
	}

	// Depois percorremos o array, e fazemos push dos seus valores. Isto vai colocar os valores na stack pela ordem inversa que tinha antes
	for(int i = 0; i < stackSize; i++){
		push(stack, popdedValues[i]);
	}
}


// Função auxiliar para buscar um valor numa determinada posição da stack (para a pergunta 5)
int getValueInPosition(StackC stack, int position){
	CList currentArray = stack.valores;
	int limit = stack.sp;

	while(position >= limit){
		currentArray = currentArray->prox;
		position -= limit;
		limit = MAXc;
	}

	return currentArray->vs[limit - 1 - position];
}


// Função auxiliar para fazer set de um valor numa determinada posição da stack (para a pergunta 5)
void setValueInPosition(StackC *stack, int position, int value){
	CList currentArray = stack->valores;
	int limit = stack->sp;

	while(position >= limit){
		currentArray = currentArray->prox;
		position -= limit;
		limit = MAXc;
	}

	currentArray->vs[limit - 1 - position] = value;
}


/* Pergunta 5
* Esta função faz o reverse da stack sem utilizar as funções push e pop. Não percebi muito bem o que o professor quis dizer com
* "que reutiliza as células da lista". Creio que isso apenas é para dizer para não usar o push e o pop. O que eu fiz foi simplesmente
* trocar o primeiro valor pelo último, o segundo pelo penúltimo, etc.
*/
void alternativeReverse(StackC *stack){
	int beginning = 0, end = size(*stack) - 1;
	int aux;

	while(beginning < end){
		aux = getValueInPosition(*stack, beginning);
		setValueInPosition(stack, beginning++, getValueInPosition(*stack, end));
		setValueInPosition(stack, end--, aux);
	}
}



int main(void){
	// Inicializacao da stack. Inicialmente o valor em sp é 0, porque nao tem nenhum valor.
	StackC stack;
	stack.sp = 0;

	CList clist = malloc(sizeof(struct chunk));
	clist->prox = NULL;
	stack.valores = clist;

	// Passa um apontador para a stack, para que possamos mudar o seu valor (passar o objecto por referência). Esta funcao vai
	// colocar os valores dados no teste na stack.
	initializeStack(&stack);

	// Imprime a stack, tal como é dada no teste, e o seu tamanho.
	printf("Initialized stack: \n");
	printStack(&stack);
	printf("Current size: %d\n", size(stack));



	// Variável que terá o último valor retirado da stack.
	int popedValue;

	// Retira o primeiro valor da stack. É passado apontadores para ambas stack e vairável 'popedValue', para que possamos
	// modificar as variáveis (a stack terá menos um valor, e a variável terá esse valor)
	pop(&stack, &popedValue);
	printf("\n\nPopedValue: %d\nNew state of the stack:\n", popedValue);
	printStack(&stack);
	printf("Current size: %d\n", size(stack));

	pop(&stack, &popedValue);
	printf("\n\nPopedValue: %d\nNew state of the stack:\n", popedValue);
	printStack(&stack);
	printf("Current size: %d\n", size(stack));

	pop(&stack, &popedValue);
	printf("\n\nPopedValue: %d\nNew state of the stack:\n", popedValue);
	printStack(&stack);
	printf("Current size: %d\n", size(stack));


	// Faz o reverse da stack, utilizando as funcoes push e pop implementadas
	reverse(&stack);
	printf("\n\nReversed stack: \n");
	printStack(&stack);
	printf("Current size: %d\n", size(stack));


	// Faz o reverse da stack apenas trocando valores (o primeiro pelo último, o segundo pelo penúltimo, etc.)
	alternativeReverse(&stack);
	printf("\n\nAlternative reversed stack: \n");
	printStack(&stack);
	return 0;
}