OrderedCollections (ordered_collections v0.3.3)

OrderedCollections provides sorted data structures for Elixir, including a SortedMap and a SortedSet.

For SortedMap, keys are maintained in a sorted order per Erlang's :gb_trees module.

For SortedSet, elements are maintained in a sorted order per Erlang's :gb_sets module.

Core Modules

OrderedCollections.SortedMap - A sorted key-value store implemented using Erlang's :gb_trees.
OrderedCollections.SortedSet - A sorted set implemented using Erlang's :gb_sets.

Core Module Examples

iex> sm = OrderedCollections.SortedMap.new(%{b: 2, a: 1})
iex> OrderedCollections.SortedMap.get(sm, :a)
1

iex> ss = OrderedCollections.SortedSet.new([3, 1, 2])
iex> OrderedCollections.SortedSet.to_list(ss)
[1, 2, 3]

Convenience Functions

This module also provides convenience functions that wrap the core module functions. These functions are prefixed with map_ for SortedMap operations and set_ for SortedSet operations.

Map Convenience Functions

iex> sm = OrderedCollections.new_map(%{x: 10})
iex> sm = OrderedCollections.map_put(sm, :y, 20)
iex> OrderedCollections.map_get(sm, :y)
20

iex> sm = OrderedCollections.new_map()
iex> sm = OrderedCollections.map_put(sm, :a, 1)
iex> OrderedCollections.map_to_map(sm)
%{a: 1}

Set Convenience Functions

iex> ss = OrderedCollections.new_set([3, 1, 2])
iex> ss = OrderedCollections.set_add_value(ss, 4)
iex> OrderedCollections.set_member?(ss, 4)
true

iex> ss = OrderedCollections.new_set()
iex> ss = OrderedCollections.set_add_value(ss, 1)
iex> OrderedCollections.SortedSet.to_list(ss)
[1]

Map Operations via Convenience Functions

The following examples show how to use the convenience functions for map operations:

iex> sm = OrderedCollections.new_map(%{b: 2, a: 1, c: 3})
iex> OrderedCollections.map_keys(sm)
[:a, :b, :c]
iex> OrderedCollections.map_values(sm)
[1, 2, 3]
iex> sm2 = OrderedCollections.new_map(%{b: 4, d: 5})
iex> OrderedCollections.map_merge(sm, sm2) |> OrderedCollections.map_to_map()
%{a: 1, b: 4, c: 3, d: 5}
iex> OrderedCollections.map_range(sm, :a, :b)
[a: 1, b: 2]
iex> OrderedCollections.map_min_key(sm)
:a
iex> OrderedCollections.map_max_key(sm)
:c

Set Operations via Convenience Functions

The following examples show how to use the convenience functions for set operations:

iex> set1 = OrderedCollections.new_set([1, 2, 3])
iex> set2 = OrderedCollections.new_set([3, 4, 5])
iex> OrderedCollections.set_union(set1, set2) |> OrderedCollections.SortedSet.to_list()
[1, 2, 3, 4, 5]
iex> OrderedCollections.set_difference(set1, set2) |> OrderedCollections.SortedSet.to_list()
[1, 2]
iex> OrderedCollections.set_intersection(set1, set2) |> OrderedCollections.SortedSet.to_list()
[3]

Range Operations via Convenience Functions

You can get elements within a specific range using convenience functions:

iex> set = OrderedCollections.new_set([1, 2, 3, 4, 5])
iex> OrderedCollections.set_range(set, 2, 4) |> OrderedCollections.SortedSet.to_list()
[2, 3, 4]

Min/Max Operations via Convenience Functions

You can get the minimum and maximum elements using convenience functions:

iex> set = OrderedCollections.new_set([3, 1, 2])
iex> OrderedCollections.set_min(set)
1
iex> OrderedCollections.set_max(set)
3

Summary

Functions

map_delete(map, key)

Deletes a key.

map_get(sorted_map, key, default \\ nil)

Retrieves the value for the given key from a SortedMap, returning a default if the key is missing.

map_has_key?(map, key)

Checks if a key exists.

map_keys(sorted_map)

Returns the keys of the SortedMap in sorted order.

map_max_key(map)

Returns the largest key. Returns :none if the map is empty.

map_merge(map1, map2)

Merges two SortedMaps. In case of duplicate keys, values from the second map override those from the first.

map_min_key(map)

Returns the smallest key. Returns :none if the map is empty.

map_put(sorted_map, key, value)

Inserts a key-value pair into a SortedMap.

