linked-list.spice

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

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

/**
 * Node of a LinkedList
 */
type Node<T> struct {
    T value
    heap Node<T>* next = nil<heap Node<T>*>
}

p Node.ctor(const T& value) {
    this.value = value;
}

/**
 * A linked list is a common, dynamically resizable data structure to store uniform data in order.
 * It is characterized by the pointer for each item, pointing to the next one.
 *
 * E.g. for a LinkedList<int>:
 * 1234 -> 4567 -> 7890 -> 4567 -> nil<int*>
 * tail                    head
 *
 * Time complexity:
 * Insert: O(1)
 * Delete: O(1)
 * Search: O(n)
 *
 * Beware that each add operation allocates memory and every remove operation frees memory.
 */
public type LinkedList<T> struct : IIterable<T> {
    heap Node<T>* tail = nil<heap Node<T>*>
    heap Node<T>* head = nil<heap Node<T>*>
    unsigned long size = 0l
}

public p LinkedList.ctor() {}

/**
 * Pushes a new item to the back of the list
 *
 * @param value Value to push
 */
public p LinkedList.pushBack(const T& value) {
    // Create new node
    heap Node<T>* newNode = this.createNode(value);

    // Insert at head
    if this.isEmpty() {
        this.head = this.tail = newNode;
    } else {
        this.head.next = newNode; // Link the new node to the previous one
        this.head = newNode; // Set the head to the new node
    }
    this.size++;
}

/**
 * Pushes a new item to the front of the list
 *
 * @param value Value to push
 */
public p LinkedList.pushFront(const T& value) {
    // Create new node
    heap Node<T>* newNode = this.createNode(value);

    // Insert at tail
    if this.isEmpty() {
        this.head = this.tail = newNode;
    } else {
        newNode.next = this.tail; // Link the next node to the new one
        this.tail = newNode; // Set the tail to the new node
    }
    this.size++;
}

/**
 * Inserts a new item at the given index
 *
 * @param idx Index to insert the new item
 * @param value Value to insert
 */
public p LinkedList.insertAt(unsigned long idx, const T& value) {
    // Abort if the index is out of bounds
    if idx < 0l || idx >= this.size { return; }

    // Create new node
    heap Node<T>* newNode = this.createNode(value);

    if this.isEmpty() {
        this.head = this.tail = newNode;
    } else if idx == 0l {
        newNode.next = this.tail; // Link the next node to the new one
        this.tail = newNode; // Set the tail to the new node
    } else {
        heap Node<T>* curr = this.tail;
        for unsigned long i = 0l; i < idx - 1l; i++ {
            curr = curr.next;
        }
        newNode.next = curr.next; // Link the next node to the new one
        curr.next = newNode; // Link the new node to the previous one
    }
    this.size++;
}

/**
 * Inserts a new item at the given index
 *
 * @param idx Index to insert the new item
 * @param value Value to insert
 */
public inline p LinkedList.insertAt(unsigned int idx, const T& value) {
    this.insertAt((unsigned long) idx, value);
}

/**
 * Removes the first occurrence of the given value
 *
 * @param valueToRemove Value to remove
 */
public p LinkedList.remove(const T& valueToRemove) {
    // Abort if the list is already empty
    if this.isEmpty() { return; }

    if this.tail.value == valueToRemove {
        heap Node<T>* temp = this.tail;
        this.tail = this.tail.next;
        unsafe {
            sDealloc((heap byte*) temp);
        }
        this.size--;
        return;
    }

    heap Node<T>* curr = this.tail;
    while curr.next != nil<heap Node<T>*> && curr.next.value != valueToRemove {
        curr = curr.next;
    }
    if curr.next == nil<heap Node<T>*> { return; }

    heap Node<T>* temp = curr.next;
    curr.next = curr.next.next;
    unsafe {
        sDealloc((heap byte*) temp);
    }

    this.size--;
}

