001/*
002 * $Id: WordTest.java 5292 2015-08-05 21:54:16Z kredel $
003 */
004
005package edu.jas.poly;
006
007
008import java.util.Collection;
009import java.util.List;
010import java.util.SortedMap;
011import java.util.Arrays;
012
013import junit.framework.Test;
014import junit.framework.TestCase;
015import junit.framework.TestSuite;
016
017import org.apache.log4j.BasicConfigurator;
018
019
020/**
021 * Word and WordFactory tests with JUnit. Tests construction and arithmetic
022 * operations.
023 * @author Heinz Kredel.
024 */
025
026public class WordTest extends TestCase {
027
028
029    /**
030     * main.
031     */
032    public static void main(String[] args) {
033        BasicConfigurator.configure();
034        junit.textui.TestRunner.run(suite());
035    }
036
037
038    /**
039     * Constructs a <CODE>WordTest</CODE> object.
040     * @param name String.
041     */
042    public WordTest(String name) {
043        super(name);
044    }
045
046
047    /**
048     */
049    public static Test suite() {
050        TestSuite suite = new TestSuite(WordTest.class);
051        return suite;
052    }
053
054
055    //private final static int bitlen = 100;
056
057    Word a;
058
059
060    Word b;
061
062
063    Word c;
064
065
066    Word d;
067
068
069    @Override
070    protected void setUp() {
071        a = b = c = d = null;
072    }
073
074
075    @Override
076    protected void tearDown() {
077        a = b = c = d = null;
078    }
079
080
081    /**
082     * Test constructor and toString.
083     */
084    public void testConstructor() {
085        WordFactory wf = new WordFactory("abcdefg");
086        a = new Word(wf);
087        b = a;
088        //System.out.println("a = " + a);
089        assertEquals("() = ()", a, b);
090        assertEquals("length( () ) = 0", a.length(), 0);
091        assertTrue("isONE( () )", a.isONE());
092        assertTrue("isUnit( () )", a.isUnit());
093
094        b = new Word(wf, "abc");
095        c = wf.parse(" a b c ");
096        //System.out.println("b = " + b);
097        //System.out.println("c = " + c);
098        assertEquals("b = c: ", b, c);
099
100        assertFalse("isONE( () )", b.isONE());
101        assertFalse("isUnit( () )", b.isUnit());
102        assertFalse("isONE( () )", c.isONE());
103        assertFalse("isUnit( () )", c.isUnit());
104
105        String s = b.toString();
106        String t = c.toString();
107        //System.out.println("s = " + s);
108        //System.out.println("t = " + t);
109        assertEquals("s = t: ", s, t);
110    }
111
112
113    /**
114     * Test word factory.
115     */
116    public void testFactory() {
117        WordFactory wf = new WordFactory("abcdefg");
118        //System.out.println("wf = " + wf);
119        Word w = wf.getONE();
120        //System.out.println("w = " + w);
121        assertTrue("w == (): ", w.isONE());
122
123        w = wf.parse("aaabbbcccaaa");
124        //System.out.println("w = " + w);
125        assertFalse("w != (): ", w.isONE());
126
127        a = wf.parse(w.toString());
128        //System.out.println("a = " + a);
129        assertEquals("w = a", a, w);
130
131        WordFactory wf2 = new WordFactory(w.toString());
132        //System.out.println("wf2 = " + wf2);
133
134        a = wf2.parse(w.toString());
135        //System.out.println("a = " + a);
136        assertEquals("w = a", a, w);
137
138        List<Word> gens = wf.generators();
139        //System.out.println("gens = " + gens);
140        assertTrue("#gens == 7: ", gens.size() == 7);
141        for (Word v : gens) {
142            a = wf.parse(v.toString());
143            assertEquals("a == v", a, v);
144        }
145    }
146
147
148    /**
149     * Test random word.
150     */
151    public void testRandom() {
152        WordFactory wf = new WordFactory("uvw");
153        //System.out.println("wf = " + wf);
154
155        a = wf.random(5);
156        b = wf.random(6);
157        c = wf.random(7);
158        //System.out.println("a = " + a);
159        //System.out.println("b = " + b);
160        //System.out.println("c = " + c);
161
162        assertFalse("a != (): ", a.isONE());
163        assertFalse("b != (): ", b.isONE());
164        assertFalse("c != (): ", c.isONE());
165        assertTrue("#a == 5", a.length() == 5);
166        assertTrue("#b == 6", b.length() == 6);
167        assertTrue("#c == 7", c.length() == 7);
168
169        SortedMap<String, Integer> ma = a.dependencyOnVariables();
170        SortedMap<String, Integer> mb = b.dependencyOnVariables();
171        SortedMap<String, Integer> mc = c.dependencyOnVariables();
172        //System.out.println("ma = " + ma);
173        //System.out.println("mb = " + mb);
174        //System.out.println("mc = " + mc);
175        assertTrue("#ma <= 3", ma.size() <= wf.length());
176        assertTrue("#mb <= 3", mb.size() <= wf.length());
177        assertTrue("#mc <= 3", mc.size() <= wf.length());
178        assertTrue("S ma <= #a", sum(ma.values()) == a.length());
179        assertTrue("S mb <= #b", sum(mb.values()) == b.length());
180        assertTrue("S mc <= #c", sum(mc.values()) == c.length());
181    }
182
183
184    int sum(Collection<Integer> li) {
185        int s = 0;
186        for (Integer i : li) {
187            s += i;
188        }
189        return s;
190    }
191
192
193    /**
194     * Test multiplication.
195     */
196    public void testMultiplication() {
197        WordFactory wf = new WordFactory("abcdefgx");
198        a = new Word(wf, "abc");
199        b = new Word(wf, "cddaa");
200        //System.out.println("a = " + a);
201        //System.out.println("b = " + b);
202
203        c = a.multiply(b);
204        //System.out.println("c = " + c);
205
206        assertTrue("divides: ", a.divides(c));
207        assertTrue("divides: ", b.divides(c));
208        assertTrue("multiple: ", c.multipleOf(a));
209        assertTrue("multiple: ", c.multipleOf(b));
210
211        d = c.divideRight(a);
212        //System.out.println("d = " + d);
213        assertEquals("d = b", d, b);
214
215        d = c.divideLeft(b);
216        //System.out.println("d = " + d);
217        assertEquals("d = a", d, a);
218
219        d = c.divide(c);
220        //System.out.println("d = " + d);
221        assertTrue("isONE( () )", d.isONE());
222
223        d = new Word(wf, "xx");
224        c = a.multiply(d).multiply(b);
225        //System.out.println("d = " + d);
226        //System.out.println("c = " + c);
227
228        assertTrue("divides: ", d.divides(c));
229        Word[] ret = c.divideWord(d,false);
230        //System.out.println("ret = " + ret[0] + ", " + ret[1]);
231
232        assertEquals("prefix(c/d) = a", a, ret[0]);
233        assertEquals("suffix(c/d) = b", b, ret[1]);
234
235        Word e = ret[0].multiply(d).multiply(ret[1]);
236        assertEquals("prefix(c/d) d suffix(c/d) = e", e, c);
237
238        ret = c.divideWord(d,true);
239        //System.out.println("ret = " + ret[0] + ", " + ret[1]);
240
241        assertEquals("prefix(c/d) = a", a, ret[0]);
242        assertEquals("suffix(c/d) = b", b, ret[1]);
243
244        e = ret[0].multiply(d).multiply(ret[1]);
245        assertEquals("prefix(c/d) d suffix(c/d) = e", e, c);
246    }
247
248
249    /**
250     * Test overlap.
251     */
252    public void testOverlap() {
253        WordFactory wf = new WordFactory("abcdefg");
254        a = new Word(wf, "abc");
255        b = new Word(wf, "ddabca");
256        //System.out.println("a = " + a);
257        //System.out.println("b = " + b);
258
259        OverlapList ol = a.overlap(b);
260        //System.out.println("ol = " + ol);
261        assertTrue("isOverlap: ", ol.isOverlap(a,b));
262
263        ol = b.overlap(a);
264        //System.out.println("ol = " + ol);
265        assertTrue("isOverlap: ", ol.isOverlap(b,a));
266
267        a = new Word(wf,   "abcfff");
268        b = new Word(wf, "ddabc");
269        //System.out.println("a = " + a);
270        //System.out.println("b = " + b);
271
272        ol = a.overlap(b);
273        //System.out.println("ol = " + ol);
274        assertTrue("isOverlap: ", ol.isOverlap(a,b));
275
276        ol = b.overlap(a);
277        //System.out.println("ol = " + ol);
278        assertTrue("isOverlap: ", ol.isOverlap(b,a));
279
280        a = new Word(wf, "fffabc");
281        b = new Word(wf,    "abcdd");
282        //System.out.println("a = " + a);
283        //System.out.println("b = " + b);
284
285        ol = a.overlap(b);
286        //System.out.println("ol = " + ol);
287        assertTrue("isOverlap: ", ol.isOverlap(a,b));
288
289        ol = b.overlap(a);
290        //System.out.println("ol = " + ol);
291        assertTrue("isOverlap: ", ol.isOverlap(b,a));
292
293        a = new Word(wf, "ab");
294        b = new Word(wf, "dabeabfabc");
295        //System.out.println("a = " + a);
296        //System.out.println("b = " + b);
297        ol = a.overlap(b);
298        //System.out.println("ol = " + ol);
299        assertTrue("isOverlap: ", ol.isOverlap(a,b));
300        ol = b.overlap(a);
301        //System.out.println("ol = " + ol);
302        assertTrue("isOverlap: ", ol.isOverlap(b,a));
303
304        a = new Word(wf, "abc");
305        b = new Word(wf, "abceabcfabc");
306        //System.out.println("a = " + a);
307        //System.out.println("b = " + b);
308        ol = a.overlap(b);
309        //System.out.println("ol = " + ol);
310        assertTrue("isOverlap: ", ol.isOverlap(a,b));
311        ol = b.overlap(a);
312        //System.out.println("ol = " + ol);
313        assertTrue("isOverlap: ", ol.isOverlap(b,a));
314
315        a = new Word(wf, "aa");
316        b = new Word(wf, "aaaaaaaaa");
317        //System.out.println("a = " + a);
318        //System.out.println("b = " + b);
319        ol = a.overlap(b);
320        //System.out.println("ol = " + ol);
321        assertTrue("isOverlap: ", ol.isOverlap(a,b));
322        ol = b.overlap(a);
323        //System.out.println("ol = " + ol);
324        assertTrue("isOverlap: ", ol.isOverlap(b,a));
325    }
326
327
328    /**
329     * Test valueOf.
330     */
331    public void testValueOf() {
332        String[] vars = new String[] { "a", "b", "c", "d" };
333        WordFactory wf = new WordFactory(vars);
334
335        ExpVector ef = ExpVector.random(4,5L,0.5f);
336        //System.out.println("ef = " + ef);
337
338        a = wf.valueOf(ef);
339        //System.out.println("a = " + a);
340        assertTrue("deg(ef) == deg(a): " + ef + ", " + a, ef.degree() == a.degree() );
341
342        String es = ef.toString(vars);
343        //System.out.println("es = " + es);
344        assertTrue("ef != ''" + ef, es.length() >= 0 );
345    }
346
347
348    /**
349     * Test constructor with multi-letter Strings.
350     */
351    public void testMultiLetters() {
352        String[] vars = new String[] {"a1", "b", " e23", "tt*", "x y" };
353        WordFactory wf = new WordFactory(vars);
354        //System.out.println("wf = " + wf);
355        String s = wf.toString();
356        assertEquals("w == vars: ", s, "\"a1,b,e23,tt,xy\"");
357
358        Word w = wf.parse("a1 a1 b*b*b tt xy e23 tt xy");
359        s = w.toString();
360        String t = "\"a1 a1 b b b tt xy e23 tt xy\"";
361        //System.out.println("s = " + s);
362        //System.out.println("t = " + t);
363        assertEquals("w == parse: ", s, t);
364
365        Word u = wf.parse("xy e23 tt xy a1 a1 b*b*b tt");
366        s = u.toString();
367        String t1 = "\"xy e23 tt xy a1 a1 b b b tt\"";
368        //System.out.println("s = " + s);
369        //System.out.println("t = " + t1);
370        assertEquals("w == parse: ", s, t1);
371
372        Word v = u.multiply(w);
373        s = v.toString();
374        String t2 = t1.substring(0,t1.length()-1) + " " + t.substring(1);
375        //System.out.println("s = " + s);
376        //System.out.println("t = " + t2);
377        assertEquals("w == parse: ", s, t2);
378
379        v = w.multiply(u);
380        s = v.toString();
381        t2 = t.substring(0,t.length()-1) + " " + t1.substring(1);
382        //System.out.println("s = " + s);
383        //System.out.println("t = " + t2);
384        assertEquals("w == parse: ", s, t2);
385
386        w = wf.random(5);
387        //System.out.println("w = " + w);
388        u = wf.random(5);
389        //System.out.println("u = " + u);
390        v = u.multiply(w);
391        //System.out.println("v = " + v);
392        assertTrue("#v = #w+#u: ", v.length() == w.length()+u.length());
393
394        List<Word> gens = wf.generators();
395        //System.out.println("gens = " + gens);
396        assertTrue("#gens == 5: ", gens.size() == 5);
397        for (Word x : gens) {
398            a = wf.parse(x.toString());
399            assertEquals("a == x", a, x);
400        }
401    }
402
403
404    /**
405     * Test leadingExpVector and reductum.
406     */
407    public void testExpVector() {
408        String[] vars = new String[] { "a", "b", "cc", "d1", "g" };
409        WordFactory wf = new WordFactory(vars);
410
411        Word w = wf.random(10);
412        //System.out.println("w = " + w);
413        long lw = w.degree();
414        long le = 0L;
415
416        Word r = w;
417        while ( !r.isONE() ) {
418            ExpVector ef = r.leadingExpVector();
419            Word r1 = r.reductum();
420            //System.out.println("ef = " + ef.toString(vars) + ", r1 = " + r1);
421            le += ef.degree();
422            Word w1 = wf.valueOf(ef);
423            Word w2 = w1.multiply(r1);
424            assertEquals("r == w2", r, w2);
425            r = r1;
426        }
427        assertTrue("deg(prod(ef)) == deg(w): " + lw + ", " + le, lw == le );
428    }
429
430}