%% Author: peo
%% Created: 06.09.2006
%% Description: MOLAP cube data query routines.
-module( cube ).
-export( [prepare/1, agg/2, test/0] ).


% ---------------------------------------------------- prepare/1


prepare( [] ) ->
    [];
prepare( [ Keys | SubKeyLists ] ) ->
    [ lists:sort( Keys ) | prepare( SubKeyLists ) ].
        

% ---------------------------------------------------- agg/2


agg( {}, _ListOfKeyLists ) -> % no data
	0.0;
agg( Value, [] ) -> % terminal value
    %log( {data, Value} ),
	Value;
agg( Cube, [ Keys | SubKeyLists ] ) ->
	agg_dim( Cube, Keys, 1, size(Cube), SubKeyLists, 0.0 ).

agg_dim( _Cube, [], _StartAt, _Len, _SubKeyLists, Sofar ) ->
    %log( {no_keys} ),
	Sofar;
agg_dim( _Cube, _Keys, StartAt, Len, _SubKeyLists, Sofar ) when StartAt > Len ->
    %log( {keys_past_end, StartAt, Len, _Keys} ),
    Sofar;
agg_dim( Cube, [ Key | Keys ], StartAt, Len, SubKeyLists, Sofar ) ->
    %log( {try_key, Key, StartAt, Len} ),
    { ThisKeysResult, StartNextAt } = agg_key( Cube, Key, StartAt, Len, SubKeyLists ), %% recursion for dimensions
    %log( {got_key, Key, ThisKeysResult, StartNextAt} ),
    agg_dim( Cube, Keys, StartNextAt, Len, SubKeyLists, Sofar + ThisKeysResult ). %% tail call for elements
	
agg_key( _Cube, _Key, StartAt, Len, _SubKeyLists ) when StartAt > Len ->
    %log( {key_past_end, Key, StartAt, Len} ),
    { 0.0, StartAt };
agg_key( Cube, Key, StartAt, Len, SubKeyLists ) ->
    TryNext = agg_key_if_match( Cube, Key, StartAt, SubKeyLists ),
    case TryNext of
        nomatch ->
        	IdxOfKeyOrNext = binary_search( Cube, Key, StartAt, Len ),
	    	agg_key_possibly_at( Cube, Key, IdxOfKeyOrNext, Len, SubKeyLists );
        Result ->
            { Result, StartAt + 1 }
    end.

agg_key_possibly_at( _Cube, _Key, At, Len, _SubKeyLists ) when At > Len ->
    %log( {key_find_past_end, Key, At, Len} ),
    { 0.0, At };
agg_key_possibly_at( Cube, Key, At, _Len, SubKeyLists ) ->
    TryAt = agg_key_if_match( Cube, Key, At, SubKeyLists ),
    case TryAt of
        nomatch ->
            { 0.0, At };
        Result ->
            %log( {key_not_found, Key, At} ),
            { Result, At + 1 }
    end.

agg_key_if_match( Cube, Key, At, SubKeyLists ) ->
    { AtKey, SubCube } = element( At, Cube ),
    case AtKey of
        Key ->
            %log( {key_found, Key, At} ),
            agg( SubCube, SubKeyLists );
        _ ->
            nomatch
    end.


binary_search( _Cube, _Key, StartAt, EndAt ) when StartAt >= EndAt ->
    StartAt;
binary_search( Cube, Key, StartAt, EndAt ) ->
	MidAt = (StartAt + EndAt + 1) div 2,
    { MidKey, _ } = element( MidAt, Cube ),
    if
    	MidKey > Key ->
            binary_search( Cube, Key, StartAt, MidAt - 1 );
        true ->
			binary_search( Cube, Key, MidAt, EndAt )
    end.


% ---------------------------------------------------- test/0


test() ->
    put( cube_test, ok ),
    test_binary_search(),
    test_agg(),
    get( cube_test ).

test_agg() ->
    Cube = cube_load:finalize( cube_load:prefilled() ),
    check( 9200.0, agg( Cube, [ [2002, 2003, 2004, 2005], [ch, de, fr], [notebook] ] ), notebooks ),
    check( 8100.0, agg( Cube, [ [2002, 2003], [ch, de, fr], [desktop] ] ), {desktops, 2003} ),
    check( 12100.0, agg( Cube, [ [2003, 2004], [ch, fr], [desktop] ] ), desktops ),
    check( 4000.0, agg( Cube, [ [2004], [fr], [desktop] ] ), {desktops, 2004} ),
    check( 0.0, agg( Cube, [ [2002, 2007], [ch, fr], [desktop] ] ), {2002, 2007} ),
    done.

test_binary_search() ->
    Cube4 = { {2,x}, {4,x}, {6,x}, {8,x} },

    check_search( Cube4, 2, 1, 1 ),
    check_search( Cube4, 2, 2, 1 ),
    check_search( Cube4, 2, 3, 1 ),
    check_search( Cube4, 2, 4, 2 ),
    check_search( Cube4, 2, 5, 2 ),

    check_search( Cube4, 3, 1, 1 ),
    check_search( Cube4, 3, 2, 1 ),
    check_search( Cube4, 3, 3, 1 ),
    check_search( Cube4, 3, 4, 2 ),
    check_search( Cube4, 3, 5, 2 ),
    check_search( Cube4, 3, 6, 3 ),
    check_search( Cube4, 3, 7, 3 ),

    check_search( Cube4, 4, 2, 1 ),
    check_search( Cube4, 4, 4, 2 ),
    check_search( Cube4, 4, 6, 3 ),
    check_search( Cube4, 4, 8, 4 ),
    
    done.

check_search( Cube, Len, Key, At ) ->
    I = binary_search( Cube, Key, 1, Len ),
    check( At, I, {search, Key} ).

check( Expected, Actual, _Message ) when Expected == Actual ->
    ok;
check( Expected, Actual, Message ) ->
    io:format( "TEST FAILED. Expected <~w>, got <~w>. ~w~n", [ Expected, Actual, Message ] ),
    put( cube_test, {failed, Expected, Actual, Message} ),
    failed.

log( Msg ) ->
    % io:format( "> ~w~n", [Msg] ).
    Msg.