/**
 * Removes the first occurrence of the given value
 *
 * @param valueToRemove Value to remove
 */
public p LinkedList.removeAt(unsigned long idx) {
    // Abort if the index is out of bounds
    if idx < 0l || idx >= this.size { return; }

    if idx == 0l {
        heap Node<T>* temp = this.tail;
        this.tail = this.tail.next;
        unsafe {
            sDealloc((heap byte*) temp);
        }
        this.size--;
        return;
    }

    heap Node<T>* curr = this.tail;
    for unsigned long i = 0l; i < idx - 1l; i++ {
        curr = curr.next;
    }

    heap Node<T>* temp = curr.next;
    curr.next = curr.next.next;
    unsafe {
        sDealloc((heap byte*) temp);
    }

    if idx == this.size - 1l {
        this.head = curr;
    }

    this.size--;
}

/**
 * Removes the first occurrence of the given value
 *
 * @param idx Index to remove
 */
public inline p LinkedList.removeAt(unsigned int idx) {
    this.removeAt((unsigned long) idx);
}

/**
 * Removes the first item of the list
 */
public inline p LinkedList.removeFront() {
    this.removeAt(0l);
}

/**
 * Removes the last item of the list
 */
public inline p LinkedList.removeBack() {
    this.removeAt(this.size - 1l);
}

/**
 * Returns the size of the list
 *
 * @return Size of the list
 */
public inline f<unsigned long> LinkedList.getSize() {
    return this.size;
}

/**
 * Returns if the list is empty
 *
 * @return true if the list is empty, false otherwise
 */
public inline f<bool> LinkedList.isEmpty() {
    return this.size == 0l;
}

/**
 * Returns the item at the given index
 *
 * @param idx Index to access
 * @return Reference to the item
 */
public f<T&> LinkedList.get(unsigned long idx) {
    // Abort if the index is out of bounds
    if idx < 0 || idx >= this.size { panic(Error("Access index out of bound")); }

    heap Node<T>* curr = this.tail;
    for unsigned long i = 0l; i < idx; i++ {
        curr = curr.next;
    }
    return curr.value;
}

/**
 * Returns the item at the given index
 *
 * @param idx Index to access
 * @return Reference to the item
 */
public inline f<T&> LinkedList.get(unsigned int idx) {
    return this.get((unsigned long) idx);
}

/**
 * Returns the first item of the list
 *
 * @return Reference to the first item
 */
public inline f<T&> LinkedList.getFront() {
    if this.isEmpty() { panic(Error("Access index out of bounds")); }
    return this.tail.value;
}

/**
 * Returns the last item of the list
 *
 * @return Reference to the last item
 */
public inline f<T&> LinkedList.getBack() {
    if this.isEmpty() { panic(Error("Access index out of bounds")); }
    return this.head.value;
}

/**
 * Clears the list
 */
public inline p LinkedList.clear() {
    while !this.isEmpty() {
        this.removeFront();
    }
}

f<heap Node<T>*> LinkedList.createNode(const T& value) {
    heap Node<T>* newNode;
    unsafe {
        Result<heap byte*> allocResult = sAlloc(sizeof(type Node<T>));
        newNode = (heap Node<T>*) allocResult.unwrap();
    }
    newNode.value = value;
    newNode.next = nil<heap Node<T>*>;
    return newNode;
}

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

public p LinkedListIterator.ctor<T>(LinkedList<T>& list) {
    this.list = list;
    this.cursor = 0l;
}

/**
 * Returns the current item of the vector
 *
 * @return Reference to the current item
 */
public inline f<T&> LinkedListIterator.get() {
    return this.list.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&>> LinkedListIterator.getIdx() {
    return Pair<unsigned long, T&>(this.cursor, this.list.get(this.cursor));
}

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

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

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

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

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

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

/**
 * Retrieve an forward iterator for the linked list
 */
public f<LinkedListIterator<T>> LinkedList.getIterator() {
    return LinkedListIterator<T>(*this);
}