1%%
2%% %CopyrightBegin%
3%%
4%% Copyright Ericsson AB 1996-2017. All Rights Reserved.
5%%
6%% Licensed under the Apache License, Version 2.0 (the "License");
7%% you may not use this file except in compliance with the License.
8%% You may obtain a copy of the License at
9%%
10%%     http://www.apache.org/licenses/LICENSE-2.0
11%%
12%% Unless required by applicable law or agreed to in writing, software
13%% distributed under the License is distributed on an "AS IS" BASIS,
14%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15%% See the License for the specific language governing permissions and
16%% limitations under the License.
17%%
18%% %CopyrightEnd%
19%%
20
21-module(orddict).
22
23%% Standard interface.
24-export([new/0,is_key/2,to_list/1,from_list/1,size/1,is_empty/1]).
25-export([fetch/2,find/2,fetch_keys/1,erase/2,take/2]).
26-export([store/3,append/3,append_list/3,update/3,update/4,update_counter/3]).
27-export([fold/3,map/2,filter/2,merge/3]).
28
29-export_type([orddict/0, orddict/2]).
30
31%%---------------------------------------------------------------------------
32
33-type orddict() :: orddict(_, _).
34
35-type orddict(Key, Value) :: [{Key, Value}].
36
37%%---------------------------------------------------------------------------
38
39-spec new() -> orddict().
40
41new() -> [].
42
43-spec is_key(Key, Orddict) -> boolean() when
44      Orddict :: orddict(Key, Value :: term()).
45
46is_key(Key, [{K,_}|_]) when Key < K -> false;
47is_key(Key, [{K,_}|Dict]) when Key > K -> is_key(Key, Dict);
48is_key(_Key, [{_K,_Val}|_]) -> true;		%Key == K
49is_key(_, []) -> false.
50
51-spec to_list(Orddict) -> List when
52      Orddict :: orddict(Key, Value),
53      List :: [{Key, Value}].
54
55to_list(Dict) -> Dict.
56
57-spec from_list(List) -> Orddict when
58      List :: [{Key, Value}],
59      Orddict :: orddict(Key, Value).
60
61from_list([]) -> [];
62from_list([{_,_}]=Pair) -> Pair;
63from_list(Pairs) ->
64    lists:ukeysort(1, reverse_pairs(Pairs, [])).
65
66-spec size(Orddict) -> non_neg_integer() when
67      Orddict :: orddict().
68
69size(D) -> length(D).
70
71-spec is_empty(Orddict) -> boolean() when
72      Orddict :: orddict().
73
74is_empty([]) -> true;
75is_empty([_|_]) -> false.
76
77-spec fetch(Key, Orddict) -> Value when
78      Orddict :: orddict(Key, Value).
79
80fetch(Key, [{K,_}|D]) when Key > K -> fetch(Key, D);
81fetch(Key, [{K,Value}|_]) when Key == K -> Value.
82
83-spec find(Key, Orddict) -> {'ok', Value} | 'error' when
84      Orddict :: orddict(Key, Value).
85
86find(Key, [{K,_}|_]) when Key < K -> error;
87find(Key, [{K,_}|D]) when Key > K -> find(Key, D);
88find(_Key, [{_K,Value}|_]) -> {ok,Value};	%Key == K
89find(_, []) -> error.
90
91-spec fetch_keys(Orddict) -> Keys when
92      Orddict :: orddict(Key, Value :: term()),
93      Keys :: [Key].
94
95fetch_keys([{Key,_}|Dict]) ->
96    [Key|fetch_keys(Dict)];
97fetch_keys([]) -> [].
98
99-spec erase(Key, Orddict1) -> Orddict2 when
100      Orddict1 :: orddict(Key, Value),
101      Orddict2 :: orddict(Key, Value).
102
103erase(Key, [{K,_}=E|Dict]) when Key < K -> [E|Dict];
104erase(Key, [{K,_}=E|Dict]) when Key > K ->
105    [E|erase(Key, Dict)];
106erase(_Key, [{_K,_Val}|Dict]) -> Dict;		%Key == K
107erase(_, []) -> [].
108
109-spec take(Key, Orddict) -> {Value, Orddict1} | error when
110      Orddict :: orddict(Key, Value),
111      Orddict1 :: orddict(Key, Value),
112      Key :: term(),
113      Value :: term().
114
115take(Key, Dict) ->
116    take_1(Key, Dict, []).
117
118take_1(Key, [{K,_}|_], _Acc) when Key < K ->
119    error;
120take_1(Key, [{K,_}=P|D], Acc) when Key > K ->
121    take_1(Key, D, [P|Acc]);
122take_1(_Key, [{_K,Value}|D], Acc) ->
123    {Value,lists:reverse(Acc, D)};
124take_1(_, [], _) -> error.
125
126-spec store(Key, Value, Orddict1) -> Orddict2 when
127      Orddict1 :: orddict(Key, Value),
128      Orddict2 :: orddict(Key, Value).
129
130store(Key, New, [{K,_}|_]=Dict) when Key < K ->
131    [{Key,New}|Dict];
132store(Key, New, [{K,_}=E|Dict]) when Key > K ->
133    [E|store(Key, New, Dict)];
134store(Key, New, [{_K,_Old}|Dict]) ->		%Key == K
135    [{Key,New}|Dict];
136store(Key, New, []) -> [{Key,New}].
137
138-spec append(Key, Value, Orddict1) -> Orddict2 when
139      Orddict1 :: orddict(Key, Value),
140      Orddict2 :: orddict(Key, Value).
141
142append(Key, New, [{K,_}|_]=Dict) when Key < K ->
143    [{Key,[New]}|Dict];
144append(Key, New, [{K,_}=E|Dict]) when Key > K ->
145    [E|append(Key, New, Dict)];
146append(Key, New, [{_K,Old}|Dict]) ->		%Key == K
147    [{Key,Old ++ [New]}|Dict];
148append(Key, New, []) -> [{Key,[New]}].
149
150-spec append_list(Key, ValList, Orddict1) -> Orddict2 when
151      ValList :: [Value],
152      Orddict1 :: orddict(Key, Value),
153      Orddict2 :: orddict(Key, Value).
154
155append_list(Key, NewList, [{K,_}|_]=Dict) when Key < K ->
156    [{Key,NewList}|Dict];
157append_list(Key, NewList, [{K,_}=E|Dict]) when Key > K ->
158    [E|append_list(Key, NewList, Dict)];
159append_list(Key, NewList, [{_K,Old}|Dict]) ->		%Key == K
160    [{Key,Old ++ NewList}|Dict];
161append_list(Key, NewList, []) ->
162    [{Key,NewList}].
163
164-spec update(Key, Fun, Orddict1) -> Orddict2 when
165      Fun :: fun((Value1 :: Value) -> Value2 :: Value),
166      Orddict1 :: orddict(Key, Value),
167      Orddict2 :: orddict(Key, Value).
168
169update(Key, Fun, [{K,_}=E|Dict]) when Key > K ->
170    [E|update(Key, Fun, Dict)];
171update(Key, Fun, [{K,Val}|Dict]) when Key == K ->
172    [{Key,Fun(Val)}|Dict].
173
174-spec update(Key, Fun, Initial, Orddict1) -> Orddict2 when
175      Initial :: Value,
176      Fun :: fun((Value1 :: Value) -> Value2 :: Value),
177      Orddict1 :: orddict(Key, Value),
178      Orddict2 :: orddict(Key, Value).
179
180update(Key, _, Init, [{K,_}|_]=Dict) when Key < K ->
181    [{Key,Init}|Dict];
182update(Key, Fun, Init, [{K,_}=E|Dict]) when Key > K ->
183    [E|update(Key, Fun, Init, Dict)];
184update(Key, Fun, _Init, [{_K,Val}|Dict]) ->		%Key == K
185    [{Key,Fun(Val)}|Dict];
186update(Key, _, Init, []) -> [{Key,Init}].
187
188-spec update_counter(Key, Increment, Orddict1) -> Orddict2 when
189      Orddict1 :: orddict(Key, Value),
190      Orddict2 :: orddict(Key, Value),
191      Increment :: number().
192
193update_counter(Key, Incr, [{K,_}|_]=Dict) when Key < K ->
194    [{Key,Incr}|Dict];
195update_counter(Key, Incr, [{K,_}=E|Dict]) when Key > K ->
196    [E|update_counter(Key, Incr, Dict)];
197update_counter(Key, Incr, [{_K,Val}|Dict]) ->		%Key == K
198    [{Key,Val+Incr}|Dict];
199update_counter(Key, Incr, []) -> [{Key,Incr}].
200
201-spec fold(Fun, Acc0, Orddict) -> Acc1 when
202      Fun :: fun((Key, Value, AccIn) -> AccOut),
203      Orddict :: orddict(Key, Value),
204      Acc0 :: Acc,
205      Acc1 :: Acc,
206      AccIn :: Acc,
207      AccOut :: Acc.
208
209fold(F, Acc, [{Key,Val}|D]) ->
210    fold(F, F(Key, Val, Acc), D);
211fold(F, Acc, []) when is_function(F, 3) -> Acc.
212
213-spec map(Fun, Orddict1) -> Orddict2 when
214      Fun :: fun((Key, Value1) -> Value2),
215      Orddict1 :: orddict(Key, Value1),
216      Orddict2 :: orddict(Key, Value2).
217
218map(F, [{Key,Val}|D]) ->
219    [{Key,F(Key, Val)}|map(F, D)];
220map(F, []) when is_function(F, 2) -> [].
221
222-spec filter(Pred, Orddict1) -> Orddict2 when
223      Pred :: fun((Key, Value) -> boolean()),
224      Orddict1 :: orddict(Key, Value),
225      Orddict2 :: orddict(Key, Value).
226
227filter(F, [{Key,Val}=E|D]) ->
228    case F(Key, Val) of
229	true -> [E|filter(F, D)];
230	false -> filter(F, D)
231    end;
232filter(F, []) when is_function(F, 2) -> [].
233
234-spec merge(Fun, Orddict1, Orddict2) -> Orddict3 when
235      Fun :: fun((Key, Value1, Value2) -> Value),
236      Orddict1 :: orddict(Key, Value1),
237      Orddict2 :: orddict(Key, Value2),
238      Orddict3 :: orddict(Key, Value).
239
240merge(F, [{K1,_}=E1|D1], [{K2,_}=E2|D2]) when K1 < K2 ->
241    [E1|merge(F, D1, [E2|D2])];
242merge(F, [{K1,_}=E1|D1], [{K2,_}=E2|D2]) when K1 > K2 ->
243    [E2|merge(F, [E1|D1], D2)];
244merge(F, [{K1,V1}|D1], [{_K2,V2}|D2]) ->	%K1 == K2
245    [{K1,F(K1, V1, V2)}|merge(F, D1, D2)];
246merge(F, [], D2) when is_function(F, 3) -> D2;
247merge(F, D1, []) when is_function(F, 3) -> D1.
248
249reverse_pairs([{_,_}=H|T], Acc) ->
250    reverse_pairs(T, [H|Acc]);
251reverse_pairs([], Acc) -> Acc.
252