map_range(map, min, max)

Iterates over a range of keys, returning key-value pairs whose keys are between min and max (inclusive).

map_rebalance(map)

Rebalances the tree.

map_to_map(sorted_map)

Creates a map from a SortedMap.

map_update(map, key, fun)

Updates a key with a function. If the key doesn't exist, it is set to nil.

map_update(map, key, fun, default)

Updates a key with a function. If the key doesn't exist, it sets it to default.

map_update_with_value(map, key, new_value)

Replaces the value for key with new_value if the key exists. If key does not exist, the map remains unchanged.

map_values(sorted_map)

Returns the values of the SortedMap in the order corresponding to the sorted keys.

new_map()

Creates a new empty SortedMap.

new_map(map)

Creates a new SortedMap from a regular map.

new_set()

Creates a new empty SortedSet.

new_set(list)

Creates a new SortedSet from a list.

set_add_value(sorted_set, value)

Adds a value to the SortedSet.

set_delete_value(sorted_set, value)

Deletes a value from the SortedSet.

set_difference(set1, set2)

Returns the difference between two SortedSets.

set_intersection(set1, set2)

Returns the intersection of two SortedSets.

set_max(sorted_set)

Returns the maximum element of the SortedSet.

set_member?(sorted_set, value)

Checks if a value is a member of the SortedSet.

set_min(sorted_set)

Returns the minimum element of the SortedSet.

set_range(sorted_set, min, max)

Returns elements within a given range (inclusive).

set_union(set1, set2)

Returns the union of two SortedSets.

Functions

map_delete(map, key)

@spec map_delete(OrderedCollections.SortedMap.t(), any()) ::
  OrderedCollections.SortedMap.t()

Deletes a key.

Examples

iex> sm = OrderedCollections.new_map(%{a: 1, b: 2})
iex> sm2 = OrderedCollections.map_delete(sm, :b)
iex> OrderedCollections.map_has_key?(sm2, :b)
false

map_get(sorted_map, key, default \\ nil)

@spec map_get(OrderedCollections.SortedMap.t(), any(), any()) :: any()

Retrieves the value for the given key from a SortedMap, returning a default if the key is missing.

Examples

iex> sm = OrderedCollections.new_map(%{a: 1}) iex> OrderedCollections.map_get(sm, :a) 1 iex> OrderedCollections.map_get(sm, :b, 2) 2

map_has_key?(map, key)

@spec map_has_key?(OrderedCollections.SortedMap.t(), any()) :: boolean()

Checks if a key exists.

Examples

iex> sm = OrderedCollections.new_map(%{a: 1, b: 2})
iex> OrderedCollections.map_has_key?(sm, :a)
true
iex> OrderedCollections.map_has_key?(sm, :c)
false

map_keys(sorted_map)

@spec map_keys(OrderedCollections.SortedMap.t()) :: list()

Returns the keys of the SortedMap in sorted order.

Examples

iex> sm = OrderedCollections.new_map(%{b: 2, a: 1, c: 3})
iex> OrderedCollections.map_keys(sm)
[:a, :b, :c]

map_max_key(map)

@spec map_max_key(OrderedCollections.SortedMap.t()) :: any()

Returns the largest key. Returns :none if the map is empty.

Examples

iex> sm = OrderedCollections.new_map(%{b: 2, a: 1, c: 3})
iex> OrderedCollections.map_max_key(sm)
:c

iex> sm_empty = OrderedCollections.new_map()
iex> OrderedCollections.map_max_key(sm_empty)
:none

map_merge(map1, map2)

@spec map_merge(OrderedCollections.SortedMap.t(), OrderedCollections.SortedMap.t()) ::
  OrderedCollections.SortedMap.t()

Merges two SortedMaps. In case of duplicate keys, values from the second map override those from the first.

Examples

iex> sm1 = OrderedCollections.new_map(%{a: 1, b: 2})
iex> sm2 = OrderedCollections.new_map(%{b: 3, c: 4})
iex> OrderedCollections.map_merge(sm1, sm2) |> OrderedCollections.map_to_map()
%{a: 1, b: 3, c: 4}

map_min_key(map)

@spec map_min_key(OrderedCollections.SortedMap.t()) :: any()

Returns the smallest key. Returns :none if the map is empty.

Examples

iex> sm = OrderedCollections.new_map(%{b: 2, a: 1, c: 3})
iex> OrderedCollections.map_min_key(sm)
:a

iex> sm_empty = OrderedCollections.new_map()
iex> OrderedCollections.map_min_key(sm_empty)
:none

