ds.h

Go to the documentation of this file.

// Copyright 2024 Markus Anders
// This file is part of dejavu 2.0.
// See LICENSE for extended copyright information.
 
#ifndef DEJAVU_DS_H
#define DEJAVU_DS_H
 
#include <list>
#include <iostream>
#include <cstring>
#include <functional>
#include <algorithm>
#include <cassert>
#include "utility.h"
#include "coloring.h"
 
namespace dejavu {
 
    namespace ds {
 
        template<class T>
        void inline sort_t(T *arr, int sz) {
            std::sort(arr, arr + sz);
        }
 
        template<class T>
        class stack_t {
        private:
            std::vector<T> queue;
        public:
            void add(T &t) {
                queue.emplace_back(t);
            }
 
            void reserve(int n) {
                queue.reserve(n);
            }
 
            bool empty() {
                return queue.empty();
            }
 
            T pop() {
                auto element = queue.back();
                queue.pop_back();
                return element;
            }
        };
 
        template<class T>
        class worklist_t {
        private:
            void alloc(const int size) {
                dealloc();
                arr = new T[size];
                arr_sz = size;
            }
 
            void dealloc() {
                //if(arr) free(arr);
                if(arr) delete[] arr;
                arr = nullptr;
            }
 
        public:
            worklist_t() = default;
 
            worklist_t(const worklist_t<T>& other) {
                copy(&other);
            }
 
            worklist_t(const worklist_t<T>&& other) {
                swap(other);
            }
 
            worklist_t<T>& operator=(const worklist_t<T>& other) {
                if(other.arr == arr) return *this;
                copy(&other);
                return *this;
            }
 
            explicit worklist_t(int size) {
                dej_assert(size >= 0);
                allocate(size);
            }
 
            void swap(worklist_t<T>& other) {
                auto swap_arr = arr;
                auto swap_arr_sz = arr_sz;
                auto swap_cur_pos = cur_pos;
                arr = other.arr;
                arr_sz = other.arr_sz;
                cur_pos = other.cur_pos;
                other.arr = swap_arr;
                other.arr_sz = swap_arr_sz;
                other.cur_pos = swap_cur_pos;
            }
 
            void copy(const worklist_t<T>* other) {
                alloc(other->arr_sz);
                for(int i = 0; i < other->arr_sz; ++i) {
                    arr[i] = other->arr[i];
                }
                arr_sz  = other->arr_sz;
                cur_pos = other->cur_pos;
            }
 
            void allocate(int size) {
                dej_assert(size >= 0);
                alloc(size);
                cur_pos = 0;
            }
 
            inline void push_back(T value) {
                dej_assert(cur_pos >= 0 && cur_pos < arr_sz);
                arr[cur_pos] = value;
                cur_pos += 1;
            }
 
            inline T pop_back() {
                dej_assert(cur_pos > 0);
                return arr[--cur_pos];
            }
 
            inline T *last() const {
                return &arr[cur_pos - 1];
            }
 
            dej_nodiscard bool empty() const {
                return cur_pos == 0;
            }
 
            void set_size(const int size) {
                cur_pos = size;
            }
 
            dej_nodiscard int size() const {
                return cur_pos;
            }
 
            inline void reset() {
                cur_pos = 0;
            }
 
            int max() {
                int max_val = arr[0];
                for(int i = 1; i < cur_pos; ++i) {
                    const int val = arr[i];
                    if(val > max_val) max_val = val;
                }
                return max_val;
            }
 
            void resize(const int size) {
                dej_assert(size >= 0);
                if (arr && size <= arr_sz) return;
                T *old_arr = nullptr;
                int old_arr_sz = arr_sz;
                if (arr) old_arr = arr;
                arr = nullptr;
                alloc(size);
                if (old_arr != nullptr) {
                    int cp_pt = std::min(old_arr_sz, arr_sz);
                    memcpy(arr, old_arr, cp_pt * sizeof(T));
                    delete[] old_arr;
                }
            }
 
            ~worklist_t() {
                dealloc();
            }
 
            void sort() {
                sort_t<T>(arr, cur_pos);
            }
 
            inline T *get_array() const {
                return arr;
            }
 
            inline T &operator[](int index) const {
                dej_assert(index >= 0);
                dej_assert(index < arr_sz);
                return arr[index];
            }
 
            void sort_after_map(T *map) {
                struct comparator_map {
                    T *map;
 
                    explicit comparator_map(T *m) {
                        this->map = m;
                    }
 
                    bool operator()(const T &a, const T &b) {
                        return map[a] < map[b];
                    }
                };
                comparator_map c = comparator_map(map);
                std::sort(arr, arr + cur_pos, c);
            }
 
            int cur_pos = 0; 
        private:
            int arr_sz = 0;       
            T *arr     = nullptr; 
        };
 
        typedef worklist_t<int> worklist;
 
        class workspace {
        private:
            void alloc(const int size) {
                dej_assert(size >= 0);
                dealloc();
                arr = (int*) calloc(size, sizeof(int));
                arr_sz = size;
            }
 
            void dealloc() {
                if(arr) free(arr);
                arr = nullptr;
            }
 
        public:
            workspace() = default;
 
            explicit workspace(int size) {
                allocate(size);
            }
 
            workspace(const workspace& other)  {
                copy(other);
            }
 
