OKlibrary  0.2.1.6
HashMaps.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 4.5.2008 (Guangzhou) */
00002 /* Copyright 2008, 2009, 2010, 2012 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00022 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")$
00023 
00024 
00025 /* ************************
00026    * Set-theoretical maps *
00027    ************************
00028 */
00029 
00030 /* A "set-map" ("sm") is a set of pairs [x,y], such that x is unique.
00031    An "ordered set-map" ("osm") is a list of pairs without repetitions
00032    whose setification is a set-map.
00033 */
00034 
00035 /* Checks whether M is a set-map. */
00036 /* RENAME: sm_p */
00037 setmapp(M) := if not setp(M) then false else block([is_setm : true],
00038   for p in M while is_setm do
00039     if not listp(p) or length(p) # 2 then is_setm : false,
00040   return(is_setm and length(map(first,M)) = length(M)))$
00041 osm_p(M) := if not listp(M) then false else
00042  block([l : length(M)],
00043   if length(unique(M)) # l then return(false),
00044   block([is_osm : true],
00045     for p in M while is_osm do
00046       if not listp(p) or length(p) # 2 then is_osm : false,
00047     return(is_osm and length(unique(map(first,M))) = l)))$
00048 
00049 /* Set a value for a set-map. */
00050 /* RENAME: set_sm */
00051 define_set_map(M,x,y) := block([found : false],
00052  for p in M unless found do
00053    if p[1] = x then (
00054      found : true,
00055      if p[2] # y then M : adjoin([x,y],disjoin(p,M))),
00056  if found then return(M) else return(adjoin([x,y],M)))$
00057 
00058 /* Compute the value for an argument in the domain of a set-map.
00059    If x is not in the domain, then "done" is returned. */
00060 /* RENAME: ev_sm */
00061 evaluate_set_map(M,x) := for p in M do if p[1] = x then return(p[2])$
00062 /* Use a default value if undefined. */
00063 /* RENAME: ev_sm_d */
00064 evaluate_set_map_d(M,x,y) := block([found : false, val],
00065  for p in M unless found do if p[1] = x then (found : true, val : p[2]),
00066  if found then val else y)$
00067 
00068 /* Transforming a list of values into a set-map (taking the indices
00069    of the list as arguments):
00070 */
00071 l2sm(L) := setify(map("[",create_list(i,i,1,length(L)),L))$
00072 l2osm(L) := map("[",create_list(i,i,1,length(L)),L)$
00073 /* More generally, using list LA as list of arguments: */
00074 ll2sm(LA,L) := setify(map("[",LA,L))$
00075 ll2osm(LA,L) := map("[",LA,L)$
00076 
00077 /* Now taking the values of the list as arguments, mapped to their
00078    indices:
00079 */
00080 l2osm_inv(L) := map("[", L, create_list(i,i,1,length(L)))$
00081 
00082 /* The set of all bijections from set A to set B as set-maps: */
00083 allbij_sm(A,B) := if length(A) # length(B) then {} else
00084  block([LA : listify(A)],
00085   map(lambda([p],setify(map("[",LA,p))),permutations(B)))$
00086 allperm_sm(A) := allbij_sm(A,A);
00087 /* The list of all injections from set A to set B as set-maps
00088    (with the same order as given by kpermutations): */
00089 allinj_sm(A,B) := block(
00090  [LA : listify(A)],
00091   map(
00092     lambda([L], ll2sm(LA,L)),
00093     kpermutations(B,length(A))))$
00094 
00095 
00096 /* *********************************
00097    * Hash maps as provided by Lisp *
00098    *********************************
00099 */
00100 
00101 /* ATTENTION: The following two functions are only for
00102    compatability reasons - in the OKlibrary the functions
00103    below are to be used! (Which convert hash keys into
00104    strings.)
00105 */
00106 
00107 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/HashMaps.lisp")$
00108 
00109 /* Given a map as a set-map, create a hash-map. */
00110 /* The assignments are entered into the hash-map according to their
00111    order in the set-map (i.e., according to orderlessp).
00112    The order of the hash-map is the reverse order of the order in which
00113    the elements were entered. */
00114 create_hash_map(S) := block([h : hash_table_okl()],
00115   for p in S do set_hash_okl(p[1],h,p[2]), return(h))$
00116 
00117 /* Given a hash-map, create the corresponding set-theoretical map
00118    (as a set of pairs). */
00119 create_set_map(h) :=
00120  setify(map(args,hash_table_data_okl(h)))$
00121 
00122 /* The IMPROVED hash-map facilities */
00123 
00124 /* The hash-map data type is given by the 7 functions
00125  - set_hm
00126  - ev_hm, ev_hm_d
00127  - del_hm
00128  - sm2hm, osm2hm
00129  - hm2osm, hm2sm
00130  - compose_hm_sm
00131  - lambda_hm.
00132 */
00133 
00134 /* Set a value for the hash map: */
00135 set_hm(h,x,y) := set_hash_okl(sconcat(x),h,y)$
00136 /* Compute a value, returning false if undefined: */
00137 ev_hm(h,x) := get_hash_okl(sconcat(x),h)$
00138 /* Compute a value, returning the provided value if undefined: */
00139 ev_hm_d(h,x,y) := get_hash_okl(sconcat(x),h,y)$
00140 /* Delete a key from a hash map. Returns false if x is not in h, otherwise
00141    return true. */
00142 del_hm(h,x) := del_hash_okl(sconcat(x),h)$
00143 
00144 /* Converting set-maps to hash-maps, and hash-maps to set-maps. */
00145 /* The order of entries in the hash-map is (only) implementation-defined. */
00146 sm2hm(M) := block([h : hash_table_okl()],
00147   for p in M do set_hm(h,p[1],p[2]), return(h))$
00148 osm2hm(M) := sm2hm(M)$
00149 /* The inverse conversions: */
00150 hm2osm(h) :=
00151  map(lambda([a],[eval_string(first(a)),second(a)]),hash_table_data_okl(h))$
00152 hm2sm(h) :=
00153  setify(hm2osm(h))$
00154 
00155 /* Extending a hash-map by a set-map, overwriting old settings. */
00156 compose_hm_sm(h,M) := (for p in M do set_hm(h,p[1],p[2]), h)$
00157 
00158 /* Converting a hash-map into a lambda-term.
00159    Attention: the lambda-term is a *reference* to h! */
00160 lambda_hm(h) := buildq([h],lambda([x],ev_hm(h,x)))$
00161 
00162 
00163 /* ***********************
00164    * Arrays as hash-maps *
00165    ***********************
00166 */
00167 
00168 /* Similar functions for arrays (like hash-maps, but fixed lenghts,
00169    and only integer indices, starting with 1). */
00170 
00171 /* "okl-arrays" are 1-based, and at index 0 they contain their length. */
00172 
00173 /* The equivalents of the built-in functions: */
00174 
00175 okl_make_array(type,dim) := block([a : make_array(type,dim+1)],
00176   a[0] : dim, a)$
00177 /* Remark: the possibilities for "type" are
00178   fixnum, flonum, any.
00179 */
00180 okl_listarray(a) := rest(listarray(a))$
00181 /* RENAME: ary2l */
00182 array2l(a) := okl_listarray(a)$
00183 ary2l(a) := okl_listarray(a)$
00184 /* Here L must be a list and a an okl-array: */
00185 okl_fillarray_l(a,L) := fillarray(a,cons(a[0],L))$
00186 
00187 /* Creating okl-arrays from lists: */
00188 
00189 /* RENAME: l2ary */
00190 l2array(L) := okl_fillarray_l(okl_make_array(any,length(L)),L)$
00191 l2ary(L) := l2array(L)$
00192 /* If the list contains only integers, and the array shall be
00193    an array of integers: */
00194 /* RENAME: il2ary */
00195 il2array(L) := okl_fillarray_l(okl_make_array(fixnum,length(L)),L)$
00196 il2ary(L) := il2array(L)$
00197 /* If the list contains only floating-point numbers, and the array shall be
00198    an array of floating-point numbers: */
00199 /* RENAME: fl2ary */
00200 fl2array(L) := okl_fillarray_l(okl_make_array(flonum,length(L)),L)$
00201 
00202 
00203 /* Creating okl-arrays from set-maps: */
00204 
00205 /* RENAME: sm2ary */
00206 sm2array(M) := sm2array_lt(M,length(M),any)$
00207 sm2ary(M) := sm2array(M)$
00208 /* RENAME: osm2ary */
00209 osm2array(M) := sm2array(M)$
00210 osm2ary(M) := osm2array(M)$
00211 /* If the type of the indices is known, and the length of the array
00212    is also to be specified: */
00213 /* RENAME: sm2ary_lt */
00214 sm2array_lt(M,l,type) := block([a : okl_make_array(type,l)],
00215   for p in M do a[p[1]] : p[2], return(a))$
00216 sm2ary_lt(M,l,type) := sm2array_lt(M,l,type)$
00217 /* RENAME: osm2ary_lt */
00218 osm2array_lt(M,l,type) := sm2array_lt(M,l,type)$
00219 osm2ary_lt(M,l,type) := osm2array_lt(M,l,type)$
00220 
00221 /* Interpreting a value "false" as "not assigned": */
00222 /* RENAME: ary2osm */
00223 array2osm(a) := array2osm_v(a,false)$
00224 /* Specifying the value which signals "not assigned": */
00225 /* RENAME: ary2osm */
00226 array2osm_v(a,v) := block([L : okl_listarray(a)],
00227   delete(v,create_list(if L[i]=false then false else [i,L[i]],i,1,length(L))))$
00228 
00229 /* Creating lambda-maps with "built-in okl-array": */
00230 
00231 /* Converting an array or an array-function into a lambda-term: */
00232 /* RENAME: ary2lmp2 */
00233 lambda_array(a) := buildq([a],lambda([x],a[x]))$
00234 /* Extracting the array from a lambda-term created by lambda_array: */
00235 /* RENAME: lmpa2ary */
00236 extract_array(h) := part(h,2,0);
00237 /* RENAME: lmpa2l */
00238 extract_arraylist(h) := okl_listarray(extract_array(h))$
00239 
00240 
00241 /* *********************
00242    * Frequency counter *
00243    *********************
00244 */
00245 
00246 /* Given a list L of objects for which we want to count the number
00247    of occurrences, and then get the list of pairs [x,count],
00248    sorted by x, where the x are the different objects:
00249     - first create an empty hash-map h : sm2hm({})
00250     - then call enter_new_occurrence(h,x) for each occurrence,
00251     - and finally get the result via get_distribution(h).
00252 */
00253 enter_new_occurrence(h,x) :=
00254   set_hm(h,x,ev_hm_d(h,x,0)+1)$
00255 /* Allowing the addition of multiple occurrences at once, taking
00256    a pair with x and n the number of occurrences of x, and adding n
00257    to the number of occurrences in the map. */
00258 enter_new_occurrences(h,P) :=
00259   set_hm(h,P[1],ev_hm_d(h,P[1],0)+P[2])$
00260 get_distribution(h) := listify(hm2sm(h))$
00261 
00262 /* Canning the above process in a function, that is, compute the
00263    list of pairs [x,count]:
00264 */
00265 list_distribution(L) := block([h : sm2hm({})],
00266   for x in L do enter_new_occurrence(h,x),
00267   get_distribution(h))$
00268 
00269 /* Given a list of pairs of the form [x,count], returns a list of pairs of the
00270    form [x, sumcount] for every unique such x in the input, where sumcount is
00271    the sum of counts over all pairs with x as the first element, and no two
00272    pairs in the result have the same first element. */
00273 multi_list_distribution2list_distribution(L) := block([h : sm2hm({})],
00274   for P in L do enter_new_occurrences(h,P),
00275   get_distribution(h))$
00276 /* As an example we have:
00277      multi_list_distribution2list_distribution(
00278        [[1,5],[2,3],[1,6],[2,1]]) = [[1,11],[2,4]]
00279 */
00280 
00281 /* In the special case, where the x are numerical, we could do as
00282    follows; HOWEVER this is MUCH slower than the above: */
00283 oklib_plain_include(descriptive)$
00284 num_distribution(L) := block([D : discrete_freq(L)],
00285   sort(map("[",D[1],D[2]),
00286     lambda([P1,P2], is(first(P1) < first(P2)))))$
00287 
00288