Store a string of symbols from a small alphabet using a vector of * BitArray. */
| 15 | * BitArray. |
| 16 | */ |
| 17 | class BitArrays |
| 18 | { |
| 19 | /** A symbol. */ |
| 20 | typedef uint8_t T; |
| 21 | |
| 22 | /** The sentinel symbol. */ |
| 23 | static T SENTINEL() { return std::numeric_limits<T>::max(); } |
| 24 | |
| 25 | public: |
| 26 | /** Count the occurrences of the symbols of [first, last). */ |
| 27 | template<typename It> |
| 28 | void assign(It first, It last) |
| 29 | { |
| 30 | assert(first < last); |
| 31 | m_data.clear(); |
| 32 | |
| 33 | // Determine the size of the alphabet ignoring the sentinel. |
| 34 | T n = 0; |
| 35 | for (It it = first; it != last; ++it) |
| 36 | if (*it != SENTINEL()) |
| 37 | n = std::max(n, *it); |
| 38 | n++; |
| 39 | |
| 40 | assert(n < std::numeric_limits<T>::max()); |
| 41 | m_data.resize(n, wat_array::BitArray(last - first)); |
| 42 | |
| 43 | size_t i = 0; |
| 44 | for (It it = first; it != last; ++it, ++i) { |
| 45 | T c = *it; |
| 46 | if (c == SENTINEL()) |
| 47 | continue; |
| 48 | assert(c < m_data.size()); |
| 49 | m_data[c].SetBit(1, i); |
| 50 | } |
| 51 | |
| 52 | std::for_each( |
| 53 | m_data.begin(), m_data.end(), [](wat_array::BitArray& b) { return b.Build(); }); |
| 54 | } |
| 55 | |
| 56 | /** Return the size of the string. */ |
| 57 | size_t size() const |
| 58 | { |
| 59 | assert(!m_data.empty()); |
| 60 | return m_data.front().length(); |
| 61 | } |
| 62 | |
| 63 | /** Return the number of occurrences of the specified symbol. */ |
| 64 | size_t count(T c) const { return m_data[c].one_num(); } |
| 65 | |
| 66 | /** Return the count of symbol c in s[0, i). */ |
| 67 | size_t rank(T c, size_t i) const { return m_data[c].Rank(1, i); } |
| 68 | |
| 69 | /** Return the symbol at the specified position. */ |
| 70 | T at(size_t i) const |
| 71 | { |
| 72 | assert(!m_data.empty()); |
| 73 | assert(i < m_data.front().length()); |
| 74 | for (Data::const_iterator it = m_data.begin(); it != m_data.end(); ++it) |