{"action":"created","comment":{"url":"https://api.github.com/repos/valhalla/baldr/pulls/comments/88227220","pull_request_review_id":8805704,"id":88227220,"diff_hunk":"@@ -0,0 +1,414 @@\n+#include \"valhalla/baldr/merge.h\"\n+#include \"valhalla/baldr/graphreader.h\"\n+#include \"valhalla/midgard/logging.h\"\n+\n+#include <boost/range/adaptor/map.hpp>\n+#include <boost/optional.hpp>\n+\n+namespace bra = boost::adaptors;\n+\n+namespace valhalla {\n+namespace baldr {\n+namespace merge {\n+\n+namespace {\n+\n+// a place we can mark what edges we've seen, even for the planet we should\n+// need ~ 100mb, as it allocates one bit per ID. there are currently around\n+// 453 million ways in OSM, and we might allocate two edge IDs per way,\n+// giving something like 108mb of bits needed.\n+struct bitset_t {\n+  bitset_t(size_t size) {bits.resize(size);}\n+  void set(const uint64_t id) {\n+    if (id >= static_cast<uint64_t>(bits.size()) * 64) throw std::runtime_error(\"id out of bounds\");\n+    bits[id / 64] |= static_cast<uint64_t>(1) << (id % static_cast<uint64_t>(64));\n+  }\n+  bool get(const uint64_t id) const {\n+    if (id >= static_cast<uint64_t>(bits.size()) * 64) throw std::runtime_error(\"id out of bounds\");\n+    return bits[id / 64] & (static_cast<uint64_t>(1) << (id % static_cast<uint64_t>(64)));\n+  }\n+protected:\n+  std::vector<uint64_t> bits;\n+};\n+\n+// edge tracker wraps a bitset to provide compact storage of GraphIds.\n+//\n+// the GraphReader is crawled to enumerate all tiles, and the range of tile IDs\n+// is used to construct a compact range by concatenating all the existing\n+// compact ranges for each tile.\n+struct edge_tracker {\n+  explicit edge_tracker(GraphReader &reader);\n+\n+  bool get(const GraphId &edge_id) const;\n+  void set(const GraphId &edge_id);\n+\n+  typedef std::unordered_map<GraphId, uint64_t> edge_index_t;\n+  edge_index_t m_edges_in_tiles;\n+  //this is how we know what i've touched and what we havent\n+  bitset_t m_edge_set;\n+\n+  static bitset_t count_all_edges(GraphReader &reader, const edge_index_t &edges);\n+  static edge_index_t edges_in_tiles(GraphReader &reader);\n+};\n+\n+edge_tracker::edge_tracker(GraphReader &reader)\n+  : m_edges_in_tiles(edges_in_tiles(reader))\n+  , m_edge_set(count_all_edges(reader, m_edges_in_tiles)) {\n+}\n+\n+bool edge_tracker::get(const GraphId &edge_id) const {\n+  auto itr = m_edges_in_tiles.find(edge_id.Tile_Base());\n+  assert(itr != m_edges_in_tiles.end());\n+  return m_edge_set.get(edge_id.id() + itr->second);\n+}\n+\n+void edge_tracker::set(const GraphId &edge_id) {\n+  auto itr = m_edges_in_tiles.find(edge_id.Tile_Base());\n+  assert(itr != m_edges_in_tiles.end());\n+  m_edge_set.set(edge_id.id() + itr->second);\n+}\n+\n+uint64_t count_tiles_in_levels(GraphReader &reader) {\n+  uint64_t tile_count = 0;\n+  for (auto level : reader.GetTileHierarchy().levels() | bra::map_values) {\n+    tile_count += level.tiles.ncolumns() * level.tiles.nrows();\n+  }\n+  return tile_count;\n+}\n+\n+edge_tracker::edge_index_t edge_tracker::edges_in_tiles(GraphReader &reader) {\n+  uint64_t tiles_in_levels = count_tiles_in_levels(reader);\n+\n+  //keep the global number of edges encountered at the point we encounter each tile\n+  //this allows an edge to have a sequential global id and makes storing it very small\n+  LOG_INFO(\"Enumerating edges...\");\n+  uint64_t edge_count = 0;\n+  edge_tracker::edge_index_t edges_in_tiles(tiles_in_levels);\n+  for (auto level : reader.GetTileHierarchy().levels() | bra::map_values) {\n+    for (uint32_t i = 0; i < level.tiles.TileCount(); ++i) {\n+      GraphId tile_id{i, level.level, 0};\n+      if (reader.DoesTileExist(tile_id)) {\n+        //TODO: just read the header, parsing the whole thing isnt worth it at this point\n+        edges_in_tiles.emplace(tile_id, edge_count);\n+        const auto* tile = reader.GetGraphTile(tile_id);\n+        edge_count += tile->header()->directededgecount();\n+        // this clears the cache, and the test relies on being able to inject\n+        // stuff into the cache :-(\n+        //\n+        // TODO: presumably this is bad when the cache doesn't behave like a","path":"src/baldr/merge.cc","position":null,"original_position":98,"commit_id":"709ec6eb5e7c542a69c9f1d16fa0c3fdd4cab09f","original_commit_id":"297b332927e660089a55432f351f2694b3ffc7cd","user":{"login":"zerebubuth","id":271360,"avatar_url":"https://avatars.githubusercontent.com/u/271360?v=3","gravatar_id":"","url":"https://api.github.com/users/zerebubuth","html_url":"https://github.com/zerebubuth","followers_url":"https://api.github.com/users/zerebubuth/followers","following_url":"https://api.github.com/users/zerebubuth/following{/other_user}","gists_url":"https://api.github.com/users/zerebubuth/gists{/gist_id}","starred_url":"https://api.github.com/users/zerebubuth/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/zerebubuth/subscriptions","organizations_url":"https://api.github.com/users/zerebubuth/orgs","repos_url":"https://api.github.com/users/zerebubuth/repos","events_url":"https://api.github.com/users/zerebubuth/events{/privacy}","received_events_url":"https://api.github.com/users/zerebubuth/received_events","type":"User","site_admin":false},"body":"Ah, I had missed the `GraphReader::OverCommitted()` function. Thanks for pointing it out. Fixed in 709ec6e.","created_at":"2016-11-16T12:34:33Z","updated_at":"2016-11-16T12:34:33Z","html_url":"https://github.com/valhalla/baldr/pull/316#discussion_r88227220","pull_request_url":"https://api.github.com/repos/valhalla/baldr/pulls/316","_links":{"self":{"href":"https://api.github.com/repos/valhalla/baldr/pulls/comments/88227220"},"html":{"href":"https://github.com/valhalla/baldr/pull/316#discussion_r88227220"},"pull_request":{"href":"https://api.github.com/repos/valhalla/baldr/pulls/316"}}},"pull_request":{"url":"https://api.github.com/repos/valhalla/baldr/pulls/316","id":93820232,"html_url":"https://github.com/valhalla/baldr/pull/316","diff_url":"https://github.com/valhalla/baldr/pull/316.diff","patch_url":"https://github.com/valhalla/baldr/pull/316.patch","issue_url":"https://api.github.com/repos/valhalla/baldr/issues/316","number":316,"state":"open","locked":false,"title":"Add edge merging","user":{"login":"zerebubuth","id":271360,"avatar_url":"https://avatars.githubusercontent.com/u/271360?v=3","gravatar_id":"","url":"https://api.github.com/users/zerebubuth","html_url":"https://github.com/zerebubuth","followers_url":"https://api.github.com/users/zerebubuth/followers","following_url":"https://api.github.com/users/zerebubuth/following{/other_user}","gists_url":"https://api.github.com/users/zerebubuth/gists{/gist_id}","starred_url":"https://api.github.com/users/zerebubuth/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/zerebubuth/subscriptions","organizations_url":"https://api.github.com/users/zerebubuth/orgs","repos_url":"https://api.github.com/users/zerebubuth/repos","events_url":"https://api.github.com/users/zerebubuth/events{/privacy}","received_events_url":"https://api.github.com/users/zerebubuth/received_events","type":"User","site_admin":false},"body":"This adds a function `valhalla::baldr::merge` which takes a `GraphReader` and a functor, and iterates over all the edges in the graph to find those which are collapsible, calling the functor for each collapsed set of edges.\r\n\r\nThis is a building block for OpenLR-like descriptors, and intended to group edges into sequences where there are no true intersections, but there might be bridges or changes in other properties such as max speed.\r\n\r\n@kevinkreiser could you take a look and let me know what you think, please?\r\n","created_at":"2016-11-15T18:22:04Z","updated_at":"2016-11-16T12:34:33Z","closed_at":null,"merged_at":null,"merge_commit_sha":"2fa56b237299053d2bf854850352ba19f212c57a","assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/valhalla/baldr/pulls/316/commits","review_comments_url":"https://api.github.com/repos/valhalla/baldr/pulls/316/comments","review_comment_url":"https://api.github.com/repos/valhalla/baldr/pulls/comments{/number}","comments_url":"https://api.github.com/repos/valhalla/baldr/issues/316/comments","statuses_url":"https://api.github.com/repos/valhalla/baldr/statuses/709ec6eb5e7c542a69c9f1d16fa0c3fdd4cab09f","head":{"label":"valhalla:mla_edge_merging","ref":"mla_edge_merging","sha":"709ec6eb5e7c542a69c9f1d16fa0c3fdd4cab09f","user":{"login":"valhalla","id":10232331,"avatar_url":"https://avatars.githubusercontent.com/u/10232331?v=3","gravatar_id":"","url":"https://api.github.com/users/valhalla","html_url":"https://github.com/valhalla","followers_url":"https://api.github.com/users/valhalla/followers","following_url":"https://api.github.com/users/valhalla/following{/other_user}","gists_url":"https://api.github.com/users/valhalla/gists{/gist_id}","starred_url":"https://api.github.com/users/valhalla/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/valhalla/subscriptions","organizations_url":"https://api.github.com/users/valhalla/orgs","repos_url":"https://api.github.com/users/valhalla/repos","events_url":"https://api.github.com/users/valhalla/events{/privacy}","received_events_url":"https://api.github.com/users/valhalla/received_events","type":"Organization","site_admin":false},"repo":{"id":28186324,"name":"baldr","full_name":"valhalla/baldr","owner":{"login":"valhalla","id":10232331,"avatar_url":"https://avatars.githubusercontent.com/u/10232331?v=3","gravatar_id":"","url":"https://api.github.com/users/valhalla","html_url":"https://github.com/valhalla","followers_url":"https://api.github.com/users/valhalla/followers","following_url":"https://api.github.com/users/valhalla/following{/other_user}","gists_url":"https://api.github.com/users/valhalla/gists{/gist_id}","starred_url":"https://api.github.com/users/valhalla/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/valhalla/subscriptions","organizations_url":"https://api.github.com/users/valhalla/orgs","repos_url":"https://api.github.com/users/valhalla/repos","events_url":"https://api.github.com/users/valhalla/events{/privacy}","received_events_url":"https://api.github.com/users/valhalla/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/valhalla/baldr","description":"Routing-specific data structures distilled into a library for use within other parts of the system","fork":false,"url":"https://api.github.com/repos/valhalla/baldr","forks_url":"https://api.github.com/repos/valhalla/baldr/forks","keys_url":"https://api.github.com/repos/valhalla/baldr/keys{/key_id}","collaborators_url":"https://api.github.com/repos/valhalla/baldr/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/valhalla/baldr/teams","hooks_url":"https://api.github.com/repos/valhalla/baldr/hooks","issue_events_url":"https://api.github.com/repos/valhalla/baldr/issues/events{/number}","events_url":"https://api.github.com/repos/valhalla/baldr/events","assignees_url":"https://api.github.com/repos/valhalla/baldr/assignees{/user}","branches_url":"https://api.github.com/repos/valhalla/baldr/branches{/branch}","tags_url":"https://api.github.com/repos/valhalla/baldr/tags","blobs_url":"https://api.github.com/repos/valhalla/baldr/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/valhalla/baldr/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/valhalla/baldr/git/refs{/sha}","trees_url":"https://api.github.com/repos/valhalla/baldr/git/trees{/sha}","statuses_url":"https://api.github.com/repos/valhalla/baldr/statuses/{sha}","languages_url":"https://api.github.com/repos/valhalla/baldr/languages","stargazers_url":"https://api.github.com/repos/valhalla/baldr/stargazers","contributors_url":"https://api.github.com/repos/valhalla/baldr/contributors","subscribers_url":"https://api.github.com/repos/valhalla/baldr/subscribers","subscription_url":"https://api.github.com/repos/valhalla/baldr/subscription","commits_url":"https://api.github.com/repos/valhalla/baldr/commits{/sha}","git_commits_url":"https://api.github.com/repos/valhalla/baldr/git/commits{/sha}","comments_url":"https://api.github.com/repos/valhalla/baldr/comments{/number}","issue_comment_url":"https://api.github.com/repos/valhalla/baldr/issues/comments{/number}","contents_url":"https://api.github.com/repos/valhalla/baldr/contents/{+path}","compare_url":"https://api.github.com/repos/valhalla/baldr/compare/{base}...{head}","merges_url":"https://api.github.com/repos/valhalla/baldr/merges","archive_url":"https://api.github.com/repos/valhalla/baldr/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/valhalla/baldr/downloads","issues_url":"https://api.github.com/repos/valhalla/baldr/issues{/number}","pulls_url":"https://api.github.com/repos/valhalla/baldr/pulls{/number}","milestones_url":"https://api.github.com/repos/valhalla/baldr/milestones{/number}","notifications_url":"https://api.github.com/repos/valhalla/baldr/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/valhalla/baldr/labels{/name}","releases_url":"https://api.github.com/repos/valhalla/baldr/releases{/id}","deployments_url":"https://api.github.com/repos/valhalla/baldr/deployments","created_at":"2014-12-18T14:18:18Z","updated_at":"2016-11-02T20:29:38Z","pushed_at":"2016-11-16T12:32:14Z","git_url":"git://github.com/valhalla/baldr.git","ssh_url":"git@github.com:valhalla/baldr.git","clone_url":"https://github.com/valhalla/baldr.git","svn_url":"https://github.com/valhalla/baldr","homepage":null,"size":2556,"stargazers_count":6,"watchers_count":6,"language":"C++","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":8,"mirror_url":null,"open_issues_count":9,"forks":8,"open_issues":9,"watchers":6,"default_branch":"master"}},"base":{"label":"valhalla:master","ref":"master","sha":"fda07603c06fb6c3749b321b456030245df378c4","user":{"login":"valhalla","id":10232331,"avatar_url":"https://avatars.githubusercontent.com/u/10232331?v=3","gravatar_id":"","url":"https://api.github.com/users/valhalla","html_url":"https://github.com/valhalla","followers_url":"https://api.github.com/users/valhalla/followers","following_url":"https://api.github.com/users/valhalla/following{/other_user}","gists_url":"https://api.github.com/users/valhalla/gists{/gist_id}","starred_url":"https://api.github.com/users/valhalla/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/valhalla/subscriptions","organizations_url":"https://api.github.com/users/valhalla/orgs","repos_url":"https://api.github.com/users/valhalla/repos","events_url":"https://api.github.com/users/valhalla/events{/privacy}","received_events_url":"https://api.github.com/users/valhalla/received_events","type":"Organization","site_admin":false},"repo":{"id":28186324,"name":"baldr","full_name":"valhalla/baldr","owner":{"login":"valhalla","id":10232331,"avatar_url":"https://avatars.githubusercontent.com/u/10232331?v=3","gravatar_id":"","url":"https://api.github.com/users/valhalla","html_url":"https://github.com/valhalla","followers_url":"https://api.github.com/users/valhalla/followers","following_url":"https://api.github.com/users/valhalla/following{/other_user}","gists_url":"https://api.github.com/users/valhalla/gists{/gist_id}","starred_url":"https://api.github.com/users/valhalla/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/valhalla/subscriptions","organizations_url":"https://api.github.com/users/valhalla/orgs","repos_url":"https://api.github.com/users/valhalla/repos","events_url":"https://api.github.com/users/valhalla/events{/privacy}","received_events_url":"https://api.github.com/users/valhalla/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/valhalla/baldr","description":"Routing-specific data structures distilled into a library for use within other parts of the system","fork":false,"url":"https://api.github.com/repos/valhalla/baldr","forks_url":"https://api.github.com/repos/valhalla/baldr/forks","keys_url":"https://api.github.com/repos/valhalla/baldr/keys{/key_id}","collaborators_url":"https://api.github.com/repos/valhalla/baldr/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/valhalla/baldr/teams","hooks_url":"https://api.github.com/repos/valhalla/baldr/hooks","issue_events_url":"https://api.github.com/repos/valhalla/baldr/issues/events{/number}","events_url":"https://api.github.com/repos/valhalla/baldr/events","assignees_url":"https://api.github.com/repos/valhalla/baldr/assignees{/user}","branches_url":"https://api.github.com/repos/valhalla/baldr/branches{/branch}","tags_url":"https://api.github.com/repos/valhalla/baldr/tags","blobs_url":"https://api.github.com/repos/valhalla/baldr/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/valhalla/baldr/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/valhalla/baldr/git/refs{/sha}","trees_url":"https://api.github.com/repos/valhalla/baldr/git/trees{/sha}","statuses_url":"https://api.github.com/repos/valhalla/baldr/statuses/{sha}","languages_url":"https://api.github.com/repos/valhalla/baldr/languages","stargazers_url":"https://api.github.com/repos/valhalla/baldr/stargazers","contributors_url":"https://api.github.com/repos/valhalla/baldr/contributors","subscribers_url":"https://api.github.com/repos/valhalla/baldr/subscribers","subscription_url":"https://api.github.com/repos/valhalla/baldr/subscription","commits_url":"https://api.github.com/repos/valhalla/baldr/commits{/sha}","git_commits_url":"https://api.github.com/repos/valhalla/baldr/git/commits{/sha}","comments_url":"https://api.github.com/repos/valhalla/baldr/comments{/number}","issue_comment_url":"https://api.github.com/repos/valhalla/baldr/issues/comments{/number}","contents_url":"https://api.github.com/repos/valhalla/baldr/contents/{+path}","compare_url":"https://api.github.com/repos/valhalla/baldr/compare/{base}...{head}","merges_url":"https://api.github.com/repos/valhalla/baldr/merges","archive_url":"https://api.github.com/repos/valhalla/baldr/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/valhalla/baldr/downloads","issues_url":"https://api.github.com/repos/valhalla/baldr/issues{/number}","pulls_url":"https://api.github.com/repos/valhalla/baldr/pulls{/number}","milestones_url":"https://api.github.com/repos/valhalla/baldr/milestones{/number}","notifications_url":"https://api.github.com/repos/valhalla/baldr/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/valhalla/baldr/labels{/name}","releases_url":"https://api.github.com/repos/valhalla/baldr/releases{/id}","deployments_url":"https://api.github.com/repos/valhalla/baldr/deployments","created_at":"2014-12-18T14:18:18Z","updated_at":"2016-11-02T20:29:38Z","pushed_at":"2016-11-16T12:32:14Z","git_url":"git://github.com/valhalla/baldr.git","ssh_url":"git@github.com:valhalla/baldr.git","clone_url":"https://github.com/valhalla/baldr.git","svn_url":"https://github.com/valhalla/baldr","homepage":null,"size":2556,"stargazers_count":6,"watchers_count":6,"language":"C++","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":8,"mirror_url":null,"open_issues_count":9,"forks":8,"open_issues":9,"watchers":6,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/valhalla/baldr/pulls/316"},"html":{"href":"https://github.com/valhalla/baldr/pull/316"},"issue":{"href":"https://api.github.com/repos/valhalla/baldr/issues/316"},"comments":{"href":"https://api.github.com/repos/valhalla/baldr/issues/316/comments"},"review_comments":{"href":"https://api.github.com/repos/valhalla/baldr/pulls/316/comments"},"review_comment":{"href":"https://api.github.com/repos/valhalla/baldr/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/valhalla/baldr/pulls/316/commits"},"statuses":{"href":"https://api.github.com/repos/valhalla/baldr/statuses/709ec6eb5e7c542a69c9f1d16fa0c3fdd4cab09f"}}}}
{"actor":{"display_login":"zerebubuth"}}