GitHub PullRequestReviewCommentEvent at 2014-11-22 23:21:12
Repository: collect-rs
Actor: Gankro
Payload: {"action":"created","comment":{"url":"https://api.github.com/repos/Gankro/collect-rs/pulls/comments/20760661","id":20760661,"diff_hunk":"@@ -0,0 +1,393 @@\n+//! This module contains the implementation of an interval heap data structure.\n+\n+use std::mem;\n+use std::vec;\n+\n+// Interval Heap:\n+// --------------\n+// (1) each node (except possibly the last leaf) contains two values\n+//     where the first one is less than or equal to the second one\n+// (2) each node represents a closed interval\n+// (3) a child node's interval is completely contained in the parent node's\n+//     interval\n+\n+\n+// item indices...\n+//\n+//          (0 1)\n+//         /     \\\n+//    (2 3)       (4 5)\n+//    /   \\       /    \\\n+//  (6 7)(8 9)(10 11)(12 13)\n+//  ........................\n+\n+\n+// v[x] for x in [0,len-1) is considered a valid interval heap.\n+// The last item in v is to be added.\n+fn inteval_heap_push<T: Ord>(v: &mut [T]) {\n+    debug_assert!(v.len() > 0);\n+    let mut node_r = v.len() - 1;\n+    let mut node_l = node_r & !1u;\n+    if v[node_l] > v[node_r] { v.swap(node_l, node_r); }\n+    while node_l > 0 {\n+        let parent_l = (node_l / 2 - 1) & !1u;\n+        let parent_r = parent_l + 1;\n+        if v[node_l] < v[parent_l] {\n+            v.swap(parent_l, node_l);\n+        } else if v[parent_r] < v[node_r] {\n+            v.swap(parent_r, node_r);\n+        } else {\n+            return; // nothing to do anymore\n+        }\n+        debug_assert!(!(v[node_r] < v[node_l]));\n+        node_l = parent_l;\n+        node_r = parent_r;\n+    }\n+}\n+\n+// pushes item v[index] down the tree as needed\n+// to restore interval heap properties\n+fn down_min<T: Ord>(v: &mut [T], mut index: uint) {\n+    debug_assert!(index & 1 == 0);\n+    loop {\n+        let c1 = index * 2 + 2;\n+        let c2 = index * 2 + 4;\n+        if v.len() <= c1 { return; }\n+        // which path to go down in the tree?\n+        let ch = if v.len() <= c2 {\n+                     c1 // c1 is the only child\n+                 } else {\n+                     if v[c1] < v[c2] { c1 } else { c2 }\n+                 };\n+        if v[ch] < v[index] {\n+            v.swap(ch, index);\n+            index = ch;\n+            let right = index + 1;\n+            if right < v.len() {\n+                if v[index] > v[right] { v.swap(index, right); }\n+            }\n+        } else {\n+            break;\n+        }\n+    }\n+}\n+\n+// pushes item v[index] down the tree as needed\n+// to restore interval heap properties\n+fn down_max<T: Ord>(v: &mut [T], mut index: uint) {\n+    debug_assert!(index & 1 == 1);\n+    loop {\n+        let c1 = index * 2 + 1;\n+        let c2 = index * 2 + 3;\n+        if v.len() <= c1 { return; }\n+        // which path to go down in the tree?\n+        let ch = if v.len() <= c2 {\n+                     c1 // c1 is the only child\n+                 } else {\n+                     if v[c1] > v[c2] { c1 } else { c2 }\n+                 };\n+        if v[ch] > v[index] {\n+            v.swap(ch, index);\n+            index = ch;\n+            let left = index - 1;\n+            if v[left] > v[index] { v.swap(left, index); }\n+        } else {\n+            break;\n+        }\n+    }\n+}\n+\n+// replaces and element and propagates the new one down the tree\n+fn replace_and_down<T: Ord>(v: &mut [T], index: uint, x: T) -> T {\n+    let res = mem::replace(&mut v[index], x);\n+    if index & 1 == 0 { down_min(v, index); }\n+    else { down_max(v, index); }\n+    res\n+}\n+\n+/// An `IntervalHeap` is an implementation of a double-ended priority queue.\n+/// As such, it supports the following operations: `push`, `get_min`,\n+/// `get_max`, `pop_min`, `pop_max` where insertion takes amortized O(log n)\n+/// time, removal takes O(log n) time and accessing minimum and maximum can\n+/// be done in constant time. Also, other convenient functions are provided\n+/// that handle conversion from and into vectors and allow iteration etc.\n+#[deriving(Clone)]\n+pub struct IntervalHeap<T> {\n+    data: Vec<T>\n+}\n+\n+pub type MoveItems<T> = vec::MoveItems<T>;\n+\n+impl<T> IntervalHeap<T> {\n+    /// creates empty interval heap\n+    pub fn new() -> IntervalHeap<T> {\n+        IntervalHeap { data: Vec::new() }\n+    }\n+    /// creates empty interval heap with a user-defined initial capacity\n+    /// which causes insertions not to reallocate memory if the capacity\n+    /// is sufficient to hold the new items.\n+    pub fn with_capacity(c: uint) -> IntervalHeap<T> {","path":"src/intervalheap.rs","position":129,"original_position":129,"commit_id":"341b061e5fa24d51c994676a227e12cce44f702b","original_commit_id":"341b061e5fa24d51c994676a227e12cce44f702b","user":{"login":"Gankro","id":1136864,"avatar_url":"https://avatars.githubusercontent.com/u/1136864?v=3","gravatar_id":"","url":"https://api.github.com/users/Gankro","html_url":"https://github.com/Gankro","followers_url":"https://api.github.com/users/Gankro/followers","following_url":"https://api.github.com/users/Gankro/following{/other_user}","gists_url":"https://api.github.com/users/Gankro/gists{/gist_id}","starred_url":"https://api.github.com/users/Gankro/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Gankro/subscriptions","organizations_url":"https://api.github.com/users/Gankro/orgs","repos_url":"https://api.github.com/users/Gankro/repos","events_url":"https://api.github.com/users/Gankro/events{/privacy}","received_events_url":"https://api.github.com/users/Gankro/received_events","type":"User","site_admin":false},"body":"I'd just steal the text from BinaryHeap:\r\n\r\n```\r\nCreates an empty BinaryHeap with a specific capacity. This preallocates enough memory for capacity elements, so that the BinaryHeap does not have to be reallocated until it contains at least that many values.\r\n```","created_at":"2014-11-22T23:21:12Z","updated_at":"2014-11-22T23:21:12Z","html_url":"https://github.com/Gankro/collect-rs/pull/1#discussion_r20760661","pull_request_url":"https://api.github.com/repos/Gankro/collect-rs/pulls/1","_links":{"self":{"href":"https://api.github.com/repos/Gankro/collect-rs/pulls/comments/20760661"},"html":{"href":"https://github.com/Gankro/collect-rs/pull/1#discussion_r20760661"},"pull_request":{"href":"https://api.github.com/repos/Gankro/collect-rs/pulls/1"}}},"pull_request":{"url":"https://api.github.com/repos/Gankro/collect-rs/pulls/1","id":24734872,"html_url":"https://github.com/Gankro/collect-rs/pull/1","diff_url":"https://github.com/Gankro/collect-rs/pull/1.diff","patch_url":"https://github.com/Gankro/collect-rs/pull/1.patch","issue_url":"https://api.github.com/repos/Gankro/collect-rs/issues/1","number":1,"state":"open","locked":false,"title":"added interval heap implementation and fixed immutslist test code","user":{"login":"sellibitze","id":290865,"avatar_url":"https://avatars.githubusercontent.com/u/290865?v=3","gravatar_id":"","url":"https://api.github.com/users/sellibitze","html_url":"https://github.com/sellibitze","followers_url":"https://api.github.com/users/sellibitze/followers","following_url":"https://api.github.com/users/sellibitze/following{/other_user}","gists_url":"https://api.github.com/users/sellibitze/gists{/gist_id}","starred_url":"https://api.github.com/users/sellibitze/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sellibitze/subscriptions","organizations_url":"https://api.github.com/users/sellibitze/orgs","repos_url":"https://api.github.com/users/sellibitze/repos","events_url":"https://api.github.com/users/sellibitze/events{/privacy}","received_events_url":"https://api.github.com/users/sellibitze/received_events","type":"User","site_admin":false},"body":"The interval heap seems to be working. Some more tests are probably needed.\r\n\r\ncargo test didn't work for me on immutslist.rs since my version of rustc does not implicitly convert a `[T,..N]` into a `&[T]`. So, I added the necessary ampersands to make it compile.\r\n\r\n","created_at":"2014-11-20T00:51:50Z","updated_at":"2014-11-22T23:21:12Z","closed_at":null,"merged_at":null,"merge_commit_sha":"3eaf8a0f3fdf617166fdbd5392fc6d42164610b8","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/Gankro/collect-rs/pulls/1/commits","review_comments_url":"https://api.github.com/repos/Gankro/collect-rs/pulls/1/comments","review_comment_url":"https://api.github.com/repos/Gankro/collect-rs/pulls/comments/{number}","comments_url":"https://api.github.com/repos/Gankro/collect-rs/issues/1/comments","statuses_url":"https://api.github.com/repos/Gankro/collect-rs/statuses/341b061e5fa24d51c994676a227e12cce44f702b","head":{"label":"sellibitze:master","ref":"master","sha":"341b061e5fa24d51c994676a227e12cce44f702b","user":{"login":"sellibitze","id":290865,"avatar_url":"https://avatars.githubusercontent.com/u/290865?v=3","gravatar_id":"","url":"https://api.github.com/users/sellibitze","html_url":"https://github.com/sellibitze","followers_url":"https://api.github.com/users/sellibitze/followers","following_url":"https://api.github.com/users/sellibitze/following{/other_user}","gists_url":"https://api.github.com/users/sellibitze/gists{/gist_id}","starred_url":"https://api.github.com/users/sellibitze/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sellibitze/subscriptions","organizations_url":"https://api.github.com/users/sellibitze/orgs","repos_url":"https://api.github.com/users/sellibitze/repos","events_url":"https://api.github.com/users/sellibitze/events{/privacy}","received_events_url":"https://api.github.com/users/sellibitze/received_events","type":"User","site_admin":false},"repo":{"id":26888201,"name":"collect-rs","full_name":"sellibitze/collect-rs","owner":{"login":"sellibitze","id":290865,"avatar_url":"https://avatars.githubusercontent.com/u/290865?v=3","gravatar_id":"","url":"https://api.github.com/users/sellibitze","html_url":"https://github.com/sellibitze","followers_url":"https://api.github.com/users/sellibitze/followers","following_url":"https://api.github.com/users/sellibitze/following{/other_user}","gists_url":"https://api.github.com/users/sellibitze/gists{/gist_id}","starred_url":"https://api.github.com/users/sellibitze/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sellibitze/subscriptions","organizations_url":"https://api.github.com/users/sellibitze/orgs","repos_url":"https://api.github.com/users/sellibitze/repos","events_url":"https://api.github.com/users/sellibitze/events{/privacy}","received_events_url":"https://api.github.com/users/sellibitze/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/sellibitze/collect-rs","description":"Miscellanious Collections","fork":true,"url":"https://api.github.com/repos/sellibitze/collect-rs","forks_url":"https://api.github.com/repos/sellibitze/collect-rs/forks","keys_url":"https://api.github.com/repos/sellibitze/collect-rs/keys{/key_id}","collaborators_url":"https://api.github.com/repos/sellibitze/collect-rs/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/sellibitze/collect-rs/teams","hooks_url":"https://api.github.com/repos/sellibitze/collect-rs/hooks","issue_events_url":"https://api.github.com/repos/sellibitze/collect-rs/issues/events{/number}","events_url":"https://api.github.com/repos/sellibitze/collect-rs/events","assignees_url":"https://api.github.com/repos/sellibitze/collect-rs/assignees{/user}","branches_url":"https://api.github.com/repos/sellibitze/collect-rs/branches{/branch}","tags_url":"https://api.github.com/repos/sellibitze/collect-rs/tags","blobs_url":"https://api.github.com/repos/sellibitze/collect-rs/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/sellibitze/collect-rs/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/sellibitze/collect-rs/git/refs{/sha}","trees_url":"https://api.github.com/repos/sellibitze/collect-rs/git/trees{/sha}","statuses_url":"https://api.github.com/repos/sellibitze/collect-rs/statuses/{sha}","languages_url":"https://api.github.com/repos/sellibitze/collect-rs/languages","stargazers_url":"https://api.github.com/repos/sellibitze/collect-rs/stargazers","contributors_url":"https://api.github.com/repos/sellibitze/collect-rs/contributors","subscribers_url":"https://api.github.com/repos/sellibitze/collect-rs/subscribers","subscription_url":"https://api.github.com/repos/sellibitze/collect-rs/subscription","commits_url":"https://api.github.com/repos/sellibitze/collect-rs/commits{/sha}","git_commits_url":"https://api.github.com/repos/sellibitze/collect-rs/git/commits{/sha}","comments_url":"https://api.github.com/repos/sellibitze/collect-rs/comments{/number}","issue_comment_url":"https://api.github.com/repos/sellibitze/collect-rs/issues/comments/{number}","contents_url":"https://api.github.com/repos/sellibitze/collect-rs/contents/{+path}","compare_url":"https://api.github.com/repos/sellibitze/collect-rs/compare/{base}...{head}","merges_url":"https://api.github.com/repos/sellibitze/collect-rs/merges","archive_url":"https://api.github.com/repos/sellibitze/collect-rs/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/sellibitze/collect-rs/downloads","issues_url":"https://api.github.com/repos/sellibitze/collect-rs/issues{/number}","pulls_url":"https://api.github.com/repos/sellibitze/collect-rs/pulls{/number}","milestones_url":"https://api.github.com/repos/sellibitze/collect-rs/milestones{/number}","notifications_url":"https://api.github.com/repos/sellibitze/collect-rs/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/sellibitze/collect-rs/labels{/name}","releases_url":"https://api.github.com/repos/sellibitze/collect-rs/releases{/id}","created_at":"2014-11-20T00:22:33Z","updated_at":"2014-11-21T17:41:21Z","pushed_at":"2014-11-21T17:41:21Z","git_url":"git://github.com/sellibitze/collect-rs.git","ssh_url":"git@github.com:sellibitze/collect-rs.git","clone_url":"https://github.com/sellibitze/collect-rs.git","svn_url":"https://github.com/sellibitze/collect-rs","homepage":null,"size":120,"stargazers_count":0,"watchers_count":0,"language":"Rust","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":"Gankro:master","ref":"master","sha":"c257ed92081e7b7568f812cbbe4f598679321d2b","user":{"login":"Gankro","id":1136864,"avatar_url":"https://avatars.githubusercontent.com/u/1136864?v=3","gravatar_id":"","url":"https://api.github.com/users/Gankro","html_url":"https://github.com/Gankro","followers_url":"https://api.github.com/users/Gankro/followers","following_url":"https://api.github.com/users/Gankro/following{/other_user}","gists_url":"https://api.github.com/users/Gankro/gists{/gist_id}","starred_url":"https://api.github.com/users/Gankro/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Gankro/subscriptions","organizations_url":"https://api.github.com/users/Gankro/orgs","repos_url":"https://api.github.com/users/Gankro/repos","events_url":"https://api.github.com/users/Gankro/events{/privacy}","received_events_url":"https://api.github.com/users/Gankro/received_events","type":"User","site_admin":false},"repo":{"id":25849693,"name":"collect-rs","full_name":"Gankro/collect-rs","owner":{"login":"Gankro","id":1136864,"avatar_url":"https://avatars.githubusercontent.com/u/1136864?v=3","gravatar_id":"","url":"https://api.github.com/users/Gankro","html_url":"https://github.com/Gankro","followers_url":"https://api.github.com/users/Gankro/followers","following_url":"https://api.github.com/users/Gankro/following{/other_user}","gists_url":"https://api.github.com/users/Gankro/gists{/gist_id}","starred_url":"https://api.github.com/users/Gankro/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Gankro/subscriptions","organizations_url":"https://api.github.com/users/Gankro/orgs","repos_url":"https://api.github.com/users/Gankro/repos","events_url":"https://api.github.com/users/Gankro/events{/privacy}","received_events_url":"https://api.github.com/users/Gankro/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/Gankro/collect-rs","description":"Miscellanious Collections","fork":false,"url":"https://api.github.com/repos/Gankro/collect-rs","forks_url":"https://api.github.com/repos/Gankro/collect-rs/forks","keys_url":"https://api.github.com/repos/Gankro/collect-rs/keys{/key_id}","collaborators_url":"https://api.github.com/repos/Gankro/collect-rs/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/Gankro/collect-rs/teams","hooks_url":"https://api.github.com/repos/Gankro/collect-rs/hooks","issue_events_url":"https://api.github.com/repos/Gankro/collect-rs/issues/events{/number}","events_url":"https://api.github.com/repos/Gankro/collect-rs/events","assignees_url":"https://api.github.com/repos/Gankro/collect-rs/assignees{/user}","branches_url":"https://api.github.com/repos/Gankro/collect-rs/branches{/branch}","tags_url":"https://api.github.com/repos/Gankro/collect-rs/tags","blobs_url":"https://api.github.com/repos/Gankro/collect-rs/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/Gankro/collect-rs/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/Gankro/collect-rs/git/refs{/sha}","trees_url":"https://api.github.com/repos/Gankro/collect-rs/git/trees{/sha}","statuses_url":"https://api.github.com/repos/Gankro/collect-rs/statuses/{sha}","languages_url":"https://api.github.com/repos/Gankro/collect-rs/languages","stargazers_url":"https://api.github.com/repos/Gankro/collect-rs/stargazers","contributors_url":"https://api.github.com/repos/Gankro/collect-rs/contributors","subscribers_url":"https://api.github.com/repos/Gankro/collect-rs/subscribers","subscription_url":"https://api.github.com/repos/Gankro/collect-rs/subscription","commits_url":"https://api.github.com/repos/Gankro/collect-rs/commits{/sha}","git_commits_url":"https://api.github.com/repos/Gankro/collect-rs/git/commits{/sha}","comments_url":"https://api.github.com/repos/Gankro/collect-rs/comments{/number}","issue_comment_url":"https://api.github.com/repos/Gankro/collect-rs/issues/comments/{number}","contents_url":"https://api.github.com/repos/Gankro/collect-rs/contents/{+path}","compare_url":"https://api.github.com/repos/Gankro/collect-rs/compare/{base}...{head}","merges_url":"https://api.github.com/repos/Gankro/collect-rs/merges","archive_url":"https://api.github.com/repos/Gankro/collect-rs/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/Gankro/collect-rs/downloads","issues_url":"https://api.github.com/repos/Gankro/collect-rs/issues{/number}","pulls_url":"https://api.github.com/repos/Gankro/collect-rs/pulls{/number}","milestones_url":"https://api.github.com/repos/Gankro/collect-rs/milestones{/number}","notifications_url":"https://api.github.com/repos/Gankro/collect-rs/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/Gankro/collect-rs/labels{/name}","releases_url":"https://api.github.com/repos/Gankro/collect-rs/releases{/id}","created_at":"2014-10-28T02:35:00Z","updated_at":"2014-11-20T22:51:57Z","pushed_at":"2014-11-20T22:51:55Z","git_url":"git://github.com/Gankro/collect-rs.git","ssh_url":"git@github.com:Gankro/collect-rs.git","clone_url":"https://github.com/Gankro/collect-rs.git","svn_url":"https://github.com/Gankro/collect-rs","homepage":null,"size":120,"stargazers_count":0,"watchers_count":0,"language":"Rust","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":1,"mirror_url":null,"open_issues_count":1,"forks":1,"open_issues":1,"watchers":0,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/Gankro/collect-rs/pulls/1"},"html":{"href":"https://github.com/Gankro/collect-rs/pull/1"},"issue":{"href":"https://api.github.com/repos/Gankro/collect-rs/issues/1"},"comments":{"href":"https://api.github.com/repos/Gankro/collect-rs/issues/1/comments"},"review_comments":{"href":"https://api.github.com/repos/Gankro/collect-rs/pulls/1/comments"},"review_comment":{"href":"https://api.github.com/repos/Gankro/collect-rs/pulls/comments/{number}"},"commits":{"href":"https://api.github.com/repos/Gankro/collect-rs/pulls/1/commits"},"statuses":{"href":"https://api.github.com/repos/Gankro/collect-rs/statuses/341b061e5fa24d51c994676a227e12cce44f702b"}}}}