map_put(sorted_map, key, value)

@spec map_put(OrderedCollections.SortedMap.t(), any(), any()) ::
  OrderedCollections.SortedMap.t()

Inserts a key-value pair into a SortedMap.

Examples

iex> sm = OrderedCollections.new_map() iex> sm = OrderedCollections.map_put(sm, :a, 1) iex> OrderedCollections.map_get(sm, :a) 1

map_range(map, min, max)

@spec map_range(OrderedCollections.SortedMap.t(), any(), any()) :: [{any(), any()}]

Iterates over a range of keys, returning key-value pairs whose keys are between min and max (inclusive).

Examples

iex> sm = OrderedCollections.new_map(%{a: 1, b: 2, c: 3, d: 4})
iex> OrderedCollections.map_range(sm, :b, :c)
[b: 2, c: 3]

map_rebalance(map)

@spec map_rebalance(OrderedCollections.SortedMap.t()) ::
  OrderedCollections.SortedMap.t()

Rebalances the tree.

Examples

iex> sm = OrderedCollections.new_map(%{a: 1, b: 2, c: 3})
iex> smi = OrderedCollections.new_map() |> OrderedCollections.map_put(:a, 1) |> OrderedCollections.map_put(:b, 2) |> OrderedCollections.map_put(:c, 3)
iex> sm == smi
false
iex> OrderedCollections.map_rebalance(sm) == OrderedCollections.map_rebalance(smi)
true

map_to_map(sorted_map)

@spec map_to_map(OrderedCollections.SortedMap.t()) :: map()

Creates a map from a SortedMap.

Examples

iex> sm = OrderedCollections.new_map(%{b: 2, a: 1}) iex> OrderedCollections.map_to_map(sm) %{a: 1, b: 2}

map_update(map, key, fun)

@spec map_update(OrderedCollections.SortedMap.t(), any(), (any() -> any())) ::
  OrderedCollections.SortedMap.t()

Updates a key with a function. If the key doesn't exist, it is set to nil.

Examples

iex> sm = OrderedCollections.new_map(%{a: 1})
iex> sm = OrderedCollections.map_update(sm, :a, &(&1 + 1))
iex> OrderedCollections.map_get(sm, :a)
2

iex> OrderedCollections.new_map(%{a: 1}) |> OrderedCollections.map_update(:b, &(&1 + 1)) |> OrderedCollections.map_get(:b)
nil

map_update(map, key, fun, default)

@spec map_update(OrderedCollections.SortedMap.t(), any(), (any() -> any()), any()) ::
  OrderedCollections.SortedMap.t()

Updates a key with a function. If the key doesn't exist, it sets it to default.

Examples

iex> sm = OrderedCollections.new_map(%{a: 1})
iex> sm = OrderedCollections.map_update(sm, :a, &(&1 + 5), 0)
iex> OrderedCollections.map_get(sm, :a)
6

iex> OrderedCollections.new_map(%{a: 1}) |> OrderedCollections.map_update(:b, &(&1 + 1), 10) |> OrderedCollections.map_get(:b)
10

map_update_with_value(map, key, new_value)

@spec map_update_with_value(OrderedCollections.SortedMap.t(), any(), any()) ::
  OrderedCollections.SortedMap.t()

Replaces the value for key with new_value if the key exists. If key does not exist, the map remains unchanged.

Examples

iex> sm = OrderedCollections.new_map(%{a: 1, b: 2})
iex> sm = OrderedCollections.map_update_with_value(sm, :a, 100)
iex> OrderedCollections.map_get(sm, :a)
100
iex> OrderedCollections.map_update_with_value(sm, :c, 300)
iex> OrderedCollections.map_get(sm, :c)
nil

map_values(sorted_map)

@spec map_values(OrderedCollections.SortedMap.t()) :: list()

Returns the values of the SortedMap in the order corresponding to the sorted keys.

Examples

iex> sm = OrderedCollections.new_map(%{b: 2, a: 1, c: 3})
iex> OrderedCollections.map_values(sm)
[1, 2, 3]

new_map()

@spec new_map() :: OrderedCollections.SortedMap.t()

Creates a new empty SortedMap.

Examples

iex> sm = OrderedCollections.new_map() iex> OrderedCollections.map_to_map(sm) %{}

new_map(map)

@spec new_map(map()) :: OrderedCollections.SortedMap.t()

Creates a new SortedMap from a regular map.

Examples

