83 lines
2.0 KiB
C
83 lines
2.0 KiB
C
//
|
|
// Created by nano on 4/30/25.
|
|
//
|
|
|
|
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
#include "stack.h"
|
|
|
|
#include <limits.h>
|
|
#include <math.h>
|
|
|
|
void stack_init(stack *stack) {
|
|
stack -> length = 0;
|
|
stack -> size = 1;
|
|
stack -> data = calloc(stack->size,sizeof(cell));
|
|
}
|
|
|
|
void stack_free(stack *stack) {
|
|
free(stack -> data);
|
|
stack->size = 0;
|
|
stack->length = 0;
|
|
}
|
|
|
|
void stack_reinit(stack *stack) {
|
|
stack_free(stack);
|
|
stack_init(stack);
|
|
}
|
|
|
|
void stack_expand(stack *stack) {
|
|
stack -> size = stack -> size *2;
|
|
cell *new_data = calloc(stack -> size ,sizeof(cell));
|
|
memcpy(new_data, stack -> data, stack -> size/2 * sizeof(cell));
|
|
free(stack -> data);
|
|
stack -> data = new_data;
|
|
}
|
|
|
|
void stack_push(stack *stack, cell c) {
|
|
if (stack -> length + 1 == stack -> size) {
|
|
stack_expand(stack);
|
|
}
|
|
stack -> data[stack -> length++] = c;
|
|
}
|
|
|
|
void stack_shrink(stack *stack) {
|
|
stack -> size = stack -> size / 2;
|
|
cell *new_data = calloc(stack -> size , sizeof(cell));
|
|
memcpy(new_data, stack -> data, stack -> size * sizeof(cell));
|
|
free(stack -> data);
|
|
stack -> data = new_data;
|
|
}
|
|
|
|
cell stack_pop(stack *stack) {
|
|
if (stack -> length > 0) {
|
|
const cell c = stack -> data[stack -> length - 1];
|
|
if ((stack->length - 1) == (stack->size / 2) && stack -> size/2 !=0) {
|
|
stack_shrink(stack);
|
|
}
|
|
stack -> length--;
|
|
return c;
|
|
}
|
|
return (cell) {INT_MAX,INT_MAX};
|
|
}
|
|
|
|
void stack_invert(stack *stack) {
|
|
cell *inv_data = calloc(stack -> size , sizeof(cell));
|
|
for (int i=0;i<stack->length;i++)
|
|
inv_data[stack->length -1 - i] = stack->data[i];
|
|
free(stack -> data);
|
|
stack -> data = inv_data;
|
|
}
|
|
|
|
void stack_append(const stack *from, stack *to) {
|
|
const int size = (int) pow(2, ceil(log2(to->length + from->length)));
|
|
// power of 2 which has enough space to hold all the contents of both stacks.
|
|
cell *new_data = calloc(size,sizeof(cell));
|
|
memcpy(new_data, to->data, to->length * sizeof(cell));
|
|
memcpy(new_data+to->length, from -> data, from -> length * sizeof(cell));
|
|
free(to->data);
|
|
to->data = new_data;
|
|
to->length = to->length + from -> length;
|
|
to->size = size;
|
|
} |