diff options
Diffstat (limited to 'compressed_vector.hpp')
-rw-r--r-- | compressed_vector.hpp | 112 |
1 files changed, 0 insertions, 112 deletions
diff --git a/compressed_vector.hpp b/compressed_vector.hpp deleted file mode 100644 index 780a563..0000000 --- a/compressed_vector.hpp +++ /dev/null @@ -1,112 +0,0 @@ -//Chris Xiong 2022 -//License: MPL-2.0 -#ifndef COMPRESSED_VECTOR -#define COMPRESSED_VECTOR - -#include <cstdint> -#include <cstddef> -#include <cassert> -#include <vector> - -#include "base64.hpp" - -template <class T, int B> -struct compressed_vector_hash; - -/*limitations: - * current implementation never returns a reference - */ -template <class T, int B> -class compressed_vector -{ - static_assert(std::is_unsigned<T>::value); - static_assert(sizeof(T) * 8 >= B); - static_assert(B > 0 && B < 64); -private: - const int P = 64 / B; - const uint64_t M = (1 << B) - 1; - std::vector<uint64_t> v; - size_t sz; -public: - compressed_vector() : sz(0) {} - void push_back(T val) - { - //assert(v <= M); - if (sz % P == 0) - v.push_back(0); - set(sz++, val); - } - void pop_back() - { - //assert(sz > 0); - if (--sz % P == 0) - v.pop_back(); - else - //zero out the now unused bits - v[sz / P] &= ~(M << (sz % P * B)); - } - T front() const {return get(0);} - T back() const {return get(sz - 1);} - T get(size_t i) const - { - assert(i < sz && (i / P) < v.size()); - return (T)((v[i / P] >> (i % P * B)) & M); - } - void set(size_t i, T val) - { - assert(i < sz && (i / P) < v.size()); - v[i / P] &= ~(M << (i % P * B)); - v[i / P] |= ((uint64_t) val) << (i % P * B); - } - size_t size() const - { - return sz; - } - void clear() - { - sz = 0; - v.clear(); - } - - bool operator ==(const compressed_vector& other) const - { - return sz == other.sz && v == other.v; - } - - // unsafe stuff! potentially invariant-breaking. only use for data exchanging. - void internal_container_resize(size_t ds) - { - v.resize(ds); - } - size_t internal_container_size() - { - return v.size(); - } - void* internal_data() - { - return v.data(); - } - void internal_set_size(int sz) - { - this->sz = sz; - } - - friend struct compressed_vector_hash<T, B>; -}; - -template <class T, int B> -struct compressed_vector_hash -{ - size_t operator()(compressed_vector<T, B> const& s) const noexcept - { - size_t ret = 0; - //Fibonacci hashing - for (size_t i = 0; i < s.v.size(); ++i) { - ret ^= (size_t)(s.v[i] & ~0U) + 0x9e3779b9 + (ret << 6) + (ret >> 2); - ret ^= (size_t)(s.v[i] >> 32) + 0x9e3779b9 + (ret << 6) + (ret >> 2); - } - return ret; - } -}; - -#endif |