IntervalMap (interval_map v0.1.0) View Source

IntervalMap is an interval-bucketizing map. Given a key, you can ask for the interval in which it falls, intervals do not have to be contiguous.

Intervals are "bounded, left open, right closed". That is, all intervals are finite, and "left < n <= right". Intervals may not overlap.

You can use any term types to specify interval bounds, just take care to make sure it's meaningful, see the "Term ordering" section of Elixir's Operators documentation.

IntervalMap is implemented as a :gb_tree, where the "right" value is used as the storage key, this should give us O(log n) for get/put.

Link to this section Summary

Types

bound()

bounds()

key()

t()

value()

Functions

bounds_member?(map, arg)

Indicates if the given bounds fall within a single interval.

contiguous?(map)

Indicates if the given intervals form a continuous range (no gaps between any intervals)

delete(map, bounds)

Removes the given bounds_or_interval from the map, removing or modifying any intervals necessary.

get(interval_map, key)

Gets the interval in which the provided key resides.

get_value(map, key)

Gets the value from the interval in which the provided key resides.

key_member?(map, key)

Indicates if the given key falls into one of the map's intervals.

new()

Creates a new Interval Map

put(map, bounds, value \\ nil)

Puts the given interval into the map, specified by the bounds left and `right``, and an optional value to store with the interval.

range(map)

Returns the range of the map, that is, the leftmost and rightmost members.

to_list(interval_map)

Returns an in-order list of intervals in the provided map.

Link to this section Types

bound()

Specs

bound() :: any()

bounds()

Specs

bounds() :: {bound(), bound()}

key()

Specs

key() :: bound()

t()

Specs

t() :: %IntervalMap{tree: :gb_trees.tree(bound(), IntervalMap.Interval.t())}

value()

Specs

value() :: any()

Link to this section Functions

bounds_member?(map, arg)

Specs

bounds_member?(t(), bounds()) :: boolean()

Indicates if the given bounds fall within a single interval.

contiguous?(map)

Specs

contiguous?(t()) :: boolean()

Indicates if the given intervals form a continuous range (no gaps between any intervals)

delete(map, bounds)

Specs

delete(t(), bounds_or_interval :: bounds() | IntervalMap.Interval.t()) :: t()

Removes the given bounds_or_interval from the map, removing or modifying any intervals necessary.

O(n) at the moment, but could be made O(log(n)) for cases that only involve one or fewer intervals

get(interval_map, key)

Specs

get(t(), key()) :: IntervalMap.Interval.t() | :not_found

Gets the interval in which the provided key resides.

get_value(map, key)

Specs

get_value(t(), key()) :: {:value, value()} | :not_found

Gets the value from the interval in which the provided key resides.

key_member?(map, key)

Specs

key_member?(t(), key()) :: boolean()

Indicates if the given key falls into one of the map's intervals.

new()

Specs

new() :: t()

Creates a new Interval Map

put(map, bounds, value \\ nil)

Specs

put(t(), bounds(), value()) ::
  t()
  | {:error,
     IntervalMap.OverlappingIntervalsError.t()
     | IntervalMap.InvalidIntervalError.t()}

Puts the given interval into the map, specified by the bounds left and `right``, and an optional value to store with the interval.

range(map)

Specs

range(t()) :: IntervalMap.Interval.t()

Returns the range of the map, that is, the leftmost and rightmost members.

Remember, intervals are "left open, right closed".

to_list(interval_map)

Specs

to_list(t()) :: [IntervalMap.Interval.t()]

Returns an in-order list of intervals in the provided map.