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