{"action":"created","comment":{"url":"https://api.github.com/repos/bluss/rust-itertools/pulls/comments/52802960","id":52802960,"diff_hunk":"@@ -689,6 +690,133 @@ impl<I, J, F> Iterator for MergeBy<I, J, F> where\n     }\n }\n \n+/// A non-empty sequence\n+pub struct NonEmpty<I> where\n+    I: Iterator\n+{\n+    head: I::Item,\n+    tail: I,\n+}\n+\n+impl<I> NonEmpty<I> where\n+    I: Iterator,\n+{\n+    /// Constructs a `NonEmpty` from an `Iterator`. Returns `None` if the `Iterator` is empty.\n+    fn new(mut it: I) -> Option<NonEmpty<I>> {\n+        let head = it.next();\n+        head.map(|h| NonEmpty { head: h, tail: it })\n+    }\n+\n+    /// Returns the next item in the sequence. If more items remain, the remainder of the sequence\n+    /// is returned as well, otherwise `None`.\n+    fn next(self) -> (I::Item, Option<Self>) {\n+        (self.head, NonEmpty::new(self.tail))\n+    }\n+\n+    /// Hints at the size of the sequence, same as the `Iterator` method.\n+    fn size_hint(&self) -> (usize, Option<usize>) {\n+        size_hint::add_scalar(self.tail.size_hint(), 1)\n+    }\n+}\n+\n+impl<I> Clone for NonEmpty<I> where\n+    I: Iterator + Clone,\n+    I::Item: Clone\n+{\n+    fn clone(&self) -> Self {\n+        clone_fields!(NonEmpty, self, head, tail)\n+    }\n+}\n+\n+impl<I> PartialEq for NonEmpty<I> where\n+    I: Iterator,\n+    I::Item: PartialEq\n+{\n+    fn eq(&self, other: &NonEmpty<I>) -> bool {\n+        self.head.eq(&other.head)\n+    }\n+}\n+\n+impl<I> Eq for NonEmpty<I> where\n+    I: Iterator,\n+    I::Item: Eq\n+{ }\n+\n+impl<I> PartialOrd for NonEmpty<I> where\n+    I: Iterator,\n+    I::Item: PartialOrd\n+{\n+    fn partial_cmp(&self, other: &NonEmpty<I>) -> Option<Ordering> {\n+        self.head.partial_cmp(&other.head).map(Ordering::reverse)","path":"src/adaptors.rs","position":72,"original_position":72,"commit_id":"5f0d718d0d6f65b18232541cf2d738d13096e156","original_commit_id":"5f0d718d0d6f65b18232541cf2d738d13096e156","user":{"login":"bluss","id":3209739,"avatar_url":"https://avatars.githubusercontent.com/u/3209739?v=3","gravatar_id":"","url":"https://api.github.com/users/bluss","html_url":"https://github.com/bluss","followers_url":"https://api.github.com/users/bluss/followers","following_url":"https://api.github.com/users/bluss/following{/other_user}","gists_url":"https://api.github.com/users/bluss/gists{/gist_id}","starred_url":"https://api.github.com/users/bluss/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bluss/subscriptions","organizations_url":"https://api.github.com/users/bluss/orgs","repos_url":"https://api.github.com/users/bluss/repos","events_url":"https://api.github.com/users/bluss/events{/privacy}","received_events_url":"https://api.github.com/users/bluss/received_events","type":"User","site_admin":false},"body":"Instead of mapping reverse I'd just use other.head.partial_cmp(&self.head) here. Simple and less noise.\r\n\r\nWhat's more important is that it should implement all of lt, le, gt, ge. Implementing the specific comparison operators should have a noticable effect in benchmarks. BinaryHeap uses `>`, `>=`, `<=` it looks like (we just impl all).","created_at":"2016-02-12T21:49:22Z","updated_at":"2016-02-12T21:49:22Z","html_url":"https://github.com/bluss/rust-itertools/pull/97#discussion_r52802960","pull_request_url":"https://api.github.com/repos/bluss/rust-itertools/pulls/97","_links":{"self":{"href":"https://api.github.com/repos/bluss/rust-itertools/pulls/comments/52802960"},"html":{"href":"https://github.com/bluss/rust-itertools/pull/97#discussion_r52802960"},"pull_request":{"href":"https://api.github.com/repos/bluss/rust-itertools/pulls/97"}}},"pull_request":{"url":"https://api.github.com/repos/bluss/rust-itertools/pulls/97","id":59225637,"html_url":"https://github.com/bluss/rust-itertools/pull/97","diff_url":"https://github.com/bluss/rust-itertools/pull/97.diff","patch_url":"https://github.com/bluss/rust-itertools/pull/97.patch","issue_url":"https://api.github.com/repos/bluss/rust-itertools/issues/97","number":97,"state":"open","locked":false,"title":"Add k-way merge adaptor.","user":{"login":"bsteinb","id":3883096,"avatar_url":"https://avatars.githubusercontent.com/u/3883096?v=3","gravatar_id":"","url":"https://api.github.com/users/bsteinb","html_url":"https://github.com/bsteinb","followers_url":"https://api.github.com/users/bsteinb/followers","following_url":"https://api.github.com/users/bsteinb/following{/other_user}","gists_url":"https://api.github.com/users/bsteinb/gists{/gist_id}","starred_url":"https://api.github.com/users/bsteinb/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bsteinb/subscriptions","organizations_url":"https://api.github.com/users/bsteinb/orgs","repos_url":"https://api.github.com/users/bsteinb/repos","events_url":"https://api.github.com/users/bsteinb/events{/privacy}","received_events_url":"https://api.github.com/users/bsteinb/received_events","type":"User","site_admin":false},"body":"Merges an arbitrary number of iterators in ascending order.\r\n\r\nUses `std`'s `BinaryHeap` to decide which iterator to take from next. This seems quite heavyweight. Two-way merge benchmarks take roughly ten times longer than the dedicated two-way merge adaptor. Profiling identifies `BinaryHeap`s `sift_up` as the hot-spot.\r\n\r\nNot completely sure about the interface, the double use of IntoIterator in the free-standing function in particular.","created_at":"2016-02-12T20:20:05Z","updated_at":"2016-02-12T21:49:22Z","closed_at":null,"merged_at":null,"merge_commit_sha":"208330fe8b2e560fba838b9d521e5e577431bbef","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/bluss/rust-itertools/pulls/97/commits","review_comments_url":"https://api.github.com/repos/bluss/rust-itertools/pulls/97/comments","review_comment_url":"https://api.github.com/repos/bluss/rust-itertools/pulls/comments{/number}","comments_url":"https://api.github.com/repos/bluss/rust-itertools/issues/97/comments","statuses_url":"https://api.github.com/repos/bluss/rust-itertools/statuses/5f0d718d0d6f65b18232541cf2d738d13096e156","head":{"label":"bsteinb:kmerge","ref":"kmerge","sha":"5f0d718d0d6f65b18232541cf2d738d13096e156","user":{"login":"bsteinb","id":3883096,"avatar_url":"https://avatars.githubusercontent.com/u/3883096?v=3","gravatar_id":"","url":"https://api.github.com/users/bsteinb","html_url":"https://github.com/bsteinb","followers_url":"https://api.github.com/users/bsteinb/followers","following_url":"https://api.github.com/users/bsteinb/following{/other_user}","gists_url":"https://api.github.com/users/bsteinb/gists{/gist_id}","starred_url":"https://api.github.com/users/bsteinb/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bsteinb/subscriptions","organizations_url":"https://api.github.com/users/bsteinb/orgs","repos_url":"https://api.github.com/users/bsteinb/repos","events_url":"https://api.github.com/users/bsteinb/events{/privacy}","received_events_url":"https://api.github.com/users/bsteinb/received_events","type":"User","site_admin":false},"repo":{"id":51610747,"name":"rust-itertools","full_name":"bsteinb/rust-itertools","owner":{"login":"bsteinb","id":3883096,"avatar_url":"https://avatars.githubusercontent.com/u/3883096?v=3","gravatar_id":"","url":"https://api.github.com/users/bsteinb","html_url":"https://github.com/bsteinb","followers_url":"https://api.github.com/users/bsteinb/followers","following_url":"https://api.github.com/users/bsteinb/following{/other_user}","gists_url":"https://api.github.com/users/bsteinb/gists{/gist_id}","starred_url":"https://api.github.com/users/bsteinb/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bsteinb/subscriptions","organizations_url":"https://api.github.com/users/bsteinb/orgs","repos_url":"https://api.github.com/users/bsteinb/repos","events_url":"https://api.github.com/users/bsteinb/events{/privacy}","received_events_url":"https://api.github.com/users/bsteinb/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/bsteinb/rust-itertools","description":"","fork":true,"url":"https://api.github.com/repos/bsteinb/rust-itertools","forks_url":"https://api.github.com/repos/bsteinb/rust-itertools/forks","keys_url":"https://api.github.com/repos/bsteinb/rust-itertools/keys{/key_id}","collaborators_url":"https://api.github.com/repos/bsteinb/rust-itertools/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/bsteinb/rust-itertools/teams","hooks_url":"https://api.github.com/repos/bsteinb/rust-itertools/hooks","issue_events_url":"https://api.github.com/repos/bsteinb/rust-itertools/issues/events{/number}","events_url":"https://api.github.com/repos/bsteinb/rust-itertools/events","assignees_url":"https://api.github.com/repos/bsteinb/rust-itertools/assignees{/user}","branches_url":"https://api.github.com/repos/bsteinb/rust-itertools/branches{/branch}","tags_url":"https://api.github.com/repos/bsteinb/rust-itertools/tags","blobs_url":"https://api.github.com/repos/bsteinb/rust-itertools/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/bsteinb/rust-itertools/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/bsteinb/rust-itertools/git/refs{/sha}","trees_url":"https://api.github.com/repos/bsteinb/rust-itertools/git/trees{/sha}","statuses_url":"https://api.github.com/repos/bsteinb/rust-itertools/statuses/{sha}","languages_url":"https://api.github.com/repos/bsteinb/rust-itertools/languages","stargazers_url":"https://api.github.com/repos/bsteinb/rust-itertools/stargazers","contributors_url":"https://api.github.com/repos/bsteinb/rust-itertools/contributors","subscribers_url":"https://api.github.com/repos/bsteinb/rust-itertools/subscribers","subscription_url":"https://api.github.com/repos/bsteinb/rust-itertools/subscription","commits_url":"https://api.github.com/repos/bsteinb/rust-itertools/commits{/sha}","git_commits_url":"https://api.github.com/repos/bsteinb/rust-itertools/git/commits{/sha}","comments_url":"https://api.github.com/repos/bsteinb/rust-itertools/comments{/number}","issue_comment_url":"https://api.github.com/repos/bsteinb/rust-itertools/issues/comments{/number}","contents_url":"https://api.github.com/repos/bsteinb/rust-itertools/contents/{+path}","compare_url":"https://api.github.com/repos/bsteinb/rust-itertools/compare/{base}...{head}","merges_url":"https://api.github.com/repos/bsteinb/rust-itertools/merges","archive_url":"https://api.github.com/repos/bsteinb/rust-itertools/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/bsteinb/rust-itertools/downloads","issues_url":"https://api.github.com/repos/bsteinb/rust-itertools/issues{/number}","pulls_url":"https://api.github.com/repos/bsteinb/rust-itertools/pulls{/number}","milestones_url":"https://api.github.com/repos/bsteinb/rust-itertools/milestones{/number}","notifications_url":"https://api.github.com/repos/bsteinb/rust-itertools/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/bsteinb/rust-itertools/labels{/name}","releases_url":"https://api.github.com/repos/bsteinb/rust-itertools/releases{/id}","deployments_url":"https://api.github.com/repos/bsteinb/rust-itertools/deployments","created_at":"2016-02-12T19:22:51Z","updated_at":"2016-02-12T19:22:51Z","pushed_at":"2016-02-12T20:05:19Z","git_url":"git://github.com/bsteinb/rust-itertools.git","ssh_url":"git@github.com:bsteinb/rust-itertools.git","clone_url":"https://github.com/bsteinb/rust-itertools.git","svn_url":"https://github.com/bsteinb/rust-itertools","homepage":"http://bluss.github.io/rust-itertools/","size":5230,"stargazers_count":0,"watchers_count":0,"language":"Rust","has_issues":false,"has_downloads":true,"has_wiki":false,"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":"bluss:master","ref":"master","sha":"9df502075955937ff3f4bd02dcb0cdd5161ba2d1","user":{"login":"bluss","id":3209739,"avatar_url":"https://avatars.githubusercontent.com/u/3209739?v=3","gravatar_id":"","url":"https://api.github.com/users/bluss","html_url":"https://github.com/bluss","followers_url":"https://api.github.com/users/bluss/followers","following_url":"https://api.github.com/users/bluss/following{/other_user}","gists_url":"https://api.github.com/users/bluss/gists{/gist_id}","starred_url":"https://api.github.com/users/bluss/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bluss/subscriptions","organizations_url":"https://api.github.com/users/bluss/orgs","repos_url":"https://api.github.com/users/bluss/repos","events_url":"https://api.github.com/users/bluss/events{/privacy}","received_events_url":"https://api.github.com/users/bluss/received_events","type":"User","site_admin":false},"repo":{"id":22360263,"name":"rust-itertools","full_name":"bluss/rust-itertools","owner":{"login":"bluss","id":3209739,"avatar_url":"https://avatars.githubusercontent.com/u/3209739?v=3","gravatar_id":"","url":"https://api.github.com/users/bluss","html_url":"https://github.com/bluss","followers_url":"https://api.github.com/users/bluss/followers","following_url":"https://api.github.com/users/bluss/following{/other_user}","gists_url":"https://api.github.com/users/bluss/gists{/gist_id}","starred_url":"https://api.github.com/users/bluss/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bluss/subscriptions","organizations_url":"https://api.github.com/users/bluss/orgs","repos_url":"https://api.github.com/users/bluss/repos","events_url":"https://api.github.com/users/bluss/events{/privacy}","received_events_url":"https://api.github.com/users/bluss/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/bluss/rust-itertools","description":"","fork":false,"url":"https://api.github.com/repos/bluss/rust-itertools","forks_url":"https://api.github.com/repos/bluss/rust-itertools/forks","keys_url":"https://api.github.com/repos/bluss/rust-itertools/keys{/key_id}","collaborators_url":"https://api.github.com/repos/bluss/rust-itertools/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/bluss/rust-itertools/teams","hooks_url":"https://api.github.com/repos/bluss/rust-itertools/hooks","issue_events_url":"https://api.github.com/repos/bluss/rust-itertools/issues/events{/number}","events_url":"https://api.github.com/repos/bluss/rust-itertools/events","assignees_url":"https://api.github.com/repos/bluss/rust-itertools/assignees{/user}","branches_url":"https://api.github.com/repos/bluss/rust-itertools/branches{/branch}","tags_url":"https://api.github.com/repos/bluss/rust-itertools/tags","blobs_url":"https://api.github.com/repos/bluss/rust-itertools/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/bluss/rust-itertools/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/bluss/rust-itertools/git/refs{/sha}","trees_url":"https://api.github.com/repos/bluss/rust-itertools/git/trees{/sha}","statuses_url":"https://api.github.com/repos/bluss/rust-itertools/statuses/{sha}","languages_url":"https://api.github.com/repos/bluss/rust-itertools/languages","stargazers_url":"https://api.github.com/repos/bluss/rust-itertools/stargazers","contributors_url":"https://api.github.com/repos/bluss/rust-itertools/contributors","subscribers_url":"https://api.github.com/repos/bluss/rust-itertools/subscribers","subscription_url":"https://api.github.com/repos/bluss/rust-itertools/subscription","commits_url":"https://api.github.com/repos/bluss/rust-itertools/commits{/sha}","git_commits_url":"https://api.github.com/repos/bluss/rust-itertools/git/commits{/sha}","comments_url":"https://api.github.com/repos/bluss/rust-itertools/comments{/number}","issue_comment_url":"https://api.github.com/repos/bluss/rust-itertools/issues/comments{/number}","contents_url":"https://api.github.com/repos/bluss/rust-itertools/contents/{+path}","compare_url":"https://api.github.com/repos/bluss/rust-itertools/compare/{base}...{head}","merges_url":"https://api.github.com/repos/bluss/rust-itertools/merges","archive_url":"https://api.github.com/repos/bluss/rust-itertools/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/bluss/rust-itertools/downloads","issues_url":"https://api.github.com/repos/bluss/rust-itertools/issues{/number}","pulls_url":"https://api.github.com/repos/bluss/rust-itertools/pulls{/number}","milestones_url":"https://api.github.com/repos/bluss/rust-itertools/milestones{/number}","notifications_url":"https://api.github.com/repos/bluss/rust-itertools/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/bluss/rust-itertools/labels{/name}","releases_url":"https://api.github.com/repos/bluss/rust-itertools/releases{/id}","deployments_url":"https://api.github.com/repos/bluss/rust-itertools/deployments","created_at":"2014-07-28T22:34:37Z","updated_at":"2016-02-11T00:03:26Z","pushed_at":"2016-02-12T20:20:06Z","git_url":"git://github.com/bluss/rust-itertools.git","ssh_url":"git@github.com:bluss/rust-itertools.git","clone_url":"https://github.com/bluss/rust-itertools.git","svn_url":"https://github.com/bluss/rust-itertools","homepage":"http://bluss.github.io/rust-itertools/","size":5285,"stargazers_count":119,"watchers_count":119,"language":"Rust","has_issues":true,"has_downloads":true,"has_wiki":false,"has_pages":true,"forks_count":35,"mirror_url":null,"open_issues_count":18,"forks":35,"open_issues":18,"watchers":119,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/bluss/rust-itertools/pulls/97"},"html":{"href":"https://github.com/bluss/rust-itertools/pull/97"},"issue":{"href":"https://api.github.com/repos/bluss/rust-itertools/issues/97"},"comments":{"href":"https://api.github.com/repos/bluss/rust-itertools/issues/97/comments"},"review_comments":{"href":"https://api.github.com/repos/bluss/rust-itertools/pulls/97/comments"},"review_comment":{"href":"https://api.github.com/repos/bluss/rust-itertools/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/bluss/rust-itertools/pulls/97/commits"},"statuses":{"href":"https://api.github.com/repos/bluss/rust-itertools/statuses/5f0d718d0d6f65b18232541cf2d738d13096e156"}}}}