{"action":"created","comment":{"url":"https://api.github.com/repos/dotnet/roslyn/pulls/comments/47532915","id":47532915,"diff_hunk":"@@ -0,0 +1,184 @@\n+﻿using System;\n+using System.Collections.Generic;\n+using System.Collections.Immutable;\n+using System.Diagnostics;\n+using System.Linq;\n+using System.Text;\n+using System.Threading.Tasks;\n+using Roslyn.Utilities;\n+using static System.Math;\n+using static Roslyn.Utilities.PortableShim;\n+\n+namespace Roslyn.Utilities\n+{\n+    /// <summary>\n+    /// NOTE: do not use this class directly.  It is intended for use only by the spell checker.\n+    /// </summary>\n+    internal partial class BKTree\n+    {\n+        public static readonly BKTree Empty = new BKTree(\n+            SpecializedCollections.EmptyArray<char>(),\n+            ImmutableArray<Node>.Empty,\n+            ImmutableArray<Edge>.Empty);\n+\n+        // We have three completely flat arrays of structs.  These arrays fully represent the \n+        // BK tree.  The structure is as follows:\n+        //\n+        // The root node is in _nodes[0].\n+        //\n+        // It lists the count of edges it has.  These edges are in _edges in the range \n+        // [0*, childCount).  Each edge has the index of the child node it points to, and the\n+        // edit distance between the parent and the child.\n+        //\n+        // * of course '0' is only for the root case.  All nodes state where in _edges\n+        // their child edges range starts.  So the children for any node are in _edges from\n+        // [node.FirstEdgeIndex, node.FirstEdgeIndex + node.EdgeCount)","path":"src/Workspaces/Core/Portable/Utilities/BKTree.cs","position":35,"original_position":35,"commit_id":"5e08f88fefca66089a99f50389ec83b3a55e9806","original_commit_id":"5e08f88fefca66089a99f50389ec83b3a55e9806","user":{"login":"dpoeschl","id":235241,"avatar_url":"https://avatars.githubusercontent.com/u/235241?v=3","gravatar_id":"","url":"https://api.github.com/users/dpoeschl","html_url":"https://github.com/dpoeschl","followers_url":"https://api.github.com/users/dpoeschl/followers","following_url":"https://api.github.com/users/dpoeschl/following{/other_user}","gists_url":"https://api.github.com/users/dpoeschl/gists{/gist_id}","starred_url":"https://api.github.com/users/dpoeschl/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dpoeschl/subscriptions","organizations_url":"https://api.github.com/users/dpoeschl/orgs","repos_url":"https://api.github.com/users/dpoeschl/repos","events_url":"https://api.github.com/users/dpoeschl/events{/privacy}","received_events_url":"https://api.github.com/users/dpoeschl/received_events","type":"User","site_admin":false},"body":"Consider: \"All nodes state where in _edges their child edges range starts, so the children for any node are in the range [node.FirstEdgeIndex, node.FirstEdgeIndex + node.EdgeCount).\"","created_at":"2015-12-14T18:04:40Z","updated_at":"2015-12-14T18:04:40Z","html_url":"https://github.com/dotnet/roslyn/pull/7390#discussion_r47532915","pull_request_url":"https://api.github.com/repos/dotnet/roslyn/pulls/7390","_links":{"self":{"href":"https://api.github.com/repos/dotnet/roslyn/pulls/comments/47532915"},"html":{"href":"https://github.com/dotnet/roslyn/pull/7390#discussion_r47532915"},"pull_request":{"href":"https://api.github.com/repos/dotnet/roslyn/pulls/7390"}}},"pull_request":{"url":"https://api.github.com/repos/dotnet/roslyn/pulls/7390","id":53234233,"html_url":"https://github.com/dotnet/roslyn/pull/7390","diff_url":"https://github.com/dotnet/roslyn/pull/7390.diff","patch_url":"https://github.com/dotnet/roslyn/pull/7390.patch","issue_url":"https://api.github.com/repos/dotnet/roslyn/issues/7390","number":7390,"state":"open","locked":false,"title":"[WIP] Provide a faster implementation of Fuzzy Searching for 'Add Using'.","user":{"login":"CyrusNajmabadi","id":4564579,"avatar_url":"https://avatars.githubusercontent.com/u/4564579?v=3","gravatar_id":"","url":"https://api.github.com/users/CyrusNajmabadi","html_url":"https://github.com/CyrusNajmabadi","followers_url":"https://api.github.com/users/CyrusNajmabadi/followers","following_url":"https://api.github.com/users/CyrusNajmabadi/following{/other_user}","gists_url":"https://api.github.com/users/CyrusNajmabadi/gists{/gist_id}","starred_url":"https://api.github.com/users/CyrusNajmabadi/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/CyrusNajmabadi/subscriptions","organizations_url":"https://api.github.com/users/CyrusNajmabadi/orgs","repos_url":"https://api.github.com/users/CyrusNajmabadi/repos","events_url":"https://api.github.com/users/CyrusNajmabadi/events{/privacy}","received_events_url":"https://api.github.com/users/CyrusNajmabadi/received_events","type":"User","site_admin":false},"body":"This change refactors things to move fuzzy searching to a BK-tree implementatoin.  The BK tree helps reduce the number of of dictionary checks we have to do by about 90%.","created_at":"2015-12-10T09:34:57Z","updated_at":"2015-12-14T18:04:40Z","closed_at":null,"merged_at":null,"merge_commit_sha":"6bd1f47ca668bfb459dbbd15a2d959fe6aac548b","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/dotnet/roslyn/pulls/7390/commits","review_comments_url":"https://api.github.com/repos/dotnet/roslyn/pulls/7390/comments","review_comment_url":"https://api.github.com/repos/dotnet/roslyn/pulls/comments{/number}","comments_url":"https://api.github.com/repos/dotnet/roslyn/issues/7390/comments","statuses_url":"https://api.github.com/repos/dotnet/roslyn/statuses/5e08f88fefca66089a99f50389ec83b3a55e9806","head":{"label":"CyrusNajmabadi:fuzzyMatchingIndex","ref":"fuzzyMatchingIndex","sha":"5e08f88fefca66089a99f50389ec83b3a55e9806","user":{"login":"CyrusNajmabadi","id":4564579,"avatar_url":"https://avatars.githubusercontent.com/u/4564579?v=3","gravatar_id":"","url":"https://api.github.com/users/CyrusNajmabadi","html_url":"https://github.com/CyrusNajmabadi","followers_url":"https://api.github.com/users/CyrusNajmabadi/followers","following_url":"https://api.github.com/users/CyrusNajmabadi/following{/other_user}","gists_url":"https://api.github.com/users/CyrusNajmabadi/gists{/gist_id}","starred_url":"https://api.github.com/users/CyrusNajmabadi/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/CyrusNajmabadi/subscriptions","organizations_url":"https://api.github.com/users/CyrusNajmabadi/orgs","repos_url":"https://api.github.com/users/CyrusNajmabadi/repos","events_url":"https://api.github.com/users/CyrusNajmabadi/events{/privacy}","received_events_url":"https://api.github.com/users/CyrusNajmabadi/received_events","type":"User","site_admin":false},"repo":{"id":30565155,"name":"roslyn","full_name":"CyrusNajmabadi/roslyn","owner":{"login":"CyrusNajmabadi","id":4564579,"avatar_url":"https://avatars.githubusercontent.com/u/4564579?v=3","gravatar_id":"","url":"https://api.github.com/users/CyrusNajmabadi","html_url":"https://github.com/CyrusNajmabadi","followers_url":"https://api.github.com/users/CyrusNajmabadi/followers","following_url":"https://api.github.com/users/CyrusNajmabadi/following{/other_user}","gists_url":"https://api.github.com/users/CyrusNajmabadi/gists{/gist_id}","starred_url":"https://api.github.com/users/CyrusNajmabadi/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/CyrusNajmabadi/subscriptions","organizations_url":"https://api.github.com/users/CyrusNajmabadi/orgs","repos_url":"https://api.github.com/users/CyrusNajmabadi/repos","events_url":"https://api.github.com/users/CyrusNajmabadi/events{/privacy}","received_events_url":"https://api.github.com/users/CyrusNajmabadi/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/CyrusNajmabadi/roslyn","description":"The .NET Compiler Platform (\"Roslyn\") provides open-source C# and Visual Basic compilers with rich code analysis APIs.","fork":true,"url":"https://api.github.com/repos/CyrusNajmabadi/roslyn","forks_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/forks","keys_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/keys{/key_id}","collaborators_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/teams","hooks_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/hooks","issue_events_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/issues/events{/number}","events_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/events","assignees_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/assignees{/user}","branches_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/branches{/branch}","tags_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/tags","blobs_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/git/refs{/sha}","trees_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/git/trees{/sha}","statuses_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/statuses/{sha}","languages_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/languages","stargazers_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/stargazers","contributors_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/contributors","subscribers_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/subscribers","subscription_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/subscription","commits_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/commits{/sha}","git_commits_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/git/commits{/sha}","comments_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/comments{/number}","issue_comment_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/issues/comments{/number}","contents_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/contents/{+path}","compare_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/compare/{base}...{head}","merges_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/merges","archive_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/downloads","issues_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/issues{/number}","pulls_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/pulls{/number}","milestones_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/milestones{/number}","notifications_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/labels{/name}","releases_url":"https://api.github.com/repos/CyrusNajmabadi/roslyn/releases{/id}","created_at":"2015-02-09T23:45:22Z","updated_at":"2015-02-12T20:34:05Z","pushed_at":"2015-12-14T02:46:35Z","git_url":"git://github.com/CyrusNajmabadi/roslyn.git","ssh_url":"git@github.com:CyrusNajmabadi/roslyn.git","clone_url":"https://github.com/CyrusNajmabadi/roslyn.git","svn_url":"https://github.com/CyrusNajmabadi/roslyn","homepage":"","size":119495,"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":"dotnet:master","ref":"master","sha":"458725cede9fd3ad43bd465c0dfe2f9096f36b1e","user":{"login":"dotnet","id":9141961,"avatar_url":"https://avatars.githubusercontent.com/u/9141961?v=3","gravatar_id":"","url":"https://api.github.com/users/dotnet","html_url":"https://github.com/dotnet","followers_url":"https://api.github.com/users/dotnet/followers","following_url":"https://api.github.com/users/dotnet/following{/other_user}","gists_url":"https://api.github.com/users/dotnet/gists{/gist_id}","starred_url":"https://api.github.com/users/dotnet/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dotnet/subscriptions","organizations_url":"https://api.github.com/users/dotnet/orgs","repos_url":"https://api.github.com/users/dotnet/repos","events_url":"https://api.github.com/users/dotnet/events{/privacy}","received_events_url":"https://api.github.com/users/dotnet/received_events","type":"Organization","site_admin":false},"repo":{"id":29078997,"name":"roslyn","full_name":"dotnet/roslyn","owner":{"login":"dotnet","id":9141961,"avatar_url":"https://avatars.githubusercontent.com/u/9141961?v=3","gravatar_id":"","url":"https://api.github.com/users/dotnet","html_url":"https://github.com/dotnet","followers_url":"https://api.github.com/users/dotnet/followers","following_url":"https://api.github.com/users/dotnet/following{/other_user}","gists_url":"https://api.github.com/users/dotnet/gists{/gist_id}","starred_url":"https://api.github.com/users/dotnet/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dotnet/subscriptions","organizations_url":"https://api.github.com/users/dotnet/orgs","repos_url":"https://api.github.com/users/dotnet/repos","events_url":"https://api.github.com/users/dotnet/events{/privacy}","received_events_url":"https://api.github.com/users/dotnet/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/dotnet/roslyn","description":"The .NET Compiler Platform (\"Roslyn\") provides open-source C# and Visual Basic compilers with rich code analysis APIs.","fork":false,"url":"https://api.github.com/repos/dotnet/roslyn","forks_url":"https://api.github.com/repos/dotnet/roslyn/forks","keys_url":"https://api.github.com/repos/dotnet/roslyn/keys{/key_id}","collaborators_url":"https://api.github.com/repos/dotnet/roslyn/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/dotnet/roslyn/teams","hooks_url":"https://api.github.com/repos/dotnet/roslyn/hooks","issue_events_url":"https://api.github.com/repos/dotnet/roslyn/issues/events{/number}","events_url":"https://api.github.com/repos/dotnet/roslyn/events","assignees_url":"https://api.github.com/repos/dotnet/roslyn/assignees{/user}","branches_url":"https://api.github.com/repos/dotnet/roslyn/branches{/branch}","tags_url":"https://api.github.com/repos/dotnet/roslyn/tags","blobs_url":"https://api.github.com/repos/dotnet/roslyn/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/dotnet/roslyn/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/dotnet/roslyn/git/refs{/sha}","trees_url":"https://api.github.com/repos/dotnet/roslyn/git/trees{/sha}","statuses_url":"https://api.github.com/repos/dotnet/roslyn/statuses/{sha}","languages_url":"https://api.github.com/repos/dotnet/roslyn/languages","stargazers_url":"https://api.github.com/repos/dotnet/roslyn/stargazers","contributors_url":"https://api.github.com/repos/dotnet/roslyn/contributors","subscribers_url":"https://api.github.com/repos/dotnet/roslyn/subscribers","subscription_url":"https://api.github.com/repos/dotnet/roslyn/subscription","commits_url":"https://api.github.com/repos/dotnet/roslyn/commits{/sha}","git_commits_url":"https://api.github.com/repos/dotnet/roslyn/git/commits{/sha}","comments_url":"https://api.github.com/repos/dotnet/roslyn/comments{/number}","issue_comment_url":"https://api.github.com/repos/dotnet/roslyn/issues/comments{/number}","contents_url":"https://api.github.com/repos/dotnet/roslyn/contents/{+path}","compare_url":"https://api.github.com/repos/dotnet/roslyn/compare/{base}...{head}","merges_url":"https://api.github.com/repos/dotnet/roslyn/merges","archive_url":"https://api.github.com/repos/dotnet/roslyn/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/dotnet/roslyn/downloads","issues_url":"https://api.github.com/repos/dotnet/roslyn/issues{/number}","pulls_url":"https://api.github.com/repos/dotnet/roslyn/pulls{/number}","milestones_url":"https://api.github.com/repos/dotnet/roslyn/milestones{/number}","notifications_url":"https://api.github.com/repos/dotnet/roslyn/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/dotnet/roslyn/labels{/name}","releases_url":"https://api.github.com/repos/dotnet/roslyn/releases{/id}","created_at":"2015-01-11T02:39:03Z","updated_at":"2015-12-14T16:59:18Z","pushed_at":"2015-12-14T16:00:03Z","git_url":"git://github.com/dotnet/roslyn.git","ssh_url":"git@github.com:dotnet/roslyn.git","clone_url":"https://github.com/dotnet/roslyn.git","svn_url":"https://github.com/dotnet/roslyn","homepage":"","size":145280,"stargazers_count":4003,"watchers_count":4003,"language":"C#","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":983,"mirror_url":null,"open_issues_count":1793,"forks":983,"open_issues":1793,"watchers":4003,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/dotnet/roslyn/pulls/7390"},"html":{"href":"https://github.com/dotnet/roslyn/pull/7390"},"issue":{"href":"https://api.github.com/repos/dotnet/roslyn/issues/7390"},"comments":{"href":"https://api.github.com/repos/dotnet/roslyn/issues/7390/comments"},"review_comments":{"href":"https://api.github.com/repos/dotnet/roslyn/pulls/7390/comments"},"review_comment":{"href":"https://api.github.com/repos/dotnet/roslyn/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/dotnet/roslyn/pulls/7390/commits"},"statuses":{"href":"https://api.github.com/repos/dotnet/roslyn/statuses/5e08f88fefca66089a99f50389ec83b3a55e9806"}}}}