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