-module(numidx).

-export([add/2, lookup/2, range/2, delete/2]).

-record(node, {
    key = nil,
    value = [],
    lt = nil,
    gt = nil
}).

% Examples:
%Ni1 = numidx:add(nil, {"foobar1", 1}).
%Ni2 = numidx:add(Ni1, {"foobar2", 5}).
%Ni3 = numidx:add(Ni2, {"foobar3", 8}).
%Ni4 = numidx:add(Ni3, {"foobar4", 10}).
%numidx:lookup(Ni4, {3,9}).
%Ni5 = numidx:delete(Ni4, "foobar3").
%Ni6 = numidx:delete(Ni4, "foobar4").
%Ni7 = numidx:delete(Ni6, "foobar1").
%Ni8 = numidx:delete(Ni7, "foobar2").
%Ni9 = numidx:delete(Ni8, "foobar3").

%Ni1 = numidx:add(nil, {"foobar2", 5}).
%Ni2 = numidx:add(Ni1, {"foobar1", 1}).
%Ni3 = numidx:add(Ni2, {"foobar3", 8}).
%Ni4 = numidx:add(Ni3, {"foobar4", 10}).
%Ni5 = numidx:add(Ni4, {"foobar4", 9}).
%Ni6 = numidx:add(Ni5, {"foobar7", 7}).

%Ni1 = numidx:add(nil, {"foobar2", 5}). Ni2 = numidx:add(Ni1, {"foobar1", 1}). Ni3 = numidx:add(Ni2, {"foobar3", 8}). Ni4 = numidx:add(Ni3, {"foobar4", 10}). Ni5 = numidx:add(Ni4, {"foobar4", 9}). Ni6 = numidx:add(Ni5, {"foobar7", 7}).

%Ni7 = numidx:add(Ni6, {"foobar8", 8}).
%{node,5,
%      ["foobar2"],
%      {node,1,["foobar1"],nil,nil},
%      {node,8,
%            ["foobar3","foobar8"],
%            {node,7,["foobar7"],nil,nil},
%            {node,10,["foobar4"],{node,9,["foobar4"],nil,nil},nil}}}

%Ni10 = numidx:lookup(Ni7, 3).
%Ni11 = numidx:lookup(Ni7, 1).
%Ni12 = numidx:lookup(Ni7, 8).
%Ni13 = numidx:lookup(Ni7, 10).
%Ni14 = numidx:lookup(Ni7, 9).
%10> Ni10 = numidx:lookup(Ni7, 3).
%[]
%11> Ni11 = numidx:lookup(Ni7, 1).
%["foobar1"]
%12> Ni12 = numidx:lookup(Ni7, 8).
%["foobar3","foobar8"]
%13> Ni13 = numidx:lookup(Ni7, 10).
%["foobar4"]
%14> Ni14 = numidx:lookup(Ni7, 9).
%["foobar4"]

%31> Ni21 = numidx:delete(Ni7, {"foobar7", 7}).  
%{node,5,
%      ["foobar2"],
%      {node,1,["foobar1"],nil,nil},
%      {node,8,
%            ["foobar3","foobar8"],
%            nil,
%            {node,10,["foobar4"],{node,9,["foobar4"],nil,nil},nil}}}
%32> Ni22 = numidx:delete(Ni21, {"foobar3", 8}).
%{node,5,
%      ["foobar2"],
%      {node,1,["foobar1"],nil,nil},
%      {node,8,
%            ["foobar8"],
%            nil,
%            {node,10,["foobar4"],{node,9,["foobar4"],nil,nil},nil}}}
%33> Ni23 = numidx:delete(Ni22, {"foobar8", 8}).
%{node,5,
%      ["foobar2"],
%      {node,1,["foobar1"],nil,nil},
%      {node,10,["foobar4"],{node,9,["foobar4"],nil,nil},nil}}
%44> Ni25 = numidx:delete(Ni23, {"foobar4", 8}).
%{node,5,
%      ["foobar2"],
%      {node,1,["foobar1"],nil,nil},
%      {node,10,["foobar4"],{node,9,["foobar4"],nil,nil},nil}}
%45> Ni23.                                                              
%{node,5,
%      ["foobar2"],
%      {node,1,["foobar1"],nil,nil},
%      {node,10,["foobar4"],{node,9,["foobar4"],nil,nil},nil}}
%46> Ni26 = numidx:delete(Ni23, {"foobar4", 9}).
%{node,5,
%      ["foobar2"],
%      {node,1,["foobar1"],nil,nil},
%      {node,10,["foobar4"],nil,nil}}
%47> Ni27 = numidx:delete(Ni26, {"foobar2", 5}).  
%{node,1,["foobar1"],nil,{node,10,["foobar4"],nil,nil}}
%48> Ni28 = numidx:delete(Ni27, {"foobar4", 10}).  
%{node,1,["foobar1"],nil,nil}
%49> Ni29 = numidx:delete(Ni28, {"foobar1", 1}). 
%nil

