Current section
5 Versions
Jump to
Current section
5 Versions
Compare versions
4
files changed
+53
additions
-11
deletions
| @@ -1,4 +1,7 @@ | |
| 1 1 | # SortedSet |
| 2 | + [](https://hex.pm/packages/sorted_set) [](https://travis-ci.org/SenecaSystems/sorted_set) |
| 3 | + |
| 4 | + |
| 2 5 | A sorted set library for Elixir. Implements the |
| 3 6 | [Set](http://elixir-lang.org/docs/v1.0/elixir/Set.html) protocol. |
| 4 7 | |
| @@ -27,5 +30,24 @@ SortedSet.new() | |
| 27 30 | |> Set.put(1) |
| 28 31 | |> Set.put(3) |
| 29 32 | |> Enum.reduce([], fn (element, acc) -> [element*2|acc] end) |
| 30 | - # [2, 6, 10] |
| 33 | + |> Enum.reverse |
| 34 | + # => [2, 6, 10] |
| 35 | + ``` |
| 36 | + |
| 37 | + Can also take a custom `:comparator` function to determine ordering. The |
| 38 | + function should accept two terms and |
| 39 | + |
| 40 | + - return `0` if they are considered equal |
| 41 | + - return `-1` if the first is considered less than or before the second |
| 42 | + - return `1` if the first is considered greater than or after the second |
| 43 | + |
| 44 | + This function is passed on to the underlying [red-black tree implementation](https://github.com/SenecaSystems/red_black_tree) implemetation. Otherwise, the |
| 45 | + default Erlang term comparison is used (with an extra bit to handle edgecases — see note in [RedBlackTree](https://github.com/SenecaSystems/red_black_tree) |
| 46 | + README.) |
| 47 | + |
| 48 | + ```elixir |
| 49 | + SortedSet.new([:a, :b, :c], comparator: fn (term1, term2) -> |
| 50 | + RedBlackTree.compare_terms(term1, term2) * -1 |
| 51 | + end) |
| 52 | + # => #SortedSet<[:c, :b, :a]> |
| 31 53 | ``` |
| @@ -13,5 +13,5 @@ | |
| 13 13 | [{<<"red_black_tree">>, |
| 14 14 | [{<<"app">>,<<"red_black_tree">>}, |
| 15 15 | {<<"optional">>,nil}, |
| 16 | - {<<"requirement">>,<<"~> 1.0">>}]}]}. |
| 17 | - {<<"version">>,<<"1.0.0">>}. |
| 16 | + {<<"requirement">>,<<"~> 1.2">>}]}]}. |
| 17 | + {<<"version">>,<<"1.1.0">>}. |
| @@ -9,6 +9,8 @@ defmodule SortedSet do | |
| 9 9 | |
| 10 10 | @behaviour Set |
| 11 11 | |
| 12 | + @default_comparator &RedBlackTree.compare_terms/2 |
| 13 | + |
| 12 14 | # Define the type as opaque |
| 13 15 | |
| 14 16 | @opaque t :: %__MODULE__{members: RedBlackTree, size: non_neg_integer} |
| @@ -19,16 +21,34 @@ defmodule SortedSet do | |
| 19 21 | Returns a new `SortedSet`, initialized with the unique, sorted values of |
| 20 22 | `members`. |
| 21 23 | |
| 24 | + ## Options |
| 25 | + - `:comparator` function taking two terms and deciding their order. Passed |
| 26 | + on to the underlying data structure, in this case a Red-Black tree. The |
| 27 | + default is to compare based on standard Erlang term comparison. To learn |
| 28 | + more about this option, see the examples given for |
| 29 | + [RedBlackTree](https://github.com/SenecaSystems/red_black_tree) |
| 30 | + |
| 22 31 | ## Examples |
| 23 32 | |
| 24 | - iex> inspect SortedSet.new() |
| 25 | - "#SortedSet<[]>" |
| 33 | + iex> SortedSet.new() |
| 34 | + #SortedSet<[]> |
| 26 35 | |
| 27 | - iex> inspect SortedSet.new([1,3,5]) |
| 28 | - "#SortedSet<[1, 3, 5]>" |
| 36 | + iex> SortedSet.new([1,3,5]) |
| 37 | + #SortedSet<[1, 3, 5]> |
| 38 | + |
| 39 | + iex> SortedSet.new([:a, :b, :c], comparator: fn (term1, term2) -> |
| 40 | + ...> RedBlackTree.compare_terms(term1, term2) * -1 |
| 41 | + ...> end) |
| 42 | + #SortedSet<[:c, :b, :a]> |
| 29 43 | """ |
| 30 | - def new(members \\ []) do |
| 31 | - Enum.reduce(members, %SortedSet{}, fn(member, set) -> |
| 44 | + def new(members \\ [], options \\ []) |
| 45 | + def new(members, options) do |
| 46 | + comparator = :proplists.get_value(:comparator, options, @default_comparator) |
| 47 | + new_set = %SortedSet{ |
| 48 | + members: RedBlackTree.new([], comparator: comparator) |
| 49 | + } |
| 50 | + |
| 51 | + Enum.reduce(members, new_set, fn(member, set) -> |
| 32 52 | put(set, member) |
| 33 53 | end) |
| 34 54 | end |
| @@ -3,7 +3,7 @@ defmodule SortedSet.Mixfile do | |
| 3 3 | |
| 4 4 | def project do |
| 5 5 | [app: :sorted_set, |
| 6 | - version: "1.0.0", |
| 6 | + version: "1.1.0", |
| 7 7 | source_url: "https://github.com/SenecaSystems/sorted_set", |
| 8 8 | elixir: "~> 1.0", |
| 9 9 | description: "SortedSet implementation for Elixir", |
| @@ -19,7 +19,7 @@ defmodule SortedSet.Mixfile do | |
| 19 19 | |
| 20 20 | defp deps do |
| 21 21 | [ |
| 22 | - {:red_black_tree, "~> 1.0"}, |
| 22 | + {:red_black_tree, "~> 1.2"}, |
| 23 23 | {:earmark, "~> 0.1", only: :dev}, |
| 24 24 | {:ex_doc, "~> 0.7", only: :dev} |
| 25 25 | ] |