1/* Part of SWI-Prolog 2 3 Author: Jan Wielemaker 4 E-mail: J.Wielemaker@vu.nl 5 WWW: http://www.swi-prolog.org 6 Copyright (c) 2015, VU University Amsterdam 7 All rights reserved. 8 9 Redistribution and use in source and binary forms, with or without 10 modification, are permitted provided that the following conditions 11 are met: 12 13 1. Redistributions of source code must retain the above copyright 14 notice, this list of conditions and the following disclaimer. 15 16 2. Redistributions in binary form must reproduce the above copyright 17 notice, this list of conditions and the following disclaimer in 18 the documentation and/or other materials provided with the 19 distribution. 20 21 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 24 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 25 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 26 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 27 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 28 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 29 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 31 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 32 POSSIBILITY OF SUCH DAMAGE. 33*/ 34 35:- module(dicts, 36 [ dicts_same_tag/2, % +List, -Tag 37 dict_keys/2, % +Dict, -Keys 38 dicts_same_keys/2, % +DictList, -Keys 39 dicts_to_same_keys/3, % +DictsIn, :OnEmpty, -DictsOut 40 dict_fill/4, % +Value, +Key, +Dict, -Value 41 dict_no_fill/3, % +Key, +Dict, -Value 42 dicts_join/3, % +Key, +DictsIn, -Dicts 43 dicts_join/4, % +Key, +Dicts1, +Dicts2, -Dicts 44 dicts_slice/3, % +Keys, +DictsIn, -DictsOut 45 dicts_to_compounds/4 % ?Dicts, +Keys, :OnEmpty, ?Compounds 46 ]). 47:- use_module(library(apply)). 48:- use_module(library(pairs)). 49:- use_module(library(lists)). 50:- use_module(library(ordsets)). 51 52:- meta_predicate 53 dicts_to_same_keys(,,), 54 dicts_to_compounds(,,,). 55 56/** <module> Dict utilities 57 58This library defines utilities that operate on lists of dicts, notably 59to make lists of dicts consistent by adding missing keys, converting 60between lists of compounds and lists of dicts, joining and slicing lists 61of dicts. 62*/ 63 64%! dicts_same_tag(+List, -Tag) is semidet. 65% 66% True when List is a list of dicts that all have the tag Tag. 67 68dicts_same_tag(List, Tag) :- 69 maplist(keys_tag(Tag), List). 70 71keys_tag(Tag, Dict) :- 72 is_dict(Dict, Tag). 73 74%! dict_keys(+Dict, -Keys) is det. 75% 76% True when Keys is an ordered set of the keys appearing in Dict. 77 78dict_keys(Dict, Keys) :- 79 dict_pairs(Dict, _Tag, Pairs), 80 pairs_keys(Pairs, Keys). 81 82 83%! dicts_same_keys(+List, -Keys) is semidet. 84% 85% True if List is a list of dicts that all have the same keys and 86% Keys is an ordered set of these keys. 87 88dicts_same_keys(List, Keys) :- 89 maplist(keys_dict(Keys), List). 90 91keys_dict(Keys, Dict) :- 92 dict_keys(Dict, Keys). 93 94%! dicts_to_same_keys(+DictsIn, :OnEmpty, -DictsOut) 95% 96% DictsOut is a copy of DictsIn, where each dict contains all keys 97% appearing in all dicts of DictsIn. Values for keys that are 98% added to a dict are produced by calling OnEmpty as below. The 99% predicate dict_fill/4 provides an implementation that fills all 100% new cells with a predefined value. 101% 102% == 103% call(:OnEmpty, +Key, +Dict, -Value) 104% == 105 106dicts_to_same_keys(Dicts, _, Table) :- 107 dicts_same_keys(Dicts, _), 108 !, 109 Table = Dicts. 110dicts_to_same_keys(Dicts, OnEmpty, Table) :- 111 maplist(dict_keys, Dicts, KeysList), 112 append(KeysList, Keys0), 113 sort(Keys0, Keys), 114 maplist(extend_dict(Keys, OnEmpty), Dicts, Table). 115 116extend_dict(Keys, OnEmpty, Dict0, Dict) :- 117 dict_pairs(Dict0, Tag, Pairs), 118 pairs_keys(Pairs, DictKeys), 119 ord_subtract(Keys, DictKeys, Missing), 120 ( Missing == [] 121 -> Dict = Dict0 122 ; maplist(key_value_pair(Dict0, OnEmpty), Missing, NewPairs), 123 append(NewPairs, Pairs, AllPairs), 124 dict_pairs(Dict, Tag, AllPairs) 125 ). 126 127key_value_pair(Dict, OnEmpty, Key, Key-Value) :- 128 call(OnEmpty, Key, Dict, Value). 129 130%! dict_fill(+ValueIn, +Key, +Dict, -Value) is det. 131% 132% Implementation for the dicts_to_same_keys/3 `OnEmpty` closure 133% that fills new cells with a copy of ValueIn. Note that 134% copy_term/2 does not really copy ground terms. Below are two 135% examples. Note that when filling empty cells with a variable, 136% each empty cell is bound to a new variable. 137% 138% == 139% ?- dicts_to_same_keys([r{x:1}, r{y:2}], dict_fill(null), L). 140% L = [r{x:1, y:null}, r{x:null, y:2}]. 141% ?- dicts_to_same_keys([r{x:1}, r{y:2}], dict_fill(_), L). 142% L = [r{x:1, y:_G2005}, r{x:_G2036, y:2}]. 143% == 144% 145% Use dict_no_fill/3 to raise an error if a dict is missing a key. 146 147dict_fill(ValueIn, _, _, Value) :- 148 copy_term(ValueIn, Value). 149 150%! dict_no_fill is det. 151% 152% Can be used instead of dict_fill/4 to raise an exception if some 153% dict is missing a key. 154 155dict_no_fill(Key, Dict, Value) :- 156 Value = Dict.Key. 157 158%! dicts_join(+Key, +DictsIn, -Dicts) is semidet. 159% 160% Join dicts in Dicts that have the same value for Key, provided 161% they do not have conflicting values on other keys. For example: 162% 163% == 164% ?- dicts_join(x, [r{x:1, y:2}, r{x:1, z:3}, r{x:2,y:4}], L). 165% L = [r{x:1, y:2, z:3}, r{x:2, y:4}]. 166% == 167% 168% @error existence_error(key, Key, Dict) if a dict in Dicts1 169% or Dicts2 does not contain Key. 170 171dicts_join(Join, Dicts0, Dicts) :- 172 sort(Join, @=<, Dicts0, Dicts1), 173 join(Dicts1, Join, Dicts). 174 175join([], _, []) :- !. 176join([H0|T0], Key, [H|T]) :- 177 !, 178 get_dict(Key, H0, V0), 179 join_same(T0, Key, V0, H0, H, T1), 180 join(T1, Key, T). 181join([One], _, [One]) :- !. 182 183join_same([H|T0], Key, V0, D0, D, T) :- 184 get_dict(Key, H, V), 185 V == V0, 186 !, 187 D0 >:< H, 188 put_dict(H, D0, D1), 189 join_same(T0, Key, V0, D1, D, T). 190join_same(DL, _, _, D, D, DL). 191 192%! dicts_join(+Key, +Dicts1, +Dicts2, -Dicts) is semidet. 193% 194% Join two lists of dicts (Dicts1 and Dicts2) on Key. Each pair 195% D1-D2 from Dicts1 and Dicts2 that have the same (==) value for 196% Key creates a new dict D with the union of the keys from D1 and 197% D2, provided D1 and D2 to not have conflicting values for some 198% key. For example: 199% 200% == 201% ?- DL1 = [r{x:1,y:1},r{x:2,y:4}], 202% DL2 = [r{x:1,z:2},r{x:3,z:4}], 203% dicts_join(x, DL1, DL2, DL). 204% DL = [r{x:1, y:1, z:2}, r{x:2, y:4}, r{x:3, z:4}]. 205% == 206% 207% @error existence_error(key, Key, Dict) if a dict in Dicts1 208% or Dicts2 does not contain Key. 209 210dicts_join(Join, Dicts1, Dicts2, Dicts) :- 211 sort(Join, @=<, Dicts1, Dicts11), 212 sort(Join, @=<, Dicts2, Dicts21), 213 join(Dicts11, Dicts21, Join, Dicts). 214 215join([], [], _, []) :- !. 216join([D1|T1], [D2|T2], Join, [DNew|MoreDicts]) :- 217 !, 218 get_dict(Join, D1, K1), 219 get_dict(Join, D2, K2), 220 compare(Diff, K1, K2), 221 ( Diff == (=) 222 -> D1 >:< D2, 223 put_dict(D1, D2, DNew), 224 join(T1, T2, Join, MoreDicts) 225 ; Diff == (<) 226 -> DNew = D1, 227 join(T1, [D2|T2], Join, MoreDicts) 228 ; DNew = D2, 229 join([D1|T1], T2, Join, MoreDicts) 230 ). 231join([], Dicts, _, Dicts) :- !. 232join(Dicts, [], _, Dicts). 233 234 235%! dicts_slice(+Keys, +DictsIn, -DictsOut) is det. 236% 237% DictsOut is a list of Dicts only containing values for Keys. 238 239dicts_slice(Keys, DictsIn, DictsOut) :- 240 sort(Keys, SortedKeys), 241 maplist(dict_slice(SortedKeys), DictsIn, DictsOut). 242 243dict_slice(Keys, DictIn, DictOut) :- 244 dict_pairs(DictIn, Tag, PairsIn), 245 slice_pairs(Keys, PairsIn, PairsOut), 246 dict_pairs(DictOut, Tag, PairsOut). 247 248slice_pairs([], _, []) :- !. 249slice_pairs(_, [], []) :- !. 250slice_pairs([H|T0], [P|PL], Pairs) :- 251 P = K-_, 252 compare(D, H, K), 253 ( D == (=) 254 -> Pairs = [P|More], 255 slice_pairs(T0, PL, More) 256 ; D == (<) 257 -> slice_pairs(T0, [P|PL], Pairs) 258 ; slice_pairs([H|T0], PL, Pairs) 259 ). 260 261%! dicts_to_compounds(?Dicts, +Keys, :OnEmpty, ?Compounds) is semidet. 262% 263% True when Dicts and Compounds are lists of the same length and 264% each element of Compounds is a compound term whose arguments 265% represent the values associated with the corresponding keys in 266% Keys. When converting from dict to row, OnEmpty is used to 267% compute missing values. The functor for the compound is the same 268% as the tag of the pair. When converting from dict to row and the 269% dict has no tag, the functor `row` is used. For example: 270% 271% == 272% ?- Dicts = [_{x:1}, _{x:2, y:3}], 273% dicts_to_compounds(Dicts, [x], dict_fill(null), Compounds). 274% Compounds = [row(1), row(2)]. 275% ?- Dicts = [_{x:1}, _{x:2, y:3}], 276% dicts_to_compounds(Dicts, [x,y], dict_fill(null), Compounds). 277% Compounds = [row(1, null), row(2, 3)]. 278% ?- Compounds = [point(1,1), point(2,4)], 279% dicts_to_compounds(Dicts, [x,y], dict_fill(null), Compounds). 280% Dicts = [point{x:1, y:1}, point{x:2, y:4}]. 281% == 282% 283% When converting from Dicts to Compounds Keys may be computed by 284% dicts_same_keys/2. 285 286dicts_to_compounds(Dicts, Keys, OnEmpty, Compounds) :- 287 maplist(dict_to_compound(Keys, OnEmpty), Dicts, Compounds). 288 289dict_to_compound(Keys, OnEmpty, Dict, Row) :- 290 is_dict(Dict, Tag), 291 !, 292 default_tag(Tag, row), 293 maplist(key_value(Dict, OnEmpty), Keys, Values), 294 compound_name_arguments(Row, Tag, Values). 295dict_to_compound(Keys, _, Dict, Row) :- 296 compound(Row), 297 compound_name_arguments(Row, Tag, Values), 298 pairs_keys_values(Pairs, Keys, Values), 299 dict_pairs(Dict, Tag, Pairs). 300 301default_tag(Tag, Tag) :- !. 302default_tag(_, _). 303 304key_value(Dict, OnEmpty, Key, Value) :- 305 ( get_dict(Key, Dict, Value0) 306 -> Value = Value0 307 ; call(OnEmpty, Key, Dict, Value) 308 ).