ClosedIntervals
implements a tree storing a set of closed intervals such that the
intervals cover a one-dimensional space completely. So for a set of points {x1, x2, .., xN}
,
ClosedIntervals
builds a new set {(:"-inf", x1), (x1, x2), ..., (xN-1, xN), (xN, :"+inf")}
and
provides functions to retrieve the interval to which a value belongs.
Add the closed_intervals
dependency to your mix.exs
:
def deps do
[
{:closed_intervals, "~> 0.1"}
]
end
As a simple example, consider the following set of points:
[1, 10, 30]
With ClosedIntervals
, the points above are placed on a number line. Now, for any
value on that number line, we can retrieve the interval to which that value
belongs:
iex> import ClosedIntervals
iex> closed_intervals = from([1, 10, 30])
iex> get_interval(closed_intervals, 2)
{1, 10}
iex> get_interval(closed_intervals, 11)
{10, 30}
iex> get_interval(closed_intervals, -1)
{:"-inf", 1}
iex> get_interval(closed_intervals, 1)
{:"-inf", 1}
iex> get_interval(closed_intervals, 100)
{30, :"+inf"}
So if we retrieve the interval for 2
, we receive {1, 10}
, as the value 2
is between 1
and 10
. If we query -1
, we receive {:"-inf", 1}
, as -1
is in front of all defined intervals. Similarly for 100
, we retrieve {30, :"+inf"}
.
Defining a linear space with plain numbers is boring, however. Where ClosedIntervals
shines is to define an order on multi-dimensional values, where an order in one dimension
makes sense. This is done by defining an explicit order on
ClosedIntervals.from/2
and ClosedIntervals.get_interval/2
:
iex> import ClosedIntervals
iex> points = [%{idx: 1, data: :hello}, %{idx: 5, data: :world}]
iex> order = fn a, b -> a.idx <= b.idx end
iex> closed_intervals = from(points, order: order)
iex> get_interval(closed_intervals, %{idx: 3})
{%{idx: 1, data: :hello}, %{idx: 5, data: :world}}
ClosedIntervals
can also handle non-unique indices. This is useful when defining
a function step-wise. Note that in such a case, the intervals for a value should be retrieved
using ClosedIntervals.get_all_intervals/2
, as a value may belong to more than one interval. For this,
we must define an equality function as well. Usually, this function compares the same fields as
the order function.
iex> import ClosedIntervals
iex> points = [%{idx: 1, data: :hello}, %{idx: 1, data: :between}, %{idx: 5, data: :world}]
iex> order = fn a, b -> a.idx <= b.idx end
iex> eq = fn a, b -> a.idx == b.idx end
iex> closed_intervals = from(points, order: order, eq: eq)
iex> get_all_intervals(closed_intervals, %{idx: 3})
[{%{idx: 1, data: :between}, %{idx: 5, data: :world}}]
iex> get_all_intervals(closed_intervals, %{idx: 1})
[
{:"-inf", %{idx: 1, data: :hello}},
{%{idx: 1, data: :hello}, %{idx: 1, data: :between}},
{%{idx: 1, data: :between}, %{idx: 5, data: :world}}
]
ClosedIntervals
uses a tree of tuples to represent the set of intervals. Using
tuples is considerably faster than using maps, and it is faster than running a
simple linear search on a list of intervals. A linear search would outperform
the implementation here as long as the value queried for is at the beginning of
the list, but the performance degrades very fast for long lists. See the
benchmark/
for a simple benchmark of a linear search compared to ClosedIntervals
.
ClosedIntervals
is released under Apache License 2.0. See the LICENSE
file for more information.