OrderedCollections.SortedMap (ordered_collections v0.3.3)

A sorted key-value store implemented using Erlang's :gb_trees (Red-Black Trees).

This module stores items in sorted order by their keys and offers a rich set of features that allow it to integrate seamlessly with Elixir’s core protocols:

Enumerable: SortedMap implements the Enumerable protocol. This means you can use all the standard functions in the Enum module (like Enum.map/2, Enum.reduce/3, and Enum.slice/2) directly on a SortedMap.
Example:
```
iex> map = SortedMap.new(%{b: 2, a: 1, c: 3})
iex> Enum.map(map, fn {k, v} -> {k, v * 2} end)
[a: 2, b: 4, c: 6]
```
Collectable: SortedMap implements the Collectable protocol, allowing you to build a SortedMap from any enumerable using Enum.into/2.
Example:
```
iex> map = Enum.into([{:a, 1}, {:b, 2}], SortedMap.new())
iex> SortedMap.to_list(map)
[a: 1, b: 2]
```

Inspect: SortedMap implements the Inspect protocol, providing a clean and concise representation when you use IO.inspect/1.

Example:

iex> map = SortedMap.new(%{b: 2, a: 1})
iex> captured = ExUnit.CaptureIO.capture_io(fn -> IO.inspect(map) end)
iex> captured
~s(#SortedMap<%{a: 1, b: 2}>\n)

JSON Encoding: SortedMap implements the JSON.Encoder protocol (using the native JSON support in Elixir 1.18 and later). This ensures that when you encode a SortedMap to JSON, the keys appear in sorted order.
Example:
```
iex> map = SortedMap.new(%{a: 1, b: 2})
iex> JSON.encode!(map)
~s({"a":1,"b":2})
```

Implementation Details

Internally, SortedMap wraps Erlang's :gb_trees to achieve efficient insertion, lookup, and deletion operations while automatically maintaining the order of keys. By leveraging the power of Erlang's native data structures and integrating with protocols like Enumerable, Collectable, Inspect, and JSON.Encoder, SortedMap behaves like a first-class Elixir collection with a familiar API.

Summary

Types

non_empty_t()

non_empty_tree()

t()

Functions

delete(map, key)

Deletes a key.

get(sorted_map, key, default \\ nil)

Retrieves a value by key, returning a default if missing.

has_key?(sorted_map, key)

Checks if a key exists.

keys(sorted_map)

Returns the keys of the SortedMap in sorted order.

max_key(sorted_map)

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

merge(sorted_map1, sorted_map2)

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

min_key(sorted_map)

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

new()

Creates a new empty sorted map.

new(map)

Creates a new sorted map from a standard map.

put(map, key, value)

Inserts a key-value pair, maintaining order.

range(sorted_map, min, max)

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

rebalance(sorted_map)

Rebalances the tree.

to_list(sorted_map)

Returns all key-value pairs in sorted order.

to_map(sorted_map)

Converts the SortedMap into a standard Map, losing the sorted property.

update(map, key, fun)

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

update(map, key, fun, default)

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

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.

values(sorted_map)

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

Types

non_empty_t()

@type non_empty_t() :: %OrderedCollections.SortedMap{tree: non_empty_tree()}

non_empty_tree()

@type non_empty_tree() :: :gb_trees.tree()

t()

@type t() :: %OrderedCollections.SortedMap{tree: :gb_trees.tree()}

Functions

delete(map, key)

@spec delete(t(), any()) :: t()

Deletes a key.

Examples

iex> sm = SortedMap.new(%{a: 1, b: 2})
iex> sm2 = SortedMap.delete(sm, :b)
iex> SortedMap.has_key?(sm2, :b)
false

get(sorted_map, key, default \\ nil)

@spec get(t(), any(), any()) :: any()

Retrieves a value by key, returning a default if missing.

Examples

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

has_key?(sorted_map, key)

@spec has_key?(t(), any()) :: boolean()

Checks if a key exists.

Examples

iex> sm = SortedMap.new(%{a: 1, b: 2})
iex> SortedMap.has_key?(sm, :a)
true
iex> SortedMap.has_key?(sm, :c)
false

keys(sorted_map)

@spec keys(t()) :: list()

Returns the keys of the SortedMap in sorted order.

Examples

iex> sm = SortedMap.new(%{b: 2, a: 1, c: 3})
iex> SortedMap.keys(sm)
[:a, :b, :c]

max_key(sorted_map)

@spec max_key(t()) :: any()

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

Examples

iex> sm = SortedMap.new(%{b: 2, a: 1, c: 3})
iex> SortedMap.max_key(sm)
:c

iex> sm = SortedMap.new(%{b: 10, a: 99, c: 3})
iex> SortedMap.max_key(sm)
:c

iex> sm_empty = SortedMap.new()
iex> SortedMap.max_key(sm_empty)
:none

merge(sorted_map1, sorted_map2)

@spec merge(t(), t()) :: any()

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

Examples

iex> sm1 = SortedMap.new(%{a: 1, b: 2})
iex> sm2 = SortedMap.new(%{b: 3, c: 4})
iex> SortedMap.merge(sm1, sm2) |> SortedMap.to_list()
[{:a, 1}, {:b, 3}, {:c, 4}]

min_key(sorted_map)

@spec min_key(t()) :: any()

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

Examples

iex> sm = SortedMap.new(%{b: 2, a: 1, c: 3})
iex> SortedMap.min_key(sm)
:a

iex> sm_empty = SortedMap.new()
iex> SortedMap.min_key(sm_empty)
:none

new()

@spec new() :: t()

Creates a new empty sorted map.

Examples

iex> sm = SortedMap.new()
iex> SortedMap.to_map(sm)
%{}

new(map)

@spec new(map()) :: t()

Creates a new sorted map from a standard map.

Examples

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

put(map, key, value)

@spec put(t(), any(), any()) :: t()

Inserts a key-value pair, maintaining order.

Examples

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

range(sorted_map, min, max)

@spec range(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 = SortedMap.new(%{a: 1, b: 2, c: 3, d: 4})
iex> SortedMap.range(sm, :b, :c)
[{:b, 2}, {:c, 3}]

rebalance(sorted_map)

@spec rebalance(t()) :: t()

Rebalances the tree.

Examples

iex> sm = SortedMap.new(%{a: 1, b: 2, c: 3}) iex> smi = SortedMap.new() |> SortedMap.put(:a, 1) |> SortedMap.put(:b, 2) |> SortedMap.put(:c, 3) iex> sm == smi false iex> sm |> SortedMap.rebalance() == smi |> SortedMap.rebalance() true

to_list(sorted_map)

@spec to_list(t()) :: [{any(), any()}]

Returns all key-value pairs in sorted order.

Examples

iex> sm = SortedMap.new(%{b: 2, a: 1})
iex> SortedMap.to_list(sm)
[{:a, 1}, {:b, 2}]

to_map(sorted_map)

@spec to_map(t()) :: map()

Converts the SortedMap into a standard Map, losing the sorted property.

Examples

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

iex> sm = SortedMap.new(%{a: 2, b: 1})
iex> captured = ExUnit.CaptureIO.capture_io(fn -> IO.inspect(sm) end)
iex> captured
~s(#SortedMap<%{a: 2, b: 1}>\n)
iex> SortedMap.to_map(sm)
%{a: 2, b: 1}

update(map, key, fun)

@spec update(t(), any(), (any() -> any())) :: t()

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

Examples

iex> sm = SortedMap.new(%{a: 1})
iex> sm = SortedMap.update(sm, :a, &(&1 + 1))
iex> SortedMap.get(sm, :a)
2

iex> SortedMap.new(%{a: 1}) |> SortedMap.update(:b, &(&1 + 1)) |> SortedMap.get(:b)
nil

update(map, key, fun, default)

@spec update(t(), any(), (any() -> any()), any()) :: t()

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

Examples

iex> sm = SortedMap.new(%{a: 1})
iex> sm = SortedMap.update(sm, :a, &(&1 + 5), 0)
iex> SortedMap.get(sm, :a)
6

iex> SortedMap.new(%{a: 1}) |> SortedMap.update(:b, &(&1 + 1), 10) |> SortedMap.get(:b)
10

update_with_value(map, key, new_value)

@spec update_with_value(t(), any(), any()) :: 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 = SortedMap.new(%{a: 1, b: 2})
iex> sm = SortedMap.update_with_value(sm, :a, 100)
iex> SortedMap.get(sm, :a)
100
iex> SortedMap.update_with_value(sm, :c, 300)
iex> SortedMap.get(sm, :c)
nil

values(sorted_map)

@spec values(t()) :: list()

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

Examples

iex> sm = SortedMap.new(%{b: 2, a: 1, c: 3})
iex> SortedMap.values(sm)
[1, 2, 3]