{"action":"created","comment":{"url":"https://api.github.com/repos/nitlang/nit/pulls/comments/38716632","id":38716632,"diff_hunk":"@@ -0,0 +1,614 @@\n+# This file is part of NIT ( http://www.nitlanguage.org ).\n+#\n+# Licensed under the Apache License, Version 2.0 (the \"License\");\n+# you may not use this file except in compliance with the License.\n+# You may obtain a copy of the License at\n+#\n+#     http://www.apache.org/licenses/LICENSE-2.0\n+#\n+# Unless required by applicable law or agreed to in writing, software\n+# distributed under the License is distributed on an \"AS IS\" BASIS,\n+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n+# See the License for the specific language governing permissions and\n+# limitations under the License.\n+\n+# Common tree structure\n+#\n+# Hierarchical representation of data using recursive collections of nodes.\n+#\n+# This one differs from the `bintree` and `rbtree` implementation since it allows\n+# more tha two children by node.\n+module tree\n+\n+import abstract_tree\n+\n+# Tree structure\n+#\n+# The tree contains a `root` node. If `root == null` then the tree is empty.\n+# Each node can have `0..n` children.\n+#\n+# Usage:\n+#\n+# ~~~\n+# var tree = new Tree[Int, String]\n+# var na = new TreeNode[Int, String](0, \"a\")\n+# var nb = new TreeNode[Int, String](1, \"b\")\n+# var nc = new TreeNode[Int, String](2, \"c\")\n+# var nd = new TreeNode[Int, String](3, \"d\")\n+#\n+# tree.add_node(na) # a is root\n+# tree.add_node(nb, na)\n+# tree.add_node(nc, na)\n+# tree.add_node(nd, nc)\n+#\n+# assert tree.to_formatted_string == \"\"\"\n+# a\n+#  b\n+#  c\n+#   d\n+# \"\"\"\n+# ~~~\n+#\n+# Use `show_dot` to display a graphic representation of a tree using graphiz.\n+#\n+# Trees are also comparable, see `Tree::distance_from`.\n+class Tree[K: Comparable, E]\n+\tsuper TreeMap[K, E]\n+\n+\tredef type N: TreeNode[K, E]\n+\n+\t# Initialize a tree from a formatted string\n+\t#\n+\t# Mainly used for testing purpose.\n+\t#\n+\t# Format:\n+\t# * root must be on the first column\n+\t# * only one root is allowed (no forest)\n+\t# * nodes are indented with a space character defining their depth in tree\n+\t# * empty lines are skip\n+\t#\n+\t# Usage:\n+\t# ~~~\n+\t# var str = \"\"\"\n+\t# root\n+\t#  a\n+\t#   b\n+\t#    c\n+\t#   d\n+\t#    e\n+\t#     f\n+\t# \"\"\"\n+\t# var tree = new Tree[Int, String].from_string(str)\n+\t# assert tree[0] == \"root\"\n+\t# assert tree[1] == \"a\"\n+\t# assert tree[2] == \"b\"\n+\t# ~~~\n+\t#\n+\t# Node keys can be specified in the format:\n+\t# ~~~\n+\t# str = \"\"\"\n+\t# 1:root\n+\t#  2:b\n+\t#   3:c\n+\t#  4:d\n+\t# \"\"\"\n+\t# tree = new Tree[Int, String].from_string(str)\n+\t# assert tree.length == 4\n+\t# assert tree[4] == \"d\"\n+\t# ~~~\n+\t#\n+\t# TODO accept more format (like with indents)\n+\t# FIXME This is unsafe:\n+\t# * returned nodes are of the type TreeNode[Int, String]\n+\t# * self is typed by Tree[K, E]\n+\t#\n+\t# Should we declare this as a top_level function?\n+\tinit from_string(str: String) do\n+\t\tvar lines = str.split(\"\\n\")\n+\t\tif lines.is_empty then return\n+\t\tvar root = parse_line(0, lines.first)\n+\t\tadd_node(root)\n+\t\tvar parents = new List[N]\n+\t\tparents.add root\n+\t\tfor i in [1..lines.length[ do\n+\t\t\tvar line = lines[i]\n+\t\t\tif line.is_empty then continue\n+\t\t\tvar node = parse_line(i, lines[i])\n+\t\t\tvar space = line.space_before\n+\t\t\tif space > parents.last.depth then\n+\t\t\t\tadd_node(node, parents.last)\n+\t\t\t\tparents.add node\n+\t\t\telse\n+\t\t\t\twhile space <= parents.last.depth do\n+\t\t\t\t\tparents.pop\n+\t\t\t\tend\n+\t\t\t\tadd_node(node, parents.last)\n+\t\t\t\tparents.add node\n+\t\t\tend\n+\t\tend\n+\tend\n+\n+\t# Build this tree from a source file formatted as expected by `from_string`\n+\tinit from_file(file: String) do\n+\t\tassert file.file_exists\n+\t\tvar r = new FileReader.open(file)\n+\t\tfrom_string r.read_all\n+\t\tr.close\n+\tend\n+\n+\t# Extract the node representation from a formated `line`\n+\t#\n+\t# Format is of the form `key:value` where `key:` is optional.\n+\t# If `key:` is found in string, the `key` parameter is overriden.\n+\t#\n+\t# Used by `from_string` constructor.\n+\t#\n+\t#     intrude import tree\n+\t#     var tree = new Tree[Int, String]\n+\t#     assert tree.parse_line(0, \"foo\").key == 0\n+\t#     assert tree.parse_line(0, \"1:foo\").key == 1\n+\tprivate fun parse_line(id: Int, line: String): N do\n+\t\tvar ls = line.trim.split(\":\")\n+\t\tif ls.length > 1 then\n+\t\t\treturn new TreeNode[Int, String](ls.first.to_i, ls.last)\n+\t\tend\n+\t\treturn new TreeNode[Int, String](id, line.trim)\n+\tend\n+\n+\t# Add a node to the tree\n+\t#\n+\t# If `parent == null` then node is set as the root node.\n+\t# Set `node.parent = parent` otherelse.\n+\t#\n+\t# It is recommanded to use this method instead setting the parent by hand\n+\t# because it also handles the `Tree::ids` and `node.children` saving.\n+\tfun add_node(node: N, parent: nullable N) do\n+\t\tnodes[node.key] = node\n+\t\tif parent == null then\n+\t\t\troot = node\n+\t\telse\n+\t\t\tnode.parent = parent\n+\t\t\tparent.children.add node\n+\t\tend\n+\tend\n+\n+\t# Tree nodes mapped to their key ids\n+\t# ~~~\n+\t# var str = \"\"\"\n+\t# a\n+\t#  b\n+\t#   c\n+\t# \"\"\"\n+\t# var tree = new Tree[Int, String].from_string(str)\n+\t# assert tree.nodes[0].value == \"a\"\n+\t# assert tree.nodes[1].value == \"b\"\n+\t# assert tree.nodes[2].value == \"c\"\n+\t# ~~~\n+\t#\n+\t# Ids can be specified in the format:\n+\t# ~~~\n+\t# str = \"\"\"\n+\t# 10:a\n+\t#  20:b\n+\t#   0:c\n+\t# \"\"\"\n+\t# tree = new Tree[Int, String].from_string(str)\n+\t# assert tree.nodes[10].value == \"a\"\n+\t# assert tree.nodes[20].value == \"b\"\n+\t# assert tree.nodes[0].value == \"c\"\n+\t# ~~~\n+\tvar nodes = new HashMap[K, N]","path":"lib/trees/tree.nit","position":200,"original_position":200,"commit_id":"010076612d1d99fe71e6ec140dde2b7aaf178351","original_commit_id":"010076612d1d99fe71e6ec140dde2b7aaf178351","user":{"login":"privat","id":135828,"avatar_url":"https://avatars.githubusercontent.com/u/135828?v=3","gravatar_id":"","url":"https://api.github.com/users/privat","html_url":"https://github.com/privat","followers_url":"https://api.github.com/users/privat/followers","following_url":"https://api.github.com/users/privat/following{/other_user}","gists_url":"https://api.github.com/users/privat/gists{/gist_id}","starred_url":"https://api.github.com/users/privat/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/privat/subscriptions","organizations_url":"https://api.github.com/users/privat/orgs","repos_url":"https://api.github.com/users/privat/repos","events_url":"https://api.github.com/users/privat/events{/privacy}","received_events_url":"https://api.github.com/users/privat/received_events","type":"User","site_admin":false},"body":"protected? private?","created_at":"2015-09-04T02:14:42Z","updated_at":"2015-09-04T02:14:42Z","html_url":"https://github.com/nitlang/nit/pull/1689#discussion_r38716632","pull_request_url":"https://api.github.com/repos/nitlang/nit/pulls/1689","_links":{"self":{"href":"https://api.github.com/repos/nitlang/nit/pulls/comments/38716632"},"html":{"href":"https://github.com/nitlang/nit/pull/1689#discussion_r38716632"},"pull_request":{"href":"https://api.github.com/repos/nitlang/nit/pulls/1689"}}},"pull_request":{"url":"https://api.github.com/repos/nitlang/nit/pulls/1689","id":44176617,"html_url":"https://github.com/nitlang/nit/pull/1689","diff_url":"https://github.com/nitlang/nit/pull/1689.diff","patch_url":"https://github.com/nitlang/nit/pull/1689.patch","issue_url":"https://api.github.com/repos/nitlang/nit/issues/1689","number":1689,"state":"open","locked":false,"title":"Common Trees and Tree Edition Distance","user":{"login":"Morriar","id":583144,"avatar_url":"https://avatars.githubusercontent.com/u/583144?v=3","gravatar_id":"","url":"https://api.github.com/users/Morriar","html_url":"https://github.com/Morriar","followers_url":"https://api.github.com/users/Morriar/followers","following_url":"https://api.github.com/users/Morriar/following{/other_user}","gists_url":"https://api.github.com/users/Morriar/gists{/gist_id}","starred_url":"https://api.github.com/users/Morriar/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Morriar/subscriptions","organizations_url":"https://api.github.com/users/Morriar/orgs","repos_url":"https://api.github.com/users/Morriar/repos","events_url":"https://api.github.com/users/Morriar/events{/privacy}","received_events_url":"https://api.github.com/users/Morriar/received_events","type":"User","site_admin":false},"body":"This PR make some cleaning and renaming in `abstract_tree` to introduce `Tree`.\r\n\r\nUnlike BinTree, a Tree can have more than two children so it can represent hierarchical data like a file and folder or a table of content.\r\n\r\nTree also provides the service `distance_from` used to compute the Tree Edition Distance between two trees.\r\n\r\nSigned-off-by: Alexandre Terrasa <alexandre@moz-code.org>","created_at":"2015-09-04T01:52:39Z","updated_at":"2015-09-04T02:14:42Z","closed_at":null,"merged_at":null,"merge_commit_sha":"a8b3bf15d3837ea3afc1c43095924e1747107dba","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/nitlang/nit/pulls/1689/commits","review_comments_url":"https://api.github.com/repos/nitlang/nit/pulls/1689/comments","review_comment_url":"https://api.github.com/repos/nitlang/nit/pulls/comments{/number}","comments_url":"https://api.github.com/repos/nitlang/nit/issues/1689/comments","statuses_url":"https://api.github.com/repos/nitlang/nit/statuses/010076612d1d99fe71e6ec140dde2b7aaf178351","head":{"label":"Morriar:trees","ref":"trees","sha":"010076612d1d99fe71e6ec140dde2b7aaf178351","user":{"login":"Morriar","id":583144,"avatar_url":"https://avatars.githubusercontent.com/u/583144?v=3","gravatar_id":"","url":"https://api.github.com/users/Morriar","html_url":"https://github.com/Morriar","followers_url":"https://api.github.com/users/Morriar/followers","following_url":"https://api.github.com/users/Morriar/following{/other_user}","gists_url":"https://api.github.com/users/Morriar/gists{/gist_id}","starred_url":"https://api.github.com/users/Morriar/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Morriar/subscriptions","organizations_url":"https://api.github.com/users/Morriar/orgs","repos_url":"https://api.github.com/users/Morriar/repos","events_url":"https://api.github.com/users/Morriar/events{/privacy}","received_events_url":"https://api.github.com/users/Morriar/received_events","type":"User","site_admin":false},"repo":{"id":1456691,"name":"nit","full_name":"Morriar/nit","owner":{"login":"Morriar","id":583144,"avatar_url":"https://avatars.githubusercontent.com/u/583144?v=3","gravatar_id":"","url":"https://api.github.com/users/Morriar","html_url":"https://github.com/Morriar","followers_url":"https://api.github.com/users/Morriar/followers","following_url":"https://api.github.com/users/Morriar/following{/other_user}","gists_url":"https://api.github.com/users/Morriar/gists{/gist_id}","starred_url":"https://api.github.com/users/Morriar/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Morriar/subscriptions","organizations_url":"https://api.github.com/users/Morriar/orgs","repos_url":"https://api.github.com/users/Morriar/repos","events_url":"https://api.github.com/users/Morriar/events{/privacy}","received_events_url":"https://api.github.com/users/Morriar/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/Morriar/nit","description":"Nit language","fork":true,"url":"https://api.github.com/repos/Morriar/nit","forks_url":"https://api.github.com/repos/Morriar/nit/forks","keys_url":"https://api.github.com/repos/Morriar/nit/keys{/key_id}","collaborators_url":"https://api.github.com/repos/Morriar/nit/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/Morriar/nit/teams","hooks_url":"https://api.github.com/repos/Morriar/nit/hooks","issue_events_url":"https://api.github.com/repos/Morriar/nit/issues/events{/number}","events_url":"https://api.github.com/repos/Morriar/nit/events","assignees_url":"https://api.github.com/repos/Morriar/nit/assignees{/user}","branches_url":"https://api.github.com/repos/Morriar/nit/branches{/branch}","tags_url":"https://api.github.com/repos/Morriar/nit/tags","blobs_url":"https://api.github.com/repos/Morriar/nit/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/Morriar/nit/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/Morriar/nit/git/refs{/sha}","trees_url":"https://api.github.com/repos/Morriar/nit/git/trees{/sha}","statuses_url":"https://api.github.com/repos/Morriar/nit/statuses/{sha}","languages_url":"https://api.github.com/repos/Morriar/nit/languages","stargazers_url":"https://api.github.com/repos/Morriar/nit/stargazers","contributors_url":"https://api.github.com/repos/Morriar/nit/contributors","subscribers_url":"https://api.github.com/repos/Morriar/nit/subscribers","subscription_url":"https://api.github.com/repos/Morriar/nit/subscription","commits_url":"https://api.github.com/repos/Morriar/nit/commits{/sha}","git_commits_url":"https://api.github.com/repos/Morriar/nit/git/commits{/sha}","comments_url":"https://api.github.com/repos/Morriar/nit/comments{/number}","issue_comment_url":"https://api.github.com/repos/Morriar/nit/issues/comments{/number}","contents_url":"https://api.github.com/repos/Morriar/nit/contents/{+path}","compare_url":"https://api.github.com/repos/Morriar/nit/compare/{base}...{head}","merges_url":"https://api.github.com/repos/Morriar/nit/merges","archive_url":"https://api.github.com/repos/Morriar/nit/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/Morriar/nit/downloads","issues_url":"https://api.github.com/repos/Morriar/nit/issues{/number}","pulls_url":"https://api.github.com/repos/Morriar/nit/pulls{/number}","milestones_url":"https://api.github.com/repos/Morriar/nit/milestones{/number}","notifications_url":"https://api.github.com/repos/Morriar/nit/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/Morriar/nit/labels{/name}","releases_url":"https://api.github.com/repos/Morriar/nit/releases{/id}","created_at":"2011-03-08T22:16:33Z","updated_at":"2015-06-06T03:02:03Z","pushed_at":"2015-09-04T01:50:45Z","git_url":"git://github.com/Morriar/nit.git","ssh_url":"git@github.com:Morriar/nit.git","clone_url":"https://github.com/Morriar/nit.git","svn_url":"https://github.com/Morriar/nit","homepage":"http://nitlanguage.org","size":68803,"stargazers_count":3,"watchers_count":3,"language":"C","has_issues":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":2,"mirror_url":null,"open_issues_count":16,"forks":2,"open_issues":16,"watchers":3,"default_branch":"master"}},"base":{"label":"nitlang:master","ref":"master","sha":"bd0c71a5ff3ee1a4df7e1c6687818e2f71b005b5","user":{"login":"nitlang","id":5420298,"avatar_url":"https://avatars.githubusercontent.com/u/5420298?v=3","gravatar_id":"","url":"https://api.github.com/users/nitlang","html_url":"https://github.com/nitlang","followers_url":"https://api.github.com/users/nitlang/followers","following_url":"https://api.github.com/users/nitlang/following{/other_user}","gists_url":"https://api.github.com/users/nitlang/gists{/gist_id}","starred_url":"https://api.github.com/users/nitlang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nitlang/subscriptions","organizations_url":"https://api.github.com/users/nitlang/orgs","repos_url":"https://api.github.com/users/nitlang/repos","events_url":"https://api.github.com/users/nitlang/events{/privacy}","received_events_url":"https://api.github.com/users/nitlang/received_events","type":"Organization","site_admin":false},"repo":{"id":328597,"name":"nit","full_name":"nitlang/nit","owner":{"login":"nitlang","id":5420298,"avatar_url":"https://avatars.githubusercontent.com/u/5420298?v=3","gravatar_id":"","url":"https://api.github.com/users/nitlang","html_url":"https://github.com/nitlang","followers_url":"https://api.github.com/users/nitlang/followers","following_url":"https://api.github.com/users/nitlang/following{/other_user}","gists_url":"https://api.github.com/users/nitlang/gists{/gist_id}","starred_url":"https://api.github.com/users/nitlang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nitlang/subscriptions","organizations_url":"https://api.github.com/users/nitlang/orgs","repos_url":"https://api.github.com/users/nitlang/repos","events_url":"https://api.github.com/users/nitlang/events{/privacy}","received_events_url":"https://api.github.com/users/nitlang/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/nitlang/nit","description":"Nit language","fork":false,"url":"https://api.github.com/repos/nitlang/nit","forks_url":"https://api.github.com/repos/nitlang/nit/forks","keys_url":"https://api.github.com/repos/nitlang/nit/keys{/key_id}","collaborators_url":"https://api.github.com/repos/nitlang/nit/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/nitlang/nit/teams","hooks_url":"https://api.github.com/repos/nitlang/nit/hooks","issue_events_url":"https://api.github.com/repos/nitlang/nit/issues/events{/number}","events_url":"https://api.github.com/repos/nitlang/nit/events","assignees_url":"https://api.github.com/repos/nitlang/nit/assignees{/user}","branches_url":"https://api.github.com/repos/nitlang/nit/branches{/branch}","tags_url":"https://api.github.com/repos/nitlang/nit/tags","blobs_url":"https://api.github.com/repos/nitlang/nit/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/nitlang/nit/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/nitlang/nit/git/refs{/sha}","trees_url":"https://api.github.com/repos/nitlang/nit/git/trees{/sha}","statuses_url":"https://api.github.com/repos/nitlang/nit/statuses/{sha}","languages_url":"https://api.github.com/repos/nitlang/nit/languages","stargazers_url":"https://api.github.com/repos/nitlang/nit/stargazers","contributors_url":"https://api.github.com/repos/nitlang/nit/contributors","subscribers_url":"https://api.github.com/repos/nitlang/nit/subscribers","subscription_url":"https://api.github.com/repos/nitlang/nit/subscription","commits_url":"https://api.github.com/repos/nitlang/nit/commits{/sha}","git_commits_url":"https://api.github.com/repos/nitlang/nit/git/commits{/sha}","comments_url":"https://api.github.com/repos/nitlang/nit/comments{/number}","issue_comment_url":"https://api.github.com/repos/nitlang/nit/issues/comments{/number}","contents_url":"https://api.github.com/repos/nitlang/nit/contents/{+path}","compare_url":"https://api.github.com/repos/nitlang/nit/compare/{base}...{head}","merges_url":"https://api.github.com/repos/nitlang/nit/merges","archive_url":"https://api.github.com/repos/nitlang/nit/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/nitlang/nit/downloads","issues_url":"https://api.github.com/repos/nitlang/nit/issues{/number}","pulls_url":"https://api.github.com/repos/nitlang/nit/pulls{/number}","milestones_url":"https://api.github.com/repos/nitlang/nit/milestones{/number}","notifications_url":"https://api.github.com/repos/nitlang/nit/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/nitlang/nit/labels{/name}","releases_url":"https://api.github.com/repos/nitlang/nit/releases{/id}","created_at":"2009-10-06T15:03:00Z","updated_at":"2015-08-22T03:08:22Z","pushed_at":"2015-09-04T01:52:40Z","git_url":"git://github.com/nitlang/nit.git","ssh_url":"git@github.com:nitlang/nit.git","clone_url":"https://github.com/nitlang/nit.git","svn_url":"https://github.com/nitlang/nit","homepage":"http://nitlanguage.org","size":97386,"stargazers_count":77,"watchers_count":77,"language":"C","has_issues":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":45,"mirror_url":null,"open_issues_count":118,"forks":45,"open_issues":118,"watchers":77,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/nitlang/nit/pulls/1689"},"html":{"href":"https://github.com/nitlang/nit/pull/1689"},"issue":{"href":"https://api.github.com/repos/nitlang/nit/issues/1689"},"comments":{"href":"https://api.github.com/repos/nitlang/nit/issues/1689/comments"},"review_comments":{"href":"https://api.github.com/repos/nitlang/nit/pulls/1689/comments"},"review_comment":{"href":"https://api.github.com/repos/nitlang/nit/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/nitlang/nit/pulls/1689/commits"},"statuses":{"href":"https://api.github.com/repos/nitlang/nit/statuses/010076612d1d99fe71e6ec140dde2b7aaf178351"}}}}