{"action":"created","comment":{"url":"https://api.github.com/repos/mlpack/mlpack/pulls/comments/69030868","id":69030868,"diff_hunk":"@@ -0,0 +1,260 @@\n+/**\n+ * @file minimal_coverage_sweep_impl.hpp\n+ * @author Mikhail Lozhnikov\n+ *\n+ * Implementation of the MinimalCoverageSweep class, a class that finds a\n+ * partition of a node along an axis.\n+ */\n+#ifndef MLPACK_CORE_TREE_RECTANGLE_TREE_MINIMAL_COVERAGE_SWEEP_IMPL_HPP\n+#define MLPACK_CORE_TREE_RECTANGLE_TREE_MINIMAL_COVERAGE_SWEEP_IMPL_HPP\n+\n+#include \"minimal_coverage_sweep.hpp\"\n+\n+namespace mlpack {\n+namespace tree {\n+\n+template<typename SplitPolicy>\n+template<typename TreeType>\n+typename TreeType::ElemType MinimalCoverageSweep<SplitPolicy>::\n+SweepNonLeafNode(const size_t axis,\n+                 const TreeType* node,\n+                 typename TreeType::ElemType& axisCut)\n+{\n+  typedef typename TreeType::ElemType ElemType;\n+\n+  std::vector<SortStruct<ElemType>> sorted(node->NumChildren());\n+\n+  for (size_t i = 0; i < node->NumChildren(); i++)\n+  {\n+    sorted[i].d = SplitPolicy::Bound(node->Child(i))[axis].Hi();\n+    sorted[i].n = i;\n+  }\n+  // Sort high bounds of children.\n+  std::sort(sorted.begin(), sorted.end(), StructComp<ElemType>);\n+\n+  size_t splitPointer = fillFactor * node->NumChildren();\n+\n+  axisCut = sorted[splitPointer - 1].d;\n+\n+  // Check if the partition is suitable.\n+  if (!CheckNonLeafSweep(node, axis, axisCut))","path":"src/mlpack/core/tree/rectangle_tree/minimal_coverage_sweep_impl.hpp","position":40,"original_position":40,"commit_id":"e165d759f9ae612b9965f70fbbf8abdb19dc8d07","original_commit_id":"e165d759f9ae612b9965f70fbbf8abdb19dc8d07","user":{"login":"lozhnikov","id":10090844,"avatar_url":"https://avatars.githubusercontent.com/u/10090844?v=3","gravatar_id":"","url":"https://api.github.com/users/lozhnikov","html_url":"https://github.com/lozhnikov","followers_url":"https://api.github.com/users/lozhnikov/followers","following_url":"https://api.github.com/users/lozhnikov/following{/other_user}","gists_url":"https://api.github.com/users/lozhnikov/gists{/gist_id}","starred_url":"https://api.github.com/users/lozhnikov/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lozhnikov/subscriptions","organizations_url":"https://api.github.com/users/lozhnikov/orgs","repos_url":"https://api.github.com/users/lozhnikov/repos","events_url":"https://api.github.com/users/lozhnikov/events{/privacy}","received_events_url":"https://api.github.com/users/lozhnikov/received_events","type":"User","site_admin":false},"body":"Absolutely so, I'll add a comment in order to clarify that.","created_at":"2016-06-29T21:24:02Z","updated_at":"2016-06-29T21:24:02Z","html_url":"https://github.com/mlpack/mlpack/pull/699#discussion_r69030868","pull_request_url":"https://api.github.com/repos/mlpack/mlpack/pulls/699","_links":{"self":{"href":"https://api.github.com/repos/mlpack/mlpack/pulls/comments/69030868"},"html":{"href":"https://github.com/mlpack/mlpack/pull/699#discussion_r69030868"},"pull_request":{"href":"https://api.github.com/repos/mlpack/mlpack/pulls/699"}}},"pull_request":{"url":"https://api.github.com/repos/mlpack/mlpack/pulls/699","id":74019104,"html_url":"https://github.com/mlpack/mlpack/pull/699","diff_url":"https://github.com/mlpack/mlpack/pull/699.diff","patch_url":"https://github.com/mlpack/mlpack/pull/699.patch","issue_url":"https://api.github.com/repos/mlpack/mlpack/issues/699","number":699,"state":"open","locked":false,"title":"R+ and R++ trees implementation","user":{"login":"lozhnikov","id":10090844,"avatar_url":"https://avatars.githubusercontent.com/u/10090844?v=3","gravatar_id":"","url":"https://api.github.com/users/lozhnikov","html_url":"https://github.com/lozhnikov","followers_url":"https://api.github.com/users/lozhnikov/followers","following_url":"https://api.github.com/users/lozhnikov/following{/other_user}","gists_url":"https://api.github.com/users/lozhnikov/gists{/gist_id}","starred_url":"https://api.github.com/users/lozhnikov/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lozhnikov/subscriptions","organizations_url":"https://api.github.com/users/lozhnikov/orgs","repos_url":"https://api.github.com/users/lozhnikov/repos","events_url":"https://api.github.com/users/lozhnikov/events{/privacy}","received_events_url":"https://api.github.com/users/lozhnikov/received_events","type":"User","site_admin":false},"body":"It seems I understood how git-cherry-pick works. If I understand correctly this branch will not be built until   the Hilbert R tree PR is merged.\r\nRight now the R+ tree passes `RectangleTreeTest/RPlusTreeOverlapTest` and `RectangleTreeTest/RPlusTreeTraverserTest`.\r\nI am not sure that the partition algorithm works correctly in general (I am not sure that the resulting nodes will not be overfull). The R+ tree paper enumerates four criteria (section 4 Packing Algorithm). I implemented the criterion \"minimal total space coverage accrued by the two subregions\". Maybe it is good idea to add a template parameter SweepType since there is another clear criterion \"minimal number of rectangle splits\". But I do not undestand how should work the criteria \"nearest neghbors\" and \"minimal total x and y displacement\" and the paper does not explain that.\r\n\r\nAlso I should use \r\n`double RPlusTreeSplit::SweepLeafNode(size_t axis, const TreeType* node,\r\n    size_t fillFactor, ElemType& axisCut)`\r\ninstead of\r\n`double RPlusTreeSplit::SweepLeafNode(size_t axis, const TreeType* node,\r\n    size_t fillFactor, double& axisCut)`\r\n\r\nThe insertion algorithm tries to find the node that contains the point that is being inserted. If there are no such nodes the algorithm tries to enlarge a node. If the algorithm failed an empty node is added to the tree.","created_at":"2016-06-16T03:59:25Z","updated_at":"2016-06-29T21:24:02Z","closed_at":null,"merged_at":null,"merge_commit_sha":"289129ab5217b0b538c2a668b31d3a346ec4a7cd","assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/mlpack/mlpack/pulls/699/commits","review_comments_url":"https://api.github.com/repos/mlpack/mlpack/pulls/699/comments","review_comment_url":"https://api.github.com/repos/mlpack/mlpack/pulls/comments{/number}","comments_url":"https://api.github.com/repos/mlpack/mlpack/issues/699/comments","statuses_url":"https://api.github.com/repos/mlpack/mlpack/statuses/e165d759f9ae612b9965f70fbbf8abdb19dc8d07","head":{"label":"lozhnikov:r_plus_tree-cherry_pick","ref":"r_plus_tree-cherry_pick","sha":"e165d759f9ae612b9965f70fbbf8abdb19dc8d07","user":{"login":"lozhnikov","id":10090844,"avatar_url":"https://avatars.githubusercontent.com/u/10090844?v=3","gravatar_id":"","url":"https://api.github.com/users/lozhnikov","html_url":"https://github.com/lozhnikov","followers_url":"https://api.github.com/users/lozhnikov/followers","following_url":"https://api.github.com/users/lozhnikov/following{/other_user}","gists_url":"https://api.github.com/users/lozhnikov/gists{/gist_id}","starred_url":"https://api.github.com/users/lozhnikov/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lozhnikov/subscriptions","organizations_url":"https://api.github.com/users/lozhnikov/orgs","repos_url":"https://api.github.com/users/lozhnikov/repos","events_url":"https://api.github.com/users/lozhnikov/events{/privacy}","received_events_url":"https://api.github.com/users/lozhnikov/received_events","type":"User","site_admin":false},"repo":{"id":53449734,"name":"mlpack","full_name":"lozhnikov/mlpack","owner":{"login":"lozhnikov","id":10090844,"avatar_url":"https://avatars.githubusercontent.com/u/10090844?v=3","gravatar_id":"","url":"https://api.github.com/users/lozhnikov","html_url":"https://github.com/lozhnikov","followers_url":"https://api.github.com/users/lozhnikov/followers","following_url":"https://api.github.com/users/lozhnikov/following{/other_user}","gists_url":"https://api.github.com/users/lozhnikov/gists{/gist_id}","starred_url":"https://api.github.com/users/lozhnikov/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lozhnikov/subscriptions","organizations_url":"https://api.github.com/users/lozhnikov/orgs","repos_url":"https://api.github.com/users/lozhnikov/repos","events_url":"https://api.github.com/users/lozhnikov/events{/privacy}","received_events_url":"https://api.github.com/users/lozhnikov/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/lozhnikov/mlpack","description":"mlpack: a scalable C++ machine learning library","fork":true,"url":"https://api.github.com/repos/lozhnikov/mlpack","forks_url":"https://api.github.com/repos/lozhnikov/mlpack/forks","keys_url":"https://api.github.com/repos/lozhnikov/mlpack/keys{/key_id}","collaborators_url":"https://api.github.com/repos/lozhnikov/mlpack/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/lozhnikov/mlpack/teams","hooks_url":"https://api.github.com/repos/lozhnikov/mlpack/hooks","issue_events_url":"https://api.github.com/repos/lozhnikov/mlpack/issues/events{/number}","events_url":"https://api.github.com/repos/lozhnikov/mlpack/events","assignees_url":"https://api.github.com/repos/lozhnikov/mlpack/assignees{/user}","branches_url":"https://api.github.com/repos/lozhnikov/mlpack/branches{/branch}","tags_url":"https://api.github.com/repos/lozhnikov/mlpack/tags","blobs_url":"https://api.github.com/repos/lozhnikov/mlpack/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/lozhnikov/mlpack/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/lozhnikov/mlpack/git/refs{/sha}","trees_url":"https://api.github.com/repos/lozhnikov/mlpack/git/trees{/sha}","statuses_url":"https://api.github.com/repos/lozhnikov/mlpack/statuses/{sha}","languages_url":"https://api.github.com/repos/lozhnikov/mlpack/languages","stargazers_url":"https://api.github.com/repos/lozhnikov/mlpack/stargazers","contributors_url":"https://api.github.com/repos/lozhnikov/mlpack/contributors","subscribers_url":"https://api.github.com/repos/lozhnikov/mlpack/subscribers","subscription_url":"https://api.github.com/repos/lozhnikov/mlpack/subscription","commits_url":"https://api.github.com/repos/lozhnikov/mlpack/commits{/sha}","git_commits_url":"https://api.github.com/repos/lozhnikov/mlpack/git/commits{/sha}","comments_url":"https://api.github.com/repos/lozhnikov/mlpack/comments{/number}","issue_comment_url":"https://api.github.com/repos/lozhnikov/mlpack/issues/comments{/number}","contents_url":"https://api.github.com/repos/lozhnikov/mlpack/contents/{+path}","compare_url":"https://api.github.com/repos/lozhnikov/mlpack/compare/{base}...{head}","merges_url":"https://api.github.com/repos/lozhnikov/mlpack/merges","archive_url":"https://api.github.com/repos/lozhnikov/mlpack/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/lozhnikov/mlpack/downloads","issues_url":"https://api.github.com/repos/lozhnikov/mlpack/issues{/number}","pulls_url":"https://api.github.com/repos/lozhnikov/mlpack/pulls{/number}","milestones_url":"https://api.github.com/repos/lozhnikov/mlpack/milestones{/number}","notifications_url":"https://api.github.com/repos/lozhnikov/mlpack/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/lozhnikov/mlpack/labels{/name}","releases_url":"https://api.github.com/repos/lozhnikov/mlpack/releases{/id}","deployments_url":"https://api.github.com/repos/lozhnikov/mlpack/deployments","created_at":"2016-03-08T22:26:22Z","updated_at":"2016-03-08T22:26:25Z","pushed_at":"2016-06-29T16:01:56Z","git_url":"git://github.com/lozhnikov/mlpack.git","ssh_url":"git@github.com:lozhnikov/mlpack.git","clone_url":"https://github.com/lozhnikov/mlpack.git","svn_url":"https://github.com/lozhnikov/mlpack","homepage":null,"size":146125,"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":"mlpack:master","ref":"master","sha":"809ed4bf33cef9de8412fc167cb0e356a369e3b6","user":{"login":"mlpack","id":10216045,"avatar_url":"https://avatars.githubusercontent.com/u/10216045?v=3","gravatar_id":"","url":"https://api.github.com/users/mlpack","html_url":"https://github.com/mlpack","followers_url":"https://api.github.com/users/mlpack/followers","following_url":"https://api.github.com/users/mlpack/following{/other_user}","gists_url":"https://api.github.com/users/mlpack/gists{/gist_id}","starred_url":"https://api.github.com/users/mlpack/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mlpack/subscriptions","organizations_url":"https://api.github.com/users/mlpack/orgs","repos_url":"https://api.github.com/users/mlpack/repos","events_url":"https://api.github.com/users/mlpack/events{/privacy}","received_events_url":"https://api.github.com/users/mlpack/received_events","type":"Organization","site_admin":false},"repo":{"id":28149409,"name":"mlpack","full_name":"mlpack/mlpack","owner":{"login":"mlpack","id":10216045,"avatar_url":"https://avatars.githubusercontent.com/u/10216045?v=3","gravatar_id":"","url":"https://api.github.com/users/mlpack","html_url":"https://github.com/mlpack","followers_url":"https://api.github.com/users/mlpack/followers","following_url":"https://api.github.com/users/mlpack/following{/other_user}","gists_url":"https://api.github.com/users/mlpack/gists{/gist_id}","starred_url":"https://api.github.com/users/mlpack/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mlpack/subscriptions","organizations_url":"https://api.github.com/users/mlpack/orgs","repos_url":"https://api.github.com/users/mlpack/repos","events_url":"https://api.github.com/users/mlpack/events{/privacy}","received_events_url":"https://api.github.com/users/mlpack/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/mlpack/mlpack","description":"mlpack: a scalable C++ machine learning library","fork":false,"url":"https://api.github.com/repos/mlpack/mlpack","forks_url":"https://api.github.com/repos/mlpack/mlpack/forks","keys_url":"https://api.github.com/repos/mlpack/mlpack/keys{/key_id}","collaborators_url":"https://api.github.com/repos/mlpack/mlpack/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/mlpack/mlpack/teams","hooks_url":"https://api.github.com/repos/mlpack/mlpack/hooks","issue_events_url":"https://api.github.com/repos/mlpack/mlpack/issues/events{/number}","events_url":"https://api.github.com/repos/mlpack/mlpack/events","assignees_url":"https://api.github.com/repos/mlpack/mlpack/assignees{/user}","branches_url":"https://api.github.com/repos/mlpack/mlpack/branches{/branch}","tags_url":"https://api.github.com/repos/mlpack/mlpack/tags","blobs_url":"https://api.github.com/repos/mlpack/mlpack/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/mlpack/mlpack/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/mlpack/mlpack/git/refs{/sha}","trees_url":"https://api.github.com/repos/mlpack/mlpack/git/trees{/sha}","statuses_url":"https://api.github.com/repos/mlpack/mlpack/statuses/{sha}","languages_url":"https://api.github.com/repos/mlpack/mlpack/languages","stargazers_url":"https://api.github.com/repos/mlpack/mlpack/stargazers","contributors_url":"https://api.github.com/repos/mlpack/mlpack/contributors","subscribers_url":"https://api.github.com/repos/mlpack/mlpack/subscribers","subscription_url":"https://api.github.com/repos/mlpack/mlpack/subscription","commits_url":"https://api.github.com/repos/mlpack/mlpack/commits{/sha}","git_commits_url":"https://api.github.com/repos/mlpack/mlpack/git/commits{/sha}","comments_url":"https://api.github.com/repos/mlpack/mlpack/comments{/number}","issue_comment_url":"https://api.github.com/repos/mlpack/mlpack/issues/comments{/number}","contents_url":"https://api.github.com/repos/mlpack/mlpack/contents/{+path}","compare_url":"https://api.github.com/repos/mlpack/mlpack/compare/{base}...{head}","merges_url":"https://api.github.com/repos/mlpack/mlpack/merges","archive_url":"https://api.github.com/repos/mlpack/mlpack/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/mlpack/mlpack/downloads","issues_url":"https://api.github.com/repos/mlpack/mlpack/issues{/number}","pulls_url":"https://api.github.com/repos/mlpack/mlpack/pulls{/number}","milestones_url":"https://api.github.com/repos/mlpack/mlpack/milestones{/number}","notifications_url":"https://api.github.com/repos/mlpack/mlpack/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/mlpack/mlpack/labels{/name}","releases_url":"https://api.github.com/repos/mlpack/mlpack/releases{/id}","deployments_url":"https://api.github.com/repos/mlpack/mlpack/deployments","created_at":"2014-12-17T18:16:59Z","updated_at":"2016-06-29T18:22:24Z","pushed_at":"2016-06-29T21:09:06Z","git_url":"git://github.com/mlpack/mlpack.git","ssh_url":"git@github.com:mlpack/mlpack.git","clone_url":"https://github.com/mlpack/mlpack.git","svn_url":"https://github.com/mlpack/mlpack","homepage":null,"size":166775,"stargazers_count":879,"watchers_count":879,"language":"C++","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":353,"mirror_url":null,"open_issues_count":72,"forks":353,"open_issues":72,"watchers":879,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/mlpack/mlpack/pulls/699"},"html":{"href":"https://github.com/mlpack/mlpack/pull/699"},"issue":{"href":"https://api.github.com/repos/mlpack/mlpack/issues/699"},"comments":{"href":"https://api.github.com/repos/mlpack/mlpack/issues/699/comments"},"review_comments":{"href":"https://api.github.com/repos/mlpack/mlpack/pulls/699/comments"},"review_comment":{"href":"https://api.github.com/repos/mlpack/mlpack/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/mlpack/mlpack/pulls/699/commits"},"statuses":{"href":"https://api.github.com/repos/mlpack/mlpack/statuses/e165d759f9ae612b9965f70fbbf8abdb19dc8d07"}}}}
{"actor":{"display_login":"lozhnikov"}}