public
Last active

  • Download Gist
gistfile1.erl
Erlang
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
%% @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 <a href="http://www.soi.city.ac.uk/~ross/papers/FingerTree.html">Finger Trees</a>
%% as a possible alternative to Red-Black trees for implementing the Interval Tree.
%%
%% @reference <a href="http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=11866">
%% Introduction to Algorithms</a>
%% @reference <a href="http://books.google.co.uk/books?id=SxPzSTcTalAC&dq=Purely+functional+data+structures">
%% Purely functional data structures</a>
%% @reference <a href="http://jamesaimonetti.com/2009/12/01/red-black-trees-in-erlang/">
%% Red-Black Trees in Erlang</a>
 
-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).

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.