OKlibrary  0.2.1.6
SetSystems.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 27.3.2008 (Swansea) */
00002 /* Copyright 2008, 2009, 2010, 2011, 2012, 2013 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/Hypergraphs/Lisp/SetSystems.mac")$
00024 
00025 
00026 kill(f)$
00027 
00028 
00029 /* ***************
00030    * Elementship *
00031    ***************
00032 */
00033 
00034 okltest_gelementp(f) := block(
00035   assert(f([],[]) = true),
00036   assert(f([],[{}]) = true),
00037   assert(f([1],[]) = false),
00038   assert(f([1],[{}]) = false),
00039   assert(f([1],[{1}]) = true),
00040   assert(f([1],[{1},{}]) = true),
00041   assert(f([1,2],[{1,2}]) = false),
00042   assert(f([1,2],[{1,2},{2,3}]) = true),
00043   assert(f([1,2],[{1,2},{2,3},{}]) = true),
00044   assert(f([1,2],[{2},{1,2},{2,3},{}]) = false),
00045   true)$
00046 
00047 
00048 /* **************
00049    * Singletons *
00050    **************
00051 */
00052 
00053 okltest_singletonp(f) := (
00054   assert(f({}) = false),
00055   assert(f({1}) = true),
00056   assert(f({1,2}) = false),
00057   true)$
00058 
00059 okltest_single_element(f) := (
00060   assert(f({1}) = 1),
00061   assert(f({{}}) = {}),
00062   true)$
00063 
00064 okltest_choose_element(f) := (
00065   assert(f({1}) = 1),
00066   assert(elementp(f({1,2}),{1,2}) = true),
00067   true)$
00068 
00069 okltest_first_element(f) := (
00070   assert(f({1}) = 1),
00071   assert(f({1,2,3}) = 1),
00072   assert(f({1,2,3,-1,-2,-3}) = -3),
00073   assert(f({{1,2},{1,3},{2,3}}) = {1,2}),
00074   assert(f({{1,2},{1,3},{2,-3}}) = {-3,2}),
00075   assert(f({[],[1],[2]}) = []),
00076   true)$
00077 
00078 okltest_last_element(f) := (
00079   assert(f({1}) = 1),
00080   assert(f({1,2,3}) = 3),
00081   assert(f({1,2,3,-1,-2,-3}) = 3),
00082   assert(f({{1,2},{1,3},{2,3}}) = {2,3}),
00083   assert(f({{1,2},{1,3},{2,-3}}) = {1,3}),
00084   assert(f({[],[1],[2]}) = [2]),
00085   true)$
00086 
00087 
00088 /* *********************
00089    * Set constructions *
00090    *********************
00091 */
00092 
00093 okltest_setn(f) := (
00094   assert(f(0) = {}),
00095   assert(f(1) = {1}),
00096   assert(f(2) = {1,2}),
00097   assert(f(-1) = {}),
00098   true)$
00099 
00100 okltest_setmn(f) := (
00101   okltest_setn(buildq([f],lambda([n],f(1,n)))),
00102   assert(f(0,0) = {0}),
00103   assert(f(2,5) = {2,3,4,5}),
00104   assert(f(2,1) = {}),
00105   assert(f(-3,-4) = {}),
00106   assert(f(-4,-3) = {-4,-3}),
00107   true)$
00108 
00109 okltest_listn(f) := (
00110   assert(f(0) = []),
00111   assert(f(1) = [1]),
00112   assert(f(2) = [1,2]),
00113   assert(f(-1) = []),
00114   true)$
00115 
00116 okltest_listmn(f) := (
00117   okltest_listn(buildq([f],lambda([n],f(1,n)))),
00118   assert(f(0,0) = [0]),
00119   assert(f(2,5) = [2,3,4,5]),
00120   assert(f(2,1) = []),
00121   assert(f(-3,-4) = []),
00122   assert(f(-4,-3) = [-4,-3]),
00123   true)$
00124 
00125 okltest_singletons(f) := (
00126   assert(f({}) = {}),
00127   assert(f({{}}) = {{{}}}),
00128   assert(f({1,2}) = {{1},{2}}),
00129   assert(f({1,2,4}) = {{1},{2},{4}}),
00130   true)$
00131 
00132 okltest_upairs(f) := (
00133   assert(f({},{}) = {}),
00134   assert(f({},{1}) = {}),
00135   assert(f({1},{}) = {}),
00136   assert(f({1},{1}) = {{1}}),
00137   assert(f({1},{2}) = {{1,2}}),
00138   assert(f({1,2},{2,3}) = {{1,2},{1,3},{2},{2,3}}),
00139   true)$
00140 
00141 
00142 /* **********************************
00143    * Constructions related to union *
00144    **********************************
00145 */
00146 
00147 okltest_lunion(f) := block(
00148   assert(f({}) = {}),
00149   assert(f({{}}) = {}),
00150   assert(f({{1,2},{2,3},{3,4}}) = {1,2,3,4}),
00151   assert(f({{-6,-5,-4,-3,-2,-1},{-6,-5,-4,-3,-2,1},{-6,-5,-4,-3,-1,2},{-6,-5,-4,-3,1,2},{-6,-5,-4,-2,-1,3},{-6,-5,-4,-2,1,3},{-6,-5,-4,-1,2,3},{-6,-5,-4,1,2,3}, {-6,-5,-3,-2,-1,4},{-6,-5,-3,-2,1,4},{-6,-5,-3,-1,2,4},{-6,-5,-3,1,2,4},{-6,-5,-2,-1,3,4},{-6,-5,-2,1,3,4},{-6,-5,-1,2,3,4},{-6,-5,1,2,3,4},{-6,-4,-3,-2,-1,5},{-6,-4,-3,-2,1,5},{-6,-4,-3,-1,2,5},{-6,-4,-3,1,2,5},{-6,-4,-2,-1,3,5},{-6,-4,-2,1,3,5},{-6,-4,-1,2,3,5},{-6,-4,1,2,3,5},{-6,-3,-2,-1,4,5},{-6,-3,-2,1,4,5},{-6,-3,-1,2,4,5},{-6,-3,1,2,4,5},{-6,-2,-1,3,4,5},{-6,-2,1,3,4,5},{-6,-1,2,3,4,5},{-6,1,2,3,4,5},{-5,-4,-3,-2,-1,6},{-5,-4,-3,-2,1,6},{-5,-4,-3,-1,2,6},{-5,-4,-3,1,2,6},{-5,-4,-2,-1,3,6},{-5,-4,-2,1,3,6}, {-5,-4,-1,2,3,6},{-5,-4,1,2,3,6},{-5,-3,-2,-1,4,6},{-5,-3,-2,1,4,6},{-5,-3,-1,2,4,6},{-5,-3,1,2,4,6},{-5,-2,-1,3,4,6},{-5,-2,1,3,4,6},{-5,-1,2,3,4,6},{-5,1,2,3,4,6}, {-4,-3,-2,-1,5,6},{-4,-3,-2,1,5,6},{-4,-3,-1,2,5,6},{-4,-3,1,2,5,6},{-4,-2,-1,3,5,6},{-4,-3,-2,-1,5,6},{-4,-3,-2,1,5,6},{-4,-3,-1,2,5,6},{-4,-3,1,2,5,6},{-4,-2,-1,3,5,6},{-4,-2,1,3,5,6},{-4,-1,2,3,5,6},{-4,1,2,3,5,6},{-3,-2,-1,4,5,6},{-3,-2,1,4,5,6}, {-3,-1,2,4,5,6},{-3,1,2,4,5,6},{-2,-1,3,4,5,6},{-2,1,3,4,5,6},{-1,2,3,4,5,6},{1,2,3,4,5,6}}) = {-1,-2,-3,-4,-5,-6,1,2,3,4,5,6}),
00152   assert(f([]) = {}),
00153   assert(f([{}]) = {}),
00154   assert(f([{1,2},{2,3},{3,4}]) = {1,2,3,4}),
00155   if oklib_test_level = 0 then return(true),
00156   assert(f(create_list({i},i,1,2^16+1)) = setn(2^16+1)),
00157   true)$
00158 
00159 okltest_family_sets_union(f) := block([func],
00160   assert(f({},func) = {}),
00161   for n : 0 thru 4 do block([N : setn(n)],
00162     assert(f(N, lambda([i],{i})) = N)),
00163   true)$
00164 
00165 okltest_set_sum(f) := (
00166   assert(f([]) = {}),
00167   assert(f([{1}]) = {[1,1]}),
00168   for n : 0 thru 3 do block([N : setn(n)],
00169     assert(f([N]) = cartesian_product(N,{1}))),
00170   assert(f([{1,2},{1,3}]) = {[1,1],[2,1],[1,2],[3,2]}),
00171   true)$
00172 
00173 okltest_cunion(f) := (
00174   assert(f({},{{1,2}}) = {}),
00175   assert(f({{}},{{1,2}}) = {{1,2}}),
00176   assert(f({{1,2},{2,3}},{{3,4},{4,5}}) = {{1,2,3,4},{1,2,4,5},{2,3,4},{2,3,4,5}}),
00177   true)$
00178 
00179 okltest_add_elements(f) := (
00180   assert(f({1,2},{{},{3,4},{1,4}}) = {{1,2},{1,2,3,4},{1,2,4}}),
00181   /* XXX */
00182   true)$
00183 
00184 okltest_add_element(f) := (
00185   assert(f(1,{}) = {}),
00186   assert(f(1,{{}}) = {{1}}),
00187   assert(f(1,{{1},{2,3}}) = {{1},{1,2,3}}),
00188   true)$
00189 
00190 okltest_cunion_l(f) := (
00191   okltest_cunion(buildq([f], lambda([A,B], setify(f(listify(A),listify(B)))))),
00192   /* XXX */
00193   true)$
00194 
00195 okltest_add_elements_l(f) := (
00196   okltest_add_elements(buildq([f], lambda([x,S], setify(f(x,listify(S)))))),
00197   /* XXX */
00198   true)$
00199 
00200 okltest_add_element_l(f) := (
00201   okltest_add_element(buildq([f], lambda([x,S], setify(f(x,listify(S)))))),
00202   /* XXX */
00203   true)$
00204 
00205 
00206 /* ********************************************
00207    * Constructions related to complementation *
00208    ********************************************
00209 */
00210 
00211 okltest_ecomp(f) := (
00212   assert(f({},{}) = {}),
00213   assert(f({},{1}) = {}),
00214   assert(f({{}},{}) = {{}}),
00215   assert(f({{}},{1}) = {{1}}),
00216   assert(f({{1},{2}},{1,2,3}) = {{2,3},{1,3}}),
00217   true)$
00218 
00219 okltest_setdifference2(f) := (
00220   assert(f({},{}) = {}),
00221   assert(f({{1},{}},{}) = {{1},{}}),
00222   assert(f({{1},{}},{2}) = {{1},{}}),
00223   assert(f({{1,2},{2,3}},{1}) = {{2},{2,3}}),
00224   assert(f({{1,2},{2,3}},{1,2,3}) = {{}}),
00225   assert(f([],{}) = []),
00226   assert(f([{1},{}],{}) = [{1},{}]),
00227   assert(f([{1},{}],{2}) = [{1},{}]),
00228   assert(f([{1,2},{2,3}],{1}) = [{2},{2,3}]),
00229   assert(f([{1,2},{2,3}],{1,2,3}) = [{},{}]),
00230   true)$
00231 
00232 okltest_setdifference2e(f) := (
00233   assert(f([],1) = []),
00234   assert(f({},1) = {}),
00235   assert(f([{1,2},{},{3},{2,3}],2) = [{1},{},{3},{3}]),
00236   true)$
00237 
00238 
00239 /* **************************************************
00240    * Constructions related to the cartesian product *
00241    **************************************************
00242 */
00243 
00244 okltest_cartesian_product_l(f) := (
00245   assert(f([]) = [[]]),
00246   assert(f([[]]) = []),
00247   assert(f([[1]]) = [[1]]),
00248   assert(f([[2,1]]) = [[2],[1]]),
00249   assert(f([[1],[]]) = []),
00250   assert(f([[1,2],[-3,-4]]) = [[1,-3],[1,-4],[2,-3],[2,-4]]),
00251   true)$
00252 
00253 okltest_all_transformations_l(f) := (
00254   assert(f({}) = {[]}),
00255   assert(f({2}) = {[2]}),
00256   assert(f({-1,1}) = {[-1,-1],[-1,1],[1,-1],[1,1]}),
00257   assert(length(f({0,2,4})) = 27),
00258   true)$
00259 
00260 okltest_all_transformations_l_l(f) := (
00261   assert(f([]) = [[]]),
00262   assert(f([2,1]) = [[2,2],[2,1],[1,2],[1,1]]),
00263   assert(okltest_all_transformations_l(buildq([f],lambda([X],setify(f(listify(X))))))),
00264   true)$
00265 
00266 okltest_all_tuples(f) := (
00267   assert(f({},0) = {[]}),
00268   assert(f({},1) = {}),
00269   assert(f({1},0) = {[]}),
00270   assert(f({1},1) = {[1]}),
00271   assert(f({1},2) = {[1,1]}),
00272   assert(f({1,2},0) = {[]}),
00273   assert(f({1,2},1) = {[1],[2]}),
00274   assert(f({1,2},2) = {[1,2],[2,1],[1,1],[2,2]}),
00275   assert(f({1,2},3) = {[1,1,1],[1,1,2],[1,2,1],[2,1,1],[1,2,2],[2,1,2],[2,2,1],[2,2,2]}),
00276   assert(okltest_all_transformations_l(buildq([f],lambda([X],f(X,length(X))))) = true),
00277   true)$
00278 
00279 okltest_all_tuples_l(f) := (
00280   assert(f([],0) = [[]]),
00281   assert(f([],1) = []),
00282   assert(f([1],0) = [[]]),
00283   assert(f([1],1) = [[1]]),
00284   assert(f([1],2) = [[1,1]]),
00285   assert(f([1,2],0) = [[]]),
00286   assert(f([1,2],1) = [[1],[2]]),
00287   assert(f([1,2],2) = [[1,1],[1,2],[2,1],[2,2]]),
00288   assert(f([1,2],3) = [[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,1],[2,1,2],[2,2,1],[2,2,2]]),
00289   assert(okltest_all_transformations_l_l(buildq([f],lambda([X],f(X,length(X))))) = true),
00290   true)$
00291 
00292 okltest_all_ord_tuples(f) := (
00293   assert(f({},0) = {[]}),
00294   assert(f({},1) = {}),
00295   assert(f({1},0) = {[]}),
00296   assert(f({1},1) = {[1]}),
00297   assert(f({1},2) = {[1,1]}),
00298   assert(f({1,2},0) = {[]}),
00299   assert(f({1,2},1) = {[1],[2]}),
00300   assert(f({1,2},2) = {[1,2],[1,1],[2,2]}),
00301   assert(f({1,2},3) = {[1,1,1],[1,1,2],[1,2,2],[2,2,2]}),
00302   true)$
00303 
00304 okltest_all_ord_tuples_l(f) := (
00305   assert(f([],0) = [[]]),
00306   assert(f([],1) = []),
00307   assert(f([1],0) = [[]]),
00308   assert(f([1],1) = [[1]]),
00309   assert(f([1],2) = [[1,1]]),
00310   assert(f([1,2],0) = [[]]),
00311   assert(f([1,2],1) = [[1],[2]]),
00312   assert(f([1,2],2) = [[1,1],[1,2],[2,2]]),
00313   assert(f([1,2],3) = [[1,1,1],[1,1,2],[1,2,2],[2,2,2]]),
00314   true)$
00315 
00316 
00317 /* ************************************
00318    * Constructions related to subsets *
00319    ************************************
00320 */
00321 
00322 okltest_kpermutations(f) := (
00323   for n : 0 thru 5 do block([N : setn(n)],
00324     assert(f(N,0) = [[]]),
00325     assert(f(N,1) = create_list([i],i,1,n))
00326   ),
00327   assert(f({1,3,5},2) = [[1,3],[3,1],[1,5],[5,1],[3,5],[5,3]]),
00328   assert(length(f({1,4,8,9},3)) = 4*3*2),
00329   true)$
00330 
00331 okltest_powerset_l(f) := (
00332   assert(f([],0) = [[]]),
00333   assert(f([],1) = []),
00334   assert(f([1],0) = [[]]),
00335   assert(f([1],1) = [[1]]),
00336   assert(f([1],2) = []),
00337   assert(f([1,1],0) = [[]]),
00338   assert(f([1,1],1) = [[1]]),
00339   assert(f([1,1],2) = []),
00340   assert(f([1,2],0) = [[]]),
00341   assert(f([1,2],1) = [[1],[2]]),
00342   assert(f([1,2],2) = [[1,2]]),
00343   assert(f([1,2],3) = []),
00344   assert(f([2,1],0) = [[]]),
00345   assert(f([2,1],1) = [[1],[2]]),
00346   assert(f([2,1],2) = [[1,2]]),
00347   assert(f([2,1],3) = []),
00348   assert(f([2,1,2,2,1,1],0) = [[]]),
00349   assert(f([2,1,2,2,1,1],1) = [[1],[2]]),
00350   assert(f([2,1,2,2,1,1],2) = [[1,2]]),
00351   assert(f([2,1,2,2,1,1],3) = []),
00352   assert(f([1,2,3],0) = [[]]),
00353   assert(f([1,2,3],1) = [[1],[2],[3]]),
00354   assert(f([1,2,3],2) = [[1,2],[1,3],[2,3]]),
00355   assert(f([1,2,3],3) = [[1,2,3]]),
00356   assert(f([1,2,3],4) = []),
00357   true)$
00358 
00359 okltest_powerlist2(f) := block(
00360   assert(f([]) = []),
00361   assert(f([1]) = []),
00362   for n : 0 thru 5 do 
00363     assert(f(create_list(1,i,1,n)) = create_list([1,1],i,1,binomial(n,2))),
00364   assert(f([1,2]) = [[1,2]]),
00365   assert(f([1,2,3]) = [[1,2],[1,3],[2,3]]),
00366   assert(f([1,2,1]) = [[1,2],[1,1],[2,1]]),
00367   if oklib_test_level = 0 then return(true),
00368   assert(f(create_list(1,i,1,300)) = create_list([1,1],i,1,binomial(300,2))),
00369   block([R : f(create_list(i,i,1,300))],
00370     assert(length(R) = binomial(300,2)),
00371     assert(setify(R) = map(listify,powerset(setn(300),2)))
00372   ),
00373   true)$
00374 
00375 
00376 /* *********************************************
00377    * Tests related to unions and intersections *
00378    *********************************************
00379 */
00380 
00381 okltest_bunion_closed_p(f) := (
00382   assert(f({}) = true),
00383   assert(f({{}}) = true),
00384   assert(f({{1}}) = true),
00385   assert(f({{1},{}}) = true),
00386   assert(f({{1},{2}}) = false),
00387   assert(f({{1},{2},{1,2}}) = true),
00388   for n : 0 thru 4 do block([N : setn(n), P],
00389     P : powerset(N),
00390     assert(f(P) = true),
00391     assert(f(disjoin({},P)) = true),
00392     assert(f(disjoin(N,P)) = if n <= 1 then true else false)
00393   ),
00394   true)$
00395 
00396 
00397 /* *******************************
00398    * Tests related to partitions *
00399    *******************************
00400 */
00401 
00402 okltest_empty_element_p(f) := (
00403   assert(f({}) = false),
00404   assert(f({{}}) = true),
00405   assert(f({{1}}) = false),
00406   assert(f({{1},{}}) = true),
00407   true)$
00408 
00409 okltest_non_disjoint_pair(f) := (
00410   assert(f([]) = []),
00411   assert(f([{}]) = []),
00412   assert(f([{1},{2}]) = []),
00413   assert(f([{1},{1,2}]) = [1,2]),
00414   assert(f([{1,2},{3,4},{5,6},{5,7}]) = [3,4]),
00415   assert(f([{1},{1,2},{1,3}]) = [1,2]),
00416   true)$
00417 
00418 okltest_non_disjoint_pairs(f) := (
00419   assert(okltest_non_disjoint_pair(buildq([f], lambda([S], block([R:f(S)], if emptyp(R) then R else first(R))))) = true),
00420   assert(f([{1,2},{2,3},{3,4}]) = [[1,2],[2,3]]).
00421   assert(f([{1,2,3},{1,2},{2,3}]) = [[1,2],[1,3],[2,3]]),
00422   true)$
00423 
00424 okltest_disjoint_set_system_p(f) := (
00425   assert(f({}) = true),
00426   assert(f({{}}) = true),
00427   assert(f({{1},{},{2}}) = true),
00428   assert(f({{1}}) = true),
00429   assert(f({{1,2},{2,3}}) = false),
00430   assert(f({{1},{2},{},{3},{3,4}}) = false),
00431   assert(f([]) = true),
00432   assert(f([{},{}]) = true),
00433   assert(f([{1},{1}]) = false),
00434   true)$
00435 
00436 okltest_blockpartitionp(f) := (
00437   assert(f([],{}) = true),
00438   assert(f([{}],{}) = true),
00439   assert(f([{},{}],{}) = true),
00440   assert(f([{},{}],{1}) = false),
00441   assert(f([{1},{}],{}) = false),
00442   assert(f([{1},{}],{1}) = true),
00443   assert(f([{1},{1}],{1}) = false),
00444   true)$
00445 
00446 okltest_partitionp(f) := block(
00447   assert(f({},{}) = true),
00448   assert(f({{}},{}) = false),
00449   assert(f({{1},{}},{1}) = false),
00450   assert(f({{1}},{1}) = true),
00451   assert(f({{}},{1}) = false),
00452   assert(f({{2}},{1}) = false),
00453   assert(f({{2},{1}},{1}) = false),
00454   assert(f({{1},{2},{3}},{1,2,3}) = true),
00455   assert(f({{1},{2,3},{3,4}},{1,2,3,4}) = false),
00456   assert(f({{1,2,3,4}},{1,2,3,4}) = true),
00457   assert(f({{1},{2},{3},{4}},{1,2,3}) = false),
00458   true)$
00459 
00460 
00461 /* ********************************
00462    * Tests related to subsumption *
00463    ********************************
00464 */
00465 
00466 okltest_antichain_p(f) := (
00467   assert(f({}) = true),
00468   assert(f({{}}) = true),
00469   assert(f({{1}}) = true),
00470   assert(f({{1,2},{2,3}}) = true),
00471   assert(f({{1,2},{2}}) = false),
00472   assert(f([]) = true),
00473   assert(f([{1,2,3},{2,3,4}]) = true),
00474   true)$
00475 
00476 okltest_subsumption_closed_p(f) := (
00477   assert(f({}) = true),
00478   assert(f({{}}) = true),
00479   assert(f({{1}}) = false),
00480   assert(f({{},{1}}) = true),
00481   for n : 0 thru 3 do block([U : setify(create_list(i,i,1,n)), S],
00482     S : powerset(U),
00483     assert(f(S) = true),
00484     for x in S do
00485       assert(f(disjoin(x,S)) = is(x=U))
00486   ),
00487   true)$
00488 
00489 okltest_accessible_ss_p(f) := (
00490   assert(f({}) = true),
00491   assert(f({{}}) = true),
00492   assert(f({{1}}) = false),
00493   assert(f({{1},{}}) = true),
00494   assert(f({{1,2},{1},{}}) = true),
00495   assert(f({{1,2,3,4},{1,2},{1},{}}) = false),
00496   assert(f({{1,2,3,4},{1,2},{1},{},{1,2,4}}) = true),
00497   assert(f({{1,2,3,4},{1,2},{1},{},{1,2,4},{1,3}}) = true),
00498   assert(f({{1,2,3,4},{1,2},{1},{},{1,2,4},{1,3},{3,4}}) = false),
00499   assert(f({{1,2,3,4},{1,2},{1},{},{1,2,4},{1,3},{3,4},{3}}) = true),
00500   true)$
00501 
00502 okltest_lr_subsetp(f) := block([S],
00503   assert(f({},{}) = true),
00504   assert(f({},S) = true),
00505   assert(f({{}},{}) = false),
00506   assert(f({{}},{{}}) = true),
00507   assert(f({{}},{{1}}) = true),
00508   assert(f({{}},{{1},{}}) = true),
00509   assert(f({{1,2},{2,3}},{{1,2,3}}) = true),
00510   assert(f({{1,2},{2,3}},{{1,2,4}}) = false),
00511   assert(f({{1,2},{2,3}},{{1,2,4},{2,3,5},{}}) = true),
00512   true)$
00513 
00514 okltest_l1r_subsetp(f) := (
00515   assert(f({},{}) = false),
00516   assert(f({},{{}}) = true),
00517   assert(f({},{{1}}) = true),
00518   assert(f({1},{{1}}) = true),
00519   assert(f({1},{{1},{}}) = true),
00520   assert(f({2},{{1}}) = false),
00521   assert(f({2},{{1},{}}) = false),
00522   assert(f({1,2},{{},{4,5},{1,2,3}}) = true),
00523   assert(f({1,2},{{},{4,5},{1,3}}) = false),
00524   true)$
00525 
00526 okltest_rl_subsetp(f) := block([S],
00527   assert(f({},{}) = true),
00528   assert(f(S,{}) = true),
00529   assert(f({},{{}}) = false),
00530   assert(f({{1}},{{}}) = false),
00531   assert(f({{}},{{}}) = true),
00532   assert(f({{},{1}},{{}}) = true),
00533   assert(f({{}},{{1}}) = true),
00534   assert(f({{2}},{{1}}) = false),
00535   assert(f({{2,3}},{{1,2,3},{2,3,4}}) = true),
00536   assert(f({{1,3},{2,4}},{{1,2,3},{2,3,4}}) = true),
00537   true)$
00538 
00539 okltest_r1l_subsetp(f) := (
00540   assert(f({},{}) = false),
00541   assert(f({{}},{}) = true),
00542   assert(f({{1},{}},{}) = true),
00543   assert(f({{1},{2}},{}) = false),
00544   assert(f({{1,3},{2,4}},{1,2}) = false),
00545   assert(f({{1,3},{2,4},{1}},{1,2}) = true),
00546   true)$
00547 
00548 
00549 /* *****************************************
00550    * Constructions related to disjointness *
00551    *****************************************
00552 */
00553 
00554 okltest_remove_with_element(f) := (
00555   assert(f({},1) = {}),
00556   assert(f({{1},{2}},1) = {{2}}),
00557   true)$
00558 
00559 okltest_remove_with_element_l(f) := (
00560   assert(f([],1) = []),
00561   assert(f([{1},{2},{1},{1,3},{2,3}],1) = [{2},{2,3}]),
00562   true)$
00563 
00564 okltest_remove_non_disjoint(f) := (
00565   assert(f({},{}) = {}),
00566   assert(f({{1,2},{2,3},{3,4},{},{1,3}},{2,4}) = {{},{1,3}}),
00567   true)$
00568 
00569 okltest_unify_nondisjoint_elements(f) := (
00570   /* XXX */
00571   true)$
00572 
00573 
00574 /* *****************************************
00575    * Constructions related to subsumption  *
00576    *****************************************
00577 */
00578 
00579 okltest_min_elements_l(f) := (
00580   assert(f([]) = []),
00581   assert(f([{}]) = [{}]),
00582   assert(f([{},{}]) = [{}]),
00583   assert(f([{2},{},{1}]) = [{}]),
00584   assert(f([{1,2},{2,3},{1,2,3},{3}]) = [{3},{1,2}]),
00585   assert(f([{1,2},{1,2,3},{4,5},{1,2},{1,2,3},{4,5}]) = [{1,2},{4,5}]),
00586   assert(f([{1,2},{1},{3,4},{1},{2},{5,6},{3,4},{2},{3,4,5},{1},{3,4}]) = [{1},{2},{3,4},{5,6}]),
00587   true)$
00588 
00589 okltest_min_elements(f) := (
00590   assert(f({}) = {}),
00591   assert(f({{}}) = {{}}),
00592   assert(f({{1},{2}}) = {{1},{2}}),
00593   assert(f({{1,2},{1,2,4},{3},{3,4},{5,6}}) = {{1,2},{3},{5,6}}),
00594   assert(f({{1,3,5},{2,4,6},{1,3,5,2,4,6},{1,3,5,11},{1,2,4,6}}) = {{1,3,5},{2,4,6}}),
00595   for n : 0 thru 3 do
00596     assert(f(powerset(setn(n))) = {{}}),
00597   true)$
00598 
00599 okltest_max_elements_l(f) := (
00600   assert(f([]) = []),
00601   assert(f([{}]) = [{}]),
00602   assert(f([{},{}]) = [{}]),
00603   assert(f([{2},{},{1}]) = [{2},{1}]),
00604   assert(f([{1,2},{2,3},{1,2,3},{3}]) = [{1,2,3}]),
00605   assert(f([{1,2},{1,2,3},{4,5},{1,2},{1,2,3},{4,5}]) = [{1,2,3},{4,5}]),
00606   assert(f([{1,2},{1},{3,4},{1},{2},{5,6},{3,4},{2},{3,4,5},{1},{3,4}]) = [{3,4,5},{1,2},{5,6}]),
00607   true)$
00608 
00609 okltest_max_elements(f) := (
00610   assert(f({}) = {}),
00611   assert(f({{}}) = {{}}),
00612   assert(f({{1},{2}}) = {{1},{2}}),
00613   assert(f({{1,2},{1,2,4},{3},{3,4},{5,6}}) = {{1,2,4},{3,4},{5,6}}),
00614   for n : 0 thru 3 do
00615     assert(f(powerset(setn(n))) = {setn(n)}),
00616   true)$
00617 
00618 okltest_check_subsumption(f) := block([ss,x],
00619   ss : f({}),
00620   assert(ss(x) = false),
00621   ss : f({{}}),
00622   assert(ss(x) = true),
00623   ss : f({{},{1,2,3}}),
00624   assert(ss(x) = true),
00625   ss : f({{1}}),
00626   assert(ss({1}) = true),
00627   assert(ss({1,2}) = true),
00628   assert(ss({2}) = false),
00629   ss : f({{1},{2}}),
00630   assert(ss({1}) = true),
00631   assert(ss({1,2}) = true),
00632   assert(ss({2}) = true),
00633   assert(ss({3}) = false),
00634   ss : f({{1,2},{2,3},{3,4},{5}}),
00635   assert(ss({}) = false),
00636   for i : 1 thru 4 do
00637     assert(ss({i}) = false),
00638   assert(ss({1,2}) = true),
00639   assert(ss({2,3}) = true),
00640   assert(ss({3,4}) = true),
00641   assert(ss({1,3}) = false),
00642   assert(ss({2,4}) = false),
00643   assert(ss({1,2,3}) = true),
00644   assert(ss({2,3,4}) = true),
00645   assert(ss({5}) = true),
00646   assert(ss({1,5}) = true),
00647   assert(ss({6}) = false),
00648   ss : f({{1},{2,3},{3,4,5},{6,7,8,9}}),
00649   assert(ss({1}) = true),
00650   assert(ss({2}) = false),
00651   assert(ss({2,3}) = true),
00652   assert(ss({3,4}) = false),
00653   assert(ss({3,4,5}) = true),
00654   assert(ss({6,7,8}) = false),
00655   assert(ss({6,7,8,9}) = true),
00656   assert(ss({1,2,3,4,5,6,7,8,9}) = true),
00657   true)$
00658