{"action":"created","comment":{"url":"https://api.github.com/repos/mapsme/omim/pulls/comments/46555926","id":46555926,"diff_hunk":"@@ -0,0 +1,156 @@\n+#pragma once\n+\n+#include \"bit_streams.hpp\"\n+#include \"dd_vector.hpp\"\n+#include \"varint.hpp\"\n+#include \"writer.hpp\"\n+\n+#include \"std/algorithm.hpp\"\n+#include \"std/unique_ptr.hpp\"\n+#include \"std/vector.hpp\"\n+\n+\n+/// Disk driven vector for optimal storing small values with rare big values.\n+/// Format:\n+/// 4 bytes to store vector's size\n+/// Buffer of ceil(Size * Bits / 8) bytes, e.g. vector of Bits-sized elements.\n+/// - values in range [0, (1 << Bits) - 2] stored as is\n+/// - value (1 << Bits) - 1 tells that actual value is stored in the exceptions table below.\n+/// Buffer with exceptions table, e.g. vector of (index, value) pairs till the end of the reader,\n+/// sorted by index parameter.\n+\n+template\n+<\n+  size_t Bits,                /// number of fixed bits\n+  class TReader,              /// reader with random offset read functions\n+  typename TSize = uint32_t,  /// vector index type (platform independent)\n+  typename TValue = uint32_t  /// vector value type (platform independent)\n+>\n+class FixedBitsDDVector\n+{\n+  static_assert(is_unsigned<TSize>::value, \"\");\n+  static_assert(is_unsigned<TValue>::value, \"\");\n+  // 16 - is the maximum bits count to get all needed bits in random access within uint32_t.\n+  static_assert(Bits <= 16, \"\");\n+\n+  using TSelf = FixedBitsDDVector<Bits, TReader, TSize, TValue>;\n+\n+  struct IndexValue\n+  {\n+    TSize m_index;\n+    TValue m_value;\n+    bool operator<(IndexValue const & rhs) const { return m_index < rhs.m_index; }\n+  };\n+\n+  TReader m_bits;\n+  DDVector<IndexValue, TReader, TSize> m_vector;\n+\n+#ifdef DEBUG\n+  TSize const m_size;\n+#endif\n+\n+  using TBlock = uint32_t;\n+\n+  static uint64_t AlignBytesCount(uint64_t count)\n+  {\n+    return max(count, static_cast<uint64_t>(sizeof(TBlock)));\n+  }\n+\n+  static TBlock constexpr kMask = (1 << Bits) - 1;\n+\n+  TValue FindInVector(TSize index) const\n+  {\n+    auto it = lower_bound(m_vector.begin(), m_vector.end(), IndexValue{index, 0});\n+    ASSERT(it != m_vector.end() && it->m_index == index, ());\n+    return it->m_value;\n+  }\n+\n+  FixedBitsDDVector(TReader const & bitsReader, TReader const & vecReader, TSize size)\n+    : m_bits(bitsReader)\n+    , m_vector(vecReader)\n+  #ifdef DEBUG\n+    , m_size(size)\n+  #endif\n+  {\n+  }\n+\n+public:\n+  static unique_ptr<TSelf> Create(TReader const & reader)\n+  {\n+    TSize const size = ReadPrimitiveFromPos<TSize>(reader, 0);\n+\n+    uint64_t const off1 = sizeof(TSize);\n+    uint64_t const off2 = AlignBytesCount((size * Bits + CHAR_BIT - 1) / CHAR_BIT) + off1;\n+    return unique_ptr<TSelf>(new TSelf(reader.SubReader(off1, off2 - off1),\n+                                       reader.SubReader(off2, reader.Size() - off2),\n+                                       size));\n+  }\n+\n+  TValue Get(TSize index) const\n+  {\n+    ASSERT_LESS(index, m_size, ());\n+    uint64_t const bitsOffset = index * Bits;\n+\n+    uint64_t bytesOffset = bitsOffset / CHAR_BIT;\n+    size_t constexpr kBlockSize = sizeof(TBlock);\n+    if (bytesOffset + kBlockSize > m_bits.Size())\n+      bytesOffset = m_bits.Size() - kBlockSize;\n+\n+    TBlock v = ReadPrimitiveFromPos<TBlock>(m_bits, bytesOffset);\n+    v >>= (bitsOffset - bytesOffset * CHAR_BIT);\n+    v &= kMask;\n+    return (v == kMask ? FindInVector(index) : v);\n+  }\n+\n+  template <class TWriter> class Builder\n+  {\n+    using TData = vector<uint8_t>;\n+    using TempWriter = MemWriter<TData>;\n+    using TBits = BitWriter<TempWriter>;\n+\n+    TData m_data;\n+    TempWriter m_writer;\n+    unique_ptr<TBits> m_bits;\n+\n+    vector<IndexValue> m_excepts;\n+    TSize m_index = 0;","path":"coding/fixed_bits_vector.hpp","position":116,"original_position":116,"commit_id":"46bc7f6b484a66d21d185874b1addf20788a94b5","original_commit_id":"46bc7f6b484a66d21d185874b1addf20788a94b5","user":{"login":"vng","id":175612,"avatar_url":"https://avatars.githubusercontent.com/u/175612?v=3","gravatar_id":"","url":"https://api.github.com/users/vng","html_url":"https://github.com/vng","followers_url":"https://api.github.com/users/vng/followers","following_url":"https://api.github.com/users/vng/following{/other_user}","gists_url":"https://api.github.com/users/vng/gists{/gist_id}","starred_url":"https://api.github.com/users/vng/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/vng/subscriptions","organizations_url":"https://api.github.com/users/vng/orgs","repos_url":"https://api.github.com/users/vng/repos","events_url":"https://api.github.com/users/vng/events{/privacy}","received_events_url":"https://api.github.com/users/vng/received_events","type":"User","site_admin":false},"body":"На самом деле это не просто счетчик. Он на каждом вызове PushBack используется как индекс для сохранения.","created_at":"2015-12-03T14:22:50Z","updated_at":"2015-12-03T14:22:50Z","html_url":"https://github.com/mapsme/omim/pull/822#discussion_r46555926","pull_request_url":"https://api.github.com/repos/mapsme/omim/pulls/822","_links":{"self":{"href":"https://api.github.com/repos/mapsme/omim/pulls/comments/46555926"},"html":{"href":"https://github.com/mapsme/omim/pull/822#discussion_r46555926"},"pull_request":{"href":"https://api.github.com/repos/mapsme/omim/pulls/822"}}},"pull_request":{"url":"https://api.github.com/repos/mapsme/omim/pulls/822","id":52411227,"html_url":"https://github.com/mapsme/omim/pull/822","diff_url":"https://github.com/mapsme/omim/pull/822.diff","patch_url":"https://github.com/mapsme/omim/pull/822.patch","issue_url":"https://api.github.com/repos/mapsme/omim/issues/822","number":822,"state":"open","locked":false,"title":"[Review] Implemented FixedBitsDDVector.","user":{"login":"vng","id":175612,"avatar_url":"https://avatars.githubusercontent.com/u/175612?v=3","gravatar_id":"","url":"https://api.github.com/users/vng","html_url":"https://github.com/vng","followers_url":"https://api.github.com/users/vng/followers","following_url":"https://api.github.com/users/vng/following{/other_user}","gists_url":"https://api.github.com/users/vng/gists{/gist_id}","starred_url":"https://api.github.com/users/vng/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/vng/subscriptions","organizations_url":"https://api.github.com/users/vng/orgs","repos_url":"https://api.github.com/users/vng/repos","events_url":"https://api.github.com/users/vng/events{/privacy}","received_events_url":"https://api.github.com/users/vng/received_events","type":"User","site_admin":false},"body":"Заимплементил random access vector для fixed bit size значений с хранением исключений.","created_at":"2015-12-02T15:37:12Z","updated_at":"2015-12-03T14:22:50Z","closed_at":null,"merged_at":null,"merge_commit_sha":"9f821fd35ac7a0d21fe5be5351a1fcde517e2931","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/mapsme/omim/pulls/822/commits","review_comments_url":"https://api.github.com/repos/mapsme/omim/pulls/822/comments","review_comment_url":"https://api.github.com/repos/mapsme/omim/pulls/comments{/number}","comments_url":"https://api.github.com/repos/mapsme/omim/issues/822/comments","statuses_url":"https://api.github.com/repos/mapsme/omim/statuses/46bc7f6b484a66d21d185874b1addf20788a94b5","head":{"label":"vng:ns","ref":"ns","sha":"46bc7f6b484a66d21d185874b1addf20788a94b5","user":{"login":"vng","id":175612,"avatar_url":"https://avatars.githubusercontent.com/u/175612?v=3","gravatar_id":"","url":"https://api.github.com/users/vng","html_url":"https://github.com/vng","followers_url":"https://api.github.com/users/vng/followers","following_url":"https://api.github.com/users/vng/following{/other_user}","gists_url":"https://api.github.com/users/vng/gists{/gist_id}","starred_url":"https://api.github.com/users/vng/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/vng/subscriptions","organizations_url":"https://api.github.com/users/vng/orgs","repos_url":"https://api.github.com/users/vng/repos","events_url":"https://api.github.com/users/vng/events{/privacy}","received_events_url":"https://api.github.com/users/vng/received_events","type":"User","site_admin":false},"repo":{"id":43431189,"name":"omim","full_name":"vng/omim","owner":{"login":"vng","id":175612,"avatar_url":"https://avatars.githubusercontent.com/u/175612?v=3","gravatar_id":"","url":"https://api.github.com/users/vng","html_url":"https://github.com/vng","followers_url":"https://api.github.com/users/vng/followers","following_url":"https://api.github.com/users/vng/following{/other_user}","gists_url":"https://api.github.com/users/vng/gists{/gist_id}","starred_url":"https://api.github.com/users/vng/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/vng/subscriptions","organizations_url":"https://api.github.com/users/vng/orgs","repos_url":"https://api.github.com/users/vng/repos","events_url":"https://api.github.com/users/vng/events{/privacy}","received_events_url":"https://api.github.com/users/vng/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/vng/omim","description":"MAPS.ME - Offline OpenStreetMap maps for iOS/Android/Mac/Linux/Windows","fork":true,"url":"https://api.github.com/repos/vng/omim","forks_url":"https://api.github.com/repos/vng/omim/forks","keys_url":"https://api.github.com/repos/vng/omim/keys{/key_id}","collaborators_url":"https://api.github.com/repos/vng/omim/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/vng/omim/teams","hooks_url":"https://api.github.com/repos/vng/omim/hooks","issue_events_url":"https://api.github.com/repos/vng/omim/issues/events{/number}","events_url":"https://api.github.com/repos/vng/omim/events","assignees_url":"https://api.github.com/repos/vng/omim/assignees{/user}","branches_url":"https://api.github.com/repos/vng/omim/branches{/branch}","tags_url":"https://api.github.com/repos/vng/omim/tags","blobs_url":"https://api.github.com/repos/vng/omim/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/vng/omim/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/vng/omim/git/refs{/sha}","trees_url":"https://api.github.com/repos/vng/omim/git/trees{/sha}","statuses_url":"https://api.github.com/repos/vng/omim/statuses/{sha}","languages_url":"https://api.github.com/repos/vng/omim/languages","stargazers_url":"https://api.github.com/repos/vng/omim/stargazers","contributors_url":"https://api.github.com/repos/vng/omim/contributors","subscribers_url":"https://api.github.com/repos/vng/omim/subscribers","subscription_url":"https://api.github.com/repos/vng/omim/subscription","commits_url":"https://api.github.com/repos/vng/omim/commits{/sha}","git_commits_url":"https://api.github.com/repos/vng/omim/git/commits{/sha}","comments_url":"https://api.github.com/repos/vng/omim/comments{/number}","issue_comment_url":"https://api.github.com/repos/vng/omim/issues/comments{/number}","contents_url":"https://api.github.com/repos/vng/omim/contents/{+path}","compare_url":"https://api.github.com/repos/vng/omim/compare/{base}...{head}","merges_url":"https://api.github.com/repos/vng/omim/merges","archive_url":"https://api.github.com/repos/vng/omim/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/vng/omim/downloads","issues_url":"https://api.github.com/repos/vng/omim/issues{/number}","pulls_url":"https://api.github.com/repos/vng/omim/pulls{/number}","milestones_url":"https://api.github.com/repos/vng/omim/milestones{/number}","notifications_url":"https://api.github.com/repos/vng/omim/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/vng/omim/labels{/name}","releases_url":"https://api.github.com/repos/vng/omim/releases{/id}","created_at":"2015-09-30T12:19:26Z","updated_at":"2015-09-30T12:21:35Z","pushed_at":"2015-12-03T12:37:37Z","git_url":"git://github.com/vng/omim.git","ssh_url":"git@github.com:vng/omim.git","clone_url":"https://github.com/vng/omim.git","svn_url":"https://github.com/vng/omim","homepage":null,"size":1879633,"stargazers_count":0,"watchers_count":0,"language":"C++","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"mapsme:new-search","ref":"new-search","sha":"89603abb41465aa82eb064c55ef1eb4bb1cf3278","user":{"login":"mapsme","id":14185141,"avatar_url":"https://avatars.githubusercontent.com/u/14185141?v=3","gravatar_id":"","url":"https://api.github.com/users/mapsme","html_url":"https://github.com/mapsme","followers_url":"https://api.github.com/users/mapsme/followers","following_url":"https://api.github.com/users/mapsme/following{/other_user}","gists_url":"https://api.github.com/users/mapsme/gists{/gist_id}","starred_url":"https://api.github.com/users/mapsme/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mapsme/subscriptions","organizations_url":"https://api.github.com/users/mapsme/orgs","repos_url":"https://api.github.com/users/mapsme/repos","events_url":"https://api.github.com/users/mapsme/events{/privacy}","received_events_url":"https://api.github.com/users/mapsme/received_events","type":"Organization","site_admin":false},"repo":{"id":42798033,"name":"omim","full_name":"mapsme/omim","owner":{"login":"mapsme","id":14185141,"avatar_url":"https://avatars.githubusercontent.com/u/14185141?v=3","gravatar_id":"","url":"https://api.github.com/users/mapsme","html_url":"https://github.com/mapsme","followers_url":"https://api.github.com/users/mapsme/followers","following_url":"https://api.github.com/users/mapsme/following{/other_user}","gists_url":"https://api.github.com/users/mapsme/gists{/gist_id}","starred_url":"https://api.github.com/users/mapsme/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mapsme/subscriptions","organizations_url":"https://api.github.com/users/mapsme/orgs","repos_url":"https://api.github.com/users/mapsme/repos","events_url":"https://api.github.com/users/mapsme/events{/privacy}","received_events_url":"https://api.github.com/users/mapsme/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/mapsme/omim","description":"MAPS.ME - Offline OpenStreetMap maps for iOS/Android/Mac/Linux/Windows","fork":false,"url":"https://api.github.com/repos/mapsme/omim","forks_url":"https://api.github.com/repos/mapsme/omim/forks","keys_url":"https://api.github.com/repos/mapsme/omim/keys{/key_id}","collaborators_url":"https://api.github.com/repos/mapsme/omim/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/mapsme/omim/teams","hooks_url":"https://api.github.com/repos/mapsme/omim/hooks","issue_events_url":"https://api.github.com/repos/mapsme/omim/issues/events{/number}","events_url":"https://api.github.com/repos/mapsme/omim/events","assignees_url":"https://api.github.com/repos/mapsme/omim/assignees{/user}","branches_url":"https://api.github.com/repos/mapsme/omim/branches{/branch}","tags_url":"https://api.github.com/repos/mapsme/omim/tags","blobs_url":"https://api.github.com/repos/mapsme/omim/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/mapsme/omim/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/mapsme/omim/git/refs{/sha}","trees_url":"https://api.github.com/repos/mapsme/omim/git/trees{/sha}","statuses_url":"https://api.github.com/repos/mapsme/omim/statuses/{sha}","languages_url":"https://api.github.com/repos/mapsme/omim/languages","stargazers_url":"https://api.github.com/repos/mapsme/omim/stargazers","contributors_url":"https://api.github.com/repos/mapsme/omim/contributors","subscribers_url":"https://api.github.com/repos/mapsme/omim/subscribers","subscription_url":"https://api.github.com/repos/mapsme/omim/subscription","commits_url":"https://api.github.com/repos/mapsme/omim/commits{/sha}","git_commits_url":"https://api.github.com/repos/mapsme/omim/git/commits{/sha}","comments_url":"https://api.github.com/repos/mapsme/omim/comments{/number}","issue_comment_url":"https://api.github.com/repos/mapsme/omim/issues/comments{/number}","contents_url":"https://api.github.com/repos/mapsme/omim/contents/{+path}","compare_url":"https://api.github.com/repos/mapsme/omim/compare/{base}...{head}","merges_url":"https://api.github.com/repos/mapsme/omim/merges","archive_url":"https://api.github.com/repos/mapsme/omim/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/mapsme/omim/downloads","issues_url":"https://api.github.com/repos/mapsme/omim/issues{/number}","pulls_url":"https://api.github.com/repos/mapsme/omim/pulls{/number}","milestones_url":"https://api.github.com/repos/mapsme/omim/milestones{/number}","notifications_url":"https://api.github.com/repos/mapsme/omim/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/mapsme/omim/labels{/name}","releases_url":"https://api.github.com/repos/mapsme/omim/releases{/id}","created_at":"2015-09-20T02:57:13Z","updated_at":"2015-12-03T12:14:06Z","pushed_at":"2015-12-03T14:22:46Z","git_url":"git://github.com/mapsme/omim.git","ssh_url":"git@github.com:mapsme/omim.git","clone_url":"https://github.com/mapsme/omim.git","svn_url":"https://github.com/mapsme/omim","homepage":null,"size":1913759,"stargazers_count":1514,"watchers_count":1514,"language":"C++","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":184,"mirror_url":null,"open_issues_count":71,"forks":184,"open_issues":71,"watchers":1514,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/mapsme/omim/pulls/822"},"html":{"href":"https://github.com/mapsme/omim/pull/822"},"issue":{"href":"https://api.github.com/repos/mapsme/omim/issues/822"},"comments":{"href":"https://api.github.com/repos/mapsme/omim/issues/822/comments"},"review_comments":{"href":"https://api.github.com/repos/mapsme/omim/pulls/822/comments"},"review_comment":{"href":"https://api.github.com/repos/mapsme/omim/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/mapsme/omim/pulls/822/commits"},"statuses":{"href":"https://api.github.com/repos/mapsme/omim/statuses/46bc7f6b484a66d21d185874b1addf20788a94b5"}}}}