Source code

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