OKlibrary  0.2.1.6
Basics.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 29.6.2008 (Swansea) */
00002 /* Copyright 2008, 2009, 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/TestSystem/Lisp/Asserts.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/Trees/Lisp/Basics.mac")$
00024 
00025 kill(f)$
00026 
00027 /* ****************************
00028    * Unlabelled rooted trees  *
00029    ****************************
00030 */
00031 
00032 okltest_rt_p(f) := block([x],
00033   assert(f([]) = true),
00034   assert(f(0) = false),
00035   assert(f({}) = false),
00036   assert(f(x) = false),
00037   assert(f([[]]) = true),
00038   assert(f([1]) = false),
00039   assert(f([[[]]]) = true),
00040   assert(f([[],[[]],[[],[]],[]]) = true),
00041   assert(f([[],[[]],[[],[]],[1,[]]]) = false),
00042   true)$
00043 
00044 okltest_rt2_p(f) := (
00045   assert(f([]) = true),
00046   assert(f([[]]) = false),
00047   assert(f([[],[]]) = true),
00048   assert(f([[],[],[]]) = false),
00049   assert(f([[[]],[]]) = false),
00050   assert(f([[[],[]],[]]) = true),
00051   assert(f([[[],[]],[[]]]) = false),
00052   assert(f([[[],[]],[[],[]]]) = true),
00053   assert(f([[[],[],[]],[[],[]]]) = false),
00054   assert(f([[[],[]],[[],[],[]]]) = false),
00055   true)$
00056 
00057 okltest_lvs(f) := (
00058   assert(f([]) = {[]}),
00059   assert(f([[]]) = {[1]}),
00060   assert(f([[[]]]) = {[1,1]}),
00061   assert(f([[],[]]) = {[1],[2]}),
00062   assert(f([[],[],[[]]]) = {[1],[2],[3,1]}),
00063   true)$
00064 
00065 okltest_nds(f) := (
00066   assert(f([]) = {[]}),
00067   assert(f([[]]) = {[],[1]}),
00068   assert(f([[[]]]) = {[],[1],[1,1]}),
00069   assert(f([[],[]]) = {[],[1],[2]}),
00070   assert(f([[],[],[[]]]) = {[],[1],[2],[3],[3,1]}),
00071   true)$
00072 
00073 okltest_subtree(f) := block([T,S],
00074   assert(f([],[]) = []),
00075   assert(f([[]],[]) = [[]]),
00076   assert(f([[]],[1]) = []),
00077   T : [[[]]], S : f(T,[1]),
00078   assert(S = [[]]),
00079   S[1] : [[],[]],
00080   assert(T=[[[[],[]]]]),
00081   true)$
00082 
00083 okltest_dst(f) := (
00084   assert(dst([],[]) = {}),
00085   assert(dst([[]],[]) = {[1]}),
00086   assert(dst([[]],[1]) = {}),
00087   assert(dst([[],[],[]],[]) = {[1],[2],[3]}),
00088   assert(dst([[[]],[[],[]],[]],[2]) = {[2,1],[2,2]}),
00089   true)$
00090 
00091 
00092 /* ****************************
00093    * Labelled rooted trees    *
00094    ****************************
00095 */
00096 
00097 okltest_lrt_p(f) := block([x],
00098   assert(f(0) = false),
00099   assert(f([]) = false),
00100   assert(f([[]]) = true),
00101   assert(f([0]) = true),
00102   assert(f([0,[]]) = false),
00103   assert(f([0,0]) = false),
00104   assert(f([0,[0]]) = true),
00105   /* XXX */
00106   true)$
00107 
00108 okltest_ndrep2l_lrt(f) := block([x,y],
00109   assert(f([], [x]) = x),
00110   assert(f([1], [x, [y]]) = y),
00111   assert(f([2], [0, [x], [y]]) = y),
00112   assert(f([1,2], [0, [0, [x], [y]]]) = y),
00113   true)$
00114 
00115 okltest_l2ult(f) := block([x],
00116   assert(f([0]) = []),
00117   assert(f([x]) = []),
00118   assert(f([x,[1],[2]]) = [[],[]]),
00119   assert(f([x,[x,[1],[2]],[x,[x],[x,[x]]]]) = [[[],[]], [[],[[]]]]),
00120   true)$
00121 
00122 okltest_lmap_lrt(f) := (
00123   assert(f([1], identity) = [1]),
00124   assert(f([1], lambda([x],x+1)) = [2]),
00125   assert(f([1,[2],[3]], identity) = [1,[2],[3]]),
00126   assert(f([1,[2],[3]], lambda([x],x+1)) = [2,[3],[4]]),
00127   true)$
00128 
00129 okltest_rt2lrt_il(f) := block([x,y],
00130   assert(f([],[],x) = [x]),
00131   assert(f([],[1],x) = [x]),
00132   assert(f([[],[]], [x], y) = [x, [y], [y]]),
00133   assert(f([[],[]], [x,1], y) = [x, [y], [y]]),
00134   assert(f([[[]]], [1,2], x) = [1, [2, [x]]]),
00135   assert(f([[[]]], [1,2,y], x) = [1, [2, [x]]]),
00136   assert(f([[[]],[[]]], [1,2,3], x) = [1, [2,[x]], [3,[x]]]),
00137   true)$
00138 
00139 okltest_ll_lrt(f) := (
00140   assert(f([1]) = {1}),
00141   assert(f([1,[2]]) = {2}),
00142   assert(f([1,[2],[3]]) = {2,3}),
00143   assert(f([1,[2,[4],[5]],[3]]) = {4,5,3}),
00144   true)$
00145 
00146 okltest_lll_lrt(f) := (
00147   assert(f([1]) = [1]),
00148   assert(f([1,[2]]) = [2]),
00149   assert(f([1,[2],[3]]) = [2,3]),
00150   assert(f([1,[2,[4],[5]],[3]]) = [4,5,3]),
00151   true)$
00152 
00153 okltest_il_lrt(f) := (
00154   assert(f([1]) = {}),
00155   assert(f([1,[2]]) = {1}),
00156   assert(f([1,[2],[3]]) = {1}),
00157   assert(f([1,[2,[4],[5]],[3]]) = {1,2}),
00158   true)$
00159 
00160 okltest_l_lrt(f) := (
00161   assert(f([1]) = {1}),
00162   assert(f([1,[2]]) = {1,2}),
00163   assert(f([1,[2],[3]]) = {1,2,3}),
00164   assert(f([1,[2,[4],[5]],[3]]) = {1,2,4,5,3}),
00165   true)$
00166 
00167 okltest_preorderl_lrt(f) := (
00168   assert(f([0]) = [0]),
00169   assert(f([0,[1]]) = [0,1]),
00170   assert(f([0,[1],[1]]) = [0,1,1]),
00171   assert(f([0,[1,[3],[4],[5]],[2]]) = [0,1,3,4,5,2]),
00172   true)$
00173 
00174 okltest_levelorderl_lrt(f) := (
00175   assert(f([0]) = [0]),
00176   assert(f([0,[1]]) = [0,1]),
00177   assert(f([0,[1],[1]]) = [0,1,1]),
00178   assert(f([0,[1,[3],[4],[5]],[2]]) = [0,1,2,3,4,5]),
00179   true)$
00180 
00181 okltest_depth_annotation_g_lrt(f) := block([x],
00182   assert(f([0],x) = [[0,x]]),
00183   assert(f([0,[1],[2]],x) = [[0,x],[[1,x+1]],[[2,x+1]]]),
00184   true)$
00185 
00186 okltest_depth_annotation_lrt(f) := (
00187   assert(f([0]) = [[0,0]]),
00188   assert(f([0,[1,[2,[3]]]]) = [[0,0],[[1,1],[[2,2],[[3,3]]]]]),
00189   true)$
00190 
00191 
00192 /* ************
00193    * Measures *
00194    ************
00195 */
00196 
00197 okltest_nnds_rt(f) := (
00198   assert(f([]) = 1),
00199   assert(f([[]]) = 2),
00200   assert(f([[[]]]) = 3),
00201   assert(f([[],[]]) = 3),
00202   assert(f([[],[],[]]) = 4),
00203   assert(f([[[]],[[[]]],[],[[],[[]]]]) = 11),
00204   true)$
00205 
00206 okltest_nnds_lrt(f) := block([x],
00207   assert(f([x]) = 1),
00208   assert(f([x,[x],[x],[x]]) = 4),
00209   assert(f([x,[x,[x,[x]]]]) = 4),
00210   assert(f([x, [x,[x]], [x, [x], [x,[x]]]]) = 7),
00211   true)$
00212 
00213 okltest_nlvs_rt(f) := (
00214   assert(f([]) = 1),
00215   assert(f([[]]) = 1),
00216   assert(f([[[]]]) = 1),
00217   assert(f([[],[]]) = 2),
00218   assert(f([[],[],[]]) = 3),
00219   assert(f([[],[[[]]],[]]) = 3),
00220   assert(f([[[]],[[[]]],[],[[],[[]]]]) = 5),
00221   true)$
00222 
00223 okltest_nlvs_lrt(f) := block([x],
00224   assert(f([x]) = 1),
00225   assert(f([x,[x],[x],[x]]) = 3),
00226   assert(f([x,[x,[x,[x]]]]) = 1),
00227   assert(f([x, [x,[x]], [x, [x], [x,[x]]]]) = 3),
00228   true)$
00229 
00230 okltest_ninds_rt(f) := (
00231   assert(f([]) = 0),
00232   assert(f([[]]) = 1),
00233   assert(f([[[]]]) = 2),
00234   assert(f([[],[]]) = 1),
00235   assert(f([[],[],[]]) = 1),
00236   assert(f([[[]],[[[]]],[],[[],[[]]]]) = 6),
00237   true)$
00238 
00239 okltest_ninds_lrt(f) := block([x],
00240   assert(f([x]) = 0),
00241   assert(f([x,[x],[x],[x]]) = 1),
00242   assert(f([x,[x,[x,[x]]]]) = 3),
00243   assert(f([x, [x,[x]], [x, [x], [x,[x]]]]) = 4),
00244   true)$
00245 
00246 okltest_height_rt(f) := (
00247   assert(f([]) = 0),
00248   assert(f([[]]) = 1),
00249   assert(f([[[]]]) = 2),
00250   assert(f([[[]],[[[]]]]) = 3),
00251   assert(f([[],[],[],[]]) = 1),
00252   true)$
00253 
00254 okltest_levelled_height_rt(f) := (
00255   assert(f([]) = 0),
00256   assert(f([[]]) = 0),
00257   assert(f([[[]]]) = 0),
00258   assert(f([[],[]]) = 1),
00259   assert(f([[[[[]]]],[]]) = 1),
00260   assert(f([[],[[],[]]]) = 1),
00261   assert(f([[],[[],[[],[]]]]) = 1),
00262   assert(f([[[],[]],[[],[]]]) = 2),
00263   for d : 0 thru 3 do
00264     for q : 2 thru 3 do
00265       assert(f(complete_rt(d,q)) = d),
00266   true)$
00267 
00268 
00269 /* ****************
00270    * Transformers *
00271    ****************
00272 */
00273 
00274 okltest_g2lrt(f) := (
00275   assert(f([{1},{}],1) = [1]),
00276   assert(f([{1,2},{{1,2}}],1) = [1,[2]]),
00277   assert(f([{1,2},{{1,2}}],2) = [2,[1]]),
00278   assert(f([{1,2,3},{{1,2},{1,3}}],1) = [1,[2],[3]]),
00279   assert(f([{1,2,3},{{1,2},{1,3}}],2) = [2,[1,[3]]]),
00280   assert(f([{1,2,3},{{1,2},{1,3}}],3) = [3,[1,[2]]]),
00281   true)$
00282 
00283 
00284 /* **************
00285    * Generators *
00286    **************
00287 */
00288 
00289 okltest_complete_rt(f) := (
00290   /* XXX */
00291   true)$
00292 
00293 okltest_random_lrt(f) := (
00294   /* XXX */
00295   true)$
00296 
00297 okltest_all2_rt(f) := (
00298   assert(f(1) = [[]]),
00299   assert(f(3) = [[[],[]]]),
00300   assert(f(5) = [[[],[[],[]]], [[[],[]], []]]),
00301   /* XXX */
00302   true)$
00303 
00304 okltest_num_all2_rt(f) := (
00305   for m in (1 .. 2 .. 11) do
00306     assert(f(m) = length(all2_rt(m))),
00307   true)$
00308 
00309 okltest_all2i_rt(f) := (
00310   assert(f(0) = [[]]),
00311   assert(f(1) = [[[],[]]]),
00312   assert(f(2) = [[[],[[],[]]], [[[],[]], []]]),
00313   /* XXX */
00314   true)$
00315 
00316 okltest_num_all2i_rt(f) := (
00317   for m in (0 .. 6) do
00318     assert(f(m) = length(all2i_rt(m))),
00319   true)$
00320 
00321 okltest_all2l_rt(f) := (
00322   assert(f(1) = [[]]),
00323   assert(f(2) = [[[],[]]]),
00324   assert(f(3) = [[[],[[],[]]], [[[],[]], []]]),
00325   /* XXX */
00326   true)$
00327 
00328 okltest_num_all2l_rt(f) := (
00329   for m in (1 .. 6) do
00330     assert(f(m) = length(all2l_rt(m))),
00331   true)$
00332 
00333 okltest_random2_rt(f) := block([x],
00334   assert(f(1) = []),
00335   assert(f(3) = [[],[]]),
00336   set_random(0),
00337   assert(f(5) = [[],[[],[]]]),
00338   assert(f(5) = [[[],[]],[]]),
00339   assert(f(7) = [[[],[[],[]]],[]]),
00340   assert(f(7) = [[[],[]],[[],[]]]),
00341   assert(f(7) = [[],[[[],[]],[]]]),
00342   assert(f(9) = [[[[],[]],[[],[]]],[]]),
00343   true)$
00344 
00345 okltest_random12_rt(f) := block([x],
00346   assert(f(1) = []),
00347   assert(f(2) = [[]]),
00348   set_random(0),
00349   assert(f(3) = [[[]]]),
00350   assert(f(4) = [[[[]]]]),
00351   assert(f(5) = [[[[[]]]]]),
00352   assert(f(3) = [[],[]]),
00353   assert(f(4) = [[[],[]]]),
00354   assert(f(5) = [[[[]]],[]]),
00355   assert(f(6) = [[[]],[[[]]]]),
00356   true)$
00357     
00358 okltest_all_rt(f) := (
00359   assert(f(-1) = []),
00360   assert(f(0) = []),
00361   assert(f(1) = [ [] ]),
00362   assert(f(2) = [ [[]] ]),
00363   assert(f(3) = [ [[],[]], [[[]]] ]),
00364   true)$
00365 
00366 okltest_num_all_rt(f) := (
00367   for m in (1 .. 7) do
00368     assert(f(m) = length(all_rt(m))),
00369   true)$
00370 
00371 okltest_catalan_number(f) := (
00372   /* XXX */
00373   true)$
00374 
00375 
00376 /* **************
00377    * Operations *
00378    **************
00379 */
00380 
00381 okltest_mirror_rt(f) := (
00382   assert(f([]) = []),
00383   assert(f([[],[[]]]) = [[[]],[]]),
00384   assert(f([[[]],[]]) = [[],[[]]]),
00385   assert(f([[[],[[]]],[]]) = [[],[[[]],[]]]),
00386   assert(f([[[],[[]]],[[[]],[]]]) = [[[],[[]]],[[[]],[]]]),
00387   /* XXX */
00388   true)$
00389 
00390 okltest_tdlrt_p(f) := block([label],
00391   assert(f(0) = false),
00392   assert(f([]) = false),
00393   assert(f([[]]) = false),
00394   assert(f([[1,2]]) = false),
00395   assert(f([[[]]]) = false),
00396   assert(f([[[1]]]) = false),
00397   assert(f([[[0,0]]]) = true),
00398   assert(f([[[0,0]],[[[1,2]]],[[[3,4]]]]) = true),
00399   assert(f([[[0,0]],[[[1,2]],[4,4]],[[[3,4]]]]) = false),
00400   assert(f([[[1,2]],[[[3,4],label]]]) = true ),
00401   true)$
00402 
00403 okltest_trans_lrt(f) := block([label],
00404   assert(f([[[1,2]]],[3,1]) = [[[4,3]]]),
00405   assert(f([[[1,2]],[[[3,4],label]]],[4,4]) = [[[5,6]],[[[7,8],label]]]),
00406   assert(f([[[1,2],label],[[[3,4]],[[[5,4],label],[[[8,7]]]]],[[[2,2]]]],[9,5]) = [[[10,7],label],[[[12,9]],[[[14,9],label],[[[17,12]]]]],[[[11,7]]]]),
00407   true)$
00408 
00409 okltest_y_extreme_tdlrt(f) := (
00410   assert(f([[[0,0]]]) = 0),
00411   assert(f([[[0,0]],[[[-1,-1]]],[[[1,-1]]]]) = -1),  
00412   assert(f([[[0,0]],[[[-2,-1]],[[[-3,-2]]],[[[-1,-2]]]],[[[2,-1]]]]) = -2),
00413   assert(f([[[0,0]],[[[-2,-1]]],[[[2,-1]],[[[1,-2]]],[[[3,-2]]]]]) = -2),
00414   assert(f([[[0,0]],[[[-2,-1]],[[[-3,-2]]]],[[[2,-1]],[[[1,-2]]]]]) = -2),
00415   assert(f([[[0,0]],[[[0,-1]],[[[0,-2]],[[[0,-3]]]]]]) = -3),
00416   assert(f([[[0,0]],[[[-1,-1]],[[[-2,-2]],[[[-2,-3]]]],[[[0,-2]]]],[[[1,-1]]]]) = -3),
00417   assert(f([[[0,0]],[[[-1,-1]],[[[-1,-2]],[[[-1,-3]]]]],[[[1,-1]],[[[0,-2]]],[[[2,-2]],[[[2,-3]],[[[2,-4]],[[[2,-5]]]]]]]]) = -5),
00418   true)$
00419 
00420