boilerplate.hpp initial upload
boilerplate.hpp initial upload

--- /dev/null
+++ b/include/boilerplate.hpp
@@ -1,1 +1,450 @@
+#include <cinttypes>

+#include <cstdarg>

+#include <cmath>

+#include <cwchar>

+#include <functional>

+#include <string>

+#include <random>

+#include <memory>

+

+typedef std::wstring wstring;

+typedef std::string string;

+

+typedef char c8;

+typedef wchar_t c16;

+

+const c8* _endl = "\n";

+const c16* _wendl = L"\n";

+

+typedef uint16_t u16;

+typedef int16_t s16;

+typedef uint32_t u32;

+typedef int32_t s32;

+typedef uint64_t u64;

+typedef int64_t s64;

+

+typedef float f32;

+typedef double f64;

+typedef long double f80;

+

+std::mt19937 rng;

+std::mt19937_64 rng64;

+

+template<typename...  params>

+wstring string_format( const wstring& format,  params... args )

+{

+    size_t size = swprintf( nullptr, 0, format.c_str(), args ... ) + 1; // Extra space for '\0'

+    std::unique_ptr<c16[]> buf( new c16[ size ] );

+    snwprintf( buf.get(), size, format.c_str(), args ... );

+    return wstring( buf.get(), buf.get() + size - 1 ); // We don't want the '\0' inside

+}

+

+template<typename ...  params>

+string string_format( const std::string& format,  params... args )

+{

+    size_t size = snprintf( nullptr, 0, format.c_str(), args ... ) + 1; // Extra space for '\0'

+	std::unique_ptr<c8[]> buf( new c8[ size ] );

+    snprintf( buf.get(), size, format.c_str(), args ... );

+    return string( buf.get(), buf.get() + size - 1 ); // We don't want the '\0' inside

+}

+

+void printline() {

+	printf(_endl);

+}

+

+template<typename...  params>

+void printline(const c8* format,  params... args) {

+	auto s = string_format(format, args ...);

+

+	printf(s.data());

+	printf(_endl);

+}

+

+template<typename...  params>

+void printline(const c16* format,  params... args) {

+	auto s = string_format(format, args ...);

+

+	wprintf(s.data());

+	wprintf(_wendl);

+}

+

+template<typename...  params>

+void die(s32 status, string message, params... args) {

+    if (message.length() > 0)

+    {

+        fprintf(stderr, string_format(message, args...).c_str());

+    }

+

+    exit(status);

+}

+

+template<typename...  params>

+void die(s32 status, wstring message, params... args) {

+    if (message.length() > 0)

+    {

+        fwprintf(stderr, string_format(message, args...).c_str());

+    }

+

+    exit(status);

+}

+

+void random_seed(u64 seed) {

+    rng64.seed(seed);

+}

+

+u64 random_long() {

+    return rng64();

+}

+

+u32 random_int() {

+    return (u32)(rng64() >> 32);

+}

+

+u16 random_short() {

+    return (u16)(rng64() >> 48);

+}

+

+// Produces a random integer in the range [range_min..range_max).

+s64 random_range(s64 range_min, s64 range_max) {

+    s64 width = range_max - range_min;

+

+    s64 num = rng64();

+

+    num %= width;

+

+    num += range_min;

+

+    if (num < range_min) {

+        num += width;

+    }

+

+    return num;

+}

+

+// List type valid up to 65536 members.

+template <typename T>

