{"action":"created","comment":{"url":"https://api.github.com/repos/baishancloud/pykit/pulls/comments/150408556","pull_request_review_id":75957361,"id":150408556,"diff_hunk":"@@ -0,0 +1,152 @@\n+from pykit import dictutil\n+\n+EOL = '\\0end'\n+\n+class TrieNode(dict):\n+\n+    def __init__(self, *args, **kwargs):\n+        super(TrieNode, self).__init__(*args, **kwargs)\n+\n+        # Total number of items with the prefix represented by this node.\n+        # `None` means there might be more items with this prefix thus its\n+        # number can not be decided yet.\n+        self.n = None\n+\n+        # Trie branch key, a single char\n+        self.char = ''\n+\n+        # An outstanding node is a node that there might be more following input\n+        # string which has its corresponding prefix.\n+        self.outstanding = None\n+\n+        # If this node is a outstanding node to its parent node.\n+        # When created, a node must be a outstanding node.\n+        self.is_outstanding = True\n+\n+    def __str__(self):\n+\n+        if self.is_outstanding:\n+            mark = '*'\n+        else:\n+            mark = ' '\n+\n+        fields = []\n+\n+        children_keys = sorted(self.keys())\n+\n+        if len(children_keys) > 0:\n+            colon = ': '\n+        else:\n+            colon = ''\n+\n+        line = '{mark}{c},{n}{colon}'.format(c=self.char, n=(self.n or '?'), mark=mark, colon=colon)\n+\n+        for c in children_keys:\n+            substr = str(self[c])\n+            indent = ' ' * len(line)\n+            substr = indent + substr.replace('\\n', '\\n' + indent)\n+\n+            fields.append(substr)\n+\n+        rst = '\\n'.join(fields)\n+        return line + rst[len(line):]\n+\n+\n+def _trie_node(parent, char):\n+    n = TrieNode()\n+    n.char = char\n+    parent.outstanding = n\n+    return n\n+\n+\n+def make_trie(sorted_strings, node_max_num=1):\n+\n+    t = TrieNode()\n+\n+    for _s in sorted_strings:\n+\n+        # find longest common prefix of _s and any seen string\n+        node = t\n+        for i, c in enumerate(_s):\n+            if c in node:\n+                node = node[c]\n+            else:\n+                break\n+\n+        # `node` now is at where the longest common prefix.\n+        # `i` points to next char not in common prefix in `_s`.\n+\n+        # Since `node` is the longest prefix and all input strings are sorted,\n+        # the prefix represented by the child `node.outstanding` can never be a prefix of\n+        # any following strings.\n+        _squash(node.outstanding, node_max_num)","path":"strutil/trie.py","position":82,"original_position":82,"commit_id":"0ae175f18c037f13d38940c6e0088a2ab07c3a82","original_commit_id":"0ae175f18c037f13d38940c6e0088a2ab07c3a82","user":{"login":"lishulong","id":13903162,"avatar_url":"https://avatars2.githubusercontent.com/u/13903162?v=4","gravatar_id":"","url":"https://api.github.com/users/lishulong","html_url":"https://github.com/lishulong","followers_url":"https://api.github.com/users/lishulong/followers","following_url":"https://api.github.com/users/lishulong/following{/other_user}","gists_url":"https://api.github.com/users/lishulong/gists{/gist_id}","starred_url":"https://api.github.com/users/lishulong/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lishulong/subscriptions","organizations_url":"https://api.github.com/users/lishulong/orgs","repos_url":"https://api.github.com/users/lishulong/repos","events_url":"https://api.github.com/users/lishulong/events{/privacy}","received_events_url":"https://api.github.com/users/lishulong/received_events","type":"User","site_admin":false},"body":"这里可能会出现叶节点EOL无法被squash的情况。\r\n例如：文档里面的例子\r\n   'abc',\r\n            'abcdef',\r\n            'abcdeg',\r\n            'abcdfg',\r\n            'abd',\r\n            'abe',\r\n            'axy',\r\n            'b11',\r\n            'b12',\r\n            'b123',\r\n            'b14',\r\n\r\n最后c会有一个EOL无法squash","created_at":"2017-11-12T12:17:39Z","updated_at":"2017-11-12T12:23:28Z","html_url":"https://github.com/baishancloud/pykit/pull/143#discussion_r150408556","pull_request_url":"https://api.github.com/repos/baishancloud/pykit/pulls/143","author_association":"NONE","_links":{"self":{"href":"https://api.github.com/repos/baishancloud/pykit/pulls/comments/150408556"},"html":{"href":"https://github.com/baishancloud/pykit/pull/143#discussion_r150408556"},"pull_request":{"href":"https://api.github.com/repos/baishancloud/pykit/pulls/143"}}},"pull_request":{"url":"https://api.github.com/repos/baishancloud/pykit/pulls/143","id":152047211,"html_url":"https://github.com/baishancloud/pykit/pull/143","diff_url":"https://github.com/baishancloud/pykit/pull/143.diff","patch_url":"https://github.com/baishancloud/pykit/pull/143.patch","issue_url":"https://api.github.com/repos/baishancloud/pykit/issues/143","number":143,"state":"open","locked":false,"title":"strutil: add make_trie() and sharding()","user":{"login":"drmingdrmer","id":44069,"avatar_url":"https://avatars0.githubusercontent.com/u/44069?v=4","gravatar_id":"","url":"https://api.github.com/users/drmingdrmer","html_url":"https://github.com/drmingdrmer","followers_url":"https://api.github.com/users/drmingdrmer/followers","following_url":"https://api.github.com/users/drmingdrmer/following{/other_user}","gists_url":"https://api.github.com/users/drmingdrmer/gists{/gist_id}","starred_url":"https://api.github.com/users/drmingdrmer/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/drmingdrmer/subscriptions","organizations_url":"https://api.github.com/users/drmingdrmer/orgs","repos_url":"https://api.github.com/users/drmingdrmer/repos","events_url":"https://api.github.com/users/drmingdrmer/events{/privacy}","received_events_url":"https://api.github.com/users/drmingdrmer/received_events","type":"User","site_admin":false},"body":"-   strutil.make_trie(): make a trie from sorted string.\r\n-   sharding(): split a list of sorted string into several equal size segement.","created_at":"2017-11-11T07:56:06Z","updated_at":"2017-11-12T12:23:28Z","closed_at":null,"merged_at":null,"merge_commit_sha":"378b90f77d1f876a76995b361fecd59617180a0f","assignee":null,"assignees":[],"requested_reviewers":[{"login":"sejust","id":2747551,"avatar_url":"https://avatars2.githubusercontent.com/u/2747551?v=4","gravatar_id":"","url":"https://api.github.com/users/sejust","html_url":"https://github.com/sejust","followers_url":"https://api.github.com/users/sejust/followers","following_url":"https://api.github.com/users/sejust/following{/other_user}","gists_url":"https://api.github.com/users/sejust/gists{/gist_id}","starred_url":"https://api.github.com/users/sejust/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sejust/subscriptions","organizations_url":"https://api.github.com/users/sejust/orgs","repos_url":"https://api.github.com/users/sejust/repos","events_url":"https://api.github.com/users/sejust/events{/privacy}","received_events_url":"https://api.github.com/users/sejust/received_events","type":"User","site_admin":false},{"login":"wenbobuaa","id":11748387,"avatar_url":"https://avatars3.githubusercontent.com/u/11748387?v=4","gravatar_id":"","url":"https://api.github.com/users/wenbobuaa","html_url":"https://github.com/wenbobuaa","followers_url":"https://api.github.com/users/wenbobuaa/followers","following_url":"https://api.github.com/users/wenbobuaa/following{/other_user}","gists_url":"https://api.github.com/users/wenbobuaa/gists{/gist_id}","starred_url":"https://api.github.com/users/wenbobuaa/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/wenbobuaa/subscriptions","organizations_url":"https://api.github.com/users/wenbobuaa/orgs","repos_url":"https://api.github.com/users/wenbobuaa/repos","events_url":"https://api.github.com/users/wenbobuaa/events{/privacy}","received_events_url":"https://api.github.com/users/wenbobuaa/received_events","type":"User","site_admin":false},{"login":"liubaohai","id":26271283,"avatar_url":"https://avatars2.githubusercontent.com/u/26271283?v=4","gravatar_id":"","url":"https://api.github.com/users/liubaohai","html_url":"https://github.com/liubaohai","followers_url":"https://api.github.com/users/liubaohai/followers","following_url":"https://api.github.com/users/liubaohai/following{/other_user}","gists_url":"https://api.github.com/users/liubaohai/gists{/gist_id}","starred_url":"https://api.github.com/users/liubaohai/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/liubaohai/subscriptions","organizations_url":"https://api.github.com/users/liubaohai/orgs","repos_url":"https://api.github.com/users/liubaohai/repos","events_url":"https://api.github.com/users/liubaohai/events{/privacy}","received_events_url":"https://api.github.com/users/liubaohai/received_events","type":"User","site_admin":false},{"login":"myy2829","id":26829930,"avatar_url":"https://avatars0.githubusercontent.com/u/26829930?v=4","gravatar_id":"","url":"https://api.github.com/users/myy2829","html_url":"https://github.com/myy2829","followers_url":"https://api.github.com/users/myy2829/followers","following_url":"https://api.github.com/users/myy2829/following{/other_user}","gists_url":"https://api.github.com/users/myy2829/gists{/gist_id}","starred_url":"https://api.github.com/users/myy2829/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/myy2829/subscriptions","organizations_url":"https://api.github.com/users/myy2829/orgs","repos_url":"https://api.github.com/users/myy2829/repos","events_url":"https://api.github.com/users/myy2829/events{/privacy}","received_events_url":"https://api.github.com/users/myy2829/received_events","type":"User","site_admin":false},{"login":"tongwei","id":32157039,"avatar_url":"https://avatars2.githubusercontent.com/u/32157039?v=4","gravatar_id":"","url":"https://api.github.com/users/tongwei","html_url":"https://github.com/tongwei","followers_url":"https://api.github.com/users/tongwei/followers","following_url":"https://api.github.com/users/tongwei/following{/other_user}","gists_url":"https://api.github.com/users/tongwei/gists{/gist_id}","starred_url":"https://api.github.com/users/tongwei/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tongwei/subscriptions","organizations_url":"https://api.github.com/users/tongwei/orgs","repos_url":"https://api.github.com/users/tongwei/repos","events_url":"https://api.github.com/users/tongwei/events{/privacy}","received_events_url":"https://api.github.com/users/tongwei/received_events","type":"User","site_admin":false}],"milestone":null,"commits_url":"https://api.github.com/repos/baishancloud/pykit/pulls/143/commits","review_comments_url":"https://api.github.com/repos/baishancloud/pykit/pulls/143/comments","review_comment_url":"https://api.github.com/repos/baishancloud/pykit/pulls/comments{/number}","comments_url":"https://api.github.com/repos/baishancloud/pykit/issues/143/comments","statuses_url":"https://api.github.com/repos/baishancloud/pykit/statuses/0ae175f18c037f13d38940c6e0088a2ab07c3a82","head":{"label":"baishancloud:xp-trie-dist","ref":"xp-trie-dist","sha":"0ae175f18c037f13d38940c6e0088a2ab07c3a82","user":{"login":"baishancloud","id":22903957,"avatar_url":"https://avatars3.githubusercontent.com/u/22903957?v=4","gravatar_id":"","url":"https://api.github.com/users/baishancloud","html_url":"https://github.com/baishancloud","followers_url":"https://api.github.com/users/baishancloud/followers","following_url":"https://api.github.com/users/baishancloud/following{/other_user}","gists_url":"https://api.github.com/users/baishancloud/gists{/gist_id}","starred_url":"https://api.github.com/users/baishancloud/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/baishancloud/subscriptions","organizations_url":"https://api.github.com/users/baishancloud/orgs","repos_url":"https://api.github.com/users/baishancloud/repos","events_url":"https://api.github.com/users/baishancloud/events{/privacy}","received_events_url":"https://api.github.com/users/baishancloud/received_events","type":"Organization","site_admin":false},"repo":{"id":75464992,"name":"pykit","full_name":"baishancloud/pykit","owner":{"login":"baishancloud","id":22903957,"avatar_url":"https://avatars3.githubusercontent.com/u/22903957?v=4","gravatar_id":"","url":"https://api.github.com/users/baishancloud","html_url":"https://github.com/baishancloud","followers_url":"https://api.github.com/users/baishancloud/followers","following_url":"https://api.github.com/users/baishancloud/following{/other_user}","gists_url":"https://api.github.com/users/baishancloud/gists{/gist_id}","starred_url":"https://api.github.com/users/baishancloud/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/baishancloud/subscriptions","organizations_url":"https://api.github.com/users/baishancloud/orgs","repos_url":"https://api.github.com/users/baishancloud/repos","events_url":"https://api.github.com/users/baishancloud/events{/privacy}","received_events_url":"https://api.github.com/users/baishancloud/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/baishancloud/pykit","description":"a collection of toolkit lib for distributed system development in python","fork":false,"url":"https://api.github.com/repos/baishancloud/pykit","forks_url":"https://api.github.com/repos/baishancloud/pykit/forks","keys_url":"https://api.github.com/repos/baishancloud/pykit/keys{/key_id}","collaborators_url":"https://api.github.com/repos/baishancloud/pykit/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/baishancloud/pykit/teams","hooks_url":"https://api.github.com/repos/baishancloud/pykit/hooks","issue_events_url":"https://api.github.com/repos/baishancloud/pykit/issues/events{/number}","events_url":"https://api.github.com/repos/baishancloud/pykit/events","assignees_url":"https://api.github.com/repos/baishancloud/pykit/assignees{/user}","branches_url":"https://api.github.com/repos/baishancloud/pykit/branches{/branch}","tags_url":"https://api.github.com/repos/baishancloud/pykit/tags","blobs_url":"https://api.github.com/repos/baishancloud/pykit/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/baishancloud/pykit/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/baishancloud/pykit/git/refs{/sha}","trees_url":"https://api.github.com/repos/baishancloud/pykit/git/trees{/sha}","statuses_url":"https://api.github.com/repos/baishancloud/pykit/statuses/{sha}","languages_url":"https://api.github.com/repos/baishancloud/pykit/languages","stargazers_url":"https://api.github.com/repos/baishancloud/pykit/stargazers","contributors_url":"https://api.github.com/repos/baishancloud/pykit/contributors","subscribers_url":"https://api.github.com/repos/baishancloud/pykit/subscribers","subscription_url":"https://api.github.com/repos/baishancloud/pykit/subscription","commits_url":"https://api.github.com/repos/baishancloud/pykit/commits{/sha}","git_commits_url":"https://api.github.com/repos/baishancloud/pykit/git/commits{/sha}","comments_url":"https://api.github.com/repos/baishancloud/pykit/comments{/number}","issue_comment_url":"https://api.github.com/repos/baishancloud/pykit/issues/comments{/number}","contents_url":"https://api.github.com/repos/baishancloud/pykit/contents/{+path}","compare_url":"https://api.github.com/repos/baishancloud/pykit/compare/{base}...{head}","merges_url":"https://api.github.com/repos/baishancloud/pykit/merges","archive_url":"https://api.github.com/repos/baishancloud/pykit/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/baishancloud/pykit/downloads","issues_url":"https://api.github.com/repos/baishancloud/pykit/issues{/number}","pulls_url":"https://api.github.com/repos/baishancloud/pykit/pulls{/number}","milestones_url":"https://api.github.com/repos/baishancloud/pykit/milestones{/number}","notifications_url":"https://api.github.com/repos/baishancloud/pykit/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/baishancloud/pykit/labels{/name}","releases_url":"https://api.github.com/repos/baishancloud/pykit/releases{/id}","deployments_url":"https://api.github.com/repos/baishancloud/pykit/deployments","created_at":"2016-12-03T09:38:38Z","updated_at":"2017-10-11T08:47:03Z","pushed_at":"2017-11-11T08:46:18Z","git_url":"git://github.com/baishancloud/pykit.git","ssh_url":"git@github.com:baishancloud/pykit.git","clone_url":"https://github.com/baishancloud/pykit.git","svn_url":"https://github.com/baishancloud/pykit","homepage":null,"size":2900,"stargazers_count":10,"watchers_count":10,"language":"Python","has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":3,"mirror_url":null,"archived":false,"open_issues_count":7,"forks":3,"open_issues":7,"watchers":10,"default_branch":"master"}},"base":{"label":"baishancloud:master","ref":"master","sha":"abc2779c9741ebffcbc687ca5c687c53c6f29660","user":{"login":"baishancloud","id":22903957,"avatar_url":"https://avatars3.githubusercontent.com/u/22903957?v=4","gravatar_id":"","url":"https://api.github.com/users/baishancloud","html_url":"https://github.com/baishancloud","followers_url":"https://api.github.com/users/baishancloud/followers","following_url":"https://api.github.com/users/baishancloud/following{/other_user}","gists_url":"https://api.github.com/users/baishancloud/gists{/gist_id}","starred_url":"https://api.github.com/users/baishancloud/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/baishancloud/subscriptions","organizations_url":"https://api.github.com/users/baishancloud/orgs","repos_url":"https://api.github.com/users/baishancloud/repos","events_url":"https://api.github.com/users/baishancloud/events{/privacy}","received_events_url":"https://api.github.com/users/baishancloud/received_events","type":"Organization","site_admin":false},"repo":{"id":75464992,"name":"pykit","full_name":"baishancloud/pykit","owner":{"login":"baishancloud","id":22903957,"avatar_url":"https://avatars3.githubusercontent.com/u/22903957?v=4","gravatar_id":"","url":"https://api.github.com/users/baishancloud","html_url":"https://github.com/baishancloud","followers_url":"https://api.github.com/users/baishancloud/followers","following_url":"https://api.github.com/users/baishancloud/following{/other_user}","gists_url":"https://api.github.com/users/baishancloud/gists{/gist_id}","starred_url":"https://api.github.com/users/baishancloud/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/baishancloud/subscriptions","organizations_url":"https://api.github.com/users/baishancloud/orgs","repos_url":"https://api.github.com/users/baishancloud/repos","events_url":"https://api.github.com/users/baishancloud/events{/privacy}","received_events_url":"https://api.github.com/users/baishancloud/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/baishancloud/pykit","description":"a collection of toolkit lib for distributed system development in python","fork":false,"url":"https://api.github.com/repos/baishancloud/pykit","forks_url":"https://api.github.com/repos/baishancloud/pykit/forks","keys_url":"https://api.github.com/repos/baishancloud/pykit/keys{/key_id}","collaborators_url":"https://api.github.com/repos/baishancloud/pykit/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/baishancloud/pykit/teams","hooks_url":"https://api.github.com/repos/baishancloud/pykit/hooks","issue_events_url":"https://api.github.com/repos/baishancloud/pykit/issues/events{/number}","events_url":"https://api.github.com/repos/baishancloud/pykit/events","assignees_url":"https://api.github.com/repos/baishancloud/pykit/assignees{/user}","branches_url":"https://api.github.com/repos/baishancloud/pykit/branches{/branch}","tags_url":"https://api.github.com/repos/baishancloud/pykit/tags","blobs_url":"https://api.github.com/repos/baishancloud/pykit/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/baishancloud/pykit/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/baishancloud/pykit/git/refs{/sha}","trees_url":"https://api.github.com/repos/baishancloud/pykit/git/trees{/sha}","statuses_url":"https://api.github.com/repos/baishancloud/pykit/statuses/{sha}","languages_url":"https://api.github.com/repos/baishancloud/pykit/languages","stargazers_url":"https://api.github.com/repos/baishancloud/pykit/stargazers","contributors_url":"https://api.github.com/repos/baishancloud/pykit/contributors","subscribers_url":"https://api.github.com/repos/baishancloud/pykit/subscribers","subscription_url":"https://api.github.com/repos/baishancloud/pykit/subscription","commits_url":"https://api.github.com/repos/baishancloud/pykit/commits{/sha}","git_commits_url":"https://api.github.com/repos/baishancloud/pykit/git/commits{/sha}","comments_url":"https://api.github.com/repos/baishancloud/pykit/comments{/number}","issue_comment_url":"https://api.github.com/repos/baishancloud/pykit/issues/comments{/number}","contents_url":"https://api.github.com/repos/baishancloud/pykit/contents/{+path}","compare_url":"https://api.github.com/repos/baishancloud/pykit/compare/{base}...{head}","merges_url":"https://api.github.com/repos/baishancloud/pykit/merges","archive_url":"https://api.github.com/repos/baishancloud/pykit/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/baishancloud/pykit/downloads","issues_url":"https://api.github.com/repos/baishancloud/pykit/issues{/number}","pulls_url":"https://api.github.com/repos/baishancloud/pykit/pulls{/number}","milestones_url":"https://api.github.com/repos/baishancloud/pykit/milestones{/number}","notifications_url":"https://api.github.com/repos/baishancloud/pykit/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/baishancloud/pykit/labels{/name}","releases_url":"https://api.github.com/repos/baishancloud/pykit/releases{/id}","deployments_url":"https://api.github.com/repos/baishancloud/pykit/deployments","created_at":"2016-12-03T09:38:38Z","updated_at":"2017-10-11T08:47:03Z","pushed_at":"2017-11-11T08:46:18Z","git_url":"git://github.com/baishancloud/pykit.git","ssh_url":"git@github.com:baishancloud/pykit.git","clone_url":"https://github.com/baishancloud/pykit.git","svn_url":"https://github.com/baishancloud/pykit","homepage":null,"size":2900,"stargazers_count":10,"watchers_count":10,"language":"Python","has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":3,"mirror_url":null,"archived":false,"open_issues_count":7,"forks":3,"open_issues":7,"watchers":10,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/baishancloud/pykit/pulls/143"},"html":{"href":"https://github.com/baishancloud/pykit/pull/143"},"issue":{"href":"https://api.github.com/repos/baishancloud/pykit/issues/143"},"comments":{"href":"https://api.github.com/repos/baishancloud/pykit/issues/143/comments"},"review_comments":{"href":"https://api.github.com/repos/baishancloud/pykit/pulls/143/comments"},"review_comment":{"href":"https://api.github.com/repos/baishancloud/pykit/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/baishancloud/pykit/pulls/143/commits"},"statuses":{"href":"https://api.github.com/repos/baishancloud/pykit/statuses/0ae175f18c037f13d38940c6e0088a2ab07c3a82"}},"author_association":"CONTRIBUTOR"}}
{"actor":{"display_login":"lishulong"}}