#ifndef QUEUE_H
#define QUEUE_H

#include <cstdint>
#include <new>
#include <print>
#include <format>
#include <expected>

/// @brief Default initial capacity for the queue
#define DEFAULT_QUEUE_SIZE 4

/**
 * @enum QueueErr
 * @brief Represents possible error states for queue operations
 */
enum class QueueErr {
    ok,         ///< Operation successful
    bad_alloc,  ///< Memory allocation failed
    empty,      ///< Queue is empty
};

/**
 * @class Queue
 * @brief A dynamically resizing circular queue implementation
 * 
 * @tparam T Type of elements stored in the queue. Must be formattable.
 */
template <typename T>
requires std::formattable<T, char>
class Queue {
private:
    uint64_t len;   ///< Current number of elements
    uint64_t cap;   ///< Current capacity
    uint64_t head;  ///< Index of next insertion
    uint64_t tail;  ///< Index of next removal
    T *data;        ///< Pointer to dynamically allocated array

public:
    /**
     * @brief Default constructor
     * Initializes the queue with DEFAULT_QUEUE_SIZE capacity
     */
    Queue();

    /**
     * @brief Constructor with custom size
     * @param size Initial capacity of the queue
     */
    Queue(uint64_t size);

    /**
     * @brief Destructor
     * Frees allocated memory
     */
    ~Queue();

    /**
     * @brief Inserts an element at the end of the queue
     * @param value Value to insert
     * @return QueueErr Status of the operation
     */
    QueueErr enqueue(T value);

    /**
     * @brief Returns the front element without removing it
     * @return std::expected<T, QueueErr> Value or error if empty
     */
    std::expected<T, QueueErr> peek();

    /**
     * @brief Removes and returns the front element
     * @return std::expected<T, QueueErr> Value or error if empty
     */
    std::expected<T, QueueErr> dequeue();

    /**
     * @brief Prints a visual representation of the queue
     */
    void print();
};

template <typename T>
requires std::formattable<T, char>
Queue<T>::Queue() {
    this->cap = DEFAULT_QUEUE_SIZE;
    this->len = 0;
    this->head = 0;
    this->tail = 0;
    this->data = new T[DEFAULT_QUEUE_SIZE];
}

template <typename T>
requires std::formattable<T, char>
Queue<T>::Queue(uint64_t size) {
    this->cap = size;
    this->len = 0;
    this->head = 0;
    this->tail = 0;
    this->data = new T[size];
}

template <typename T>
requires std::formattable<T, char> 
Queue<T>::~Queue() {
    delete[] this->data;
    this->cap = 0;
    this->len = 0;
    this->head = 0;
    this->tail = 0;
}

template <typename T>
requires std::formattable<T, char>
QueueErr Queue<T>::enqueue(T value) {
    /// Resize if needed
    if (this->len >= this->cap) {
        uint64_t new_cap = this->cap * 2;
        T *tmp;

        try {
            tmp = new T[new_cap];
        } catch(const std::bad_alloc& e) {
            return QueueErr::bad_alloc;
        }

        /// Copy elements in correct order
        for (uint64_t i = 0; i < this->len; i++) {
            uint64_t index = (this->tail + i) % this->cap;
            tmp[i] = this->data[index];
        }

        delete[] this->data;
        this->data = tmp;
        this->cap = new_cap;
        this->tail = 0;
        this->head = this->len;
    }

    this->data[this->head] = value;
    this->len++;
    this->head = (this->head + 1) % this->cap;

    return QueueErr::ok;
}

template <typename T>
requires std::formattable<T, char>
std::expected<T, QueueErr> Queue<T>::dequeue() {
    /// Check if empty
    if (this->len == 0) {
        return std::unexpected(QueueErr::empty);
    }

    /// Shrink if too sparse
    if (this->cap > DEFAULT_QUEUE_SIZE && this->cap / 4 > this->len) {
        uint64_t new_cap = this->cap / 2;
        if (new_cap < DEFAULT_QUEUE_SIZE) {
            new_cap = DEFAULT_QUEUE_SIZE;
        }

        T *tmp;
        try {
            tmp = new T[new_cap];
        } catch(const std::bad_alloc& e) {
            return std::unexpected(QueueErr::bad_alloc);
        }

        /// Copy elements
        for (uint64_t i = 0; i < this->len; i++) {
            uint64_t index = (this->tail + i) % this->cap;
            tmp[i] = this->data[index];
        }

        delete[] this->data;
        this->data = tmp;
        this->cap = new_cap;
        this->tail = 0;
        this->head = this->len;
    }

    T out = this->data[this->tail];

    this->len--;
    this->tail = (this->tail + 1) % this->cap;

    return out;
}

template <typename T>
requires std::formattable<T, char>
std::expected<T, QueueErr> Queue<T>::peek() {
    /// Check if empty
    if (this->len == 0) {
        return std::unexpected(QueueErr::empty);
    }

    return this->data[this->tail];
}

template <typename T>
requires std::formattable<T, char>
void Queue<T>::print() {
    /// Print queue state
    if (this->len == 0) {
        std::println("Queue is empty.");
        return;
    }

    std::println("Length: {}", this->len);
    std::println("Capacity: {}", this->cap);

    for (uint64_t i = 0; i < this->cap; i++) {
        if (i == this->tail && i == this->head) {
            std::print("H/T --->");
        } else if (i == this->tail) {
            std::print("Tail--->");
        } else if (i == this->head) {
            std::print("Head--->");
        } else {
            std::print("        ");
        }

        uint64_t dist = (i + this->cap - this->tail) % this->cap;

        if (dist < this->len) {
            std::println("|{:^20}|", this->data[i]);
        } else {
            std::println("|{:^20}|", "");
        }    
    }
}

#endif // !QUEUE_H