Skip to content

Instantly share code, notes, and snippets.

@iStefo

iStefo/range_tree.ex

Last active March 18, 2026 09:10
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save iStefo/01c34ff10db499ad14223679582893c8 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save iStefo/01c34ff10db499ad14223679582893c8 to your computer and use it in GitHub Desktop.
Download ZIP
Elixir RangeTree backed by :gb_trees
Raw
range_tree.ex
defmodule RangeTree do
@moduledoc """
An integer interval tree backed by Erlang's `:gb_trees` that automatically merges adjacent
intervals on insertion.
Intervals are stored as `{from, to}` pairs (inclusive on both ends) where keys represent offsets
from a 1900-01-01 epoch, allowing dates to be mapped to integers via `to_int/1` and `from_int/1`.
Supports efficient lookup of whether a point is covered, counting total covered points, finding
uncovered gaps within a range, and a compact serialization format for storage.
"""
@typedoc "Non-negative integer representing a point on the number line."
@type point :: non_neg_integer()
@typedoc "An inclusive interval `{from, to}` where `from <= to`."
@type interval :: {point(), point()}
@typedoc "Opaque range tree backed by `:gb_trees`."
@opaque t :: :gb_trees.tree(point(), point())
@doc """
Creates a new empty range tree.
"""
@spec new() :: t()
def new do
:gb_trees.empty()
end
@doc """
Inserts an interval `[from, to]` (inclusive) into the tree.
Adjacent intervals are merged automatically. Overlapping intervals raise a `RuntimeError`.
A single `Date` can be passed as shorthand for a single-day interval.
## Examples
iex> RangeTree.new() |> RangeTree.insert(4, 8) |> RangeTree.insert(9, 10) |> RangeTree.to_list()
[{4, 10}]
"""
@spec insert(t(), Date.t()) :: t()
def insert(tree, %Date{} = date), do: insert(tree, to_int(date), to_int(date))
@spec insert(t(), point(), point()) :: t()
def insert(tree, from, to) when 0 <= from and from <= to do
case :gb_trees.lookup(from, tree) do
{:value, stored_to} ->
raise "Interval [#{from}, #{to}] overlaps with existing interval [#{from}, #{stored_to}]"
_ ->
:ok
end
case {:gb_trees.smaller(from, tree), :gb_trees.larger(from, tree)} do
{{smaller_from, smaller_to}, _} when smaller_to >= from ->
raise "Interval [#{from}, #{to}] overlaps with previous interval [#{smaller_from}, #{smaller_to}]"
{_, {larger_from, larger_to}} when larger_from <= to ->
raise "Interval [#{from}, #{to}] overlaps with next interval [#{larger_from}, #{larger_to}]"
# merge left and right if adjacent
{{smaller_from, smaller_to}, {larger_from, larger_to}}
when smaller_to == from - 1 and
larger_from == to + 1 ->
tree = :gb_trees.delete(larger_from, tree)
:gb_trees.update(smaller_from, larger_to, tree)
# merge right if adjacent
{_, {larger_from, larger_to}} when larger_from == to + 1 ->
tree = :gb_trees.delete(larger_from, tree)
:gb_trees.insert(from, larger_to, tree)
# merge left if adjacent
{{smaller_from, smaller_to}, _} when smaller_to == from - 1 ->
:gb_trees.update(smaller_from, to, tree)
_ ->
:gb_trees.insert(from, to, tree)
end
end
@doc """
Looks up the interval covering `time`. Returns `{from, to}` if found, or `nil` if the point
is not covered by any interval.
"""
@spec get_at(t(), point()) :: interval() | nil
def get_at(tree, time) do
case :gb_trees.lookup(time, tree) do
{:value, to} ->
{time, to}
:none ->
case :gb_trees.smaller(time, tree) do
{from, to} when from <= time and time <= to ->
{from, to}
_ ->
nil
end
end
end
@doc """
Returns the total number of individual points covered by all intervals in the tree.
"""
@spec count_covered(t()) :: non_neg_integer()
def count_covered(tree) do
iter = :gb_trees.iterator(tree)
_count_covered(:gb_trees.next(iter), 0)
end
defp _count_covered(:none, acc), do: acc
defp _count_covered({from, to, iter}, acc),
do: _count_covered(:gb_trees.next(iter), acc + to - from + 1)
@doc """
Returns a list of `{from, to}` gaps within the range `[from, to]` that are not covered by any
interval in the tree. Returns an empty list if the entire range is covered.
## Examples
iex> RangeTree.new() |> RangeTree.insert(4, 8) |> RangeTree.uncovered(1, 10)
[{1, 3}, {9, 10}]
"""
@spec uncovered(t(), point(), point()) :: [interval()]
def uncovered(tree, from, to) do
# If `from` is covered by an interval, start iteration from that interval.
start_key =
case get_at(tree, from) do
{stored_from, _} -> stored_from
nil -> from
end
iter = :gb_trees.iterator_from(start_key, tree)
_get_uncovered(:gb_trees.next(iter), from, to, [])
end
# Return acc when cursor has reached the stopping point.
defp _get_uncovered(_entry, cursor, stop, acc) when cursor >= stop,
do: Enum.reverse(acc)
# Add remaining uncovered range if there are no more entries.
defp _get_uncovered(:none, cursor, stop, acc),
do: _get_uncovered(:none, stop, stop, [{cursor, stop} | acc])
# Skip coverered range by advancing cursor without adding to acc.
defp _get_uncovered({stored_from, stored_to, iter}, cursor, stop, acc)
when stored_from <= cursor and cursor <= stored_to,
do:
_get_uncovered(
:gb_trees.next(iter),
stored_to + 1,
stop,
acc
)
# Since stored_from must be greather than cursor, add this uncovered range to acc.
defp _get_uncovered({stored_from, stored_to, iter}, cursor, stop, acc),
do:
_get_uncovered(
:gb_trees.next(iter),
stored_to + 1,
stop,
[{cursor, min(stop, stored_from - 1)} | acc]
)
@doc """
Converts the tree to a sorted list of `{from, to}` interval tuples.
"""
@spec to_list(t()) :: [interval()]
def to_list(tree) do
:gb_trees.to_list(tree)
end
@doc """
Serializes the tree into a compact flat list of integers. Single-point intervals are encoded as
a negative value (e.g. `[5, 5]` becomes `-5`), and ranges are stored as two consecutive values
`[from, to]`. Use `deserialize/1` to reconstruct the tree.
"""
@spec serialize(t()) :: [integer()]
def serialize(tree) do
iterator = :gb_trees.iterator(tree)
serialize(:gb_trees.next(iterator), [])
end
def serialize(:none, acc), do: acc
def serialize({from, from, iterator}, acc) when from != 0,
do: serialize(:gb_trees.next(iterator), [-from | acc])
def serialize({from, to, iterator}, acc),
do: serialize(:gb_trees.next(iterator), [from, to | acc])
@doc """
Reconstructs a range tree from a list produced by `serialize/1`.
"""
@spec deserialize([integer()], t()) :: t()
def deserialize(list, tree \\ new())
def deserialize([], tree), do: tree
def deserialize([from | rest], tree) when from < 0,
do: deserialize(rest, insert(tree, -from, -from))
def deserialize([from, to | rest], tree),
do: deserialize(rest, insert(tree, from, to))
@epoch ~D[1900-01-01]
@doc """
Converts a `Date` to an integer offset from the 1900-01-01 epoch.
"""
@spec to_int(Date.t()) :: point()
def to_int(%Date{} = date) do
Date.diff(date, @epoch)
end
@doc """
Converts an integer offset back to a `Date` relative to the 1900-01-01 epoch.
"""
@spec from_int(point()) :: Date.t()
def from_int(offset) do
Date.add(@epoch, offset)
end
end
Raw
range_tree_test.exs
defmodule RangeTreeTest do
use ExUnit.Case, async: true
import RangeTree
describe "insert" do
test "inserts non-overlapping intervals" do
tree =
new()
|> insert(4, 8)
|> insert(15, 16)
|> insert(23, 23)
assert to_list(tree) == [{4, 8}, {15, 16}, {23, 23}]
end
test "raises when inserting overlapping intervals" do
tree =
new()
|> insert(4, 8)
|> insert(15, 16)
assert_raise RuntimeError, fn -> insert(tree, 4, 4) end
assert_raise RuntimeError, fn -> insert(tree, 5, 5) end
assert_raise RuntimeError, fn -> insert(tree, 8, 8) end
assert_raise RuntimeError, fn -> insert(tree, 3, 4) end
assert_raise RuntimeError, fn -> insert(tree, 3, 9) end
assert_raise RuntimeError, fn -> insert(tree, 3, 17) end
assert_raise RuntimeError, fn -> insert(tree, 5, 10) end
end
test "merges adjacent interval to the left" do
tree =
new()
|> insert(4, 8)
|> insert(9, 10)
assert to_list(tree) == [{4, 10}]
end
test "merges adjacent interval to the right" do
tree =
new()
|> insert(4, 8)
|> insert(1, 3)
assert to_list(tree) == [{1, 8}]
end
test "merges adjacent intervals on both sides" do
tree =
new()
|> insert(4, 8)
|> insert(15, 16)
|> insert(9, 14)
assert to_list(tree) == [{4, 16}]
end
end
describe "uncovered" do
test "returns full range for empty tree" do
tree = new()
assert uncovered(tree, 4, 23) == [{4, 23}]
end
test "returns uncovered ranges" do
tree =
new()
|> insert(1, 1)
|> insert(4, 8)
|> insert(15, 16)
# Fully inside a single interval
assert uncovered(tree, 4, 8) == []
assert uncovered(tree, 5, 6) == []
# Half inside an interval
assert uncovered(tree, 1, 5) == [{2, 3}]
assert uncovered(tree, 5, 10) == [{9, 10}]
assert uncovered(tree, 10, 15) == [{10, 14}]
# Starting and ending in an interval
assert uncovered(tree, 5, 15) == [{9, 14}]
# Spanning complete intervals
assert uncovered(tree, 2, 10) == [{2, 3}, {9, 10}]
assert uncovered(tree, 2, 23) == [{2, 3}, {9, 14}, {17, 23}]
# Completely outside all intervals
assert uncovered(tree, 2, 3) == [{2, 3}]
assert uncovered(tree, 23, 42) == [{23, 42}]
end
end
describe "serialize & deserialize" do
test "re-creates the same tree" do
tree =
new()
|> insert(0, 0)
|> insert(4, 8)
|> insert(15, 16)
recreated_tree = deserialize(serialize(tree))
assert to_list(tree) == to_list(recreated_tree)
end
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment