{"action":"created","comment":{"url":"https://api.github.com/repos/tgstation/-tg-station/pulls/comments/40734414","id":40734414,"diff_hunk":"@@ -0,0 +1,78 @@\n+\n+//////////////////////\n+//Heap object\n+//////////////////////\n+\n+/Heap\n+\tvar/list/L\n+\tvar/cmp\n+\n+/Heap/New(compare)\n+\tL = new()\n+\tcmp = compare\n+\n+/Heap/proc/IsEmpty()\n+\treturn !L.len\n+\n+//Insert and place at its position a new node in the heap\n+/Heap/proc/Insert(atom/A)\n+\n+\tL.Add(A)\n+\tSwim(L.len)\n+\n+//removes and returns the first element of the heap\n+//(i.e the max or the min dependant on the comparison function)\n+/Heap/proc/Pop()\n+\tif(!L.len)\n+\t\treturn 0\n+\t. = L[1]\n+\n+\tL[1] = L[L.len]\n+\tL.Cut(L.len)\n+\n+\tSink(1)\n+\n+\treturn .","path":"code/__DATASTRUCTURES/heap.dm","position":35,"original_position":35,"commit_id":"452816475e55f20073994bf3901a03e5143d74e3","original_commit_id":"452816475e55f20073994bf3901a03e5143d74e3","user":{"login":"Menshin","id":7117411,"avatar_url":"https://avatars.githubusercontent.com/u/7117411?v=3","gravatar_id":"","url":"https://api.github.com/users/Menshin","html_url":"https://github.com/Menshin","followers_url":"https://api.github.com/users/Menshin/followers","following_url":"https://api.github.com/users/Menshin/following{/other_user}","gists_url":"https://api.github.com/users/Menshin/gists{/gist_id}","starred_url":"https://api.github.com/users/Menshin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Menshin/subscriptions","organizations_url":"https://api.github.com/users/Menshin/orgs","repos_url":"https://api.github.com/users/Menshin/repos","events_url":"https://api.github.com/users/Menshin/events{/privacy}","received_events_url":"https://api.github.com/users/Menshin/received_events","type":"User","site_admin":false},"body":"Byond never ceases to amaze me.","created_at":"2015-09-29T21:45:22Z","updated_at":"2015-09-29T21:45:22Z","html_url":"https://github.com/tgstation/-tg-station/pull/12076#discussion_r40734414","pull_request_url":"https://api.github.com/repos/tgstation/-tg-station/pulls/12076","_links":{"self":{"href":"https://api.github.com/repos/tgstation/-tg-station/pulls/comments/40734414"},"html":{"href":"https://github.com/tgstation/-tg-station/pull/12076#discussion_r40734414"},"pull_request":{"href":"https://api.github.com/repos/tgstation/-tg-station/pulls/12076"}}},"pull_request":{"url":"https://api.github.com/repos/tgstation/-tg-station/pulls/12076","id":46336021,"html_url":"https://github.com/tgstation/-tg-station/pull/12076","diff_url":"https://github.com/tgstation/-tg-station/pull/12076.diff","patch_url":"https://github.com/tgstation/-tg-station/pull/12076.patch","issue_url":"https://api.github.com/repos/tgstation/-tg-station/issues/12076","number":12076,"state":"open","locked":false,"title":"Some datastructures and A* tweaks","user":{"login":"Menshin","id":7117411,"avatar_url":"https://avatars.githubusercontent.com/u/7117411?v=3","gravatar_id":"","url":"https://api.github.com/users/Menshin","html_url":"https://github.com/Menshin","followers_url":"https://api.github.com/users/Menshin/followers","following_url":"https://api.github.com/users/Menshin/following{/other_user}","gists_url":"https://api.github.com/users/Menshin/gists{/gist_id}","starred_url":"https://api.github.com/users/Menshin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Menshin/subscriptions","organizations_url":"https://api.github.com/users/Menshin/orgs","repos_url":"https://api.github.com/users/Menshin/repos","events_url":"https://api.github.com/users/Menshin/events{/privacy}","received_events_url":"https://api.github.com/users/Menshin/received_events","type":"User","site_admin":false},"body":"### Some datastructures and A* tweaks\r\n\r\n* Made the Priority Queue insertion use dichotomic search to find the position of the inserted element\r\n* Added a generic (array based) heap data structure\r\n* Changed A* to use a heap for the open set instead of a priority queue\r\n* Fixed A* not checking for already processed turfs (shame on whoever fiddled with A*)\r\n* Fixed A* number of traversed nodes not being updated on new route\r\n* Changed the heuristic proc for every A* calls to /turf/proc/Distance_cardinal, since A* now only progress in cardinal directions\r\n\r\nApparently A* had some changes in the recent past, as it:\r\n* now only progress in cardinal directions,\r\n* only progress on simulated turfs,\r\n* check for adjacent turf access if an id is specified (mobs, robots),\r\n* only check adjacent turfs with atmos if no id is specified (meaning everything without an id is considered to spread like a disease).\r\n\r\nThe old procs that were allowing A* progression through space or with diagonal movements are gone, as far as i can tell.","created_at":"2015-09-29T21:42:18Z","updated_at":"2015-09-29T21:45:22Z","closed_at":null,"merged_at":null,"merge_commit_sha":"2daeaa39e11b2b4399302aa7822a2877a50dfca8","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/tgstation/-tg-station/pulls/12076/commits","review_comments_url":"https://api.github.com/repos/tgstation/-tg-station/pulls/12076/comments","review_comment_url":"https://api.github.com/repos/tgstation/-tg-station/pulls/comments{/number}","comments_url":"https://api.github.com/repos/tgstation/-tg-station/issues/12076/comments","statuses_url":"https://api.github.com/repos/tgstation/-tg-station/statuses/452816475e55f20073994bf3901a03e5143d74e3","head":{"label":"Menshin:letsbeaheapstar","ref":"letsbeaheapstar","sha":"452816475e55f20073994bf3901a03e5143d74e3","user":{"login":"Menshin","id":7117411,"avatar_url":"https://avatars.githubusercontent.com/u/7117411?v=3","gravatar_id":"","url":"https://api.github.com/users/Menshin","html_url":"https://github.com/Menshin","followers_url":"https://api.github.com/users/Menshin/followers","following_url":"https://api.github.com/users/Menshin/following{/other_user}","gists_url":"https://api.github.com/users/Menshin/gists{/gist_id}","starred_url":"https://api.github.com/users/Menshin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Menshin/subscriptions","organizations_url":"https://api.github.com/users/Menshin/orgs","repos_url":"https://api.github.com/users/Menshin/repos","events_url":"https://api.github.com/users/Menshin/events{/privacy}","received_events_url":"https://api.github.com/users/Menshin/received_events","type":"User","site_admin":false},"repo":{"id":18300603,"name":"-tg-station","full_name":"Menshin/-tg-station","owner":{"login":"Menshin","id":7117411,"avatar_url":"https://avatars.githubusercontent.com/u/7117411?v=3","gravatar_id":"","url":"https://api.github.com/users/Menshin","html_url":"https://github.com/Menshin","followers_url":"https://api.github.com/users/Menshin/followers","following_url":"https://api.github.com/users/Menshin/following{/other_user}","gists_url":"https://api.github.com/users/Menshin/gists{/gist_id}","starred_url":"https://api.github.com/users/Menshin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Menshin/subscriptions","organizations_url":"https://api.github.com/users/Menshin/orgs","repos_url":"https://api.github.com/users/Menshin/repos","events_url":"https://api.github.com/users/Menshin/events{/privacy}","received_events_url":"https://api.github.com/users/Menshin/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/Menshin/-tg-station","description":"/tg/'s SS13 branch","fork":true,"url":"https://api.github.com/repos/Menshin/-tg-station","forks_url":"https://api.github.com/repos/Menshin/-tg-station/forks","keys_url":"https://api.github.com/repos/Menshin/-tg-station/keys{/key_id}","collaborators_url":"https://api.github.com/repos/Menshin/-tg-station/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/Menshin/-tg-station/teams","hooks_url":"https://api.github.com/repos/Menshin/-tg-station/hooks","issue_events_url":"https://api.github.com/repos/Menshin/-tg-station/issues/events{/number}","events_url":"https://api.github.com/repos/Menshin/-tg-station/events","assignees_url":"https://api.github.com/repos/Menshin/-tg-station/assignees{/user}","branches_url":"https://api.github.com/repos/Menshin/-tg-station/branches{/branch}","tags_url":"https://api.github.com/repos/Menshin/-tg-station/tags","blobs_url":"https://api.github.com/repos/Menshin/-tg-station/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/Menshin/-tg-station/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/Menshin/-tg-station/git/refs{/sha}","trees_url":"https://api.github.com/repos/Menshin/-tg-station/git/trees{/sha}","statuses_url":"https://api.github.com/repos/Menshin/-tg-station/statuses/{sha}","languages_url":"https://api.github.com/repos/Menshin/-tg-station/languages","stargazers_url":"https://api.github.com/repos/Menshin/-tg-station/stargazers","contributors_url":"https://api.github.com/repos/Menshin/-tg-station/contributors","subscribers_url":"https://api.github.com/repos/Menshin/-tg-station/subscribers","subscription_url":"https://api.github.com/repos/Menshin/-tg-station/subscription","commits_url":"https://api.github.com/repos/Menshin/-tg-station/commits{/sha}","git_commits_url":"https://api.github.com/repos/Menshin/-tg-station/git/commits{/sha}","comments_url":"https://api.github.com/repos/Menshin/-tg-station/comments{/number}","issue_comment_url":"https://api.github.com/repos/Menshin/-tg-station/issues/comments{/number}","contents_url":"https://api.github.com/repos/Menshin/-tg-station/contents/{+path}","compare_url":"https://api.github.com/repos/Menshin/-tg-station/compare/{base}...{head}","merges_url":"https://api.github.com/repos/Menshin/-tg-station/merges","archive_url":"https://api.github.com/repos/Menshin/-tg-station/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/Menshin/-tg-station/downloads","issues_url":"https://api.github.com/repos/Menshin/-tg-station/issues{/number}","pulls_url":"https://api.github.com/repos/Menshin/-tg-station/pulls{/number}","milestones_url":"https://api.github.com/repos/Menshin/-tg-station/milestones{/number}","notifications_url":"https://api.github.com/repos/Menshin/-tg-station/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/Menshin/-tg-station/labels{/name}","releases_url":"https://api.github.com/repos/Menshin/-tg-station/releases{/id}","created_at":"2014-03-31T16:52:25Z","updated_at":"2014-12-13T21:38:46Z","pushed_at":"2015-09-29T21:27:26Z","git_url":"git://github.com/Menshin/-tg-station.git","ssh_url":"git@github.com:Menshin/-tg-station.git","clone_url":"https://github.com/Menshin/-tg-station.git","svn_url":"https://github.com/Menshin/-tg-station","homepage":"","size":537413,"stargazers_count":0,"watchers_count":0,"language":"DM","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":"tgstation:master","ref":"master","sha":"bb28a8ce14db4bf7323e5473c82af3fbbd9126c2","user":{"login":"tgstation","id":1363778,"avatar_url":"https://avatars.githubusercontent.com/u/1363778?v=3","gravatar_id":"","url":"https://api.github.com/users/tgstation","html_url":"https://github.com/tgstation","followers_url":"https://api.github.com/users/tgstation/followers","following_url":"https://api.github.com/users/tgstation/following{/other_user}","gists_url":"https://api.github.com/users/tgstation/gists{/gist_id}","starred_url":"https://api.github.com/users/tgstation/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tgstation/subscriptions","organizations_url":"https://api.github.com/users/tgstation/orgs","repos_url":"https://api.github.com/users/tgstation/repos","events_url":"https://api.github.com/users/tgstation/events{/privacy}","received_events_url":"https://api.github.com/users/tgstation/received_events","type":"Organization","site_admin":false},"repo":{"id":3234987,"name":"-tg-station","full_name":"tgstation/-tg-station","owner":{"login":"tgstation","id":1363778,"avatar_url":"https://avatars.githubusercontent.com/u/1363778?v=3","gravatar_id":"","url":"https://api.github.com/users/tgstation","html_url":"https://github.com/tgstation","followers_url":"https://api.github.com/users/tgstation/followers","following_url":"https://api.github.com/users/tgstation/following{/other_user}","gists_url":"https://api.github.com/users/tgstation/gists{/gist_id}","starred_url":"https://api.github.com/users/tgstation/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tgstation/subscriptions","organizations_url":"https://api.github.com/users/tgstation/orgs","repos_url":"https://api.github.com/users/tgstation/repos","events_url":"https://api.github.com/users/tgstation/events{/privacy}","received_events_url":"https://api.github.com/users/tgstation/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/tgstation/-tg-station","description":"the /tg/station branch of SS13","fork":false,"url":"https://api.github.com/repos/tgstation/-tg-station","forks_url":"https://api.github.com/repos/tgstation/-tg-station/forks","keys_url":"https://api.github.com/repos/tgstation/-tg-station/keys{/key_id}","collaborators_url":"https://api.github.com/repos/tgstation/-tg-station/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/tgstation/-tg-station/teams","hooks_url":"https://api.github.com/repos/tgstation/-tg-station/hooks","issue_events_url":"https://api.github.com/repos/tgstation/-tg-station/issues/events{/number}","events_url":"https://api.github.com/repos/tgstation/-tg-station/events","assignees_url":"https://api.github.com/repos/tgstation/-tg-station/assignees{/user}","branches_url":"https://api.github.com/repos/tgstation/-tg-station/branches{/branch}","tags_url":"https://api.github.com/repos/tgstation/-tg-station/tags","blobs_url":"https://api.github.com/repos/tgstation/-tg-station/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/tgstation/-tg-station/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/tgstation/-tg-station/git/refs{/sha}","trees_url":"https://api.github.com/repos/tgstation/-tg-station/git/trees{/sha}","statuses_url":"https://api.github.com/repos/tgstation/-tg-station/statuses/{sha}","languages_url":"https://api.github.com/repos/tgstation/-tg-station/languages","stargazers_url":"https://api.github.com/repos/tgstation/-tg-station/stargazers","contributors_url":"https://api.github.com/repos/tgstation/-tg-station/contributors","subscribers_url":"https://api.github.com/repos/tgstation/-tg-station/subscribers","subscription_url":"https://api.github.com/repos/tgstation/-tg-station/subscription","commits_url":"https://api.github.com/repos/tgstation/-tg-station/commits{/sha}","git_commits_url":"https://api.github.com/repos/tgstation/-tg-station/git/commits{/sha}","comments_url":"https://api.github.com/repos/tgstation/-tg-station/comments{/number}","issue_comment_url":"https://api.github.com/repos/tgstation/-tg-station/issues/comments{/number}","contents_url":"https://api.github.com/repos/tgstation/-tg-station/contents/{+path}","compare_url":"https://api.github.com/repos/tgstation/-tg-station/compare/{base}...{head}","merges_url":"https://api.github.com/repos/tgstation/-tg-station/merges","archive_url":"https://api.github.com/repos/tgstation/-tg-station/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/tgstation/-tg-station/downloads","issues_url":"https://api.github.com/repos/tgstation/-tg-station/issues{/number}","pulls_url":"https://api.github.com/repos/tgstation/-tg-station/pulls{/number}","milestones_url":"https://api.github.com/repos/tgstation/-tg-station/milestones{/number}","notifications_url":"https://api.github.com/repos/tgstation/-tg-station/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/tgstation/-tg-station/labels{/name}","releases_url":"https://api.github.com/repos/tgstation/-tg-station/releases{/id}","created_at":"2012-01-21T17:32:47Z","updated_at":"2015-09-24T06:16:15Z","pushed_at":"2015-09-29T21:42:18Z","git_url":"git://github.com/tgstation/-tg-station.git","ssh_url":"git@github.com:tgstation/-tg-station.git","clone_url":"https://github.com/tgstation/-tg-station.git","svn_url":"https://github.com/tgstation/-tg-station","homepage":"http://www.tgstation13.org/","size":761917,"stargazers_count":244,"watchers_count":244,"language":"DM","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":837,"mirror_url":null,"open_issues_count":862,"forks":837,"open_issues":862,"watchers":244,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/tgstation/-tg-station/pulls/12076"},"html":{"href":"https://github.com/tgstation/-tg-station/pull/12076"},"issue":{"href":"https://api.github.com/repos/tgstation/-tg-station/issues/12076"},"comments":{"href":"https://api.github.com/repos/tgstation/-tg-station/issues/12076/comments"},"review_comments":{"href":"https://api.github.com/repos/tgstation/-tg-station/pulls/12076/comments"},"review_comment":{"href":"https://api.github.com/repos/tgstation/-tg-station/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/tgstation/-tg-station/pulls/12076/commits"},"statuses":{"href":"https://api.github.com/repos/tgstation/-tg-station/statuses/452816475e55f20073994bf3901a03e5143d74e3"}}}}