Welcome to Programming and Data Structures

module;

#include <cassert>
#include <iostream>
#include <stdexcept>

export module SimpleLinkedList;

using namespace std;

///-----------------------------LIST NODE---------------------------------
export template<typename T>
struct ListNode {
    T data;
    ListNode* next = nullptr;

    // Maintain a count of active nodes for testing
    //  Not normally a part of the struct.
    //  You should NOT modify or even use this value in your code.
    static int nodeCount;

    ListNode(const T& value) {
        data = value;
        nodeCount++;
    }

    ~ListNode() {
        nodeCount--;
    }
};

template<typename T>
int ListNode<T>::nodeCount = 0;

///-----------------------------LINKED LIST---------------------------------
export template<typename T>
class SimpleLinkedList {
    // Would normally be private. Public to enable simpler unit tests.
public:
    ListNode<T>* head = nullptr;

public:
    /**
     * @brief Construct empty linked list
     */
    SimpleLinkedList();

    // Disable the default copy constructor and assignment operator to prevent
    // shallow copies
    SimpleLinkedList(const SimpleLinkedList<T>& other) = delete;
    SimpleLinkedList<T>& operator=(const SimpleLinkedList<T>& other) = delete;

    /**
     * @brief Destructor
     */
    ~SimpleLinkedList();

    /**
     * @brief Print contents of list to cout
     */
    void print() const;

    /**
     * @brief Inserts given value at head of the list
     * @param value Value to insert
     */
    void insertStart(const T& value);

    /**
     * @brief Inserts given value at end of the list
     * @param value Value to insert
     */
    void insertEnd(const T& value);

    /**
     * @brief Remove first item from list
     * @throw out_of_range if empty
     */
    void removeStart();

    /**
     * @brief Removes all values from list
     */
    void clear();

    /**
     * @brief Insert given value into list at given location
     * @param index Location to insert value
     * @throw out_of_range if index is invalid
     * @param value Value to insert
     */
    void insertAt(int index, const T& value);

    /**
     * @brief Remove item at given index from list
     * @param index Location of item to remove
     * @throw out_of_range if index is invalid
     */
    void removeAt(int index);

    /**
     * @brief Get the length of the list
     * @return int representing number of values (nodes) in list
     */
    int listSize() const;

    /**
     * @brief Gets value stored at specified index
     * @param index Location we want to retrieve from
     * @throw out_of_range if index is invalid
     * @return value
     */
    T retrieveAt(int index) const;
};

//-------------------Provided Functions-------------------------

template<typename T>
SimpleLinkedList<T>::SimpleLinkedList() {
    // Nothing to do since head is already initialized to nullptr
}

template<typename T>
SimpleLinkedList<T>::~SimpleLinkedList() {
    clear();
}

template<typename T>
void SimpleLinkedList<T>::clear() {
    while (head != nullptr) {
        // or removeStart if it is implemented
        ListNode<T>* temp = head;
        head = head->next;
        delete temp;
    }
}

template<typename T>
void SimpleLinkedList<T>::insertStart(const T& value) {
    ListNode<T>* temp = new ListNode<T>(value);

    temp->next = head; // old head is what new node points to
    head = temp;       // new node is now head
}

template<typename T>
void SimpleLinkedList<T>::print() const {
    // current will point to each element in turn
    ListNode<T>* current = head;

    while (current != nullptr) {
        cout << current->data << " "; // print current item
        current = current->next;      // advance to next
    }
    cout << endl;
}

template<typename T>
T SimpleLinkedList<T>::retrieveAt(int index) const {
    if (index < 0 || head == nullptr) {
        throw out_of_range("Index out of range");
    }

    ListNode<T>* current = head;
    for (int i = 0; i < index; i++) {
        current = current->next;
        if (current == nullptr) {
            throw std::out_of_range("Index out of range");
        }
    }
    return current->data;
}

template<typename T>
void SimpleLinkedList<T>::removeAt(int index) {
    // No bounds checking!

    // First item is special case... use removeStart for it
    if (index == 0) {
        removeStart();
        return;
    }
    ListNode<T>* current = head;
    // Move current to the node before the desired index
    for (int i = 0; i < index - 1; i++) {
        current = current->next;
    }
    ListNode<T>* toDelete = current->next;
    current->next = toDelete->next;
    delete toDelete;
}