stack.spice

import "std/type/error";

// Constants
const unsigned long INITIAL_ALLOC_COUNT = 5l;
const unsigned int RESIZE_FACTOR = 2;

// Add generic type definition
type T dyn;

/**
 * A stack in Spice is a commonly used data structure, which uses the FiLo (first in, last out) principle.
 *
 * Time complexity:
 * Insert: O(1)
 * Delete: O(1)
 * Search: O(n)
 *
 * Stacks pre-allocate space using an initial size and a resize factor to not have to re-allocate
 * with every item pushed.
 */
public type Stack<T> struct {
    heap T* contents        // Pointer to the first data element
    unsigned long capacity  // Allocated number of items
    unsigned long size      // Current number of items
}

public p Stack.ctor(unsigned long initAllocItems, const T &defaultValue) {
    // Allocate space for the initial number of elements
    this.ctor(initAllocItems);
    // Fill in the default values
    for unsigned long index = 0; index < initAllocItems; index++ {
        unsafe {
            this.contents[index] = defaultValue;
        }
    }
    this.size = initAllocItems;
}

public p Stack.ctor(unsigned int initAllocItems) {
    this.ctor((unsigned long) initAllocItems);
}

public p Stack.ctor(unsigned long initAllocItems = INITIAL_ALLOC_COUNT) {
    // Allocate space for the initial number of elements
    const unsigned long itemSize = sizeof(type T) / 8l;
    unsafe {
        Result<heap byte*> allocResult = sAlloc(itemSize * initAllocItems);
        this.contents = (heap T*) allocResult.unwrap();
    }
    this.size = 0l;
    this.capacity = initAllocItems;
}

/**
 * Add an item to the stack
 */
public p Stack.push(const T& item) {
    // Check if we need to re-allocate memory
    if this.isFull() {
        this.resize(this.capacity * RESIZE_FACTOR);
    }

    // Insert the element at the back
    unsafe {
        this.contents[(int) this.size++] = item;
    }
}

/**
 * Retrieve item and remove it from the stack
 */
public f<T&> Stack.pop() {
    if this.isEmpty() { panic(Error("The stack is empty")); }
    // Pop the element from the stack
    unsafe {
        return this.contents[(int) --this.size];
    }
}

/**
 * Retrieve topmost without removing it from the stack
 */
public f<T&> Stack.top() {
    if this.isEmpty() { panic(Error("The stack is empty")); }
    // Peek the element from the stack
    unsafe {
        return this.contents[(int) this.size - 1l];
    }
}

/**
 * Retrieve the current size of the stack
 *
 * @return Current size of the stack
 */
public f<long> Stack.getSize() {
    return this.size;
}

/**
 * Retrieve the current capacity of the stack
 *
 * @return Current capacity of the stack
 */
 public f<long> Stack.getCapacity() {
     return this.capacity;
 }

/**
 * Checks if the queue contains any items at the moment
 *
 * @return Empty or not empty
 */
public f<bool> Stack.isEmpty() {
    return this.size == 0;
}

/**
 * Checks if the queue exhausts its capacity and needs to resize at the next call of push
 *
 * @return Full or not full
 */
public f<bool> Stack.isFull() {
    return this.size == this.capacity;
}

/**
 * Frees allocated memory that is not used by the queue
 */
public p Stack.pack() {
    // Return if no packing is required
    if this.isFull() { return; }
    // Pack the array
    this.resize(this.size);
}

public f<bool> operator==<T>(const Stack<T>& lhs, const Stack<T>& rhs) {
    // Compare the sizes
    if lhs.size != rhs.size { return false; }
    // Compare the contents
    for unsigned long i = 0l; index < lhs.size; i++ {
        if lhs.contents[i] != rhs.contents[i] { return false; }
    }
    return true;
}

public f<bool> operator!=<T>(const Stack<T>& lhs, const Stack<T>& rhs) {
    return !(lhs == rhs);
}

/**
 * Re-allocates heap space for the queue contents
 */
p Stack.resize(unsigned long itemCount) {
    // Allocate the new memory
    const unsigned long itemSize = sizeof(type T) / 8l;
    unsafe {
        heap byte* oldAddress = (heap byte*) this.contents;
        unsigned long newSize = (unsigned long) (itemSize * itemCount);
        Result<heap byte*> allocResult = sRealloc(oldAddress, newSize);
        this.contents = (heap T*) allocResult.unwrap();
    }
    // Set new capacity
    this.capacity = itemCount;
}