Because C++ maybe be influenza, but STL is cancer

templates.hpp

/*
 * Creator: Naman Dixit
 * Notice: © Copyright 2024 Naman Dixit
 * License: MIT No Attribution
 * SPDX: MIT-0 (https://spdx.org/licenses/MIT-0.html)
 */

#pragma once

template<typename T>
const T& max (const T& a, const T& b)
{
    return (a < b) ? b : a;
}

template<typename T>
const T& min (const T& a, const T& b)
{
    return (a > b) ? b : a;
}

template<class T>
T* addressof(T& arg) noexcept
{
    return reinterpret_cast<T*>(&const_cast<char&>(reinterpret_cast<const volatile char&>(arg)));
}

template<typename T>
constexpr const T& clamp(const T& val, const T& min, const T& max)
{
    return val < min ? min : val > max ? max : val;
}

template<typename T, Memory_Allocator *Alloc>
struct Vector {
    Memory_Allocator *alloc;

    Size cap = 0; // NOTE(naman): Maximum number of elements that can be stored
    Size len = 0; // NOTE(naman): Count of elements actually stored
    T *buf = nullptr;

    void init_ () {
        cap = 0;
        len = 0;
        buf = nullptr;

        if constexpr (Alloc == nullptr) {
            alloc = memGetHeap();
        } else {
            alloc = Alloc;
        }
    }

    Vector() {
        init_();
    }

    Vector(Size elems) {
        init_();

        GrowToCap(elems);
    }

    Vector(Vector &t) {
        cap = t.cap;
        len = t.len;
        buf = t.buf;
        alloc = t.alloc;
    }

    ~Vector () {
        for (Size i = 0; i < cap; i++) {
            (addressof(buf[i]))->~T();
        }
        memDealloc(alloc, buf);
        cap = 0;
        len = 0;
    }

    T& operator[] (Size index) const {
        return buf[index];
    }

    void AddInPlace_ (Size index, T elem) {
        buf[index] = elem;
    }

    Bool IsFull_ () {
        return len + 1 > cap;
    }

    void Grow () {
        GrowToCap(2 * cap);
    }

    void Add (T elem) {
        if (unlikely(IsFull_())) Grow();
        buf[len] = elem;
        len++;
    }

    void RemoveUnsorted (Size index) {
        buf[index] = buf[len - 1];
        len--;
    }

    void Clear () {
        memset(buf, 0, len * sizeof(T));
        len = 0;
    }

    void Resize (Size new_count) {
        if (new_count > cap) {
            GrowToCap(new_count);
        }
    }

    Size SizeOf    () { return len * sizeof(T); }
    Size ElemIn    () { return len;             }
    Size MaxSizeOf () { return cap * sizeof(T); }
    Size MaxElemIn () { return cap * sizeof(T); }

    Bool IsEmpty    () { return len == 0;       }
    Bool IsNotEmpty () { return !IsEmpty();     }
    Bool IsNull     () { return buf == nullptr; }

    T* PtrOnePastLast () {
        return buf + len;
    }

    T* PtrLast () {
        return buf + (len - 1);
    }

    T* PtrFirst () {
        return buf;
    }

    void GrowToSize_ (Size new_size) {
        if (IsNull()) {
            buf = static_cast<T*>(memAlloc(alloc, new_size));
        } else {
            buf = static_cast<T*>(memRealloc(alloc, buf, new_size));
        }
    }

    void GrowToCap (Size elem_count) {
        Size new_cap = max(elem_count, 16ULL);
        GrowToSize_(new_cap * sizeof(T));
        for (Size i = cap; i < new_cap; i++) {
            new (addressof(buf[i])) T();
        }
        cap = new_cap;
    }

    void IncreaseCapBy (Size elem_count) {
        Size new_cap = max(elem_count + len, 16ULL);
        GrowToCap(new_cap);
        cap = new_cap;
    }
};

template<typename T, Memory_Allocator *Alloc>
struct Stack {
    Vector<T, Alloc> data;

    void Push (T elem) {
        data.Add(elem);
    }

    T Peek () {  // NOTE(naman): Check if stack is empty before calling
        T elem = *data.PtrLast();
        return elem;
    }

    T Pop () { // NOTE(naman): Check if stack is empty before calling
        T elem = Peek();
        data.len--;
        return elem;
    }

    Bool IsEmpty () {
        return data.IsEmpty();
    }

    Bool IsNotEmpty () {
        return !IsEmpty();
    }

    Size ElemIn () {
        return data.ElemIn();
    }
};

// TODO(naman): Convert this from two-stack approach to some better (more performant) one.
// Right now, the amortized time is constant, but it's not real-time.
template<typename T, Memory_Allocator *Alloc>
struct Queue { // Double Ended
    Stack<T, Alloc> head, tail;

    void PushFront (T elem) {
        head.Push(elem);
    }

    T PeekFront () {  // NOTE(naman): Check if queue is empty before calling
        if (head.IsEmpty()) {
            claim(tail.IsEmpty() == false);
            Size iter = max(1ULL, tail.ElemIn() / 2);
            for (Size i = 0; i < iter; i++) {
                head.Push(tail.Pop());
            }
        }

        return head.Peek();
    }

    T PopFront () { // NOTE(naman): Check if queue is empty before calling
        PeekFront();
        return head.Pop();
    }

    void PushBack (T elem) {
        tail.Push(elem);
    }

    T PeekBack () { // NOTE(naman): Check if queue is empty before calling
        if (tail.IsEmpty()) {
            claim(head.IsEmpty() == false);
            Size iter = max(1, head.ElemIn() / 2);
            for (Size i = 0; i < iter; i++) {
                tail.Push(head.Pop());
            }
        }

        return tail.Peek();
    }

    T PopBack () { // NOTE(naman): Check if queue is empty before calling
        PeekBack();
        return tail.Pop();
    }

    Bool IsEmpty () {
        return head.IsEmpty() && tail.IsEmpty();
    }

    Bool IsNotEmpty () {
        return !IsEmpty();
    }

    Size ElemIn () {
        return head.ElemIn() + tail.ElemIn();
    }
};