{"action":"created","comment":{"url":"https://api.github.com/repos/elixir-lang/elixir/pulls/comments/28192868","id":28192868,"diff_hunk":"@@ -0,0 +1,114 @@\n+defmodule MapSet do\n+  @moduledoc \"\"\"\n+  A set store.\n+\n+  The `MapSet` is represented internally as a struct, therefore\n+  `%MapSet{}` can be used whenever there is a need to match\n+  on any `MapSet`. Note though the struct fields are private and\n+  must not be accessed directly. Instead, use the functions on this\n+  or in the `Set` module.\n+\n+  The `MapSet` is implemented using `Map` data type.\n+  For more information about the functions\n+  and their APIs, please consult the `Set` module.\n+  \"\"\"\n+\n+  @behaviour Set\n+\n+  defstruct map: %{}\n+\n+  def new(), do: %MapSet{}\n+\n+  def delete(%MapSet{map: map} = set, term) do\n+    %{set | map: Map.delete(map, term)}\n+  end\n+\n+  def difference(%MapSet{} = set1, %MapSet{} = set2) do\n+    reduce(set2, {:cont, set1}, fn value, acc ->\n+      {:cont, delete(acc, value)}\n+    end) |> elem(1)\n+  end\n+\n+  def disjoint?(%MapSet{} = set1, %MapSet{} = set2) do\n+    reduce(set1, {:cont, true}, fn value, _ ->\n+      if member?(set2, value) do\n+        {:halt, false}\n+      else\n+        {:cont, true}\n+      end\n+    end) |> elem(1)\n+  end\n+\n+  def equal?(%MapSet{map: map1}, %MapSet{map: map2}) do\n+    Map.equal?(map1, map2)\n+  end\n+\n+  def intersection(%MapSet{} = set1, %MapSet{} = set2) do\n+    reduce(set1, {:cont, new}, fn value, acc ->\n+      if member?(set2, value) do\n+        {:cont, put(acc, value)}\n+      else\n+        {:cont, acc}\n+      end\n+    end) |> elem(1)\n+  end\n+\n+  def member?(%MapSet{map: map}, value) do\n+    Map.has_key?(map, value)\n+  end\n+\n+  def put(%MapSet{map: map} = set, value) do\n+    %{set | map: Map.put(map, value, nil)}\n+  end\n+\n+  def size(%MapSet{map: map}) do\n+    map_size(map)\n+  end\n+\n+  def subset?(%MapSet{} = set1, %MapSet{} = set2) do","path":"lib/elixir/lib/map_set.ex","position":68,"original_position":68,"commit_id":"96c721314faa2f3ad7551a3b4247109cc8a2ece2","original_commit_id":"96c721314faa2f3ad7551a3b4247109cc8a2ece2","user":{"login":"josevalim","id":9582,"avatar_url":"https://avatars.githubusercontent.com/u/9582?v=3","gravatar_id":"","url":"https://api.github.com/users/josevalim","html_url":"https://github.com/josevalim","followers_url":"https://api.github.com/users/josevalim/followers","following_url":"https://api.github.com/users/josevalim/following{/other_user}","gists_url":"https://api.github.com/users/josevalim/gists{/gist_id}","starred_url":"https://api.github.com/users/josevalim/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/josevalim/subscriptions","organizations_url":"https://api.github.com/users/josevalim/orgs","repos_url":"https://api.github.com/users/josevalim/repos","events_url":"https://api.github.com/users/josevalim/events{/privacy}","received_events_url":"https://api.github.com/users/josevalim/received_events","type":"User","site_admin":false},"body":"A good technique here would be to find the smaller set and use it on the traversal.","created_at":"2015-04-11T06:34:55Z","updated_at":"2015-04-11T06:34:55Z","html_url":"https://github.com/elixir-lang/elixir/pull/3258#discussion_r28192868","pull_request_url":"https://api.github.com/repos/elixir-lang/elixir/pulls/3258","_links":{"self":{"href":"https://api.github.com/repos/elixir-lang/elixir/pulls/comments/28192868"},"html":{"href":"https://github.com/elixir-lang/elixir/pull/3258#discussion_r28192868"},"pull_request":{"href":"https://api.github.com/repos/elixir-lang/elixir/pulls/3258"}}},"pull_request":{"url":"https://api.github.com/repos/elixir-lang/elixir/pulls/3258","id":32904705,"html_url":"https://github.com/elixir-lang/elixir/pull/3258","diff_url":"https://github.com/elixir-lang/elixir/pull/3258.diff","patch_url":"https://github.com/elixir-lang/elixir/pull/3258.patch","issue_url":"https://api.github.com/repos/elixir-lang/elixir/issues/3258","number":3258,"state":"open","locked":false,"title":"Introduce `MapSet` data type","user":{"login":"lexmag","id":248290,"avatar_url":"https://avatars.githubusercontent.com/u/248290?v=3","gravatar_id":"","url":"https://api.github.com/users/lexmag","html_url":"https://github.com/lexmag","followers_url":"https://api.github.com/users/lexmag/followers","following_url":"https://api.github.com/users/lexmag/following{/other_user}","gists_url":"https://api.github.com/users/lexmag/gists{/gist_id}","starred_url":"https://api.github.com/users/lexmag/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lexmag/subscriptions","organizations_url":"https://api.github.com/users/lexmag/orgs","repos_url":"https://api.github.com/users/lexmag/repos","events_url":"https://api.github.com/users/lexmag/events{/privacy}","received_events_url":"https://api.github.com/users/lexmag/received_events","type":"User","site_admin":false},"body":"Closes #3242.\r\n\r\n__Erlang/OTP 18 RC-1__\r\n\r\n* [x] new\r\n* [x] put\r\n\r\n  - 100 elements\r\n  ``` \r\n  MapSet:    10000000   0.16 µs/op\r\n  HashSet:   10000000   0.37 µs/op\r\n  ```\r\n  - 200 elements\r\n  ```\r\n  MapSet:    10000000   0.16 µs/op\r\n  HashSet:   10000000   0.42 µs/op\r\n  ```\r\n  - 1000 elements\r\n  ```\r\n  MapSet:    10000000   0.21 µs/op\r\n  HashSet:   10000000   0.51 µs/op\r\n  ```\r\n  - 5000 elements\r\n  ```\r\n  MapSet:    10000000   0.26 µs/op\r\n  HashSet:   10000000   0.60 µs/op\r\n  ```\r\n\r\n* [x] delete\r\n\r\n  - 100 elements\r\n  ```\r\n  MapSet:   100000000   0.11 µs/op\r\n  HashSet:   10000000   0.17 µs/op\r\n  ```\r\n  - 200 elements\r\n  ```\r\n  MapSet:    10000000   0.11 µs/op\r\n  HashSet:   10000000   0.19 µs/op\r\n  ```\r\n  - 1000 elements\r\n  ```\r\n  MapSet:    10000000   0.11 µs/op\r\n  HashSet:   10000000   0.31 µs/op\r\n  ```\r\n  - 5000 elements\r\n  ```\r\n  MapSet:    10000000   0.13 µs/op\r\n  HashSet:   10000000   0.33 µs/op\r\n  ```\r\n\r\n* [x] difference\r\n\r\n  - 200 elements\r\n  ```\r\n  MapSet:       50000   42.51 µs/op\r\n  HashSet:      20000   98.89 µs/op\r\n  ```\r\n\r\n* [x] disjoint?\r\n\r\n  - 200 elements (unequal)\r\n  ```\r\n  MapSet:      500000   2.28 µs/op\r\n  HashSet:   10000000   0.51 µs/op\r\n  ```\r\n  where the `:maps.to_list` itself is taking `2.03 µs/op`\r\n  - 200 elements (equal)\r\n  ```\r\n  MapSet:      100000   28.80 µs/op\r\n  HashSet:      10000   126.70 µs/op\r\n  ```\r\n\r\n* [x] equal?\r\n\r\n  - 200 elements\r\n  ```\r\n  MapSet:   100000000   0.07 µs/op\r\n  HashSet:      10000   128.45 µs/op\r\n  ```\r\n  - 1000 elements (equal)\r\n  ```\r\n  MapSet:   100000000   0.07 µs/op\r\n  HashSet:       5000   704.84 µs/op\r\n  ```\r\n  - 1000 elements (unequal)\r\n  ```\r\n  MapSet:   100000000   0.09 µs/op\r\n  HashSet:   10000000   0.71 µs/op\r\n  ```\r\n\r\n* [x] intersection\r\n\r\n  - 200 elements\r\n  ```\r\n  MapSet:       50000   34.56 µs/op\r\n  HashSet:      20000   83.33 µs/op\r\n  ```\r\n\r\n* [x] member?\r\n\r\n  - 200 elements\r\n  ```\r\n  MapSet:   100000000   0.07 µs/op\r\n  HashSet:   10000000   0.20 µs/op\r\n  ```\r\n  - 1000 elements\r\n  ```\r\n  MapSet:   100000000   0.07 µs/op\r\n  HashSet:   10000000   0.22 µs/op\r\n  ```\r\n  - 5000 elements\r\n  ```\r\n  MapSet:   100000000   0.08 µs/op\r\n  HashSet:   10000000   0.26 µs/op\r\n  ```\r\n\r\n* [x] size\r\n* [x] subset?\r\n\r\n  same as for `disjoint?`\r\n\r\n* [x] to_list\r\n\r\n  - 200 elements\r\n  ```\r\n  MapSet:     1000000   2.05 µs/op\r\n  HashSet:      50000   38.05 µs/op\r\n  ```\r\n  - 1000 elements\r\n  ```\r\n  MapSet:      100000   12.33 µs/op\r\n  HashSet:      10000   209.33 µs/op\r\n  ```\r\n  - 5000 elements\r\n  ```\r\n  MapSet:       50000   70.11 µs/op\r\n  HashSet:       2000   939.45 µs/op\r\n  ```\r\n\r\n* [x] union\r\n\r\n  - 200 elements\r\n  ```\r\n  MapSet:      200000   7.21 µs/op\r\n  HashSet:      10000   159.85 µs/op\r\n  ```\r\n  - 1000 elements\r\n  ```\r\n  MapSet:      100000   27.98 µs/op\r\n  HashSet:       2000   850.68 µs/op\r\n  ```\r\n  - 5000 elements\r\n  ```\r\n  MapSet:       10000   207.84 µs/op\r\n  HashSet:        500   4208.29 µs/op\r\n  ```","created_at":"2015-04-08T21:36:09Z","updated_at":"2015-04-11T06:34:55Z","closed_at":null,"merged_at":null,"merge_commit_sha":"f7dd75df8191188469fc98d295ad7ce93db4f806","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/elixir-lang/elixir/pulls/3258/commits","review_comments_url":"https://api.github.com/repos/elixir-lang/elixir/pulls/3258/comments","review_comment_url":"https://api.github.com/repos/elixir-lang/elixir/pulls/comments{/number}","comments_url":"https://api.github.com/repos/elixir-lang/elixir/issues/3258/comments","statuses_url":"https://api.github.com/repos/elixir-lang/elixir/statuses/96c721314faa2f3ad7551a3b4247109cc8a2ece2","head":{"label":"lexmag:map_set","ref":"map_set","sha":"96c721314faa2f3ad7551a3b4247109cc8a2ece2","user":{"login":"lexmag","id":248290,"avatar_url":"https://avatars.githubusercontent.com/u/248290?v=3","gravatar_id":"","url":"https://api.github.com/users/lexmag","html_url":"https://github.com/lexmag","followers_url":"https://api.github.com/users/lexmag/followers","following_url":"https://api.github.com/users/lexmag/following{/other_user}","gists_url":"https://api.github.com/users/lexmag/gists{/gist_id}","starred_url":"https://api.github.com/users/lexmag/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lexmag/subscriptions","organizations_url":"https://api.github.com/users/lexmag/orgs","repos_url":"https://api.github.com/users/lexmag/repos","events_url":"https://api.github.com/users/lexmag/events{/privacy}","received_events_url":"https://api.github.com/users/lexmag/received_events","type":"User","site_admin":false},"repo":{"id":19643959,"name":"elixir","full_name":"lexmag/elixir","owner":{"login":"lexmag","id":248290,"avatar_url":"https://avatars.githubusercontent.com/u/248290?v=3","gravatar_id":"","url":"https://api.github.com/users/lexmag","html_url":"https://github.com/lexmag","followers_url":"https://api.github.com/users/lexmag/followers","following_url":"https://api.github.com/users/lexmag/following{/other_user}","gists_url":"https://api.github.com/users/lexmag/gists{/gist_id}","starred_url":"https://api.github.com/users/lexmag/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lexmag/subscriptions","organizations_url":"https://api.github.com/users/lexmag/orgs","repos_url":"https://api.github.com/users/lexmag/repos","events_url":"https://api.github.com/users/lexmag/events{/privacy}","received_events_url":"https://api.github.com/users/lexmag/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/lexmag/elixir","description":"Elixir is a functional, meta-programming aware language built on top of the Erlang VM. It is a dynamic language that focuses on tooling to leverage Erlang's abilities to build concurrent, distributed and fault-tolerant applications with hot code upgrades","fork":true,"url":"https://api.github.com/repos/lexmag/elixir","forks_url":"https://api.github.com/repos/lexmag/elixir/forks","keys_url":"https://api.github.com/repos/lexmag/elixir/keys{/key_id}","collaborators_url":"https://api.github.com/repos/lexmag/elixir/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/lexmag/elixir/teams","hooks_url":"https://api.github.com/repos/lexmag/elixir/hooks","issue_events_url":"https://api.github.com/repos/lexmag/elixir/issues/events{/number}","events_url":"https://api.github.com/repos/lexmag/elixir/events","assignees_url":"https://api.github.com/repos/lexmag/elixir/assignees{/user}","branches_url":"https://api.github.com/repos/lexmag/elixir/branches{/branch}","tags_url":"https://api.github.com/repos/lexmag/elixir/tags","blobs_url":"https://api.github.com/repos/lexmag/elixir/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/lexmag/elixir/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/lexmag/elixir/git/refs{/sha}","trees_url":"https://api.github.com/repos/lexmag/elixir/git/trees{/sha}","statuses_url":"https://api.github.com/repos/lexmag/elixir/statuses/{sha}","languages_url":"https://api.github.com/repos/lexmag/elixir/languages","stargazers_url":"https://api.github.com/repos/lexmag/elixir/stargazers","contributors_url":"https://api.github.com/repos/lexmag/elixir/contributors","subscribers_url":"https://api.github.com/repos/lexmag/elixir/subscribers","subscription_url":"https://api.github.com/repos/lexmag/elixir/subscription","commits_url":"https://api.github.com/repos/lexmag/elixir/commits{/sha}","git_commits_url":"https://api.github.com/repos/lexmag/elixir/git/commits{/sha}","comments_url":"https://api.github.com/repos/lexmag/elixir/comments{/number}","issue_comment_url":"https://api.github.com/repos/lexmag/elixir/issues/comments{/number}","contents_url":"https://api.github.com/repos/lexmag/elixir/contents/{+path}","compare_url":"https://api.github.com/repos/lexmag/elixir/compare/{base}...{head}","merges_url":"https://api.github.com/repos/lexmag/elixir/merges","archive_url":"https://api.github.com/repos/lexmag/elixir/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/lexmag/elixir/downloads","issues_url":"https://api.github.com/repos/lexmag/elixir/issues{/number}","pulls_url":"https://api.github.com/repos/lexmag/elixir/pulls{/number}","milestones_url":"https://api.github.com/repos/lexmag/elixir/milestones{/number}","notifications_url":"https://api.github.com/repos/lexmag/elixir/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/lexmag/elixir/labels{/name}","releases_url":"https://api.github.com/repos/lexmag/elixir/releases{/id}","created_at":"2014-05-10T14:57:40Z","updated_at":"2015-02-18T22:20:49Z","pushed_at":"2015-04-10T20:16:51Z","git_url":"git://github.com/lexmag/elixir.git","ssh_url":"git@github.com:lexmag/elixir.git","clone_url":"https://github.com/lexmag/elixir.git","svn_url":"https://github.com/lexmag/elixir","homepage":"http://elixir-lang.org/","size":29319,"stargazers_count":0,"watchers_count":0,"language":"Elixir","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":"elixir-lang:master","ref":"master","sha":"d5b793c73eb5e27cee134feb2d9fe5e22356b623","user":{"login":"elixir-lang","id":1481354,"avatar_url":"https://avatars.githubusercontent.com/u/1481354?v=3","gravatar_id":"","url":"https://api.github.com/users/elixir-lang","html_url":"https://github.com/elixir-lang","followers_url":"https://api.github.com/users/elixir-lang/followers","following_url":"https://api.github.com/users/elixir-lang/following{/other_user}","gists_url":"https://api.github.com/users/elixir-lang/gists{/gist_id}","starred_url":"https://api.github.com/users/elixir-lang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/elixir-lang/subscriptions","organizations_url":"https://api.github.com/users/elixir-lang/orgs","repos_url":"https://api.github.com/users/elixir-lang/repos","events_url":"https://api.github.com/users/elixir-lang/events{/privacy}","received_events_url":"https://api.github.com/users/elixir-lang/received_events","type":"Organization","site_admin":false},"repo":{"id":1234714,"name":"elixir","full_name":"elixir-lang/elixir","owner":{"login":"elixir-lang","id":1481354,"avatar_url":"https://avatars.githubusercontent.com/u/1481354?v=3","gravatar_id":"","url":"https://api.github.com/users/elixir-lang","html_url":"https://github.com/elixir-lang","followers_url":"https://api.github.com/users/elixir-lang/followers","following_url":"https://api.github.com/users/elixir-lang/following{/other_user}","gists_url":"https://api.github.com/users/elixir-lang/gists{/gist_id}","starred_url":"https://api.github.com/users/elixir-lang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/elixir-lang/subscriptions","organizations_url":"https://api.github.com/users/elixir-lang/orgs","repos_url":"https://api.github.com/users/elixir-lang/repos","events_url":"https://api.github.com/users/elixir-lang/events{/privacy}","received_events_url":"https://api.github.com/users/elixir-lang/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/elixir-lang/elixir","description":"Elixir is a dynamic, functional language designed for building scalable and maintainable applications","fork":false,"url":"https://api.github.com/repos/elixir-lang/elixir","forks_url":"https://api.github.com/repos/elixir-lang/elixir/forks","keys_url":"https://api.github.com/repos/elixir-lang/elixir/keys{/key_id}","collaborators_url":"https://api.github.com/repos/elixir-lang/elixir/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/elixir-lang/elixir/teams","hooks_url":"https://api.github.com/repos/elixir-lang/elixir/hooks","issue_events_url":"https://api.github.com/repos/elixir-lang/elixir/issues/events{/number}","events_url":"https://api.github.com/repos/elixir-lang/elixir/events","assignees_url":"https://api.github.com/repos/elixir-lang/elixir/assignees{/user}","branches_url":"https://api.github.com/repos/elixir-lang/elixir/branches{/branch}","tags_url":"https://api.github.com/repos/elixir-lang/elixir/tags","blobs_url":"https://api.github.com/repos/elixir-lang/elixir/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/elixir-lang/elixir/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/elixir-lang/elixir/git/refs{/sha}","trees_url":"https://api.github.com/repos/elixir-lang/elixir/git/trees{/sha}","statuses_url":"https://api.github.com/repos/elixir-lang/elixir/statuses/{sha}","languages_url":"https://api.github.com/repos/elixir-lang/elixir/languages","stargazers_url":"https://api.github.com/repos/elixir-lang/elixir/stargazers","contributors_url":"https://api.github.com/repos/elixir-lang/elixir/contributors","subscribers_url":"https://api.github.com/repos/elixir-lang/elixir/subscribers","subscription_url":"https://api.github.com/repos/elixir-lang/elixir/subscription","commits_url":"https://api.github.com/repos/elixir-lang/elixir/commits{/sha}","git_commits_url":"https://api.github.com/repos/elixir-lang/elixir/git/commits{/sha}","comments_url":"https://api.github.com/repos/elixir-lang/elixir/comments{/number}","issue_comment_url":"https://api.github.com/repos/elixir-lang/elixir/issues/comments{/number}","contents_url":"https://api.github.com/repos/elixir-lang/elixir/contents/{+path}","compare_url":"https://api.github.com/repos/elixir-lang/elixir/compare/{base}...{head}","merges_url":"https://api.github.com/repos/elixir-lang/elixir/merges","archive_url":"https://api.github.com/repos/elixir-lang/elixir/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/elixir-lang/elixir/downloads","issues_url":"https://api.github.com/repos/elixir-lang/elixir/issues{/number}","pulls_url":"https://api.github.com/repos/elixir-lang/elixir/pulls{/number}","milestones_url":"https://api.github.com/repos/elixir-lang/elixir/milestones{/number}","notifications_url":"https://api.github.com/repos/elixir-lang/elixir/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/elixir-lang/elixir/labels{/name}","releases_url":"https://api.github.com/repos/elixir-lang/elixir/releases{/id}","created_at":"2011-01-09T08:43:57Z","updated_at":"2015-04-11T04:42:39Z","pushed_at":"2015-04-11T02:49:18Z","git_url":"git://github.com/elixir-lang/elixir.git","ssh_url":"git@github.com:elixir-lang/elixir.git","clone_url":"https://github.com/elixir-lang/elixir.git","svn_url":"https://github.com/elixir-lang/elixir","homepage":"http://elixir-lang.org/","size":48972,"stargazers_count":3650,"watchers_count":3650,"language":"Elixir","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":524,"mirror_url":null,"open_issues_count":56,"forks":524,"open_issues":56,"watchers":3650,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/elixir-lang/elixir/pulls/3258"},"html":{"href":"https://github.com/elixir-lang/elixir/pull/3258"},"issue":{"href":"https://api.github.com/repos/elixir-lang/elixir/issues/3258"},"comments":{"href":"https://api.github.com/repos/elixir-lang/elixir/issues/3258/comments"},"review_comments":{"href":"https://api.github.com/repos/elixir-lang/elixir/pulls/3258/comments"},"review_comment":{"href":"https://api.github.com/repos/elixir-lang/elixir/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/elixir-lang/elixir/pulls/3258/commits"},"statuses":{"href":"https://api.github.com/repos/elixir-lang/elixir/statuses/96c721314faa2f3ad7551a3b4247109cc8a2ece2"}}}}