View Source Orderly.SortedMap (orderly v0.1.0)
Implementation of a sorted map based on Erlang's
gb_trees.
SortedMap has many of the core functions found in
Map. The important difference
between SortedMap and Map is that the keys in a sorted
map have a defined order, specifically the
Erlang term order.
For example:
map =
[b: 2, a: 1, c: 3, a: 4]
|> SortedMap.new()
|> SortedMap.to_list()
#=> [a: 4, b: 2, c: 3]All functions that involve accessing, inserting, or deleting a key have
O(log n) time complexity.
Unlike Map, SortedMap is an opaque data structure that does not support
pattern matching.
SortedMap implements the Enumerable protocol, so that Enum
functions can be applied to sorted maps. When applying Stream functions
to a sorted map, it is recommended to first create a stream using
SortedMap.to_stream/1 or SortedMap.to_stream/2, which adapts the effecient
lazy iterator pattern provided by gb_trees.
Summary
Functions
Delete the key-value pair for the given key in sorted_map.
Fetch the value for the given key in sorted_map.
Get the value for the given key in sorted_map.
Check if sorted_map has the given key.
Return the list of keys in sorted_map.
Create an empty map.
Create a new map from the given enumerable.
Removs the value associated with key in sorted_map and return the value
and the updated map.
Insert value under key into sorted_map.
Return the number of key-value pairs in sorted_map.
Return the key-value pair with the smallest key in sorted_map.
Convert sorted_map into a sorted list of elements.
Create a Stream from sorted_map
that emits key-value pairs in key-order starting from the smallest key in
the map.
Create a Stream from sorted_map
that emits key-value pairs in key-order starting from the first key in the
map greater than or equal to start_key.
Update the value under the given key in sorted_map with given function
fun.
Return the list of values in sorted_map.
Types
@type iter() :: :gb_trees.iter()
@type key() :: any()
@type t(key, value) :: %Orderly.SortedMap{map: :gb_trees.tree(key, value)}
@type value() :: any()
Functions
Delete the key-value pair for the given key in sorted_map.
If key is not present, the map is returned unchanged.
Examples
iex> map = Orderly.SortedMap.new([a: 1])
iex> Orderly.SortedMap.delete(map, :a)
Orderly.SortedMap.new([])
iex> Orderly.SortedMap.delete(map, :b)
Orderly.SortedMap.new([a: 1])Fetch the value for the given key in sorted_map.
This returns {:ok, value} if the key is present, and :error otherwise.
Examples
iex> map = Orderly.SortedMap.new([a: 1])
iex> Orderly.SortedMap.fetch(map, :a)
{:ok, 1}
iex> Orderly.SortedMap.fetch(map, :b)
:errorGet the value for the given key in sorted_map.
If key is present, the corresponding value is returned. Otherwise,
default is returned. If default is not provided, nil is returned.
Examples
iex> map = Orderly.SortedMap.new([a: 1])
iex> Orderly.SortedMap.get(map, :a)
1
iex> Orderly.SortedMap.get(map, :b, 2)
2Check if sorted_map has the given key.
Examples
iex> [a: 1] |> Orderly.SortedMap.new() |> Orderly.SortedMap.has_key?(:a)
trueReturn the list of keys in sorted_map.
The keys are returned in key-order.
Examples
iex> [b: 2, a: 1] |> Orderly.SortedMap.new() |> Orderly.SortedMap.keys()
[:a, :b]
iex> Orderly.SortedMap.new() |> Orderly.SortedMap.keys()
[]@spec new() :: t()
Create an empty map.
Examples
iex> Orderly.SortedMap.new()
Orderly.SortedMap.new([])@spec new(Enumerable.t()) :: t()
Create a new map from the given enumerable.
Examples
iex> Orderly.SortedMap.new([a: 1, b: 2])
Orderly.SortedMap.new([a: 1, b: 2])
iex> Orderly.SortedMap.new(%{a: 1, b: 2})
Orderly.SortedMap.new([a: 1, b: 2])Removs the value associated with key in sorted_map and return the value
and the updated map.
If key is present in sorted_map, it returns {value, updated_map} where
value is the value associated with key and updated_map is the result of
removing key from sorted_map. If key is not present in map,
{default, sorted_map} is returned.
Examples
iex> map = Orderly.SortedMap.new([a: 1, b: 2])
iex> Orderly.SortedMap.pop(map, :a)
{1, Orderly.SortedMap.new([b: 2])}
iex> Orderly.SortedMap.pop(map, :c, 3)
{3, map}Insert value under key into sorted_map.
If key is present, its value is updated to the given value. If key
is absent, key and value are added to sorted_map.
Examples
iex> Orderly.SortedMap.new() |> Orderly.SortedMap.put(:a, 1)
Orderly.SortedMap.new([a: 1])@spec size(t()) :: non_neg_integer()
Return the number of key-value pairs in sorted_map.
Examples
iex> map = Orderly.SortedMap.new([a: 1])
iex> Orderly.SortedMap.size(map)
1Return the key-value pair with the smallest key in sorted_map.
This returns {:ok, {key, value}} if the map is non-empty, and :error otherwise.
Examples
iex> [b: 2, a: 1] |> Orderly.SortedMap.new() |> Orderly.SortedMap.smallest()
{:ok, {:a, 1}}
iex> Orderly.SortedMap.new([]) |> Orderly.SortedMap.smallest()
:errorConvert sorted_map into a sorted list of elements.
Examples
iex> Orderly.SortedMap.new([a: 1, b: 2]) |> Orderly.SortedMap.to_list()
[a: 1, b: 2]@spec to_stream(t()) :: Enumerable.t()
Create a Stream from sorted_map
that emits key-value pairs in key-order starting from the smallest key in
the map.
To generate values lazily, this uses
:gb_trees.iterator/1 and
:gb_trees.next/1.
Examples
iex> map = Orderly.SortedMap.new([b: 2, a: 1, c: 3])
iex> stream = Orderly.SortedMap.to_stream(map)
iex> stream |> Enum.take(2)
[a: 1, b: 2]
iex> stream |> Enum.filter(fn {_k, v} -> rem(v, 2) == 0 end)
[b: 2]@spec to_stream(t(), value()) :: Enumerable.t()
Create a Stream from sorted_map
that emits key-value pairs in key-order starting from the first key in the
map greater than or equal to start_key.
To generate values lazily, this uses
:gb_trees.iterator_from/2 and
:gb_trees.next/1.
Examples
iex> map = Orderly.SortedMap.new([b: 2, a: 1, c: 3])
iex> stream = Orderly.SortedMap.to_stream(map, :b)
iex> stream |> Enum.take(2)
[b: 2, c: 3]
iex> stream |> Enum.filter(fn {_k, v} -> rem(v, 2) != 0 end)
[c: 3]Update the value under the given key in sorted_map with given function
fun.
If key is present, fun is applied to the existing value to obtain the
updated value. If key is not present, default is inserted under key.
Examples
iex> map = Orderly.SortedMap.new([a: 1])
iex> Orderly.SortedMap.update(map, :a, nil, & &1 + 1)
Orderly.SortedMap.new([a: 2])
iex> Orderly.SortedMap.update(map, :b, 2, & &1 + 1)
Orderly.SortedMap.new([a: 1, b: 2])Return the list of values in sorted_map.
The values are returned in key-order.
Examples
iex> [b: 2, a: 1] |> Orderly.SortedMap.new() |> Orderly.SortedMap.values()
[1, 2]
iex> Orderly.SortedMap.new() |> Orderly.SortedMap.values()
[]