Instantly share code, notes, and snippets.

# iw/gist:1367172 Created Nov 15, 2011

 %% @author Ian Wilkinson %% @doc interval_tree presents an Interval Tree where keys can be associated with intervals. %% Furthermore, when instantiating the Interval Tree, you can indicate whether the low or high endpoints %% can be half-open, or closed. %% %% It may be worth investigating Finger Trees %% as a possible alternative to Red-Black trees for implementing the Interval Tree. %% %% @reference %% Introduction to Algorithms %% @reference %% Purely functional data structures %% @reference %% Red-Black Trees in Erlang -module(interval_tree, [LowInterval, HighInterval]). -export([prototype/0, find/2, insert/3]). -type(colour() :: red | black). -type(interval() :: {term(), term()}). -record(interval_tree, { colour = black :: colour(), left = empty_interval_tree :: #interval_tree{} | empty_interval_tree, interval :: interval(), key :: term(), right = empty_interval_tree :: #interval_tree{} | empty_interval_tree }). -define(interval_tree(C, L, I, K, R), #interval_tree{colour = C, left = L, interval = I, key = K, right = R}). -spec(prototype() -> 'empty_interval_tree'). prototype() -> empty_interval_tree. -spec(find(I::term(), #interval_tree{} | 'empty_interval_tree') -> term()). find(_I, empty_interval_tree) -> throw(not_found); find(I, #interval_tree{left = L, interval = {Low, _High}}) when I < Low; (LowInterval =:= half_open andalso I =:= Low) -> find(I, L); find(I, #interval_tree{interval = {_Low, High}, right = R}) when I > High; (HighInterval =:= half_open andalso I =:= High) -> find(I, R); find(I, #interval_tree{interval = {Low, High}, key = K}) when LowInterval =:= half_open, Low < I, HighInterval =:= half_open, I < High -> K; find(I, #interval_tree{interval = {Low, High}, key = K}) when LowInterval =:= half_open, Low < I, HighInterval =:= closed, I =< High -> K; find(I, #interval_tree{interval = {Low, High}, key = K}) when LowInterval =:= closed, Low =< I, HighInterval =:= half_open, I < High -> K; find(I, #interval_tree{interval = {Low, High}, key = K}) when LowInterval =:= closed, Low =< I, HighInterval =:= closed, I =< High -> K; find(_, _) -> throw(not_found). -spec(insert(K::term(), Interval::interval(), T::#interval_tree{} | 'empty_interval_tree') -> #interval_tree{}). insert(K, Interval, empty_interval_tree) -> #interval_tree{key = K, interval = Interval}; insert(K, Interval, T) -> Insert = fun(empty_interval_tree, _Fun) -> #interval_tree{colour = red, interval = Interval, key = K}; (?interval_tree(Colour, L, I, K2, R), Fun) when Interval < I -> balance(Colour, Fun(L, Fun), I, K2, R); (?interval_tree(Colour, L, I, K2, R), Fun) when Interval > I -> balance(Colour, L, I, K2, Fun(R, Fun)); (T2, _Fun) -> T2 end, T3 = Insert(T, Insert), T3#interval_tree{colour = black}. -spec(balance(Colour::colour(), L::#interval_tree{}, I::interval(), K::term(), R::#interval_tree{}) -> #interval_tree{}). balance(black, ?interval_tree(red, ?interval_tree(red, L, I, K, R), I2, K2, R2), I3, K3, R3) -> ?interval_tree(red, ?interval_tree(black, L, I, K, R), I2, K2, ?interval_tree(black, R2, I3, K3, R3)); balance(black, ?interval_tree(red, L, I, K, ?interval_tree(red, L2, I2, K2, R)), I3, K3, R2) -> ?interval_tree(red, ?interval_tree(black, L, I, K, L2), I2, K2, ?interval_tree(black, R, I3, K3, R2)); balance(black, L, I, K, ?interval_tree(red, ?interval_tree(red, L2, I2, K2, R), I3, K3, R2)) -> ?interval_tree(red, ?interval_tree(black, L, I, K, L2), I2, K2, ?interval_tree(black, R, I3, K3, R2)); balance(black, L, I, K, ?interval_tree(red, L2, I2, K2, ?interval_tree(red, L3, I3, K3, R))) -> ?interval_tree(red, ?interval_tree(black, L, I, K, L2), I2, K2, ?interval_tree(black, L3, I3, K3, R)); balance(Colour, L, I, Key, R) -> ?interval_tree(Colour, L, I, Key, R).