001/*
002 * $Id: WordPseudoReductionTest.java 5863 2018-07-20 11:13:34Z 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
015
016import edu.jas.arith.BigInteger;
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 WordPseudoReductionTest 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>WordPseudoReductionTest</CODE> object.
043     * @param name String
044     */
045    public WordPseudoReductionTest(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(WordPseudoReductionTest.class);
056        return suite;
057    }
058
059
060    GenWordPolynomialRing<BigInteger> fac;
061
062
063    WordFactory wfac;
064
065
066    BigInteger cfac;
067
068
069    GenWordPolynomial<BigInteger> a, b, c, d, e;
070
071
072    List<GenWordPolynomial<BigInteger>> L;
073
074
075    WordPseudoReductionSeq<BigInteger> 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 BigInteger(0);
091        wfac = new WordFactory("abcdef");
092        fac = new GenWordPolynomialRing<BigInteger>(cfac, wfac);
093        red = new WordPseudoReductionSeq<BigInteger>();
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 testIntReduction0() {
109        L = new ArrayList<GenWordPolynomial<BigInteger>>();
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<BigInteger>>();
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 testIntReduction() {
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<BigInteger>>();
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<BigInteger>>();
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 )", red.isNormalform(L, e));
183        assertTrue("e == 0", e.isZERO());
184    }
185
186
187    /**
188     * Test rational coefficient reduction with recording.
189     */
190    public void testIntReductionRecording() {
191        List<GenWordPolynomial<BigInteger>> 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<BigInteger>>();
206        L.add(a);
207        lrow = new ArrayList<GenWordPolynomial<BigInteger>>(L.size());
208        rrow = new ArrayList<GenWordPolynomial<BigInteger>>(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<BigInteger>>(L.size());
223        rrow = new ArrayList<GenWordPolynomial<BigInteger>>(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<BigInteger>>(L.size());
237        rrow = new ArrayList<GenWordPolynomial<BigInteger>>(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<BigInteger>>(L.size());
251        rrow = new ArrayList<GenWordPolynomial<BigInteger>>(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
268
269    /**
270     * Test rational S-polynomial.
271     */
272    public void testIntSpolynomial() {
273        do {
274            a = fac.random(kl, ll, el);
275        } while (a.isZERO());
276        do {
277            b = fac.random(kl, ll, el);
278        } while (b.isZERO());
279        //System.out.println("a = " + a);
280        //System.out.println("b = " + b);
281        Word de = new Word(wfac, "a");
282        a = a.multiply(wfac.getONE(), de);
283        b = b.multiply(de, wfac.getONE());
284        //System.out.println("a = " + a);
285        //System.out.println("b = " + b);
286
287        Word ae = a.leadingWord();
288        Word be = b.leadingWord();
289        //System.out.println("ae = " + ae);
290        //System.out.println("be = " + be);
291
292        List<GenWordPolynomial<BigInteger>> S = red.SPolynomials(a, b);
293        //System.out.println("S = " + S);
294        OverlapList oll = ae.overlap(be);
295        //System.out.println("oll = " + oll);
296        for (GenWordPolynomial<BigInteger> s : S) {
297            //System.out.println("s = " + s);
298            Word ee = s.leadingWord();
299            //System.out.println("ee = " + ee);
300            boolean t = false;
301            Word ce = fac.alphabet.getONE();
302            for (Overlap ol : oll.ols) {
303                ce = ol.l1.multiply(ae).multiply(ol.r1);
304                //System.out.println("ce = " + ce);
305                if (fac.alphabet.getAscendComparator().compare(ce, ee) > 0) {
306                    t = true;
307                    break;
308                }
309            }
310            assertTrue("ce > ee: " + ce + " > " + ee, t);
311            // findbugs
312        }
313    }
314
315}