            workspace& operator=(const workspace& other) {
                if(other.arr == arr) return *this;
                copy(other);
                return *this;
            }
 
            workspace& operator=(workspace&& other) {
                swap(other);
                return *this;
            }
 
            void swap(workspace& other) {
                auto swap_arr = arr;
                auto swap_arr_sz = arr_sz;
                arr = other.arr;
                arr_sz = other.arr_sz;
                other.arr = swap_arr;
                other.arr_sz = swap_arr_sz;
            }
 
            void copy(const workspace& other) {
                alloc(other.arr_sz);
                memcpy(arr, other.arr, other.arr_sz  * sizeof(int));
                arr_sz  = other.arr_sz;
            }
 
            void allocate(int size) {
                alloc(size);
            }
 
            inline void reset() {
                memset(arr, 0, arr_sz * sizeof(int));
            }
 
            void resize(const int size) {
                dej_assert(size >= 0);
                if (arr && size <= arr_sz) return;
                int *old_arr = arr;
                arr = nullptr;
                int old_arr_sz = arr_sz;
                alloc(size);
                if (old_arr) {
                    int cp_pt = std::min(old_arr_sz, arr_sz);
                    memcpy(arr, old_arr, cp_pt * sizeof(int));
                    free(old_arr);
                }
            }
 
            ~workspace() {
                dealloc();
            }
 
            dej_nodiscard inline int* get_array() const {
                return arr;
            }
 
            inline int &operator[](int index) const {
                dej_assert(index >= 0);
                dej_assert(index < arr_sz);
                return arr[index];
            }
 
        private:
            int arr_sz = 0;     
            int *arr = nullptr; 
        };
 
 
        template<class T>
        class workset_t {
        public:
            workset_t() = default;
 
            explicit workset_t(int size) {
                initialize(size);
            }
 
            void initialize(int size) {
                s = new T[size];
                reset_queue.allocate(size);
 
                memset(s, -1, size * sizeof(T));
 
                init = true;
                sz = size;
            }
 
            void set(int index, T value) {
                dej_assert(index >= 0);
                dej_assert(index < sz);
                s[index] = value;
            }
 
            T get(int index) {
                dej_assert(index >= 0);
                dej_assert(index < sz);
                return s[index];
            }
 
            void reset() {
                while (!reset_queue.empty()) s[reset_queue.pop_back()] = -1;
            }
 
            void reset_hard() {
                memset(s, -1, sz * sizeof(T));
                reset_queue.reset();
            }
 
            T inc(int index) {
                dej_assert(index >= 0);
                dej_assert(index < sz);
                if (s[index]++ == -1)
                    reset_queue.push_back(index);
                return s[index];
            }
 
            void inline inc_nr(int index) {
                dej_assert(index >= 0 && index < sz);
                ++s[index];
            }
 
            ~workset_t() {
                if (init)
                    delete[] s;
            }
 
            worklist reset_queue;
        private:
            bool init = false;
            T   *s = nullptr;
            int sz = 0;
        };
 
        typedef workset_t<int> work_set_int;
 
        class markset {
            int *s   = nullptr;
            int mark = 0;
            int sz = 0;
 
            void full_reset() {
                memset(s, mark, sz * sizeof(int));
            }
 
        public:
            markset() = default;
 
            markset(const markset& other)  {
                copy(&other);
            }
 
            markset(markset&& other)  {
                swap(other);
            }
 
            markset& operator=(const markset& other) {
                if(other.s == s) return *this;
                copy(&other);
                return *this;
            }
 
            explicit markset(int size) {
                initialize(size);
            }
 
            void initialize(int size) {
                dej_assert(size >= 0);
                if(s && sz == size) {
                    reset();
                    return;
                }
                if(s) free(s);
                s = (int*) calloc((unsigned int) size, sizeof(int));
                sz   = size;
                mark = 0;
                reset();
            }
 
            inline bool get(int pos) {
                dej_assert(pos >= 0);
                dej_assert(pos < sz);
                return s[pos] == mark;
            }
 
            inline void set(int pos) {
                dej_assert(pos >= 0);
                dej_assert(pos < sz);
                s[pos] = mark;
            }
 
            inline void unset(int pos) {
                dej_assert(pos >= 0);
                dej_assert(pos < sz);
                s[pos] = mark - 1;
            }
            void reset() {
                if(mark == -1) full_reset();
                ++mark;
            }
 
            void swap(markset& other) {
                auto swap_s = s;
                auto swap_mark = mark;
                auto swap_sz = sz;
                s = other.s;
                mark = other.mark;
                sz = other.sz;
                other.s = swap_s;
                other.mark = swap_mark;
                other.sz = swap_sz;
            }
 
            void copy(const markset* other) {
                initialize(other->sz);
                for(int i = 0; i < other->sz; ++i) {
                    s[i] = other->s[i];
                }
                mark = other->mark;
                sz   = other->sz;
            }
 
            ~markset() {
                if(s) free(s);
            }
        };
 
//        static void bucket_sort(worklist& list,  markset& buckets, int limit) {
//            buckets.reset();
//            for(int i = 0; i < list.size(); ++i) buckets.set(list[i]);
//            list.reset();
//            for(int i = 0; i <= limit; ++i) if(buckets.get(i)) list.push_back(i);
//            buckets.reset();
//        }
    }
}
 
#endif //DEJAVU_DS_H