iex> m = %{b: 2, a: 1} iex> sm = OrderedCollections.new_map(m) iex> OrderedCollections.map_get(sm, :a) 1

new_set()

@spec new_set() :: OrderedCollections.SortedSet.t()

Creates a new empty SortedSet.

Examples

iex> ss = OrderedCollections.new_set()
iex> OrderedCollections.SortedSet.to_list(ss)
[]

new_set(list)

@spec new_set(list()) :: OrderedCollections.SortedSet.t()

Creates a new SortedSet from a list.

Examples

iex> ss = OrderedCollections.new_set([3, 1, 2])
iex> OrderedCollections.SortedSet.to_list(ss)
[1, 2, 3]

set_add_value(sorted_set, value)

@spec set_add_value(OrderedCollections.SortedSet.t(), any()) ::
  OrderedCollections.SortedSet.t()

Adds a value to the SortedSet.

Examples

iex> ss = OrderedCollections.new_set([2, 3])
iex> ss = OrderedCollections.set_add_value(ss, 1)
iex> ss = OrderedCollections.set_add_value(ss, 3)
iex> OrderedCollections.SortedSet.to_list(ss)
[1, 2, 3]

set_delete_value(sorted_set, value)

@spec set_delete_value(OrderedCollections.SortedSet.t(), any()) ::
  OrderedCollections.SortedSet.t()

Deletes a value from the SortedSet.

Examples

iex> ss = OrderedCollections.new_set([1, 2, 3])
iex> ss = OrderedCollections.set_delete_value(ss, 2)
iex> OrderedCollections.SortedSet.to_list(ss)
[1, 3]

set_difference(set1, set2)

@spec set_difference(
  OrderedCollections.SortedSet.t(),
  OrderedCollections.SortedSet.t()
) ::
  OrderedCollections.SortedSet.t()

Returns the difference between two SortedSets.

Examples

iex> set1 = OrderedCollections.new_set([1, 2, 3])
iex> set2 = OrderedCollections.new_set([3, 4, 5])
iex> OrderedCollections.set_difference(set1, set2) |> OrderedCollections.SortedSet.to_list()
[1, 2]

set_intersection(set1, set2)

@spec set_intersection(
  OrderedCollections.SortedSet.t(),
  OrderedCollections.SortedSet.t()
) ::
  OrderedCollections.SortedSet.t()

Returns the intersection of two SortedSets.

Examples

iex> set1 = OrderedCollections.new_set([1, 2, 3])
iex> set2 = OrderedCollections.new_set([3, 4, 5])
iex> OrderedCollections.set_intersection(set1, set2) |> OrderedCollections.SortedSet.to_list()
[3]

set_max(sorted_set)

@spec set_max(OrderedCollections.SortedSet.non_empty_t()) ::
  OrderedCollections.SortedSet.element()

Returns the maximum element of the SortedSet.

Examples

iex> ss = OrderedCollections.new_set([3, 1, 2])
iex> OrderedCollections.set_max(ss)
3

set_member?(sorted_set, value)

@spec set_member?(OrderedCollections.SortedSet.t(), any()) :: boolean()

Checks if a value is a member of the SortedSet.

Examples

iex> ss = OrderedCollections.new_set([1, 2, 3])
iex> OrderedCollections.set_member?(ss, 2)
true

set_min(sorted_set)

@spec set_min(OrderedCollections.SortedSet.non_empty_t()) ::
  OrderedCollections.SortedSet.element()

Returns the minimum element of the SortedSet.

Examples

iex> ss = OrderedCollections.new_set([3, 1, 2])
iex> OrderedCollections.set_min(ss)
1

set_range(sorted_set, min, max)

@spec set_range(OrderedCollections.SortedSet.t(), any(), any()) ::
  OrderedCollections.SortedSet.t()

Returns elements within a given range (inclusive).

Examples

iex> ss = OrderedCollections.new_set([1, 2, 3, 4, 5])
iex> OrderedCollections.set_range(ss, 2, 4) |> OrderedCollections.SortedSet.to_list()
[2, 3, 4]

set_union(set1, set2)

@spec set_union(OrderedCollections.SortedSet.t(), OrderedCollections.SortedSet.t()) ::
  OrderedCollections.SortedSet.t()

Returns the union of two SortedSets.

Examples

iex> set1 = OrderedCollections.new_set([1, 2, 3])
iex> set2 = OrderedCollections.new_set([3, 4, 5])
iex> OrderedCollections.set_union(set1, set2) |> OrderedCollections.SortedSet.to_list()
[1, 2, 3, 4, 5]