001/* 002 * $Id: WordPseudoReductionTest.java 5042 2014-12-29 12:32:59Z kredel $ 003 */ 004 005package edu.jas.gbufd; 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.BigInteger; 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 WordPseudoReductionTest 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>WordPseudoReductionTest</CODE> object. 045 * @param name String 046 */ 047 public WordPseudoReductionTest(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(WordPseudoReductionTest.class); 058 return suite; 059 } 060 061 062 GenWordPolynomialRing<BigInteger> fac; 063 064 065 WordFactory wfac; 066 067 068 BigInteger cfac; 069 070 071 GenWordPolynomial<BigInteger> a, b, c, d, e; 072 073 074 List<GenWordPolynomial<BigInteger>> L; 075 076 077 WordPseudoReductionSeq<BigInteger> 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 BigInteger(0); 093 wfac = new WordFactory("abcdef"); 094 fac = new GenWordPolynomialRing<BigInteger>(cfac, wfac); 095 red = new WordPseudoReductionSeq<BigInteger>(); 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 testIntReduction0() { 111 L = new ArrayList<GenWordPolynomial<BigInteger>>(); 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<BigInteger>>(); 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 testIntReduction() { 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<BigInteger>>(); 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<BigInteger>>(); 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 testIntReductionRecording() { 193 List<GenWordPolynomial<BigInteger>> 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<BigInteger>>(); 208 L.add(a); 209 lrow = new ArrayList<GenWordPolynomial<BigInteger>>(L.size()); 210 rrow = new ArrayList<GenWordPolynomial<BigInteger>>(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<BigInteger>>(L.size()); 225 rrow = new ArrayList<GenWordPolynomial<BigInteger>>(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<BigInteger>>(L.size()); 239 rrow = new ArrayList<GenWordPolynomial<BigInteger>>(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<BigInteger>>(L.size()); 253 rrow = new ArrayList<GenWordPolynomial<BigInteger>>(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 270 271 /** 272 * Test rational S-polynomial. 273 */ 274 public void testIntSpolynomial() { 275 do { 276 a = fac.random(kl, ll, el); 277 } while (a.isZERO()); 278 do { 279 b = fac.random(kl, ll, el); 280 } while (b.isZERO()); 281 //System.out.println("a = " + a); 282 //System.out.println("b = " + b); 283 Word de = new Word(wfac, "a"); 284 a = a.multiply(wfac.getONE(), de); 285 b = b.multiply(de, wfac.getONE()); 286 //System.out.println("a = " + a); 287 //System.out.println("b = " + b); 288 289 Word ae = a.leadingWord(); 290 Word be = b.leadingWord(); 291 //System.out.println("ae = " + ae); 292 //System.out.println("be = " + be); 293 294 List<GenWordPolynomial<BigInteger>> S = red.SPolynomials(a, b); 295 //System.out.println("S = " + S); 296 OverlapList oll = ae.overlap(be); 297 //System.out.println("oll = " + oll); 298 for (GenWordPolynomial<BigInteger> s : S) { 299 //System.out.println("s = " + s); 300 Word ee = s.leadingWord(); 301 //System.out.println("ee = " + ee); 302 boolean t = false; 303 Word ce = fac.alphabet.getONE(); 304 for (Overlap ol : oll.ols) { 305 ce = ol.l1.multiply(ae).multiply(ol.r1); 306 //System.out.println("ce = " + ce); 307 if (fac.alphabet.getAscendComparator().compare(ce, ee) > 0) { 308 t = true; 309 break; 310 } 311 } 312 assertTrue("ce > ee: " + ce + " > " + ee, t); 313 // findbugs 314 } 315 } 316 317}