001: /*
002: [The "BSD licence"]
003: Copyright (c) 2005-2006 Terence Parr
004: All rights reserved.
005:
006: Redistribution and use in source and binary forms, with or without
007: modification, are permitted provided that the following conditions
008: are met:
009: 1. Redistributions of source code must retain the above copyright
010: notice, this list of conditions and the following disclaimer.
011: 2. Redistributions in binary form must reproduce the above copyright
012: notice, this list of conditions and the following disclaimer in the
013: documentation and/or other materials provided with the distribution.
014: 3. The name of the author may not be used to endorse or promote products
015: derived from this software without specific prior written permission.
016:
017: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
018: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
019: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
020: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
021: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
022: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
023: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
024: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
025: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
026: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
027: */
028: package org.antlr.test;
029:
030: import org.antlr.analysis.Label;
031: import org.antlr.misc.IntervalSet;
032:
033: import java.util.ArrayList;
034: import java.util.List;
035:
036: public class TestIntervalSet extends BaseTest {
037:
038: /** Public default constructor used by TestRig */
039: public TestIntervalSet() {
040: }
041:
042: public void testSingleElement() throws Exception {
043: IntervalSet s = IntervalSet.of(99);
044: String expecting = "99";
045: assertEquals(s.toString(), expecting);
046: }
047:
048: public void testIsolatedElements() throws Exception {
049: IntervalSet s = new IntervalSet();
050: s.add(1);
051: s.add('z');
052: s.add('\uFFF0');
053: String expecting = "{1, 122, 65520}";
054: assertEquals(s.toString(), expecting);
055: }
056:
057: public void testMixedRangesAndElements() throws Exception {
058: IntervalSet s = new IntervalSet();
059: s.add(1);
060: s.add('a', 'z');
061: s.add('0', '9');
062: String expecting = "{1, 48..57, 97..122}";
063: assertEquals(s.toString(), expecting);
064: }
065:
066: public void testSimpleAnd() throws Exception {
067: IntervalSet s = IntervalSet.of(10, 20);
068: IntervalSet s2 = IntervalSet.of(13, 15);
069: String expecting = "13..15";
070: String result = (s.and(s2)).toString();
071: assertEquals(result, expecting);
072: }
073:
074: public void testRangeAndIsolatedElement() throws Exception {
075: IntervalSet s = IntervalSet.of('a', 'z');
076: IntervalSet s2 = IntervalSet.of('d');
077: String expecting = "100";
078: String result = (s.and(s2)).toString();
079: assertEquals(result, expecting);
080: }
081:
082: public void testEmptyIntersection() throws Exception {
083: IntervalSet s = IntervalSet.of('a', 'z');
084: IntervalSet s2 = IntervalSet.of('0', '9');
085: String expecting = "{}";
086: String result = (s.and(s2)).toString();
087: assertEquals(result, expecting);
088: }
089:
090: public void testEmptyIntersectionSingleElements() throws Exception {
091: IntervalSet s = IntervalSet.of('a');
092: IntervalSet s2 = IntervalSet.of('d');
093: String expecting = "{}";
094: String result = (s.and(s2)).toString();
095: assertEquals(result, expecting);
096: }
097:
098: public void testNotSingleElement() throws Exception {
099: IntervalSet vocabulary = IntervalSet.of(1, 1000);
100: vocabulary.add(2000, 3000);
101: IntervalSet s = IntervalSet.of(50, 50);
102: String expecting = "{1..49, 51..1000, 2000..3000}";
103: String result = (s.complement(vocabulary)).toString();
104: assertEquals(result, expecting);
105: }
106:
107: public void testNotSet() throws Exception {
108: IntervalSet vocabulary = IntervalSet.of(1, 1000);
109: IntervalSet s = IntervalSet.of(50, 60);
110: s.add(5);
111: s.add(250, 300);
112: String expecting = "{1..4, 6..49, 61..249, 301..1000}";
113: String result = (s.complement(vocabulary)).toString();
114: assertEquals(result, expecting);
115: }
116:
117: public void testNotEqualSet() throws Exception {
118: IntervalSet vocabulary = IntervalSet.of(1, 1000);
119: IntervalSet s = IntervalSet.of(1, 1000);
120: String expecting = "{}";
121: String result = (s.complement(vocabulary)).toString();
122: assertEquals(result, expecting);
123: }
124:
125: public void testNotSetEdgeElement() throws Exception {
126: IntervalSet vocabulary = IntervalSet.of(1, 2);
127: IntervalSet s = IntervalSet.of(1);
128: String expecting = "2";
129: String result = (s.complement(vocabulary)).toString();
130: assertEquals(result, expecting);
131: }
132:
133: public void testNotSetFragmentedVocabulary() throws Exception {
134: IntervalSet vocabulary = IntervalSet.of(1, 255);
135: vocabulary.add(1000, 2000);
136: vocabulary.add(9999);
137: IntervalSet s = IntervalSet.of(50, 60);
138: s.add(3);
139: s.add(250, 300);
140: s.add(10000); // this is outside range of vocab and should be ignored
141: String expecting = "{1..2, 4..49, 61..249, 1000..2000, 9999}";
142: String result = (s.complement(vocabulary)).toString();
143: assertEquals(result, expecting);
144: }
145:
146: public void testSubtractOfCompletelyContainedRange()
147: throws Exception {
148: IntervalSet s = IntervalSet.of(10, 20);
149: IntervalSet s2 = IntervalSet.of(12, 15);
150: String expecting = "{10..11, 16..20}";
151: String result = (s.subtract(s2)).toString();
152: assertEquals(result, expecting);
153: }
154:
155: public void testSubtractOfOverlappingRangeFromLeft()
156: throws Exception {
157: IntervalSet s = IntervalSet.of(10, 20);
158: IntervalSet s2 = IntervalSet.of(5, 11);
159: String expecting = "12..20";
160: String result = (s.subtract(s2)).toString();
161: assertEquals(result, expecting);
162:
163: IntervalSet s3 = IntervalSet.of(5, 10);
164: expecting = "11..20";
165: result = (s.subtract(s3)).toString();
166: assertEquals(result, expecting);
167: }
168:
169: public void testSubtractOfOverlappingRangeFromRight()
170: throws Exception {
171: IntervalSet s = IntervalSet.of(10, 20);
172: IntervalSet s2 = IntervalSet.of(15, 25);
173: String expecting = "10..14";
174: String result = (s.subtract(s2)).toString();
175: assertEquals(result, expecting);
176:
177: IntervalSet s3 = IntervalSet.of(20, 25);
178: expecting = "10..19";
179: result = (s.subtract(s3)).toString();
180: assertEquals(result, expecting);
181: }
182:
183: public void testSubtractOfCompletelyCoveredRange() throws Exception {
184: IntervalSet s = IntervalSet.of(10, 20);
185: IntervalSet s2 = IntervalSet.of(1, 25);
186: String expecting = "{}";
187: String result = (s.subtract(s2)).toString();
188: assertEquals(result, expecting);
189: }
190:
191: public void testSubtractOfRangeSpanningMultipleRanges()
192: throws Exception {
193: IntervalSet s = IntervalSet.of(10, 20);
194: s.add(30, 40);
195: s.add(50, 60); // s has 3 ranges now: 10..20, 30..40, 50..60
196: IntervalSet s2 = IntervalSet.of(5, 55); // covers one and touches 2nd range
197: String expecting = "56..60";
198: String result = (s.subtract(s2)).toString();
199: assertEquals(result, expecting);
200:
201: IntervalSet s3 = IntervalSet.of(15, 55); // touches both
202: expecting = "{10..14, 56..60}";
203: result = (s.subtract(s3)).toString();
204: assertEquals(result, expecting);
205: }
206:
207: /** The following was broken:
208: {0..113, 115..65534}-{0..115, 117..65534}=116..65534
209: */
210: public void testSubtractOfWackyRange() throws Exception {
211: IntervalSet s = IntervalSet.of(0, 113);
212: s.add(115, 200);
213: IntervalSet s2 = IntervalSet.of(0, 115);
214: s2.add(117, 200);
215: String expecting = "116";
216: String result = (s.subtract(s2)).toString();
217: assertEquals(result, expecting);
218: }
219:
220: public void testSimpleEquals() throws Exception {
221: IntervalSet s = IntervalSet.of(10, 20);
222: IntervalSet s2 = IntervalSet.of(10, 20);
223: Boolean expecting = new Boolean(true);
224: Boolean result = new Boolean(s.equals(s2));
225: assertEquals(result, expecting);
226:
227: IntervalSet s3 = IntervalSet.of(15, 55);
228: expecting = new Boolean(false);
229: result = new Boolean(s.equals(s3));
230: assertEquals(result, expecting);
231: }
232:
233: public void testEquals() throws Exception {
234: IntervalSet s = IntervalSet.of(10, 20);
235: s.add(2);
236: s.add(499, 501);
237: IntervalSet s2 = IntervalSet.of(10, 20);
238: s2.add(2);
239: s2.add(499, 501);
240: Boolean expecting = new Boolean(true);
241: Boolean result = new Boolean(s.equals(s2));
242: assertEquals(result, expecting);
243:
244: IntervalSet s3 = IntervalSet.of(10, 20);
245: s3.add(2);
246: expecting = new Boolean(false);
247: result = new Boolean(s.equals(s3));
248: assertEquals(result, expecting);
249: }
250:
251: public void testSingleElementMinusDisjointSet() throws Exception {
252: IntervalSet s = IntervalSet.of(15, 15);
253: IntervalSet s2 = IntervalSet.of(1, 5);
254: s2.add(10, 20);
255: String expecting = "{}"; // 15 - {1..5, 10..20} = {}
256: String result = s.subtract(s2).toString();
257: assertEquals(result, expecting);
258: }
259:
260: public void testMembership() throws Exception {
261: IntervalSet s = IntervalSet.of(15, 15);
262: s.add(50, 60);
263: assertTrue(!s.member(0));
264: assertTrue(!s.member(20));
265: assertTrue(!s.member(100));
266: assertTrue(s.member(15));
267: assertTrue(s.member(55));
268: assertTrue(s.member(50));
269: assertTrue(s.member(60));
270: }
271:
272: // {2,15,18} & 10..20
273: public void testIntersectionWithTwoContainedElements()
274: throws Exception {
275: IntervalSet s = IntervalSet.of(10, 20);
276: IntervalSet s2 = IntervalSet.of(2, 2);
277: s2.add(15);
278: s2.add(18);
279: String expecting = "{15, 18}";
280: String result = (s.and(s2)).toString();
281: assertEquals(result, expecting);
282: }
283:
284: public void testIntersectionWithTwoContainedElementsReversed()
285: throws Exception {
286: IntervalSet s = IntervalSet.of(10, 20);
287: IntervalSet s2 = IntervalSet.of(2, 2);
288: s2.add(15);
289: s2.add(18);
290: String expecting = "{15, 18}";
291: String result = (s2.and(s)).toString();
292: assertEquals(result, expecting);
293: }
294:
295: public void testComplement() throws Exception {
296: IntervalSet s = IntervalSet.of(100, 100);
297: s.add(101, 101);
298: IntervalSet s2 = IntervalSet.of(100, 102);
299: String expecting = "102";
300: String result = (s.complement(s2)).toString();
301: assertEquals(result, expecting);
302: }
303:
304: public void testComplement2() throws Exception {
305: IntervalSet s = IntervalSet.of(100, 101);
306: IntervalSet s2 = IntervalSet.of(100, 102);
307: String expecting = "102";
308: String result = (s.complement(s2)).toString();
309: assertEquals(result, expecting);
310: }
311:
312: public void testComplement3() throws Exception {
313: IntervalSet s = IntervalSet.of(1, 96);
314: s.add(99, 65534);
315: String expecting = "97..98";
316: String result = (s.complement(1, Label.MAX_CHAR_VALUE))
317: .toString();
318: assertEquals(result, expecting);
319: }
320:
321: public void testMergeOfRangesAndSingleValues() throws Exception {
322: // {0..41, 42, 43..65534}
323: IntervalSet s = IntervalSet.of(0, 41);
324: s.add(42);
325: s.add(43, 65534);
326: String expecting = "0..65534";
327: String result = s.toString();
328: assertEquals(result, expecting);
329: }
330:
331: public void testMergeOfRangesAndSingleValuesReverse()
332: throws Exception {
333: IntervalSet s = IntervalSet.of(43, 65534);
334: s.add(42);
335: s.add(0, 41);
336: String expecting = "0..65534";
337: String result = s.toString();
338: assertEquals(result, expecting);
339: }
340:
341: public void testMergeWhereAdditionMergesTwoExistingIntervals()
342: throws Exception {
343: // 42, 10, {0..9, 11..41, 43..65534}
344: IntervalSet s = IntervalSet.of(42);
345: s.add(10);
346: s.add(0, 9);
347: s.add(43, 65534);
348: s.add(11, 41);
349: String expecting = "0..65534";
350: String result = s.toString();
351: assertEquals(result, expecting);
352: }
353:
354: public void testMergeWithDoubleOverlap() throws Exception {
355: IntervalSet s = IntervalSet.of(1, 10);
356: s.add(20, 30);
357: s.add(5, 25); // overlaps two!
358: String expecting = "1..30";
359: String result = s.toString();
360: assertEquals(result, expecting);
361: }
362:
363: public void testSize() throws Exception {
364: IntervalSet s = IntervalSet.of(20, 30);
365: s.add(50, 55);
366: s.add(5, 19);
367: String expecting = "32";
368: String result = String.valueOf(s.size());
369: assertEquals(result, expecting);
370: }
371:
372: public void testToList() throws Exception {
373: IntervalSet s = IntervalSet.of(20, 25);
374: s.add(50, 55);
375: s.add(5, 5);
376: String expecting = "[5, 20, 21, 22, 23, 24, 25, 50, 51, 52, 53, 54, 55]";
377: List foo = new ArrayList();
378: String result = String.valueOf(s.toList());
379: assertEquals(result, expecting);
380: }
381:
382: /** The following was broken:
383: {'\u0000'..'s', 'u'..'\uFFFE'} & {'\u0000'..'q', 's'..'\uFFFE'}=
384: {'\u0000'..'q', 's'}!!!! broken...
385: 'q' is 113 ascii
386: 'u' is 117
387: */
388: public void testNotRIntersectionNotT() throws Exception {
389: IntervalSet s = IntervalSet.of(0, 's');
390: s.add('u', 200);
391: IntervalSet s2 = IntervalSet.of(0, 'q');
392: s2.add('s', 200);
393: String expecting = "{0..113, 115, 117..200}";
394: String result = (s.and(s2)).toString();
395: assertEquals(result, expecting);
396: }
397:
398: }
|