Specs

insert(t(val), {integer(), integer()}, term() | nil) :: t(val) when val: value()

(O(log n)). Insert an interval and associated value into a map. The map may contain duplicate intervals; the new entry will be inserted before any existing entries for the same interval.

An associated payload may be provided to be associated with the interval. Defaults to nil.

Examples

iex> insert(new(), {1, 10}, :payload)
#HalluxIMap<[{{1, 10}, :payload}]>

Specs

interval_match(t(val), {integer(), integer()}) :: [
  {{integer(), integer()}, val}
]
when val: value()

(O(m log (n/m))). All intervals that intersect with the given interval, in lexicographical order.

To check for intervals that contain a single point x, use {x, x} as an interval.

Examples

iex> im = Enum.into([
...>     {{1, 2}, :a},
...>     {{4, 10}, :b},
...>     {{9, 15}, :c}
...>   ], new())
iex> interval_match(im, {2, 4})
[{{1, 2}, :a}, {{4, 10}, :b}]

iex> im = Enum.into([
...>     {{1, 2}, :a},
...>     {{4, 10}, :b},
...>     {{9, 15}, :c}
...>   ], new())
iex> interval_match(im, {16, 20})
[]

Specs

interval_search(t(val), {integer(), integer()}) ::
  {:ok, {integer(), integer()}, val} | {:error, :not_found}
when val: value()

(O(log (n))). finds an interval overlapping with a given interval in the above times, if such an interval exists.

Returns {:ok, {low, high}, payload} if found, {:error, :not_found} otherwise.

Examples

iex> im = Enum.into([
...>     {{1, 2}, :a},
...>     {{4, 10}, :b},
...>     {{9, 15}, :c}
...>   ], new())
iex> interval_search(im, {9, 10})
{:ok, {4, 10}, :b}

iex> im = Enum.into([
...>     {{1, 2}, :a},
...>     {{4, 10}, :b},
...>     {{9, 15}, :c}
...>   ], new())
iex> interval_search(im, {20, 30})
{:error, :not_found}

Specs

new() :: t()

(O(1)). Returns a new IntervalMap.

Examples

iex> new()
#HalluxIMap<[]>