001/* 002 * $Id: WordReductionTest.java 5300 2015-08-16 14:22:16Z kredel $ 003 */ 004 005package edu.jas.gb; 006 007 008import java.util.ArrayList; 009import java.util.List; 010 011import junit.framework.Test; 012import junit.framework.TestCase; 013import junit.framework.TestSuite; 014 015import org.apache.log4j.BasicConfigurator; 016 017import edu.jas.arith.BigRational; 018import edu.jas.poly.GenWordPolynomial; 019import edu.jas.poly.GenWordPolynomialRing; 020import edu.jas.poly.Overlap; 021import edu.jas.poly.OverlapList; 022import edu.jas.poly.Word; 023import edu.jas.poly.WordFactory; 024 025 026/** 027 * Word reduction tests with JUnit. 028 * @author Heinz Kredel. 029 */ 030 031public class WordReductionTest extends TestCase { 032 033 034 /** 035 * main 036 */ 037 public static void main(String[] args) { 038 BasicConfigurator.configure(); 039 junit.textui.TestRunner.run(suite()); 040 } 041 042 043 /** 044 * Constructs a <CODE>WordReductionTest</CODE> object. 045 * @param name String 046 */ 047 public WordReductionTest(String name) { 048 super(name); 049 } 050 051 052 /** 053 * suite. 054 * @return a test suite. 055 */ 056 public static Test suite() { 057 TestSuite suite = new TestSuite(WordReductionTest.class); 058 return suite; 059 } 060 061 062 GenWordPolynomialRing<BigRational> fac; 063 064 065 WordFactory wfac; 066 067 068 BigRational cfac; 069 070 071 GenWordPolynomial<BigRational> a, b, c, d, e; 072 073 074 List<GenWordPolynomial<BigRational>> L; 075 076 077 WordReductionSeq<BigRational> red; 078 079 080 int kl = 3; 081 082 083 int ll = 7; 084 085 086 int el = 5; 087 088 089 @Override 090 protected void setUp() { 091 a = b = c = d = e = null; 092 cfac = new BigRational(0); 093 wfac = new WordFactory("abcdef"); 094 fac = new GenWordPolynomialRing<BigRational>(cfac, wfac); 095 red = new WordReductionSeq<BigRational>(); 096 } 097 098 099 @Override 100 protected void tearDown() { 101 a = b = c = d = e = null; 102 fac = null; 103 red = null; 104 } 105 106 107 /** 108 * Test constants and empty list reduction. 109 */ 110 public void testRatReduction0() { 111 L = new ArrayList<GenWordPolynomial<BigRational>>(); 112 113 a = fac.random(kl, ll, el); 114 c = fac.getONE(); 115 d = fac.getZERO(); 116 117 e = red.normalform(L, c); 118 assertTrue("isONE( e )", e.isONE()); 119 e = red.normalform(L, d); 120 assertTrue("isZERO( e )", e.isZERO()); 121 122 L.add(c); 123 e = red.normalform(L, c); 124 assertTrue("isZERO( e )", e.isZERO()); 125 e = red.normalform(L, a); 126 assertTrue("isZERO( e )", e.isZERO()); 127 e = red.normalform(L, d); 128 assertTrue("isZERO( e )", e.isZERO()); 129 130 L = new ArrayList<GenWordPolynomial<BigRational>>(); 131 L.add(d); 132 e = red.normalform(L, c); 133 assertTrue("isONE( e )", e.isONE()); 134 e = red.normalform(L, d); 135 assertTrue("isZERO( e )", e.isZERO()); 136 } 137 138 139 /** 140 * Test rational coefficient reduction. 141 */ 142 public void testRatReduction() { 143 do { 144 a = fac.random(kl, ll, el); 145 } while (a.isZERO()); 146 do { 147 b = fac.random(kl, ll, el); 148 } while (b.isZERO()); 149 //System.out.println("a = " + a); 150 //System.out.println("b = " + b); 151 152 L = new ArrayList<GenWordPolynomial<BigRational>>(); 153 L.add(a); 154 155 e = red.normalform(L, a); 156 //System.out.println("e = " + e); 157 assertTrue("isZERO( e )", e.isZERO()); 158 159 L.add(b); 160 e = red.normalform(L, a); 161 //System.out.println("e = " + e); 162 assertTrue("isZERO( e ) some times", e.isZERO()); 163 164 L = new ArrayList<GenWordPolynomial<BigRational>>(); 165 L.add(a); 166 assertTrue("isTopRed( a )", red.isTopReducible(L, a)); 167 assertTrue("isRed( a )", red.isReducible(L, a)); 168 L.add(b); 169 assertTrue("isTopRed( b )", red.isTopReducible(L, b)); 170 assertTrue("isRed( b )", red.isReducible(L, b)); 171 172 c = fac.random(kl, ll, el); 173 //System.out.println("c = " + c); 174 e = red.normalform(L, c); 175 //System.out.println("e = " + e); 176 assertTrue("isNF( e )", red.isNormalform(L, e)); 177 178 Word u = new Word(wfac, "f"); 179 Word v = new Word(wfac, "abc"); 180 c = a.multiply(cfac.getONE(), u, v); 181 //System.out.println("c = " + c); 182 e = red.normalform(L, c); 183 //System.out.println("e = " + e); 184 assertTrue("isNF( e )", red.isNormalform(L, e)); 185 assertTrue("e == 0", e.isZERO()); 186 } 187 188 189 /** 190 * Test rational coefficient reduction with recording. 191 */ 192 public void testRatReductionRecording() { 193 List<GenWordPolynomial<BigRational>> lrow, rrow = null; 194 do { 195 a = fac.random(kl, ll, el); 196 } while (a.isZERO()); 197 do { 198 b = fac.random(kl, ll, el); 199 } while (b.isZERO()); 200 c = fac.random(kl, ll, el); 201 d = fac.random(kl, ll, el); 202 //System.out.println("a = " + a); 203 //System.out.println("b = " + b); 204 //System.out.println("c = " + c); 205 //System.out.println("d = " + d); 206 207 L = new ArrayList<GenWordPolynomial<BigRational>>(); 208 L.add(a); 209 lrow = new ArrayList<GenWordPolynomial<BigRational>>(L.size()); 210 rrow = new ArrayList<GenWordPolynomial<BigRational>>(L.size()); 211 e = fac.getZERO(); 212 for (int m = 0; m < L.size(); m++) { 213 lrow.add(e); 214 rrow.add(e); 215 } 216 e = red.normalform(lrow, rrow, L, a); 217 //System.out.println("e = " + e); 218 //System.out.println("lrow = " + lrow); 219 //System.out.println("rrow = " + rrow); 220 assertTrue("isZERO( e )", e.isZERO()); 221 assertTrue("is Reduction ", red.isReductionNF(lrow, rrow, L, a, e)); 222 223 L.add(b); 224 lrow = new ArrayList<GenWordPolynomial<BigRational>>(L.size()); 225 rrow = new ArrayList<GenWordPolynomial<BigRational>>(L.size()); 226 e = fac.getZERO(); 227 for (int m = 0; m < L.size(); m++) { 228 lrow.add(e); 229 rrow.add(e); 230 } 231 e = red.normalform(lrow, rrow, L, b); 232 //System.out.println("e = " + e); 233 //System.out.println("lrow = " + lrow); 234 //System.out.println("rrow = " + rrow); 235 assertTrue("is Reduction ", red.isReductionNF(lrow, rrow, L, b, e)); 236 237 L.add(c); 238 lrow = new ArrayList<GenWordPolynomial<BigRational>>(L.size()); 239 rrow = new ArrayList<GenWordPolynomial<BigRational>>(L.size()); 240 e = fac.getZERO(); 241 for (int m = 0; m < L.size(); m++) { 242 lrow.add(e); 243 rrow.add(e); 244 } 245 e = red.normalform(lrow, rrow, L, c); 246 //System.out.println("e = " + e); 247 //System.out.println("lrow = " + lrow); 248 //System.out.println("rrow = " + rrow); 249 assertTrue("is Reduction ", red.isReductionNF(lrow, rrow, L, c, e)); 250 251 L.add(d); 252 lrow = new ArrayList<GenWordPolynomial<BigRational>>(L.size()); 253 rrow = new ArrayList<GenWordPolynomial<BigRational>>(L.size()); 254 e = fac.getZERO(); 255 for (int m = 0; m < L.size(); m++) { 256 lrow.add(e); 257 rrow.add(e); 258 } 259 Word u = new Word(wfac, "f"); 260 Word v = new Word(wfac, "abc"); 261 d = a.multiply(cfac.random(3), u, v); 262 //System.out.println("d = " + d); 263 e = red.normalform(lrow, rrow, L, d); 264 //System.out.println("e = " + e); 265 //System.out.println("lrow = " + lrow); 266 //System.out.println("rrow = " + rrow); 267 assertTrue("is Reduction ", red.isReductionNF(lrow, rrow, L, d, e)); 268 269 wfac = new WordFactory("l d"); 270 fac = new GenWordPolynomialRing<BigRational>(cfac, wfac); 271 //a = fac.parse("3 l l + 2 d"); 272 //b = fac.parse("1"); 273 a = fac.parse("81 l l l l l l - 36 l l l + 4"); 274 b = fac.parse("9 l l l - 2"); 275 //System.out.println("a = " + a); 276 //System.out.println("b = " + b); 277 278 L = new ArrayList<GenWordPolynomial<BigRational>>(); 279 L.add(b); 280 //System.out.println("L = " + L); 281 lrow = new ArrayList<GenWordPolynomial<BigRational>>(L.size()); 282 rrow = new ArrayList<GenWordPolynomial<BigRational>>(L.size()); 283 e = fac.getZERO(); 284 for (int m = 0; m < L.size(); m++) { 285 lrow.add(e); 286 rrow.add(e); 287 } 288 e = red.normalform(lrow, rrow, L, a); 289 //System.out.println("e = " + e); 290 //System.out.println("lrow = " + lrow); 291 //System.out.println("rrow = " + rrow); 292 assertTrue("is Reduction ", red.isReductionNF(lrow, rrow, L, a, e)); 293 } 294 295 296 /** 297 * Test rational S-polynomial. 298 */ 299 public void testRatSpolynomial() { 300 do { 301 a = fac.random(kl, ll, el); 302 } while (a.isZERO()); 303 do { 304 b = fac.random(kl, ll, el); 305 } while (b.isZERO()); 306 //System.out.println("a = " + a); 307 //System.out.println("b = " + b); 308 Word de = new Word(wfac, "a"); 309 a = a.multiply(wfac.getONE(), de); 310 b = b.multiply(de, wfac.getONE()); 311 //System.out.println("a = " + a); 312 //System.out.println("b = " + b); 313 314 Word ae = a.leadingWord(); 315 Word be = b.leadingWord(); 316 //System.out.println("ae = " + ae); 317 //System.out.println("be = " + be); 318 319 List<GenWordPolynomial<BigRational>> S = red.SPolynomials(a, b); 320 //System.out.println("S = " + S); 321 OverlapList oll = ae.overlap(be); 322 //System.out.println("oll = " + oll); 323 for (GenWordPolynomial<BigRational> s : S) { 324 //System.out.println("s = " + s); 325 Word ee = s.leadingWord(); 326 //System.out.println("ee = " + ee); 327 boolean t = false; 328 Word ce = fac.alphabet.getONE(); 329 for (Overlap ol : oll.ols) { 330 ce = ol.l1.multiply(ae).multiply(ol.r1); 331 //System.out.println("ce = " + ce); 332 if (fac.alphabet.getAscendComparator().compare(ce, ee) > 0) { 333 t = true; 334 break; 335 } 336 } 337 assertTrue("ce > ee: " + ce + " > " + ee, t); 338 // findbugs 339 } 340 } 341 342}