gistfile1.erl

%% @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).