vector.spice

import "std/iterator/iterable";
import "std/iterator/iterator";
import "std/data/pair";

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

// Add generic type definitions
type T dyn;
type UIntOrULong unsigned int|unsigned long;
type Numeric int|long|short;

/**
 * A vector in Spice is a commonly used data structure, which can be used to represent a list of items.
 *
 * Time complexity:
 * Insert: O(1)
 * Delete: O(n * m); n = deleted elements, m = moved elements
 * Search: O(n)
 *
 * Vectors pre-allocate space using an initial size and a resize factor to not have to re-allocate
 * with every item pushed.
 */
public type Vector<T> struct : IIterable<T> {
    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 Vector.ctor(unsigned long initialCapacity = INITIAL_CAPACITY) {
    // Allocate space for the initial number of elements
    const long itemSize = sizeof(type T) / 8l;
    assert itemSize != 0l;
    unsafe {
        Result<heap byte*> allocResult = sAlloc(itemSize * initialCapacity);
        this.contents = (heap T*) allocResult.unwrap();
    }
    this.size = 0l;
    this.capacity = initialCapacity;
}

public p Vector.ctor(unsigned int initialCapacity) {
    this.ctor((long) initialCapacity);
}

public p Vector.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;
}

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

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

/**
 * Add an item at the end of the vector
 */
public p Vector.pushBack<T>(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;
    }
}

/**
 * Get an item at a certain index
 *
 * @return item at index
 */
public f<T&> Vector.get(unsigned long index) {
    if index >= this.size { panic(Error("Access index out of bounds")); }
    unsafe {
        return this.contents[index];
    }
}

/**
 * Get an item at a certain index
 *
 * @return item at index
 */
public f<T&> Vector.get(unsigned int index) {
    return this.get((unsigned long) index);
}

/**
 * Remove an item at a certain index
 *
 * @param index Index of the item to remove
 */
public p Vector.removeAt(unsigned long index) {
    if index >= this.size { panic(Error("Access index out of bounds")); }
    // Move all elements after the index one to the front
    for unsigned long i = index; i < this.size - 1; i++ {
        unsafe {
            this.contents[i] = this.contents[i + 1];
        }
    }
    // Decrement the size
    this.size--;
}

/**
 * Remove an item at a certain index
 *
 * @param index Index of the item to remove
 */
public p Vector.removeAt(unsigned int index) {
    this.removeAt((unsigned long) index);
}

/**
 * Get the first item in the vector
 *
 * @return item at index 0
 */
public f<T&> Vector.front() {
    return this.get(0);
}

/**
 * Get the last item in the vector
 *
 * @return item at index size - 1
 */
public f<T&> Vector.back() {
    return this.get(this.size - 1);
}

/**
 * Removes all items from the vector
 */
public p Vector.clear() {
    this.size = 0l;
}

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

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

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

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

/**
 * Retrieve a pointer to the data of the vector
 */
public f<T*> Vector.getDataPtr() {
    unsafe {
        return (T*) this.contents;
    }
}

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

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

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

/**
 * Re-allocates heap space for the queue contents
 */
p Vector.resize(unsigned long itemCount) {
    // Allocate the new memory
    const long itemSize = sizeof(type T) / 8l;
    assert itemSize != 0l;
    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;
}

/**
 * Iterator to iterate over a vector data structure
 */
public type VectorIterator<T> struct : IIterator<T> {
    Vector<T>& vector
    unsigned long cursor
}

public p VectorIterator.ctor<T>(Vector<T>& vector) {
    this.vector = vector;
    this.cursor = 0l;
}

/**
 * Returns the current item of the vector
 *
 * @return Reference to the current item
 */
public inline f<T&> VectorIterator.get() {
    return this.vector.get(this.cursor);
}

/**
 * Returns the current index and the current item of the vector
 *
 * @return Pair of current index and reference to current item
 */
public inline f<Pair<unsigned long, T&>> VectorIterator.getIdx() {
    return Pair<unsigned long, T&>(this.cursor, this.vector.get(this.cursor));
}

/**
 * Check if the iterator is valid
 *
 * @return true or false
 */
public inline f<bool> VectorIterator.isValid() {
    return this.cursor < this.vector.getSize();
}

/**
 * Returns the current item of the vector iterator and moves the cursor to the next item
 */
public inline p VectorIterator.next() {
    if !this.isValid() { panic(Error("Calling next() on invalid iterator")); }
    this.cursor++;
}

/**
 * Advances the cursor by one
 *
 * @param it VectorIterator
 */
public inline p operator++<T>(VectorIterator<T>& it) {
    if it.cursor >= it.vector.getSize() { panic(Error("Iterator out of bounds")); }
    it.cursor++;
}

/**
 * Move the cursor back by one
 *
 * @param it VectorIterator
 */
public inline p operator--<T>(VectorIterator<T>& it) {
    if it.cursor <= 0 { panic(Error("Iterator out of bounds")); }
    it.cursor--;
}

/**
 * Advances the cursor by the given offset
 *
 * @param it VectorIterator
 * @param offset Offset
 */
public inline p operator+=<T, Numeric>(VectorIterator<T>& it, Numeric offset) {
    if it.cursor + offset >= it.vector.getSize() || it.cursor + offset < 0 { panic(Error("Iterator out of bounds")); }
    it.cursor += offset;
}

/**
 * Move the cursor back by the given offset
 *
 * @param it VectorIterator
 * @param offset Offset
 */
public inline p operator-=<T, Numeric>(VectorIterator<T>& it, Numeric offset) {
    if it.cursor - offset >= it.vector.getSize() || it.cursor - offset < 0 { panic(Error("Iterator out of bounds")); }
    it.cursor -= offset;
}

/**
 * Retrieve an forward iterator for the vector
 */
public f<VectorIterator<T>> Vector.getIterator() {
    return VectorIterator<T>(*this);
}