queue.spice

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

// Add generic type definition
type T dyn;

/**
 * A queue in Spice is a commonly used data structure, which uses the FiFo (first in, first out) principle.
 *
 * Time complexity:
 * Insert: O(1)
 * Delete: O(1)
 * Search: O(n)
 *
 * Queues pre-allocate space using an initial size and a resize factor to not have to re-allocate
 * with every item pushed.
 */
public type Queue<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
    unsigned long idxFront  // Index for front access
    unsigned long idxBack   // Index for back access
}

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

}

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

public p Queue.ctor(unsigned long initAllocItems = INITIAL_ALLOC_COUNT) {
    // Allocate space for the initial number of elements
    const 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;
    this.idxFront = 0l;
    this.idxBack = 0l;
}

/**
 * Add an item at the end of the queue
 */
public p Queue.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.idxBack++] = item;
    }

    // Increase size
    this.size++;
}

/**
 * Retrieve the first item and remove it
 *
 * @return First item
 */
public f<T&> Queue.pop() {
    this.size--;
    unsafe {
        return this.contents[(int) this.idxFront++];
    }
}

/**
 * Retrieve the first item without removing it from the queue
 *
 * @return First item
 */
public f<T&> Queue.front() {
    if this.isEmpty() { panic(Error("Access index out of bounds")); }
    unsafe {
        return this.contents[(int) this.idxFront];
    }
}

/**
 * Retrieve the last item without removing it from the queue
 *
 * @return Last item
 */
public f<T&> Queue.back() {
    if this.isEmpty() { panic(Error("Access index out of bounds")); }
    unsafe {
        return this.contents[(int) this.idxBack];
    }
}

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

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

/**
 * Checks if the queue contains any items at the moment
 *
 * @return Empty or not empty
 */
public f<bool> Queue.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> Queue.isFull() {
    return this.size == this.capacity;
}

/**
 * Reserves `itemCount` items
 */
public p Queue.reserve(unsigned long itemCount) {
    if itemCount > this.capacity {
        this.resize(itemCount);
    }
}

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

public f<bool> operator==<T>(const Queue<T>& lhs, const Queue<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 Queue<T>& lhs, const Queue<T>& rhs) {
    return !(lhs == rhs);
}

/**
 * Re-allocates heap space for the queue contents
 */
p Queue.resize(unsigned long itemCount) {
    // Allocate the new memory
    const 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;
}