diff options
author | Yuri Gorshenin <y@maps.me> | 2017-06-30 13:00:28 +0300 |
---|---|---|
committer | Arsentiy Milchakov <milcars@mapswithme.com> | 2017-07-04 14:09:45 +0300 |
commit | f8aeb3711100c875e718b952d8a42442030d02af (patch) | |
tree | 7b36bea7a742022b18ef43c7ee4ac3de5f0ab9a0 /base | |
parent | 043cc3623ae4a22557b7c9738d3c7e6d5cabbb0a (diff) |
[base][coding] Burrows-Wheeler coder.
Diffstat (limited to 'base')
-rw-r--r-- | base/CMakeLists.txt | 2 | ||||
-rw-r--r-- | base/base.pro | 2 | ||||
-rw-r--r-- | base/base_tests/CMakeLists.txt | 1 | ||||
-rw-r--r-- | base/base_tests/base_tests.pro | 1 | ||||
-rw-r--r-- | base/base_tests/move_to_front_tests.cpp | 32 | ||||
-rw-r--r-- | base/move_to_front.cpp | 33 | ||||
-rw-r--r-- | base/move_to_front.hpp | 25 | ||||
-rw-r--r-- | base/suffix_array.cpp | 2 |
8 files changed, 97 insertions, 1 deletions
diff --git a/base/CMakeLists.txt b/base/CMakeLists.txt index fe64857e8a..3db7f7afa9 100644 --- a/base/CMakeLists.txt +++ b/base/CMakeLists.txt @@ -36,6 +36,8 @@ set( math.hpp matrix.hpp mem_trie.hpp + move_to_front.cpp + move_to_front.hpp mutex.hpp newtype.hpp normalize_unicode.cpp diff --git a/base/base.pro b/base/base.pro index cb2cdd8888..64f3336cb0 100644 --- a/base/base.pro +++ b/base/base.pro @@ -18,6 +18,7 @@ SOURCES += \ levenshtein_dfa.cpp \ logging.cpp \ lower_case.cpp \ + move_to_front.cpp \ normalize_unicode.cpp \ pprof.cpp \ random.cpp \ @@ -63,6 +64,7 @@ HEADERS += \ math.hpp \ matrix.hpp \ mem_trie.hpp \ + move_to_front.hpp \ mutex.hpp \ newtype.hpp \ observer_list.hpp \ diff --git a/base/base_tests/CMakeLists.txt b/base/base_tests/CMakeLists.txt index 277983f38d..ad29bf1f97 100644 --- a/base/base_tests/CMakeLists.txt +++ b/base/base_tests/CMakeLists.txt @@ -17,6 +17,7 @@ set( math_test.cpp matrix_test.cpp mem_trie_test.cpp + move_to_front_tests.cpp newtype_test.cpp observer_list_test.cpp range_iterator_test.cpp diff --git a/base/base_tests/base_tests.pro b/base/base_tests/base_tests.pro index 1f2025da66..501e9d1e3a 100644 --- a/base/base_tests/base_tests.pro +++ b/base/base_tests/base_tests.pro @@ -28,6 +28,7 @@ SOURCES += \ math_test.cpp \ matrix_test.cpp \ mem_trie_test.cpp \ + move_to_front_tests.cpp \ observer_list_test.cpp \ range_iterator_test.cpp \ ref_counted_tests.cpp \ diff --git a/base/base_tests/move_to_front_tests.cpp b/base/base_tests/move_to_front_tests.cpp new file mode 100644 index 0000000000..a18c9e7abf --- /dev/null +++ b/base/base_tests/move_to_front_tests.cpp @@ -0,0 +1,32 @@ +#include "testing/testing.hpp" + +#include "base/move_to_front.hpp" + +#include <cstdint> + +using namespace base; + +namespace +{ +UNIT_TEST(MoveToFront_Smoke) +{ + MoveToFront mtf; + for (size_t i = 0; i < 256; ++i) + TEST_EQUAL(mtf[i], i, ()); + + // Initially 3 should be on the 3-th position. + TEST_EQUAL(mtf.Transform(3), 3, ()); + + // After the first transform, 3 should be moved to the 0-th position. + TEST_EQUAL(mtf.Transform(3), 0, ()); + TEST_EQUAL(mtf.Transform(3), 0, ()); + TEST_EQUAL(mtf.Transform(3), 0, ()); + + TEST_EQUAL(mtf[0], 3, ()); + TEST_EQUAL(mtf[1], 0, ()); + TEST_EQUAL(mtf[2], 1, ()); + TEST_EQUAL(mtf[3], 2, ()); + for (size_t i = 4; i < 256; ++i) + TEST_EQUAL(mtf[i], i, ()); +} +} // namespace diff --git a/base/move_to_front.cpp b/base/move_to_front.cpp new file mode 100644 index 0000000000..6091c3f232 --- /dev/null +++ b/base/move_to_front.cpp @@ -0,0 +1,33 @@ +#include "base/move_to_front.hpp" + +#include "base/assert.hpp" + +#include <algorithm> +#include <cstring> + +using namespace std; + +namespace base +{ +// static +size_t constexpr MoveToFront::kNumBytes; + +MoveToFront::MoveToFront() +{ + for (size_t i = 0; i < kNumBytes; ++i) + m_order[i] = i; +} + +uint8_t MoveToFront::Transform(uint8_t b) +{ + auto const it = find(m_order.begin(), m_order.end(), b); + ASSERT(it != m_order.end(), ()); + + size_t const result = distance(m_order.begin(), it); + ASSERT_LESS(result, kNumBytes, ()); + + rotate(m_order.begin(), it, it + 1); + ASSERT_EQUAL(m_order[0], b, ()); + return static_cast<uint8_t>(result); +} +} // namespace base diff --git a/base/move_to_front.hpp b/base/move_to_front.hpp new file mode 100644 index 0000000000..b4b329c687 --- /dev/null +++ b/base/move_to_front.hpp @@ -0,0 +1,25 @@ +#pragma once + +#include <array> +#include <cstdint> +#include <limits> + +namespace base +{ +class MoveToFront +{ +public: + static size_t constexpr kNumBytes = static_cast<size_t>(std::numeric_limits<uint8_t>::max()) + 1; + + MoveToFront(); + + // Returns index of the byte |b| in the current sequence of bytes, then, moves |b| + // to the first positions. + uint8_t Transform(uint8_t b); + + uint8_t operator[](uint8_t i) const { return m_order[i]; } + +private: + std::array<uint8_t, kNumBytes> m_order; +}; +} // namespace diff --git a/base/suffix_array.cpp b/base/suffix_array.cpp index d77a473f78..16d16bd0c1 100644 --- a/base/suffix_array.cpp +++ b/base/suffix_array.cpp @@ -33,7 +33,7 @@ void RadixSort(size_t numKeys, size_t const * keys, size_t numValues, Values con { auto const value = values[keys[i]]; ASSERT_LESS(value, count.size(), ()); - ++count[values[keys[i]]]; + ++count[value]; } for (size_t i = 1; i < numValues; ++i) count[i] += count[i - 1]; |