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}