Source code

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