{"action":"created","comment":{"url":"https://api.github.com/repos/mapsme/omim/pulls/comments/41309454","id":41309454,"diff_hunk":"@@ -0,0 +1,144 @@\n+#pragma once\n+\n+#include \"std/algorithm.hpp\"\n+#include \"std/set.hpp\"\n+#include \"std/utility.hpp\"\n+#include \"std/vector.hpp\"\n+\n+namespace my\n+{\n+// This class represents a set of disjoint intervals in the form\n+// [begin, end).  Note that neighbour intervals are always coalesced,\n+// so while [0, 1), [1, 2) and [2, 3) are disjoint, after addition to\n+// the set they will be stored as a single [0, 3).\n+template <typename TElem>\n+class IntervalSet\n+{\n+public:\n+  using TInterval = pair<TElem, TElem>;\n+\n+  // Adds an |interval| to the set, coalescing adjacent intervals if needed.\n+  //\n+  // Complexity: O(num of intervals intersecting with |interval| +\n+  // log(total number of intervals)).\n+  void Add(TInterval const & interval);\n+\n+  // Subtracts set from an |interval| and appends result to\n+  // |difference|.\n+  //\n+  // Complexity: O(num of intervals intersecting with |interval| +\n+  // log(total number of intervals)).\n+  void SubtractFrom(TInterval const & interval, vector<TInterval> & difference) const;\n+\n+  // Returns all elements of the set as a set of intervals.\n+  //\n+  // Complexity: O(1).\n+  inline set<TInterval> const & Elems() const { return m_intervals; }\n+\n+private:\n+  using TIterator = typename set<TInterval>::iterator;\n+\n+  // Calculates range of intervals that have non-empty intersection with a given |interval|.\n+  void Cover(TInterval const & interval, TIterator & begin, TIterator & end) const;\n+\n+  // This is a set of disjoint intervals.\n+  set<TInterval> m_intervals;\n+};\n+\n+template <typename TElem>\n+void IntervalSet<TElem>::Add(TInterval const & interval)\n+{\n+  // Skips empty intervals.\n+  if (interval.first == interval.second)\n+    return;\n+\n+  TIterator begin;\n+  TIterator end;\n+  Cover(interval, begin, end);\n+\n+  TElem from = interval.first;\n+  TElem to = interval.second;\n+\n+  // Update |from| and |to| in accordance with corner intervals (if any).\n+  if (begin != end)\n+  {\n+    if (begin->first < from)\n+      from = begin->first;\n+\n+    auto last = end;\n+    --last;\n+    if (last->second > to)\n+      to = last->second;\n+  }\n+\n+  // Now all elements [from, to) can be added to the set as a single\n+  // interval which replace all intervals in [begin, end). But note\n+  // that it can be possible to merge new interval with its neighbors,\n+  // so we need to check it.\n+  if (begin != m_intervals.begin())\n+  {\n+    auto prevBegin = begin;\n+    --prevBegin;\n+    if (prevBegin->second == from)\n+    {\n+      begin = prevBegin;\n+      from = prevBegin->first;\n+    }\n+  }\n+  if (end != m_intervals.end() && end->first == to)\n+  {\n+    to = end->second;\n+    ++end;\n+  }\n+\n+  m_intervals.erase(begin, end);\n+  m_intervals.emplace(from, to);\n+}\n+\n+template <typename TElem>\n+void IntervalSet<TElem>::SubtractFrom(TInterval const & interval,\n+                                      vector<TInterval> & difference) const\n+{\n+  TIterator begin;\n+  TIterator end;\n+\n+  Cover(interval, begin, end);\n+\n+  TElem from = interval.first;\n+  TElem const to = interval.second;\n+\n+  for (auto it = begin; it != end && from < to; ++it)\n+  {\n+    if (it->first > from)\n+    {\n+      difference.emplace_back(from, min(it->first, to));\n+      from = it->second;\n+    }\n+    else\n+    {\n+      from = std::max(from, it->second);","path":"search/interval_set.hpp","position":119,"original_position":119,"commit_id":"50e4af672d66b8b805a6c9080eea8ec3da0b7ac1","original_commit_id":"50e4af672d66b8b805a6c9080eea8ec3da0b7ac1","user":{"login":"kshalnev","id":8023141,"avatar_url":"https://avatars.githubusercontent.com/u/8023141?v=3","gravatar_id":"","url":"https://api.github.com/users/kshalnev","html_url":"https://github.com/kshalnev","followers_url":"https://api.github.com/users/kshalnev/followers","following_url":"https://api.github.com/users/kshalnev/following{/other_user}","gists_url":"https://api.github.com/users/kshalnev/gists{/gist_id}","starred_url":"https://api.github.com/users/kshalnev/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kshalnev/subscriptions","organizations_url":"https://api.github.com/users/kshalnev/orgs","repos_url":"https://api.github.com/users/kshalnev/repos","events_url":"https://api.github.com/users/kshalnev/events{/privacy}","received_events_url":"https://api.github.com/users/kshalnev/received_events","type":"User","site_admin":false},"body":"w/o std prefix","created_at":"2015-10-06T19:19:28Z","updated_at":"2015-10-06T19:19:28Z","html_url":"https://github.com/mapsme/omim/pull/127#discussion_r41309454","pull_request_url":"https://api.github.com/repos/mapsme/omim/pulls/127","_links":{"self":{"href":"https://api.github.com/repos/mapsme/omim/pulls/comments/41309454"},"html":{"href":"https://github.com/mapsme/omim/pull/127#discussion_r41309454"},"pull_request":{"href":"https://api.github.com/repos/mapsme/omim/pulls/127"}}},"pull_request":{"url":"https://api.github.com/repos/mapsme/omim/pulls/127","id":46794544,"html_url":"https://github.com/mapsme/omim/pull/127","diff_url":"https://github.com/mapsme/omim/pull/127.diff","patch_url":"https://github.com/mapsme/omim/pull/127.patch","issue_url":"https://api.github.com/repos/mapsme/omim/issues/127","number":127,"state":"open","locked":false,"title":"[search] Optimized retrieval algorithm.","user":{"login":"ygorshenin","id":454567,"avatar_url":"https://avatars.githubusercontent.com/u/454567?v=3","gravatar_id":"","url":"https://api.github.com/users/ygorshenin","html_url":"https://github.com/ygorshenin","followers_url":"https://api.github.com/users/ygorshenin/followers","following_url":"https://api.github.com/users/ygorshenin/following{/other_user}","gists_url":"https://api.github.com/users/ygorshenin/gists{/gist_id}","starred_url":"https://api.github.com/users/ygorshenin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ygorshenin/subscriptions","organizations_url":"https://api.github.com/users/ygorshenin/orgs","repos_url":"https://api.github.com/users/ygorshenin/repos","events_url":"https://api.github.com/users/ygorshenin/events{/privacy}","received_events_url":"https://api.github.com/users/ygorshenin/received_events","type":"User","site_admin":false},"body":"Optimized reading from mwm: during consecutive expansions of the initial viewport the same cells can be retrieved and it's redundant to read them again and again. Thus, a new data structure called IntervalSet is used to prevent such redundant readings.\r\n\r\nExperiments tell that this optimization gives us 2x speedup. Alas, but mwm reading is still a bottleneck.\r\n\r\n@mpimenov @vng PTAL","created_at":"2015-10-05T15:22:39Z","updated_at":"2015-10-06T19:19:28Z","closed_at":null,"merged_at":null,"merge_commit_sha":"4b336e86433859a21f4d61a803c57b2853863b9b","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/mapsme/omim/pulls/127/commits","review_comments_url":"https://api.github.com/repos/mapsme/omim/pulls/127/comments","review_comment_url":"https://api.github.com/repos/mapsme/omim/pulls/comments{/number}","comments_url":"https://api.github.com/repos/mapsme/omim/issues/127/comments","statuses_url":"https://api.github.com/repos/mapsme/omim/statuses/50e4af672d66b8b805a6c9080eea8ec3da0b7ac1","head":{"label":"ygorshenin:fix-cells-covering","ref":"fix-cells-covering","sha":"50e4af672d66b8b805a6c9080eea8ec3da0b7ac1","user":{"login":"ygorshenin","id":454567,"avatar_url":"https://avatars.githubusercontent.com/u/454567?v=3","gravatar_id":"","url":"https://api.github.com/users/ygorshenin","html_url":"https://github.com/ygorshenin","followers_url":"https://api.github.com/users/ygorshenin/followers","following_url":"https://api.github.com/users/ygorshenin/following{/other_user}","gists_url":"https://api.github.com/users/ygorshenin/gists{/gist_id}","starred_url":"https://api.github.com/users/ygorshenin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ygorshenin/subscriptions","organizations_url":"https://api.github.com/users/ygorshenin/orgs","repos_url":"https://api.github.com/users/ygorshenin/repos","events_url":"https://api.github.com/users/ygorshenin/events{/privacy}","received_events_url":"https://api.github.com/users/ygorshenin/received_events","type":"User","site_admin":false},"repo":{"id":43427948,"name":"omim","full_name":"ygorshenin/omim","owner":{"login":"ygorshenin","id":454567,"avatar_url":"https://avatars.githubusercontent.com/u/454567?v=3","gravatar_id":"","url":"https://api.github.com/users/ygorshenin","html_url":"https://github.com/ygorshenin","followers_url":"https://api.github.com/users/ygorshenin/followers","following_url":"https://api.github.com/users/ygorshenin/following{/other_user}","gists_url":"https://api.github.com/users/ygorshenin/gists{/gist_id}","starred_url":"https://api.github.com/users/ygorshenin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ygorshenin/subscriptions","organizations_url":"https://api.github.com/users/ygorshenin/orgs","repos_url":"https://api.github.com/users/ygorshenin/repos","events_url":"https://api.github.com/users/ygorshenin/events{/privacy}","received_events_url":"https://api.github.com/users/ygorshenin/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/ygorshenin/omim","description":"MAPS.ME - Offline OpenStreetMap maps for iOS/Android/Mac/Linux/Windows","fork":true,"url":"https://api.github.com/repos/ygorshenin/omim","forks_url":"https://api.github.com/repos/ygorshenin/omim/forks","keys_url":"https://api.github.com/repos/ygorshenin/omim/keys{/key_id}","collaborators_url":"https://api.github.com/repos/ygorshenin/omim/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/ygorshenin/omim/teams","hooks_url":"https://api.github.com/repos/ygorshenin/omim/hooks","issue_events_url":"https://api.github.com/repos/ygorshenin/omim/issues/events{/number}","events_url":"https://api.github.com/repos/ygorshenin/omim/events","assignees_url":"https://api.github.com/repos/ygorshenin/omim/assignees{/user}","branches_url":"https://api.github.com/repos/ygorshenin/omim/branches{/branch}","tags_url":"https://api.github.com/repos/ygorshenin/omim/tags","blobs_url":"https://api.github.com/repos/ygorshenin/omim/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/ygorshenin/omim/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/ygorshenin/omim/git/refs{/sha}","trees_url":"https://api.github.com/repos/ygorshenin/omim/git/trees{/sha}","statuses_url":"https://api.github.com/repos/ygorshenin/omim/statuses/{sha}","languages_url":"https://api.github.com/repos/ygorshenin/omim/languages","stargazers_url":"https://api.github.com/repos/ygorshenin/omim/stargazers","contributors_url":"https://api.github.com/repos/ygorshenin/omim/contributors","subscribers_url":"https://api.github.com/repos/ygorshenin/omim/subscribers","subscription_url":"https://api.github.com/repos/ygorshenin/omim/subscription","commits_url":"https://api.github.com/repos/ygorshenin/omim/commits{/sha}","git_commits_url":"https://api.github.com/repos/ygorshenin/omim/git/commits{/sha}","comments_url":"https://api.github.com/repos/ygorshenin/omim/comments{/number}","issue_comment_url":"https://api.github.com/repos/ygorshenin/omim/issues/comments{/number}","contents_url":"https://api.github.com/repos/ygorshenin/omim/contents/{+path}","compare_url":"https://api.github.com/repos/ygorshenin/omim/compare/{base}...{head}","merges_url":"https://api.github.com/repos/ygorshenin/omim/merges","archive_url":"https://api.github.com/repos/ygorshenin/omim/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/ygorshenin/omim/downloads","issues_url":"https://api.github.com/repos/ygorshenin/omim/issues{/number}","pulls_url":"https://api.github.com/repos/ygorshenin/omim/pulls{/number}","milestones_url":"https://api.github.com/repos/ygorshenin/omim/milestones{/number}","notifications_url":"https://api.github.com/repos/ygorshenin/omim/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/ygorshenin/omim/labels{/name}","releases_url":"https://api.github.com/repos/ygorshenin/omim/releases{/id}","created_at":"2015-09-30T10:56:11Z","updated_at":"2015-09-30T10:58:25Z","pushed_at":"2015-10-06T14:35:09Z","git_url":"git://github.com/ygorshenin/omim.git","ssh_url":"git@github.com:ygorshenin/omim.git","clone_url":"https://github.com/ygorshenin/omim.git","svn_url":"https://github.com/ygorshenin/omim","homepage":null,"size":1765708,"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":"625a4b61b890fcd26da3a7e5012010a25da6e83e","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-10-06T18:47:42Z","pushed_at":"2015-10-06T16:39:57Z","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":1769146,"stargazers_count":1170,"watchers_count":1170,"language":"C++","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":118,"mirror_url":null,"open_issues_count":27,"forks":118,"open_issues":27,"watchers":1170,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/mapsme/omim/pulls/127"},"html":{"href":"https://github.com/mapsme/omim/pull/127"},"issue":{"href":"https://api.github.com/repos/mapsme/omim/issues/127"},"comments":{"href":"https://api.github.com/repos/mapsme/omim/issues/127/comments"},"review_comments":{"href":"https://api.github.com/repos/mapsme/omim/pulls/127/comments"},"review_comment":{"href":"https://api.github.com/repos/mapsme/omim/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/mapsme/omim/pulls/127/commits"},"statuses":{"href":"https://api.github.com/repos/mapsme/omim/statuses/50e4af672d66b8b805a6c9080eea8ec3da0b7ac1"}}}}