diff options
Diffstat (limited to 'tool/src/test/java/org/antlr/test/TestIntervalSet.java')
| -rw-r--r-- | tool/src/test/java/org/antlr/test/TestIntervalSet.java | 391 |
1 files changed, 391 insertions, 0 deletions
diff --git a/tool/src/test/java/org/antlr/test/TestIntervalSet.java b/tool/src/test/java/org/antlr/test/TestIntervalSet.java new file mode 100644 index 0000000..9acc37f --- /dev/null +++ b/tool/src/test/java/org/antlr/test/TestIntervalSet.java @@ -0,0 +1,391 @@ +/* + * [The "BSD license"] + * Copyright (c) 2010 Terence Parr + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +package org.antlr.test; + +import org.antlr.analysis.Label; +import org.antlr.misc.IntervalSet; +import org.junit.Test; + +import java.util.ArrayList; +import java.util.List; + + +public class TestIntervalSet extends BaseTest { + + /** Public default constructor used by TestRig */ + public TestIntervalSet() { + } + + @Test public void testSingleElement() throws Exception { + IntervalSet s = IntervalSet.of(99); + String expecting = "99"; + assertEquals(s.toString(), expecting); + } + + @Test public void testIsolatedElements() throws Exception { + IntervalSet s = new IntervalSet(); + s.add(1); + s.add('z'); + s.add('\uFFF0'); + String expecting = "{1, 122, 65520}"; + assertEquals(s.toString(), expecting); + } + + @Test public void testMixedRangesAndElements() throws Exception { + IntervalSet s = new IntervalSet(); + s.add(1); + s.add('a','z'); + s.add('0','9'); + String expecting = "{1, 48..57, 97..122}"; + assertEquals(s.toString(), expecting); + } + + @Test public void testSimpleAnd() throws Exception { + IntervalSet s = IntervalSet.of(10,20); + IntervalSet s2 = IntervalSet.of(13,15); + String expecting = "13..15"; + String result = (s.and(s2)).toString(); + assertEquals(result, expecting); + } + + @Test public void testRangeAndIsolatedElement() throws Exception { + IntervalSet s = IntervalSet.of('a','z'); + IntervalSet s2 = IntervalSet.of('d'); + String expecting = "100"; + String result = (s.and(s2)).toString(); + assertEquals(result, expecting); + } + + @Test public void testEmptyIntersection() throws Exception { + IntervalSet s = IntervalSet.of('a','z'); + IntervalSet s2 = IntervalSet.of('0','9'); + String expecting = "{}"; + String result = (s.and(s2)).toString(); + assertEquals(result, expecting); + } + + @Test public void testEmptyIntersectionSingleElements() throws Exception { + IntervalSet s = IntervalSet.of('a'); + IntervalSet s2 = IntervalSet.of('d'); + String expecting = "{}"; + String result = (s.and(s2)).toString(); + assertEquals(result, expecting); + } + + @Test public void testNotSingleElement() throws Exception { + IntervalSet vocabulary = IntervalSet.of(1,1000); + vocabulary.add(2000,3000); + IntervalSet s = IntervalSet.of(50,50); + String expecting = "{1..49, 51..1000, 2000..3000}"; + String result = (s.complement(vocabulary)).toString(); + assertEquals(result, expecting); + } + + @Test public void testNotSet() throws Exception { + IntervalSet vocabulary = IntervalSet.of(1,1000); + IntervalSet s = IntervalSet.of(50,60); + s.add(5); + s.add(250,300); + String expecting = "{1..4, 6..49, 61..249, 301..1000}"; + String result = (s.complement(vocabulary)).toString(); + assertEquals(result, expecting); + } + + @Test public void testNotEqualSet() throws Exception { + IntervalSet vocabulary = IntervalSet.of(1,1000); + IntervalSet s = IntervalSet.of(1,1000); + String expecting = "{}"; + String result = (s.complement(vocabulary)).toString(); + assertEquals(result, expecting); + } + + @Test public void testNotSetEdgeElement() throws Exception { + IntervalSet vocabulary = IntervalSet.of(1,2); + IntervalSet s = IntervalSet.of(1); + String expecting = "2"; + String result = (s.complement(vocabulary)).toString(); + assertEquals(result, expecting); + } + + @Test public void testNotSetFragmentedVocabulary() throws Exception { + IntervalSet vocabulary = IntervalSet.of(1,255); + vocabulary.add(1000,2000); + vocabulary.add(9999); + IntervalSet s = IntervalSet.of(50,60); + s.add(3); + s.add(250,300); + s.add(10000); // this is outside range of vocab and should be ignored + String expecting = "{1..2, 4..49, 61..249, 1000..2000, 9999}"; + String result = (s.complement(vocabulary)).toString(); + assertEquals(result, expecting); + } + + @Test public void testSubtractOfCompletelyContainedRange() throws Exception { + IntervalSet s = IntervalSet.of(10,20); + IntervalSet s2 = IntervalSet.of(12,15); + String expecting = "{10..11, 16..20}"; + String result = (s.subtract(s2)).toString(); + assertEquals(result, expecting); + } + + @Test public void testSubtractOfOverlappingRangeFromLeft() throws Exception { + IntervalSet s = IntervalSet.of(10,20); + IntervalSet s2 = IntervalSet.of(5,11); + String expecting = "12..20"; + String result = (s.subtract(s2)).toString(); + assertEquals(result, expecting); + + IntervalSet s3 = IntervalSet.of(5,10); + expecting = "11..20"; + result = (s.subtract(s3)).toString(); + assertEquals(result, expecting); + } + + @Test public void testSubtractOfOverlappingRangeFromRight() throws Exception { + IntervalSet s = IntervalSet.of(10,20); + IntervalSet s2 = IntervalSet.of(15,25); + String expecting = "10..14"; + String result = (s.subtract(s2)).toString(); + assertEquals(result, expecting); + + IntervalSet s3 = IntervalSet.of(20,25); + expecting = "10..19"; + result = (s.subtract(s3)).toString(); + assertEquals(result, expecting); + } + + @Test public void testSubtractOfCompletelyCoveredRange() throws Exception { + IntervalSet s = IntervalSet.of(10,20); + IntervalSet s2 = IntervalSet.of(1,25); + String expecting = "{}"; + String result = (s.subtract(s2)).toString(); + assertEquals(result, expecting); + } + + @Test public void testSubtractOfRangeSpanningMultipleRanges() throws Exception { + IntervalSet s = IntervalSet.of(10,20); + s.add(30,40); + s.add(50,60); // s has 3 ranges now: 10..20, 30..40, 50..60 + IntervalSet s2 = IntervalSet.of(5,55); // covers one and touches 2nd range + String expecting = "56..60"; + String result = (s.subtract(s2)).toString(); + assertEquals(result, expecting); + + IntervalSet s3 = IntervalSet.of(15,55); // touches both + expecting = "{10..14, 56..60}"; + result = (s.subtract(s3)).toString(); + assertEquals(result, expecting); + } + + /** The following was broken: + {0..113, 115..65534}-{0..115, 117..65534}=116..65534 + */ + @Test public void testSubtractOfWackyRange() throws Exception { + IntervalSet s = IntervalSet.of(0,113); + s.add(115,200); + IntervalSet s2 = IntervalSet.of(0,115); + s2.add(117,200); + String expecting = "116"; + String result = (s.subtract(s2)).toString(); + assertEquals(result, expecting); + } + + @Test public void testSimpleEquals() throws Exception { + IntervalSet s = IntervalSet.of(10,20); + IntervalSet s2 = IntervalSet.of(10,20); + Boolean expecting = new Boolean(true); + Boolean result = new Boolean(s.equals(s2)); + assertEquals(result, expecting); + + IntervalSet s3 = IntervalSet.of(15,55); + expecting = new Boolean(false); + result = new Boolean(s.equals(s3)); + assertEquals(result, expecting); + } + + @Test public void testEquals() throws Exception { + IntervalSet s = IntervalSet.of(10,20); + s.add(2); + s.add(499,501); + IntervalSet s2 = IntervalSet.of(10,20); + s2.add(2); + s2.add(499,501); + Boolean expecting = new Boolean(true); + Boolean result = new Boolean(s.equals(s2)); + assertEquals(result, expecting); + + IntervalSet s3 = IntervalSet.of(10,20); + s3.add(2); + expecting = new Boolean(false); + result = new Boolean(s.equals(s3)); + assertEquals(result, expecting); + } + + @Test public void testSingleElementMinusDisjointSet() throws Exception { + IntervalSet s = IntervalSet.of(15,15); + IntervalSet s2 = IntervalSet.of(1,5); + s2.add(10,20); + String expecting = "{}"; // 15 - {1..5, 10..20} = {} + String result = s.subtract(s2).toString(); + assertEquals(result, expecting); + } + + @Test public void testMembership() throws Exception { + IntervalSet s = IntervalSet.of(15,15); + s.add(50,60); + assertTrue(!s.member(0)); + assertTrue(!s.member(20)); + assertTrue(!s.member(100)); + assertTrue(s.member(15)); + assertTrue(s.member(55)); + assertTrue(s.member(50)); + assertTrue(s.member(60)); + } + + // {2,15,18} & 10..20 + @Test public void testIntersectionWithTwoContainedElements() throws Exception { + IntervalSet s = IntervalSet.of(10,20); + IntervalSet s2 = IntervalSet.of(2,2); + s2.add(15); + s2.add(18); + String expecting = "{15, 18}"; + String result = (s.and(s2)).toString(); + assertEquals(result, expecting); + } + + @Test public void testIntersectionWithTwoContainedElementsReversed() throws Exception { + IntervalSet s = IntervalSet.of(10,20); + IntervalSet s2 = IntervalSet.of(2,2); + s2.add(15); + s2.add(18); + String expecting = "{15, 18}"; + String result = (s2.and(s)).toString(); + assertEquals(result, expecting); + } + + @Test public void testComplement() throws Exception { + IntervalSet s = IntervalSet.of(100,100); + s.add(101,101); + IntervalSet s2 = IntervalSet.of(100,102); + String expecting = "102"; + String result = (s.complement(s2)).toString(); + assertEquals(result, expecting); + } + + @Test public void testComplement2() throws Exception { + IntervalSet s = IntervalSet.of(100,101); + IntervalSet s2 = IntervalSet.of(100,102); + String expecting = "102"; + String result = (s.complement(s2)).toString(); + assertEquals(result, expecting); + } + + @Test public void testComplement3() throws Exception { + IntervalSet s = IntervalSet.of(1,96); + s.add(99,Label.MAX_CHAR_VALUE); + String expecting = "97..98"; + String result = (s.complement(1,Label.MAX_CHAR_VALUE)).toString(); + assertEquals(result, expecting); + } + + @Test public void testMergeOfRangesAndSingleValues() throws Exception { + // {0..41, 42, 43..65534} + IntervalSet s = IntervalSet.of(0,41); + s.add(42); + s.add(43,65534); + String expecting = "0..65534"; + String result = s.toString(); + assertEquals(result, expecting); + } + + @Test public void testMergeOfRangesAndSingleValuesReverse() throws Exception { + IntervalSet s = IntervalSet.of(43,65534); + s.add(42); + s.add(0,41); + String expecting = "0..65534"; + String result = s.toString(); + assertEquals(result, expecting); + } + + @Test public void testMergeWhereAdditionMergesTwoExistingIntervals() throws Exception { + // 42, 10, {0..9, 11..41, 43..65534} + IntervalSet s = IntervalSet.of(42); + s.add(10); + s.add(0,9); + s.add(43,65534); + s.add(11,41); + String expecting = "0..65534"; + String result = s.toString(); + assertEquals(result, expecting); + } + + @Test public void testMergeWithDoubleOverlap() throws Exception { + IntervalSet s = IntervalSet.of(1,10); + s.add(20,30); + s.add(5,25); // overlaps two! + String expecting = "1..30"; + String result = s.toString(); + assertEquals(result, expecting); + } + + @Test public void testSize() throws Exception { + IntervalSet s = IntervalSet.of(20,30); + s.add(50,55); + s.add(5,19); + String expecting = "32"; + String result = String.valueOf(s.size()); + assertEquals(result, expecting); + } + + @Test public void testToList() throws Exception { + IntervalSet s = IntervalSet.of(20,25); + s.add(50,55); + s.add(5,5); + String expecting = "[5, 20, 21, 22, 23, 24, 25, 50, 51, 52, 53, 54, 55]"; + List foo = new ArrayList(); + String result = String.valueOf(s.toList()); + assertEquals(result, expecting); + } + + /** The following was broken: + {'\u0000'..'s', 'u'..'\uFFFE'} & {'\u0000'..'q', 's'..'\uFFFE'}= + {'\u0000'..'q', 's'}!!!! broken... + 'q' is 113 ascii + 'u' is 117 + */ + @Test public void testNotRIntersectionNotT() throws Exception { + IntervalSet s = IntervalSet.of(0,'s'); + s.add('u',200); + IntervalSet s2 = IntervalSet.of(0,'q'); + s2.add('s',200); + String expecting = "{0..113, 115, 117..200}"; + String result = (s.and(s2)).toString(); + assertEquals(result, expecting); + } + +} |