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 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/TestSystem/Lisp/Asserts.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/HashMaps.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")$
00026 
00027 kill(f)$
00028 
00029 /* ************************
00030    * Set-theoretical maps *
00031    ************************
00032 */
00033 
00034 okltest_setmapp(f) := (
00035   assert(f(1) = false),
00036   assert(f([]) = false),
00037   assert(f({}) = true),
00038   assert(f({1}) = false),
00039   assert(f({[1,2,3]}) = false),
00040   assert(f({[1,1]}) = true),
00041   assert(f({[1,1],[1,2]}) = false),
00042   assert(f({[1,1],[2,1]}) = true),
00043   true)$
00044 
00045 okltest_osm_p(f) := block(
00046   okltest_setmapp(buildq([f],lambda([M],setp(M) and f(listify(M))))),
00047   assert(f(1) = false),
00048   assert(f([[1,1],[1,2]]) = false),
00049   true)$
00050 
00051 okltest_define_set_map(f) := block([M,x,y],
00052   M : f({},1,10),
00053   assert(M = {[1,10]}),
00054   M : f(M,1,11),
00055   assert(M = {[1,11]}),
00056   M : f(M,1,11),
00057   assert(M = {[1,11]}),
00058   M : f(M,2,20),
00059   assert(M = {[1,11],[2,20]}),
00060   M : f(M,2,21),
00061   assert(M = {[1,11],[2,21]}),
00062   true)$
00063 
00064 okltest_evaluate_set_map(f) := block([M,x],
00065   assert(f({},x) = done),
00066   assert(f({[1,10]},1) = 10),
00067   assert(f({[1,10]},2) = done),
00068   M : {[1,2],[5,10]},
00069   assert(f(M,1) = 2), assert(f(M,5) = 10), assert(f(M,2) = done),
00070   true)$
00071 
00072 okltest_evaluate_set_map_d(f) := block([M,x,y],
00073   assert(f({},x,1) = 1),
00074   assert(f({[1,10]},1,y) = 10),
00075   assert(f({[1,10]},2,20) = 20),
00076   M : {[1,2],[5,10]},
00077   assert(f(M,1,3) = 2), assert(f(M,5,9) = 10), assert(f(M,2,y) = y),
00078   true)$
00079 
00080 okltest_l2sm(f) := (
00081   assert(f([]) = {}),
00082   assert(f([4]) = {[1,4]}),
00083   assert(f([4,-1]) = {[1,4],[2,-1]}),
00084   true)$
00085 
00086 okltest_ll2sm(f) := (
00087   assert(okltest_l2sm(buildq([f],lambda([L],f(create_list(i,i,1,length(L)),L)))) = true),
00088   assert(f([-1,-3,-5],[1,2,3]) = {[-1,1],[-3,2],[-5,3]}),
00089   true)$
00090 
00091 okltest_l2osm_inv(f) := (
00092   assert(f([]) = []),
00093   assert(f([1]) = [[1,1]]),
00094   assert(f([77]) = [[77,1]]),
00095   assert(f([77,66]) = [[77,1],[66,2]]),
00096   true)$
00097 
00098 okltest_allbij_sm(f) := (
00099   for n : 0 thru 4 do
00100     assert(f({},setn(n)) = if n=0 then {{}} else {}),
00101   assert(f({1},{1,2}) = {}),
00102   assert(f({1},{3}) = {{[1,3]}}),
00103   assert(f({1,2},{3,4}) = {{[1,3],[2,4]},{[1,4],[2,3]}}),
00104   true)$
00105 
00106 okltest_allperm_sm(f) := (
00107   assert(f({}) = {{}}),
00108   assert(f({1}) = {{[1,1]}}),
00109   assert(f({-1,1}) = {{[1,1],[-1,-1]},{[1,-1],[-1,1]}}),
00110   for n : 0 thru 5 do
00111     assert(length(f(setn(n))) = n!),
00112   true)$
00113 
00114 okltest_allinj_sm(f) := (
00115   assert(okltest_allbij_sm(buildq([f],lambda([A,B],if length(A)#length(B) then {} else setify(f(A,B))))) = true),
00116   for n : 0 thru 4 do
00117     assert(f({},setn(n)) = [{}]),
00118   assert(f({1},{1,2}) = [{[1,1]},{[1,2]}]),
00119   assert(f({-1,1},{3,4,5}) = [{[-1,3],[1,4]},{[-1,4],[1,3]},{[-1,3],[1,5]},{[-1,5],[1,3]},{[-1,4],[1,5]},{[-1,5],[1,4]}]),
00120   true)$
00121 
00122 
00123 /* *********************************
00124    * Hash maps as provided by Lisp *
00125    *********************************
00126 */
00127 
00128 /* A tool for checking whether an original hash-map and a set-map are identical
00129    as mathematical functions (this is only useful for compatibility
00130    reasons). */
00131 eq_ohmsm_p(h,M) := if not setmapp(M) then
00132   error("eq_ohmsm_p: the alleged set-map is not a set-map")
00133   else is(create_set_map(h) = M)$
00134 
00135 okltest_eq_ohmsm_p(f) := block([M,h],
00136   h : hash_table_okl(),
00137   M : {},
00138   assert(f(h,M) = true),
00139   set_hash_okl(1,h,10),
00140   assert(f(h,M) = false),
00141   M : define_set_map(M,1,10),
00142   assert(f(h,M) = true),
00143   set_hash_okl(1,h,11),
00144   assert(f(h,M) = false),
00145   M : define_set_map(M,1,11),
00146   assert(f(h,M) = true),
00147   set_hash_okl([],h,1),
00148   assert(f(h,M) = false),
00149   M : define_set_map(M,[],1),
00150   assert(f(h,M) = true),
00151   h : hash_table_okl(),
00152   set_hash_okl(1,h,1), set_hash_okl(-1,h,0),
00153   M : {[1,1],[-1,0]},
00154   assert(f(h,M) = true),
00155   h : hash_table_okl(),
00156   set_hash_okl(-1,h,0), set_hash_okl(1,h,1),
00157   assert(f(h,M) = true),
00158   true)$
00159 
00160 okltest_repo_set_maps : {
00161  {},
00162  {[1,1]},
00163  {[1,1],[2,3]}
00164 }$
00165 
00166 okltest_create_hash_map(f) := (
00167   for M in okltest_repo_set_maps do block([h : f(M)],
00168     assert(length(hash_table_data_okl(h)) = length(M)),
00169     for p in M do assert(get_hash_okl(p[1],h) = p[2])
00170   ),
00171   true)$
00172 
00173 okltest_create_set_map(f) := (
00174   for M in okltest_repo_set_maps do
00175     assert(f(create_hash_map(M)) = M),
00176   true)$
00177 
00178 /* A tool for checking whether an improved hash-map and a set-map are identical
00179    as mathematical functions. */
00180 eq_hmsm_p(h,M) := (
00181  if oklib_monitor then (
00182    print("M[eq_hmsm_p]: ENTRY"),
00183    if oklib_monitor_level >= 1 then (
00184      print("The hash-map is:"),
00185      print(h),
00186      print("The set-map is:"),
00187      print(M))
00188  ),
00189  if not setmapp(M) then
00190    error("eq_hmsm_p: the alleged set-map is not a set-map")
00191  elseif not is(hm2sm(h) = M) then (
00192      if not oklib_monitor then false else (
00193        print("M[eq_hmsm_p]: translating the hash-map does not yield the given set-map!"),
00194        if oklib_monitor_level >= 1 then (
00195          print("The translated hash-map is:"),
00196          print(hm2sm(h))),
00197        false
00198      ))
00199  else true)$
00200 
00201 okltest_eq_hmsm_p(f) := block([M,h],
00202   h : hash_table_okl(),
00203   M : {},
00204   assert(f(h,M) = true),
00205   set_hm(h,1,10),
00206   assert(f(h,M) = false),
00207   M : define_set_map(M,1,10),
00208   assert(f(h,M) = true),
00209   set_hm(h,1,11),
00210   assert(f(h,M) = false),
00211   M : define_set_map(M,1,11),
00212   assert(f(h,M) = true),
00213   set_hm(h,[],1),
00214   assert(f(h,M) = false),
00215   M : define_set_map(M,[],1),
00216   assert(f(h,M) = true),
00217   h : hash_table_okl(),
00218   set_hm(h,1,1), set_hm(h,-1,0),
00219   M : {[1,1],[-1,0]},
00220   assert(f(h,M) = true),
00221   h : hash_table_okl(),
00222   set_hm(h,-1,0), set_hm(h,1,1),
00223   assert(f(h,M) = true),
00224   true)$
00225 
00226 okltest_set_hm(f) := block([h : hash_table_okl()],
00227   f(h,1,10),
00228   assert(get_hash_okl(sconcat(1),h) = 10),
00229   assert(get_hash_okl(sconcat(2),h) = false),
00230   f(h,[],20),
00231   assert(get_hash_okl(sconcat([]),h) = 20),
00232   assert(get_hash_okl(sconcat(1),h) = 10),
00233   assert(get_hash_okl(sconcat([[]]),h) = false),
00234   f(h,1,11),
00235   assert(get_hash_okl(sconcat(1),h) = 11),
00236   f(h,[],21),
00237   assert(get_hash_okl(sconcat([]),h) = 21),
00238   assert(eq_hmsm_p(h,{[1,11],[[],21]}) = true),
00239   h : hash_table_okl(),
00240   f(h,1,1),
00241   assert(ev_hm(h,1) = 1),
00242   assert(ev_hm(h,-1) = false),
00243   f(h,-1,0),
00244   assert(eq_hmsm_p(h,{[1,1],[-1,0]}) = true),
00245   true)$
00246 
00247 okltest_ev_hm(f) := block([h : hash_table_okl()],
00248   assert(f(h,1) = false),
00249   set_hash_okl(sconcat(1),h,10),
00250   assert(f(h,1) = 10),
00251   set_hash_okl(sconcat([{}]),h,20),
00252   assert(f(h,[{}]) = 20),
00253   true)$
00254 
00255 okltest_ev_hm_d(f) := block([h : hash_table_okl()],
00256   assert(f(h,1,11) = 11),
00257   set_hash_okl(sconcat(1),h,1),
00258   assert(f(h,1,11) = 1),
00259   assert(f(h,[],11) = 11),
00260   set_hash_okl(sconcat([{}]),h,20),
00261   assert(f(h,[{}],-7) = 20),
00262   assert(f(h,[],{}) = {}),
00263   h : sm2hm({}),
00264   assert(f(h,1,10) = 10),
00265   set_hm(h,1,false),
00266   assert(f(h,1,10) = false),
00267   assert(f(h,2,10) = 10),
00268   true)$
00269 
00270 okltest_del_hm(f) := block([h : sm2hm({})],
00271   set_hm(h,1,10),
00272   del_hm(h,1),
00273   assert(eq_hmsm_p(h,{}) = true),
00274   compose_hm_sm(h,{[1,11],[{},{{}}]}),
00275   assert(eq_hmsm_p(h,{[1,11],[{},{{}}]}) = true),
00276   del_hm(h,1),
00277   assert(eq_hmsm_p(h,{[{},{{}}]}) = true),
00278   del_hm(h,{}),
00279   assert(eq_hmsm_p(h,{}) = true),
00280   true)$
00281 
00282 okltest_sm2hm(f) := block([h,M],
00283   h : f({}),
00284   assert(ev_hm(h,1) = false),
00285   h : f({[1,10]}),
00286   assert(ev_hm(h,1) = 10),
00287   M : {[{},{{}}],[[1,2],[3,4]],[5,5]},
00288   h : f(M),
00289   assert(ev_hm(h,{}) = {{}}),
00290   assert(ev_hm(h,[1,2]) = [3,4]),
00291   assert(ev_hm(h,5) = 5),
00292   assert(ev_hm(h,1) = false),
00293   assert(eq_hmsm_p(h,M) = true),
00294   true)$
00295 
00296 okltest_list_osm : [
00297  [],
00298  [[1,0]],
00299  [[1,1],[2,1]],
00300  [[{},1],[{{}},2]],
00301  [[{},{{}}],[[1,2],[3,4]],[5,5]]
00302 ]$
00303   
00304 okltest_osm2hm(f) := block(
00305   okltest_sm2hm(buildq([f],lambda([M],f(listify(M))))),
00306   for M in okltest_list_osm do
00307     assert(hm2sm(f(M)) = setify(M)),
00308   true)$
00309 
00310 okltest_hm2sm(f) := block([h],
00311   h : hash_table_okl(),
00312   assert(f(h) = {}),
00313   set_hm(h,1,10),
00314   assert(f(h) = {[1,10]}),
00315   set_hm(h,{[]},20),
00316   assert(f(h) = {[1,10],[{[]},20]}),
00317   assert(eq_hmsm_p(h,{[1,10],[{[]},20]}) = true),
00318   true)$
00319 
00320 okltest_compose_hm_sm(f) := block([h],
00321   h : f(sm2hm({}),{}),
00322   assert(eq_hmsm_p(h, {}) = true),
00323   f(h,{[1,1],[{{}},2]}),
00324   assert(eq_hmsm_p(h, {[1,1],[{{}},2]}) = true),
00325   f(h,{[{{}},2],[[[]],3]}),
00326   assert(eq_hmsm_p(h, {[1,1],[{{}},2],[[[]],3]}) = true),
00327   true)$
00328 
00329 okltest_lambda_hm(f) := block([lf],
00330   lf : f(sm2hm({})),
00331   assert(lf(1) = false),
00332   lf : f(osm2hm([[{},1],[{{}},2],[1,1]])),
00333   assert(lf({}) = 1),
00334   assert(lf({{}}) = 2),
00335   assert(lf(1) = 1),
00336   block([h : sm2hm({[1,1]}), lf2],
00337     lf : f(h),
00338     set_hm(h,1,2),
00339     lf2 : f(h),
00340     assert(lf(1) = 2),
00341     assert(lf2(1) = 2)
00342   ),
00343   true)$
00344 
00345 /* ***********************
00346    * Arrays as hash-maps *
00347    ***********************
00348 */
00349 
00350 okltest_okl_make_array(f) := block(
00351   for n : 0 thru 4 do
00352     for type in [any,fixnum,flonum] do
00353       assert(f(type,n) = block([a:make_array(type,n+1)],a[0]:n,a)),
00354   true)$
00355 okltest_okl_listarray(f) := block(
00356   for n : 0 thru 4 do
00357     for type in [any,fixnum,flonum] do
00358       assert(f(okl_make_array(type,n)) = create_list(
00359         if type=fixnum then 0 elseif type=flonum then 0.0 else false, i,1,n)),
00360   true)$
00361 okltest_okl_fillarray_l(f) := block(
00362   for n : 0 thru 5 do block([L : create_list(i,i,1,n)],
00363     assert(okl_listarray(f(okl_make_array(fixnum,n),L)) = L)),
00364   true)$
00365 
00366 okltest_l2array(f) := block(
00367   for n : 0 thru 4 do block(
00368    [L : create_list(create_list(j,j,1,i),i,1,n)],
00369     assert(okl_listarray(f(L)) = L)),
00370   true)$
00371 okltest_il2array(f) := block(
00372   for n : 0 thru 4 do block(
00373    [L : create_list(i,i,1,n)],
00374     assert(okl_listarray(f(L)) = L)),
00375   true)$
00376 okltest_fl2array(f) := block(
00377   for n : 0 thru 4 do block(
00378    [L : create_list(float(i),i,1,n)],
00379     assert(okl_listarray(f(L)) = L)),
00380   true)$
00381 
00382 
00383 okltest_sm2array(f) := block([a],
00384   assert(f({}) = okl_make_array(any,0)),
00385   a : f({[1,{}]}),
00386   assert(okl_listarray(a) = [{}]),
00387   a : f({[1,{}],[2,{{}}]}),
00388   assert(okl_listarray(a) = [{},{{}}]),
00389   true)$
00390 
00391 okltest_array2osm(f) := block([a],
00392   assert(f(okl_make_array(any,0)) = []),
00393   a : okl_make_array(any,3),
00394   a[1] : 77, a[2] : {}, a[3] : {{}},
00395   assert(f(a) = [[1,77],[2,{}],[3,{{}}]]),
00396   true)$
00397 
00398 okltest_lambda_array(f) := block([lf],
00399   lf : f(sm2array({})),
00400   assert(errcatch(lf(1)) = []),
00401   lf : f(osm2array_lt([[1,1],[2,{{}},2]],3,any)),
00402   assert(lf(1) = 1),
00403   assert(lf(2) = {{}}),
00404   assert(lf(3) = false),
00405   assert(errcatch(lf(4)) = []),
00406   block([a : okl_make_array(fixnum,1), lf2],
00407     lf : f(a),
00408     a[1] : 1,
00409     lf2 : f(a),
00410     assert(lf(1) = 1),
00411     assert(lf2(1) = 1)
00412   ),
00413   true)$
00414 
00415 okltest_extract_array(f) := block([a,a2,la],
00416   a : okl_make_array(fixnum,3),
00417   la : lambda_array(a),
00418   assert(okl_listarray(f(la)) = [0,0,0]),
00419   a[1] : 3,
00420   assert(okl_listarray(f(la)) = [3,0,0]),
00421   a2 : f(la),
00422   a[2] : 77,
00423   assert(a[2] = 77),
00424   assert(okl_listarray(f(la)) = [3,77,0]),
00425   true)$
00426 
00427 okltest_extract_arraylist(f) := (
00428   for n : 0 thru 5 do block([L : create_list(i,i,1,n)],
00429     assert(f(lambda_array(okl_fillarray_l(okl_make_array(fixnum,n),L))) = L)),
00430   true)$
00431 
00432 
00433 /* *********************
00434    * Frequency counter *
00435    *********************
00436 */
00437 
00438 okltest_multi_list_distribution2list_distribution(f) := (
00439   assert(f([]) = []),
00440   assert(f([[1,0]]) = [[1,0]]),
00441   assert(f([[1,0],[2,3]]) = [[1,0],[2,3]]),
00442   assert(f([[1,5],[2,3],[1,6],[2,1]]) = [[1,11],[2,4]]),
00443   true)$
00444 
00445 okltest_list_distribution(f) := (
00446   assert(f([]) = []),
00447   assert(f([{},{1},{},{2},{1}]) = [[{},2],[{1},2],[{2},1]]),
00448   assert(f([{},{2},{},{2},{1}]) = [[{},2],[{1},1],[{2},2]]),
00449   assert(okltest_num_distribution(f)),
00450   true)$
00451 
00452 okltest_num_distribution(f) := (
00453   assert(f([]) = []),
00454   assert(f([1]) = [[1,1]]),
00455   assert(f([1,2]) = [[1,1],[2,1]]),
00456   assert(f([1,1]) = [[1,2]]),
00457   assert(f([1,1,2,3,1,2,4]) = [[1,3],[2,2],[3,1],[4,1]]),
00458   assert(f([-1,0,4,4,4,-3]) = [[-3,1],[-1,1],[0,1],[4,3]]),
00459   true)$
00460