View Source Orderly.SortedSet (orderly v0.1.0)
Implementation of a sorted set based on Erlang's
gb_sets.
SortedSet has many of the core functions found in
MapSet. The important difference
between SortedSet and MapSet is that the values in a sorted
set have a defined order, specifically the
Erlang term order.
For example:
set =
[2, 1, 3, 1]
|> SortedSet.new()
|> SortedSet.to_list()
#=> [1, 2, 3]All functions that involve accessing, inserting, or deleting an element have
O(log n) time complexity.
Like MapSet, SortedSet is an opaque data structure that does not support
pattern matching.
SortedSet implements the Enumerable protocol, so that Enum
functions can be applied to sorted sets. When applying Stream functions
to a sorted set, it is recommended to first create a stream using
SortedSet.to_stream/1 or SortedSet.to_stream/2, which adapts the effecient
lazy iterator pattern provided by gb_sets.
Summary
Functions
Delete value from sorted_set.
Obtain a set with the elements of sorted_set that are not contained in sorted_set2.
Check if two sorted sets are equal.
Obtain a set with elements in both sorted_set1 and sorted_set2.
Check if value is contained in sorted_set.
Create an empty set.
Create a new set from the given enumerable.
Insert value into sorted_set.
Return the number of elements in sorted_set.
Return the element with the smallest value in sorted_set.
Checks if all of the elements in sorted_set1 are contained in sorted_set2.
Convert sorted_set into a sorted list of elements.
Create a Stream from sorted_set
that emits elements in order starting from the smallest element in the set.
Create a Stream from sorted_set
that emits elements in order starting from the first element in the set
greater than or equal to start_value.
Obtain a set that contains all elements of sorted_set1 and sorted_set2.
Types
@type iter() :: :gb_sets.iter()
@type set(value) :: :gb_sets.set(value)
@type t(value) :: %Orderly.SortedSet{set: set(value)}
@type value() :: any()
Functions
Delete value from sorted_set.
This returns a set without value. If value is not present, the original
set is returned unchanged.
Examples
iex> set = Orderly.SortedSet.new([2, 1, 3])
iex> Orderly.SortedSet.delete(set, 2)
Orderly.SortedSet.new([1, 3])
iex> Orderly.SortedSet.delete(set, 4)
Orderly.SortedSet.new([1, 2, 3])Obtain a set with the elements of sorted_set that are not contained in sorted_set2.
Examples
iex> set1 = Orderly.SortedSet.new([2, 1, 3])
iex> set2 = Orderly.SortedSet.new([1, 2])
iex> Orderly.SortedSet.difference(set1, set2) |> Orderly.SortedSet.to_list()
[3]Check if two sorted sets are equal.
This checks the equality of the list representations.
Examples
iex> set1 = Orderly.SortedSet.new([2, 1, 3])
iex> set2 = Orderly.SortedSet.new([3, 2, 1])
iex> Orderly.SortedSet.equal?(set1, set2)Obtain a set with elements in both sorted_set1 and sorted_set2.
Examples
iex> set1 = Orderly.SortedSet.new([2, 1, 3])
iex> set2 = Orderly.SortedSet.new([1, 2])
iex> Orderly.SortedSet.intersection(set1, set2) |> Orderly.SortedSet.to_list()
[1, 2]Check if value is contained in sorted_set.
Examples
iex> set = Orderly.SortedSet.new([2, 1, 3])
iex> Orderly.SortedSet.member?(set, 2)
true
iex> Orderly.SortedSet.member?(set, 4)
false@spec new() :: t()
Create an empty set.
Examples
iex> Orderly.SortedSet.new()
Orderly.SortedSet.new([])@spec new(Enumerable.t()) :: t()
Create a new set from the given enumerable.
Examples
iex> Orderly.SortedSet.new([3, 1, 2])
Orderly.SortedSet.new([1, 2, 3])
iex> Orderly.SortedSet.new([{1, 2}, {2, 4}, {1, 3}])
Orderly.SortedSet.new([{1, 2}, {1, 3}, {2, 4}])Insert value into sorted_set.
Examples
iex> Orderly.SortedSet.new() |> Orderly.SortedSet.put(1)
Orderly.SortedSet.new([1])@spec size(t()) :: non_neg_integer()
Return the number of elements in sorted_set.
Examples
iex> Orderly.SortedSet.new([2, 1, 3]) |> Orderly.SortedSet.size()
3Return the element with the smallest value in sorted_set.
This returns {:ok, value} if the set is non-empty, and :error otherwise.
Examples
iex> Orderly.SortedSet.new([2, 1, 3]) |> Orderly.SortedSet.smallest()
{:ok, 1}
iex> Orderly.SortedSet.new([]) |> Orderly.SortedSet.smallest()
:errorChecks if all of the elements in sorted_set1 are contained in sorted_set2.
Examples
iex> set1 = Orderly.SortedSet.new([2, 1, 3])
iex> set2 = Orderly.SortedSet.new([1, 2])
iex> Orderly.SortedSet.subset?(set2, set1)
trueConvert sorted_set into a sorted list of elements.
Examples
iex> Orderly.SortedSet.new([2, 1, 3]) |> Orderly.SortedSet.to_list()
[1, 2, 3]@spec to_stream(t()) :: Enumerable.t()
Create a Stream from sorted_set
that emits elements in order starting from the smallest element in the set.
To generate values lazily, this uses
:gb_sets.iterator/1 and
:gb_sets.next/1.
Examples
iex> set = Orderly.SortedSet.new([2, 1, 3, 5, 4])
iex> stream = Orderly.SortedSet.to_stream(set)
iex> stream |> Enum.take(3)
[1, 2, 3]
iex> stream |> Enum.take_while(& &1 <= 4)
[1, 2, 3, 4]@spec to_stream(t(), value()) :: Enumerable.t()
Create a Stream from sorted_set
that emits elements in order starting from the first element in the set
greater than or equal to start_value.
To generate values lazily, this uses
:gb_sets.iterator_from/2 and
:gb_sets.next/1.
Examples
iex> set = Orderly.SortedSet.new([2, 1, 3, 5, 4])
iex> stream = Orderly.SortedSet.to_stream(set, 2)
iex> stream |> Enum.take(3)
[2, 3, 4]
iex> stream |> Enum.take_while(& &1 <= 3)
[2, 3]Obtain a set that contains all elements of sorted_set1 and sorted_set2.
Examples
iex> set1 = Orderly.SortedSet.new([2, 1, 3])
iex> set2 = Orderly.SortedSet.new([4, 5])
iex> Orderly.SortedSet.union(set1, set2) |> Orderly.SortedSet.to_list()
[1, 2, 3, 4, 5]