%%
%% %CopyrightBegin%
%%
%% Copyright Ericsson AB 1997-2009. All Rights Reserved.
%%
%% The contents of this file are subject to the Erlang Public License,
%% Version 1.1, (the "License"); you may not use this file except in
%% compliance with the License. You should have received a copy of the
%% Erlang Public License along with this software. If not, it can be
%% retrieved online at http://www.erlang.org/.
%%
%% Software distributed under the License is distributed on an "AS IS"
%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
%% the License for the specific language governing rights and limitations
%% under the License.
%%
%% %CopyrightEnd%
-module(tv_db_sort).
-export([mergesort/3, merge/4, get_compare_value/2]).
%%%*********************************************************************
%%% EXTERNAL FUNCTIONS
%%%*********************************************************************
mergesort(_KeyNo, [X], _ReverseOrder) ->
[X];
mergesort(_KeyNo, [], _ReverseOrder) ->
[];
mergesort(KeyNo, X, ReverseOrder) ->
split(KeyNo, X, [], [], ReverseOrder).
%% If we want reverse order when just merging two lists,
%% each of them has to be in reverse order first!
merge(KeyNo, [{E1, C1} | T1], [{E2, C2} | T2], Reverse) when not Reverse ->
K1 = get_compare_value(KeyNo, E1),
K2 = get_compare_value(KeyNo, E2),
case get_correct_order(K1, E1, K2, E2) of
{1, 2} ->
[{E1, C1} | merge(KeyNo, T1, [{E2, C2} | T2], Reverse)];
{2, 1} ->
[{E2, C2} | merge(KeyNo, [{E1, C1} | T1], T2, Reverse)]
end;
merge(KeyNo, [{E1, C1} | T1], [{E2, C2} | T2], Reverse) ->
K1 = get_compare_value(KeyNo, E1),
K2 = get_compare_value(KeyNo, E2),
case get_correct_order(K1, E1, K2, E2) of
{1, 2} ->
[{E2, C2} | merge(KeyNo, [{E1, C1} | T1], T2, Reverse)];
{2, 1} ->
[{E1, C1} | merge(KeyNo, T1, [{E2, C2} | T2], Reverse)]
end;
merge(_KeyNo, [], L2, _Reverse) -> % L2 may be the empty list also!
L2;
merge(_KeyNo, L1, [], _Reverse) -> % L1 may be the empty list also!
L1.
get_compare_value(KeyNo, E) when is_tuple(E) ->
case catch element(KeyNo, E) of
{'EXIT', {badarg, {?MODULE, get_compare_value, [KeyNo, E]}}} ->
short_tuple;
V ->
{tuple, V}
end;
get_compare_value(_KeyNo, _E) ->
no_tuple.
%%%********************************************************************
%%% INTERNAL FUNCTIONS
%%%********************************************************************
split(KeyNo, [A,B|T], X, Y, Reverse) ->
split(KeyNo, T, [A|X], [B|Y], Reverse);
split(KeyNo, [H], X, Y, Reverse) ->
split(KeyNo, [], [H|X], Y, Reverse);
split(KeyNo, [], X, Y, Reverse) ->
merge(KeyNo,
mergesort(KeyNo, X, Reverse),
mergesort(KeyNo, Y, Reverse),
Reverse).
get_correct_order({tuple, V1}, _E1, {tuple, V2}, _E2) when V1 < V2 ->
{1, 2};
get_correct_order({tuple, _V1}, _E1, {tuple, _V2}, _E2) ->
{2, 1};
get_correct_order(short_tuple, _E1, {tuple, _V2}, _E2) ->
{1, 2};
get_correct_order({tuple, _V1}, _E1, short_tuple, _E2) ->
{2, 1};
get_correct_order(short_tuple, E1, short_tuple, E2) when E1 < E2 ->
{1, 2};
get_correct_order(short_tuple, _E1, short_tuple, _E2) ->
{2, 1};
get_correct_order(no_tuple, E1, no_tuple, E2) when E1 < E2 ->
{1, 2};
get_correct_order(no_tuple, _E1, no_tuple, _E2) ->
{2, 1};
get_correct_order(_Anything, _E1, no_tuple, _E2) -> % Tuples first, then other
{1, 2}; % terms in correct order!
get_correct_order(no_tuple, _E1, _Anything, _E2) ->
{2, 1}.
