| 8 | /// Simple sparse vector for better memory usage. |
| 9 | template <class Value> |
| 10 | class SparseVector |
| 11 | { |
| 12 | succinct::rs_bit_vector m_bits; |
| 13 | std::vector<Value> m_values; |
| 14 | |
| 15 | public: |
| 16 | SparseVector() = default; |
| 17 | |
| 18 | bool Empty() const { return GetSize() == 0; } |
| 19 | uint64_t GetSize() const { return m_bits.size(); } |
| 20 | bool Has(uint64_t i) const { return m_bits[i]; } |
| 21 | Value const & Get(uint64_t i) const { return m_values[m_bits.rank(i)]; } |
| 22 | |
| 23 | size_t GetMemorySize() const { return m_values.capacity() * sizeof(Value) + m_bits.size() / 8; } |
| 24 | |
| 25 | private: |
| 26 | SparseVector(std::vector<Value> && values, succinct::bit_vector_builder & bitsBuilder) |
| 27 | : m_bits(&bitsBuilder) |
| 28 | , m_values(std::move(values)) |
| 29 | {} |
| 30 | |
| 31 | template <class T> |
| 32 | friend class SparseVectorBuilder; |
| 33 | }; |
| 34 | |
| 35 | template <class Value> |
| 36 | class SparseVectorBuilder |