+struct List {

+private:

+    static bool gtFunc(T l, T r) {

+        return l > r;

+    }

+

+    static bool ltFunc(T l, T r) {

+        return l < r;

+    }

+

+	u32 ITEMS_PER_BUCKET;

+    u32 MAX_BUCKETS;

+

+    T** buckets;

+

+    u32 bucketCount;

+    u64 itemCount;

+

+    T** BucketPtr(u32 idx) {

+        if (idx >= bucketCount) {

+            die(1, L"Tried to access a list sub-array with an index greater than the current count.");

+        }

+

+        return buckets + idx;

+    }

+

+    T* GetBucket(u32 idx) {

+        return *BucketPtr(idx);

+    }

+

+    void AddBucket() {

+        u32 bucketIdx = bucketCount;

+        bucketCount++;

+

+        *BucketPtr(bucketIdx) = (T*)malloc(sizeof(T) * ITEMS_PER_BUCKET);

+    }

+

+    s64 qs_partition(u64 ltIdx, u64 rtIdx, u64 pvtIdx, bool (*comp_func)(T, T)) {

+        // Fetch the value of the pivot point.

+        T pvtVal = GetItem(pvtIdx);

+

+        T swap1, swap2;

+        // Swap the pivot point to the right-most index in the partition.

+        swap1 = GetItem(rtIdx);

+        swap2 = GetItem(pvtIdx);

+

+        SetItem(pvtIdx, swap1);

+        SetItem(rtIdx, swap2);

+

+        // Store the left-most index in the partition; later we'll increment this as we

+        // swap values left of the pivot.

+        u64 strIdx = ltIdx;

+

+        for (u64 idx = ltIdx; idx < rtIdx; idx++) {

+            //

+            if ((*comp_func)(GetItem(idx), pvtVal)) {

+                swap1 = GetItem(strIdx);

+                swap2 = GetItem(idx);

+

+                SetItem(idx, swap1);

+                SetItem(strIdx, swap2);

+

+                strIdx++;

+            }

+        }

+

+        swap1 = GetItem(rtIdx);

+        swap2 = GetItem(strIdx);

+

+        SetItem(strIdx, swap1);

+        SetItem(rtIdx, swap2);

+

+        return strIdx;

+    }

+

+    void qs_region(u64 ltIdx, u64 rtIdx, bool (*comp_func)(T, T)) {

+        if (ltIdx < rtIdx && rtIdx < Count()) {

+            // Select a random pivot point between ltIdx and rtIdx.  The location is not important,

+            // and picking randomly may provide speedup in some cases.

+            u64 pvtIdx = random_range(ltIdx, rtIdx);

+

+            // L"Sift" the array around the pivot value, and record its new location.

+            s64 newIdx = qs_partition(ltIdx, rtIdx, pvtIdx, comp_func);

+

+            // Since the L"sifted" regions are not sorted, sort them.

+            qs_region(ltIdx, newIdx - 1, comp_func);

+            qs_region(newIdx + 1, rtIdx, comp_func);

+        }

+    }

+

+public:

+    static const u32 DEFAULT_ITEMS_PER_BUCKET = 256;

+    static const u32 DEFAULT_MAX_BUCKETS = 256;

+

+    bool (*comparer)(T, T);

+

+    T* ItemPtr(u32 idx) {

+        if (idx >= ITEMS_PER_BUCKET * MAX_BUCKETS) {

+            die(1, L"Tried to access List item with index outside maximum bounds.");

+        }

+

+		u32 arIdx = idx / ITEMS_PER_BUCKET;

+        u32 lfIdx = idx % ITEMS_PER_BUCKET;

+

+        return GetBucket(arIdx) + lfIdx;

+    }

+

+    T GetItem(u32 idx) {

+        return *ItemPtr(idx);

+    }

+

+    T operator[] (const u32& idx) {

+        return GetItem(idx);

+    }

+

+    void SetItem(u32 idx, T value) {

+        *ItemPtr(idx) = value;

+    }

+

+    void AddItem(T value) {

+        u32 idx = itemCount;

+        itemCount++;

+

+        if (itemCount > ITEMS_PER_BUCKET * bucketCount) {

+            AddBucket();

+        }

+

+        *ItemPtr(idx) = value;

+    }

+

+    u64 Count() {

+        return itemCount;

+    }

+

+    u64 CurrentCapacity() {

+        return (u64)ITEMS_PER_BUCKET * (u64)bucketCount;

+    }

+

+	u64 MaxCapacity() {

+		return (u64)ITEMS_PER_BUCKET * (u64)MAX_BUCKETS;

+	}

+

+    bool IsSorted(bool (*comp_func)(T, T)) {

+        T first = GetItem(0);

+        for (u32 idx = 1; idx < Count(); idx++) {

+            if ((*comp_func)(GetItem(idx), first)) {

+                return false;

+            }

+        }

+

+        return true;

+    }

+

+    bool IsSorted(bool reversed) {

+        if (reversed) {

+            return IsSorted(&gtFunc);

+        }

+        else {

+            return IsSorted(&ltFunc);

+        }

+    }

+

+    bool IsSorted() {

+        return IsSorted(false);

+    }

+

+    void Sort(bool (*comp_func)(T, T))

+    {

+        qs_region(0, Count() - 1, comp_func);

+    }

+

+    void Sort(bool reversed) {

+        if (reversed) {

+            Sort(&gtFunc);

+        }

+        else {

+            Sort(&ltFunc);

+        }

+    }

+

+    void Sort() {

+        Sort(false);

+    }

+

+    u64 SizeOf() {

+        return sizeof(T) * bucketCount * ITEMS_PER_BUCKET;

+    }

+

+    void Clear() {

+        for (u32 bIdx = 0; bIdx < bucketCount; bIdx++) {

+            free(BucketPtr(bIdx));

+        }

+

+        bucketCount = 0;

+        itemCount = 0;

+    }

+

+    List(u32 max_buckets, u32 items_per_bucket) :

+		ITEMS_PER_BUCKET(items_per_bucket),

+        MAX_BUCKETS(max_buckets),

+        bucketCount(0),

+        itemCount(0),

+        comparer(&ltFunc)

+        {

+        buckets = (T**)malloc(sizeof(T*) * MAX_BUCKETS);

+    }

+

+    List() : List(DEFAULT_MAX_BUCKETS, DEFAULT_ITEMS_PER_BUCKET) {}

+

+	List(u64 capacity, bool contiguous_small_list) : bucketCount(0), itemCount(0), comparer(&ltFunc) {

+		if (capacity > 0xfffffffe00000001)

+		{

+			capacity = 0xfffffffe00000001;

+		}

+

+		double bit_width = std::log2(capacity);

+

+		u32 items_per_bucket, max_buckets;

+

+		if (bit_width > 62)

+		{

+			max_buckets = 0xffffffff;

+		}

+		else

+		{

+			if (contiguous_small_list && bit_width < 32)

+			{

+				max_buckets = 1;

+			}

+			else if (bit_width < 8)

+			{

+				max_buckets = 1;

+			}

+			else if (bit_width < 12)

+			{

+				max_buckets = 1 << 4;

+			}

+			else if (bit_width < 40)

+			{

+				max_buckets = 1ull << 8;

+			}

+			else if (bit_width < 46)

+			{

+				max_buckets = 1ull << 14;

+			}

+			else if (bit_width < 56)

+			{

+				max_buckets = 1ull << 24;

+			}

+			else

+			{

+				max_buckets = 1ull << ((u64)ceil(bit_width) / 2ull);

+			}

+		}

+

+		items_per_bucket = (u32)(capacity / (u64)max_buckets);

+

+		u64 real_capacity = (u64)max_buckets * (u64)items_per_bucket;

+

+		if (real_capacity < capacity && items_per_bucket < 0xffffffff) {

+			items_per_bucket++;

+			real_capacity = (u64)max_buckets * (u64)items_per_bucket;

+		}

+

+		MAX_BUCKETS = max_buckets;

+		ITEMS_PER_BUCKET = items_per_bucket;

+

+		buckets = (T**)malloc(sizeof(T*) * MAX_BUCKETS);

+

+		if (contiguous_small_list && capacity < (1ull << 32))

+		{

+			AddBucket();

+			// itemCount = items_per_bucket;

+		}

+	}

+

+    ~List() {

+        for (u32 idx = 0; idx < bucketCount; idx++) {

+            free(buckets[idx]);

+        }

+

+        free(buckets);

+    }

+};

+

+

+typedef std::function<void()> Callback;

+typedef Callback* CallbackPtr;

+

+Callback* make_callback(Callback cb) {

+    return new std::function<void()> (cb);

+}

+

+struct VacuumCleaner {

+private:

+    List<CallbackPtr> cleanup_tasks;

+

+public:

+    template <typename T>

+    void AddItem(T* item) {

+        cleanup_tasks.AddItem(make_callback([item]() {

+            delete item;

+        }

+    ));

+    }

+

+    void Clean() {

+        for (u32 idx = 0; idx < cleanup_tasks.Count(); idx++) {

+            CallbackPtr cb = cleanup_tasks.GetItem(idx);

+

+            (*cb)();

+

+            delete cb;

+        }

+

+        cleanup_tasks.Clear();

+    }

+

+    VacuumCleaner() : cleanup_tasks(List<CallbackPtr>()) {}

+

+    ~VacuumCleaner() {

+        Clean();

+    }

+};