1% -*- Mode: Erlang; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2
3% Licensed under the Apache License, Version 2.0 (the "License"); you may not
4% use this file except in compliance with the License. You may obtain a copy of
5% the License at
6%
7%   http://www.apache.org/licenses/LICENSE-2.0
8%
9% Unless required by applicable law or agreed to in writing, software
10% distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
11% WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
12% License for the specific language governing permissions and limitations under
13% the License.
14
15-module(couch_skew).
16
17-export([new/0, size/1, in/3, out/2, min/1]).
18
19-define(null, []).
20
21new() ->
22    ?null.
23
24size(?null) ->
25    0;
26size({Sz, _, _, _}) ->
27    Sz.
28
29in(X, _LessFun, ?null) ->
30    {1, X, ?null, ?null};
31in(X, LessFun, A) ->
32    merge(LessFun, {1, X, ?null, ?null}, A).
33
34out(LessFun, {_Sz, X, A, B}) ->
35    {X, merge(LessFun, A, B)}.
36
37min({_, X, _, _}) ->
38    X.
39
40merge(_LessFun, A, ?null) ->
41    A;
42merge(_LessFun, ?null, B) ->
43    B;
44merge(LessFun, {_, Xa, _, _} = A, {_, Xb, _, _} = B) ->
45    case LessFun(Xa, Xb) of
46    true ->
47        join(LessFun, A, B);
48    false ->
49        join(LessFun, B, A)
50    end.
51
52join(LessFun, {Sz1, X, A, B}, {Sz2, _, _, _} = C) ->
53    {Sz1 + Sz2, X, B, merge(LessFun, A, C)}.
54