{"action":"created","comment":{"url":"https://api.github.com/repos/seomoz/simhash-cpp/pulls/comments/77031483","id":77031483,"diff_hunk":"@@ -0,0 +1,248 @@\n+#include \"permutation.h\"\n+\n+#include <algorithm>\n+#include <sstream>\n+#include <stdexcept>\n+#include <vector>\n+\n+namespace Simhash {\n+\n+    std::vector<std::vector<hash_t> > Permutation::choose(\n+            const std::vector<hash_t>& population, size_t r)\n+    {\n+        // This algorithm is cribbed from python's itertools page.\n+        size_t n = population.size();\n+        if (r > n)\n+        {\n+            throw std::invalid_argument(\"R cannot be greater than population size.\");\n+        }\n+\n+        std::vector<size_t> indices(r);\n+        for (size_t i = 0; i < r; ++i)\n+        {\n+            indices[i] = i;\n+        }\n+\n+        std::vector<std::vector<hash_t> > results;\n+        std::vector<hash_t> result(r);\n+\n+        for (size_t i = 0; i < r; ++i)\n+        {\n+            result[i] = population[indices[i]];\n+        }\n+        results.push_back(result);\n+\n+        while (true)\n+        {\n+            int i = r - 1;\n+            for (; i >= 0; --i)\n+            {\n+                if (indices[i] != i + n - r)\n+                {\n+                    break;\n+                }\n+            }\n+            if (i < 0)\n+            {\n+                return results;\n+            }\n+\n+            indices[i] += 1;\n+            for (size_t j = i + 1; j < r; ++j)\n+            {\n+                indices[j] = indices[j-1] + 1;\n+            }\n+            for (size_t j = 0; j < r; ++j)\n+            {\n+                result[j] = population[indices[j]];\n+            }\n+            results.push_back(result);\n+        }\n+    }\n+\n+    std::vector<Permutation> Permutation::create(size_t number_of_blocks,\n+                                                 size_t different_bits)\n+    {\n+        if (number_of_blocks > Simhash::BITS)\n+        {\n+            std::stringstream message;\n+            message << \"Number of blocks must not exceed \" << sizeof(hash_t) * 8;\n+            throw std::invalid_argument(message.str());\n+        }\n+\n+        if (number_of_blocks <= different_bits)\n+        {\n+            std::stringstream message;\n+            message << \"Number of blocks (\" << number_of_blocks\n+                    << \") must be greater than different_bits (\" << different_bits\n+                    << \")\";\n+            throw std::invalid_argument(message.str());\n+        }\n+\n+        /* These are the blocks, in mask form. */\n+        std::vector<hash_t> blocks;\n+        for (size_t i = 0; i < number_of_blocks; ++i)\n+        {\n+            hash_t mask(0);\n+            size_t start = (   i    * Simhash::BITS) / number_of_blocks;\n+            size_t end   = ((i + 1) * Simhash::BITS) / number_of_blocks;\n+            for (size_t j = start; j < end; ++j)\n+            {\n+                mask |= (static_cast<hash_t>(1) << j);\n+            }\n+            blocks.push_back(mask);\n+        }\n+\n+        /* This is the number of blocks in the leading prefix. */\n+        size_t count = static_cast<size_t>(number_of_blocks - different_bits);\n+\n+        /* All the mask choices. */\n+        std::vector<Permutation> results;\n+        for (std::vector<hash_t>& choice : choose(blocks, count))\n+        {\n+            // Add the remaining masks -- those that were not part of choice\n+            for (hash_t block : blocks)\n+            {\n+                if (find(choice.begin(), choice.end(), block) == choice.end())\n+                {\n+                    choice.push_back(block);\n+                }\n+            }\n+\n+            results.push_back(Permutation(different_bits, choice));\n+        }\n+        \n+        return results;\n+    }\n+    \n+    Permutation::Permutation(size_t different_bits, std::vector<hash_t>& masks)\n+        : forward_masks(masks)\n+    {\n+        std::vector<size_t> widths;\n+        std::vector<hash_t>::iterator mask_it(forward_masks.begin());\n+        int j(0), i(0), width(0); // counters\n+\n+        /* To more easily and reasonably-efficiently calculate the permutations\n+         * of each of the hashes we insert, and since each block is just\n+         * contiguous set bits, we will calculate the widths of each of these\n+         * blocks, and the offset of their rightmost bit. With this, we'll\n+         * generate net offsets between their positions in the unpermuted and\n+         * permuted forms, and simultaneously generate reverse masks */\n+        for(; mask_it != forward_masks.end(); ++mask_it)\n+        {\n+            hash_t mask = *mask_it;\n+            /* Find where the 1's start, and where they end. After this, `i` is\n+             * the position to the right of the rightmost set bit. `j` is the\n+             * position of the leftmost set bit. In `width`, we keep a running\n+             * tab of the widths of the bitmasks so far. */\n+            for (i = 0;          !((1UL << i) & mask); ++i) {}\n+            for (j = i; j < 64 && ((1UL << j) & mask); ++j) {}\n+\n+            /* Just to prove that I'm sane, and in case that I'm ever running\n+             * circles around this logic in the future, consider:\n+             *\n+             *     63---53|52---42|41---32|31---21|20---10|09---00|\n+             *     |  A   |   B   |   C   |   D   |   E   |   F   |\n+             *\n+             *                       permuted to\n+             *     63---53|52---42|41---32|31---21|20---10|09---00|\n+             *     |  C   |   D   |   E   |   A   |   B   |   F   |\n+             *\n+             * The first loop, we'll have width = 0, and examining the mask for\n+             * C, we'll find that i = 31 and j = 41, so we find that its width\n+             * is 10. In the end, the bit in position 32 needs to move to be in\n+             * position 53. Width serves as an accumulator of the widths of the\n+             * blocks inserted into the permuted value, so we increment it by\n+             * the width of C (j-i) = 10. Now the end offset is 63 - width = 53,\n+             * and the original offset for that bit was (i+1) = 32, and we find\n+             * that we need an offset of 63 - width - i - 1 = 62 - width - i:\n+             *\n+             *    C: i = 31 | j = 41 | width = 0  | end = 53\n+             *       width += (j-i)          => 10\n+             *       offset = 62 - width - i => 21\n+             *\n+             *    D: i = 20 | j = 31 | width = 10 | end = 42\n+             *       width += (j-i)          => 21\n+             *       offset = 62 - width - i => 21 */\n+            width += (j - i);\n+            widths.push_back(j - i);\n+\n+            int offset = 64 - width - i;\n+            offsets.push_back(offset);\n+\n+            /* It's a trivial transformation, but we'll pre-compute our reverse\n+             * masks so that we don't have to compute for after the every time\n+             * we unpermute a number */\n+            if (offset > 0)\n+            {\n+                reverse_masks.push_back(mask <<  offset);\n+            }\n+            else\n+            {\n+                reverse_masks.push_back(mask >> -offset);\n+            }\n+        }\n+\n+        /* Alright, we have to determine the low and high masks for this\n+         * paritcular table. If we are searching for up to /d/ differing bits,","path":"src/permutation.cpp","position":187,"original_position":187,"commit_id":"7158389ac349091d0e2d6e0befb8a23eaa605eff","original_commit_id":"7158389ac349091d0e2d6e0befb8a23eaa605eff","user":{"login":"b4hand","id":708767,"avatar_url":"https://avatars.githubusercontent.com/u/708767?v=3","gravatar_id":"","url":"https://api.github.com/users/b4hand","html_url":"https://github.com/b4hand","followers_url":"https://api.github.com/users/b4hand/followers","following_url":"https://api.github.com/users/b4hand/following{/other_user}","gists_url":"https://api.github.com/users/b4hand/gists{/gist_id}","starred_url":"https://api.github.com/users/b4hand/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/b4hand/subscriptions","organizations_url":"https://api.github.com/users/b4hand/orgs","repos_url":"https://api.github.com/users/b4hand/repos","events_url":"https://api.github.com/users/b4hand/events{/privacy}","received_events_url":"https://api.github.com/users/b4hand/received_events","type":"User","site_admin":false},"body":"s/paritcular/particular/","created_at":"2016-08-31T17:20:24Z","updated_at":"2016-08-31T17:20:24Z","html_url":"https://github.com/seomoz/simhash-cpp/pull/36#discussion_r77031483","pull_request_url":"https://api.github.com/repos/seomoz/simhash-cpp/pulls/36","_links":{"self":{"href":"https://api.github.com/repos/seomoz/simhash-cpp/pulls/comments/77031483"},"html":{"href":"https://github.com/seomoz/simhash-cpp/pull/36#discussion_r77031483"},"pull_request":{"href":"https://api.github.com/repos/seomoz/simhash-cpp/pulls/36"}}},"pull_request":{"url":"https://api.github.com/repos/seomoz/simhash-cpp/pulls/36","id":83357899,"html_url":"https://github.com/seomoz/simhash-cpp/pull/36","diff_url":"https://github.com/seomoz/simhash-cpp/pull/36.diff","patch_url":"https://github.com/seomoz/simhash-cpp/pull/36.patch","issue_url":"https://api.github.com/repos/seomoz/simhash-cpp/issues/36","number":36,"state":"open","locked":false,"title":"BIG-3679 - Slash and burn / drop libjudy","user":{"login":"dlecocq","id":952157,"avatar_url":"https://avatars.githubusercontent.com/u/952157?v=3","gravatar_id":"","url":"https://api.github.com/users/dlecocq","html_url":"https://github.com/dlecocq","followers_url":"https://api.github.com/users/dlecocq/followers","following_url":"https://api.github.com/users/dlecocq/following{/other_user}","gists_url":"https://api.github.com/users/dlecocq/gists{/gist_id}","starred_url":"https://api.github.com/users/dlecocq/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dlecocq/subscriptions","organizations_url":"https://api.github.com/users/dlecocq/orgs","repos_url":"https://api.github.com/users/dlecocq/repos","events_url":"https://api.github.com/users/dlecocq/events{/privacy}","received_events_url":"https://api.github.com/users/dlecocq/received_events","type":"User","site_admin":false},"body":"I dropped large swaths of the existing code in part to simplify reorganizing the code (dropping `catch` in preference for `gtest`, using `include` and `test` directories in addition to `src`, using fewer header-only files, etc.), and in part because there were big chunks we weren't using.  My hope is to grow this out from here as we find we need pieces (specifically thinking of when / if we start doing more tokenization and/or cyclic hashing here).\r\n\r\nThis implements Vadim's algorithm that finds all-to-all matches without external dependencies.\r\n\r\n@lindseyreno @b4hand @tammybailey ","created_at":"2016-08-30T22:19:52Z","updated_at":"2016-08-31T17:20:24Z","closed_at":null,"merged_at":null,"merge_commit_sha":"279fcf9cf4a0ed378a649adfc15cc4cbbb570bf2","assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/seomoz/simhash-cpp/pulls/36/commits","review_comments_url":"https://api.github.com/repos/seomoz/simhash-cpp/pulls/36/comments","review_comment_url":"https://api.github.com/repos/seomoz/simhash-cpp/pulls/comments{/number}","comments_url":"https://api.github.com/repos/seomoz/simhash-cpp/issues/36/comments","statuses_url":"https://api.github.com/repos/seomoz/simhash-cpp/statuses/7158389ac349091d0e2d6e0befb8a23eaa605eff","head":{"label":"seomoz:dan/big-3679-drop-libjudy","ref":"dan/big-3679-drop-libjudy","sha":"7158389ac349091d0e2d6e0befb8a23eaa605eff","user":{"login":"seomoz","id":104895,"avatar_url":"https://avatars.githubusercontent.com/u/104895?v=3","gravatar_id":"","url":"https://api.github.com/users/seomoz","html_url":"https://github.com/seomoz","followers_url":"https://api.github.com/users/seomoz/followers","following_url":"https://api.github.com/users/seomoz/following{/other_user}","gists_url":"https://api.github.com/users/seomoz/gists{/gist_id}","starred_url":"https://api.github.com/users/seomoz/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/seomoz/subscriptions","organizations_url":"https://api.github.com/users/seomoz/orgs","repos_url":"https://api.github.com/users/seomoz/repos","events_url":"https://api.github.com/users/seomoz/events{/privacy}","received_events_url":"https://api.github.com/users/seomoz/received_events","type":"Organization","site_admin":false},"repo":{"id":5158068,"name":"simhash-cpp","full_name":"seomoz/simhash-cpp","owner":{"login":"seomoz","id":104895,"avatar_url":"https://avatars.githubusercontent.com/u/104895?v=3","gravatar_id":"","url":"https://api.github.com/users/seomoz","html_url":"https://github.com/seomoz","followers_url":"https://api.github.com/users/seomoz/followers","following_url":"https://api.github.com/users/seomoz/following{/other_user}","gists_url":"https://api.github.com/users/seomoz/gists{/gist_id}","starred_url":"https://api.github.com/users/seomoz/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/seomoz/subscriptions","organizations_url":"https://api.github.com/users/seomoz/orgs","repos_url":"https://api.github.com/users/seomoz/repos","events_url":"https://api.github.com/users/seomoz/events{/privacy}","received_events_url":"https://api.github.com/users/seomoz/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/seomoz/simhash-cpp","description":"Simhashing in C++","fork":false,"url":"https://api.github.com/repos/seomoz/simhash-cpp","forks_url":"https://api.github.com/repos/seomoz/simhash-cpp/forks","keys_url":"https://api.github.com/repos/seomoz/simhash-cpp/keys{/key_id}","collaborators_url":"https://api.github.com/repos/seomoz/simhash-cpp/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/seomoz/simhash-cpp/teams","hooks_url":"https://api.github.com/repos/seomoz/simhash-cpp/hooks","issue_events_url":"https://api.github.com/repos/seomoz/simhash-cpp/issues/events{/number}","events_url":"https://api.github.com/repos/seomoz/simhash-cpp/events","assignees_url":"https://api.github.com/repos/seomoz/simhash-cpp/assignees{/user}","branches_url":"https://api.github.com/repos/seomoz/simhash-cpp/branches{/branch}","tags_url":"https://api.github.com/repos/seomoz/simhash-cpp/tags","blobs_url":"https://api.github.com/repos/seomoz/simhash-cpp/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/seomoz/simhash-cpp/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/seomoz/simhash-cpp/git/refs{/sha}","trees_url":"https://api.github.com/repos/seomoz/simhash-cpp/git/trees{/sha}","statuses_url":"https://api.github.com/repos/seomoz/simhash-cpp/statuses/{sha}","languages_url":"https://api.github.com/repos/seomoz/simhash-cpp/languages","stargazers_url":"https://api.github.com/repos/seomoz/simhash-cpp/stargazers","contributors_url":"https://api.github.com/repos/seomoz/simhash-cpp/contributors","subscribers_url":"https://api.github.com/repos/seomoz/simhash-cpp/subscribers","subscription_url":"https://api.github.com/repos/seomoz/simhash-cpp/subscription","commits_url":"https://api.github.com/repos/seomoz/simhash-cpp/commits{/sha}","git_commits_url":"https://api.github.com/repos/seomoz/simhash-cpp/git/commits{/sha}","comments_url":"https://api.github.com/repos/seomoz/simhash-cpp/comments{/number}","issue_comment_url":"https://api.github.com/repos/seomoz/simhash-cpp/issues/comments{/number}","contents_url":"https://api.github.com/repos/seomoz/simhash-cpp/contents/{+path}","compare_url":"https://api.github.com/repos/seomoz/simhash-cpp/compare/{base}...{head}","merges_url":"https://api.github.com/repos/seomoz/simhash-cpp/merges","archive_url":"https://api.github.com/repos/seomoz/simhash-cpp/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/seomoz/simhash-cpp/downloads","issues_url":"https://api.github.com/repos/seomoz/simhash-cpp/issues{/number}","pulls_url":"https://api.github.com/repos/seomoz/simhash-cpp/pulls{/number}","milestones_url":"https://api.github.com/repos/seomoz/simhash-cpp/milestones{/number}","notifications_url":"https://api.github.com/repos/seomoz/simhash-cpp/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/seomoz/simhash-cpp/labels{/name}","releases_url":"https://api.github.com/repos/seomoz/simhash-cpp/releases{/id}","deployments_url":"https://api.github.com/repos/seomoz/simhash-cpp/deployments","created_at":"2012-07-23T22:01:11Z","updated_at":"2016-08-30T14:54:10Z","pushed_at":"2016-08-31T17:04:31Z","git_url":"git://github.com/seomoz/simhash-cpp.git","ssh_url":"git@github.com:seomoz/simhash-cpp.git","clone_url":"https://github.com/seomoz/simhash-cpp.git","svn_url":"https://github.com/seomoz/simhash-cpp","homepage":null,"size":147,"stargazers_count":57,"watchers_count":57,"language":"C++","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":30,"mirror_url":null,"open_issues_count":4,"forks":30,"open_issues":4,"watchers":57,"default_branch":"master"}},"base":{"label":"seomoz:master","ref":"master","sha":"a9b21b05b7cf45fe1f42eabbb0c973cc54b0f457","user":{"login":"seomoz","id":104895,"avatar_url":"https://avatars.githubusercontent.com/u/104895?v=3","gravatar_id":"","url":"https://api.github.com/users/seomoz","html_url":"https://github.com/seomoz","followers_url":"https://api.github.com/users/seomoz/followers","following_url":"https://api.github.com/users/seomoz/following{/other_user}","gists_url":"https://api.github.com/users/seomoz/gists{/gist_id}","starred_url":"https://api.github.com/users/seomoz/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/seomoz/subscriptions","organizations_url":"https://api.github.com/users/seomoz/orgs","repos_url":"https://api.github.com/users/seomoz/repos","events_url":"https://api.github.com/users/seomoz/events{/privacy}","received_events_url":"https://api.github.com/users/seomoz/received_events","type":"Organization","site_admin":false},"repo":{"id":5158068,"name":"simhash-cpp","full_name":"seomoz/simhash-cpp","owner":{"login":"seomoz","id":104895,"avatar_url":"https://avatars.githubusercontent.com/u/104895?v=3","gravatar_id":"","url":"https://api.github.com/users/seomoz","html_url":"https://github.com/seomoz","followers_url":"https://api.github.com/users/seomoz/followers","following_url":"https://api.github.com/users/seomoz/following{/other_user}","gists_url":"https://api.github.com/users/seomoz/gists{/gist_id}","starred_url":"https://api.github.com/users/seomoz/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/seomoz/subscriptions","organizations_url":"https://api.github.com/users/seomoz/orgs","repos_url":"https://api.github.com/users/seomoz/repos","events_url":"https://api.github.com/users/seomoz/events{/privacy}","received_events_url":"https://api.github.com/users/seomoz/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/seomoz/simhash-cpp","description":"Simhashing in C++","fork":false,"url":"https://api.github.com/repos/seomoz/simhash-cpp","forks_url":"https://api.github.com/repos/seomoz/simhash-cpp/forks","keys_url":"https://api.github.com/repos/seomoz/simhash-cpp/keys{/key_id}","collaborators_url":"https://api.github.com/repos/seomoz/simhash-cpp/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/seomoz/simhash-cpp/teams","hooks_url":"https://api.github.com/repos/seomoz/simhash-cpp/hooks","issue_events_url":"https://api.github.com/repos/seomoz/simhash-cpp/issues/events{/number}","events_url":"https://api.github.com/repos/seomoz/simhash-cpp/events","assignees_url":"https://api.github.com/repos/seomoz/simhash-cpp/assignees{/user}","branches_url":"https://api.github.com/repos/seomoz/simhash-cpp/branches{/branch}","tags_url":"https://api.github.com/repos/seomoz/simhash-cpp/tags","blobs_url":"https://api.github.com/repos/seomoz/simhash-cpp/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/seomoz/simhash-cpp/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/seomoz/simhash-cpp/git/refs{/sha}","trees_url":"https://api.github.com/repos/seomoz/simhash-cpp/git/trees{/sha}","statuses_url":"https://api.github.com/repos/seomoz/simhash-cpp/statuses/{sha}","languages_url":"https://api.github.com/repos/seomoz/simhash-cpp/languages","stargazers_url":"https://api.github.com/repos/seomoz/simhash-cpp/stargazers","contributors_url":"https://api.github.com/repos/seomoz/simhash-cpp/contributors","subscribers_url":"https://api.github.com/repos/seomoz/simhash-cpp/subscribers","subscription_url":"https://api.github.com/repos/seomoz/simhash-cpp/subscription","commits_url":"https://api.github.com/repos/seomoz/simhash-cpp/commits{/sha}","git_commits_url":"https://api.github.com/repos/seomoz/simhash-cpp/git/commits{/sha}","comments_url":"https://api.github.com/repos/seomoz/simhash-cpp/comments{/number}","issue_comment_url":"https://api.github.com/repos/seomoz/simhash-cpp/issues/comments{/number}","contents_url":"https://api.github.com/repos/seomoz/simhash-cpp/contents/{+path}","compare_url":"https://api.github.com/repos/seomoz/simhash-cpp/compare/{base}...{head}","merges_url":"https://api.github.com/repos/seomoz/simhash-cpp/merges","archive_url":"https://api.github.com/repos/seomoz/simhash-cpp/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/seomoz/simhash-cpp/downloads","issues_url":"https://api.github.com/repos/seomoz/simhash-cpp/issues{/number}","pulls_url":"https://api.github.com/repos/seomoz/simhash-cpp/pulls{/number}","milestones_url":"https://api.github.com/repos/seomoz/simhash-cpp/milestones{/number}","notifications_url":"https://api.github.com/repos/seomoz/simhash-cpp/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/seomoz/simhash-cpp/labels{/name}","releases_url":"https://api.github.com/repos/seomoz/simhash-cpp/releases{/id}","deployments_url":"https://api.github.com/repos/seomoz/simhash-cpp/deployments","created_at":"2012-07-23T22:01:11Z","updated_at":"2016-08-30T14:54:10Z","pushed_at":"2016-08-31T17:04:31Z","git_url":"git://github.com/seomoz/simhash-cpp.git","ssh_url":"git@github.com:seomoz/simhash-cpp.git","clone_url":"https://github.com/seomoz/simhash-cpp.git","svn_url":"https://github.com/seomoz/simhash-cpp","homepage":null,"size":147,"stargazers_count":57,"watchers_count":57,"language":"C++","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":30,"mirror_url":null,"open_issues_count":4,"forks":30,"open_issues":4,"watchers":57,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/seomoz/simhash-cpp/pulls/36"},"html":{"href":"https://github.com/seomoz/simhash-cpp/pull/36"},"issue":{"href":"https://api.github.com/repos/seomoz/simhash-cpp/issues/36"},"comments":{"href":"https://api.github.com/repos/seomoz/simhash-cpp/issues/36/comments"},"review_comments":{"href":"https://api.github.com/repos/seomoz/simhash-cpp/pulls/36/comments"},"review_comment":{"href":"https://api.github.com/repos/seomoz/simhash-cpp/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/seomoz/simhash-cpp/pulls/36/commits"},"statuses":{"href":"https://api.github.com/repos/seomoz/simhash-cpp/statuses/7158389ac349091d0e2d6e0befb8a23eaa605eff"}}}}
{"actor":{"display_login":"b4hand"}}