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}