% entry point
add({Fd, nil}, NewItem) ->
    add(Fd, nil, NewItem);
add({Fd, Pos}, NewItem) ->
    {ok, Node} = couch_file:pread_term(Fd, Pos),
    add(Fd, Node, NewItem).
    
add(Fd, nil, {NewDocId, NewNumidx}) ->
    couch_file:append_term(Fd, #node{key=NewNumidx, value=[NewDocId]});
add(Fd, #node{key=Numidx, value=Value}=Node, {NewDocId, Numidx}) ->
    couch_file:append_term(Fd, Node#node{value=Value ++ [NewDocId]});
add(Fd, #node{key=Numidx}=Node, {_NewDocId, NewNumidx}=NewItem)
        when NewNumidx < Numidx ->
    Lt = data_at_pos(Fd, Node#node.lt),
    {ok, NewLtPos} = add(Fd, Lt, NewItem),
    couch_file:append_term(Fd, Node#node{lt=NewLtPos});
add(Fd, #node{key=Numidx}=Node, {_NewDocId, NewNumidx}=NewItem)
        when NewNumidx > Numidx ->
    Gt = data_at_pos(Fd, Node#node.gt),
    {ok, NewGtPos} = add(Fd, Gt, NewItem),
    couch_file:append_term(Fd, Node#node{gt=NewGtPos}).

data_at_pos(_Fd, nil) ->
    nil;
data_at_pos(Fd, Pos) ->
   {ok, Data} = couch_file:pread_term(Fd, Pos),
   Data.


lookup({Fd, nil}, SearchKey) ->
    lookup(Fd, nil, SearchKey);
lookup({Fd, Pos}, SearchKey) ->
    {ok, Node} = couch_file:pread_term(Fd, Pos),
    lookup(Fd, Node, SearchKey).

lookup(_Fd, nil, _SearchKey) ->
    [];
lookup(_Fd, #node{key=Key, value=Value}, Key) ->
    Value;
lookup(Fd, #node{key=Key}=Node, SearchKey) when SearchKey < Key ->
    Lt = data_at_pos(Fd, Node#node.lt),
    lookup(Fd, Lt, SearchKey);
lookup(Fd, #node{key=Key}=Node, SearchKey) when SearchKey > Key ->
    Gt = data_at_pos(Fd, Node#node.gt),
    lookup(Fd, Gt, SearchKey).


range({_Fd, nil}, _Range) ->
    [];
range({Fd, Pos}, {From, To}) ->
    lists:foldl(fun(Key, Result) ->
        [lookup({Fd, Pos}, Key)|Result]
    end, [], lists:seq(From, To)).


delete(nil, _) ->
    nil;
% Node matches and contains more than one value
delete(#node{key=Numidx, value=Value}=Node, {DelDocId, Numidx})
        when length(Value) > 1 ->
    Node#node{value=lists:delete(DelDocId, Value)};
% Node matches and has no child nodes
delete(#node{key=Numidx, lt=nil, gt=nil}, {_DelDocId, Numidx}) ->
    nil;
% Node matches and has one child (lt)
delete(#node{key=Numidx, lt=Lt, gt=nil}, {_DelDocId, Numidx}) ->
    Lt;
% Node matches and has one child (gt)
delete(#node{key=Numidx, lt=nil, gt=Gt}, {_DelDocId, Numidx}) ->
    Gt;
% Node matches and has both child nodes
delete(#node{key=Numidx, lt=Lt, gt=Gt}, {_DelDocId, Numidx}) ->
    % Find greatest node an rebuild tree (thanks Concurrent programming in
    % Erlang Part I pp. 61)
    NewNode = deletesp(Lt),
    NewNode#node{gt=Gt};
% Node doesn't match, move on
delete(#node{key=Numidx}=Node, {_DelDocId, DelNumidx}=DelItem)
        when DelNumidx < Numidx ->
    DelLt = delete(Node#node.lt, DelItem),
    Node#node{lt=DelLt};
% Node doesn't match, move on
delete(#node{key=Numidx}=Node, {_DelDocId, DelNumidx}=DelItem)
        when DelNumidx > Numidx ->
    DelGt = delete(Node#node.gt, DelItem),
    Node#node{gt=DelGt}.

% Abusing #node, always write the result into #node.lt
deletesp(#node{gt=nil}=Node) ->
    Node;
deletesp(#node{gt=Gt}=Node) ->
    NewNode = deletesp(Gt),
    NewNode#node{lt=Node#node{gt=NewNode#node.lt}}.