/*
 * [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);
	}

}