test/unit/org/apache/cassandra/utils/IntegerIntervalsTest.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package org.apache.cassandra.utils;

import static org.junit.Assert.*;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.Callable;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

import com.google.common.collect.ImmutableList;
import com.google.common.util.concurrent.Futures;

import org.junit.Test;

import org.apache.cassandra.utils.IntegerInterval.Set;

public class IntegerIntervalsTest
{
    int[] values = new int[] { Integer.MIN_VALUE, -2, -1, 0, 5, 9, 13, Integer.MAX_VALUE };

    @Test
    public void testMake()
    {
        IntegerInterval iv;
        for (int i = 0; i < values.length; ++i)
        {
            for (int j = i; j < values.length; ++j)
            {
                iv = new IntegerInterval(values[i], values[j]);
                assertEquals(values[i], iv.lower());
                assertEquals(values[j], iv.upper());
            }
        }

        for (int i = 0; i < values.length; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                try
                {
                    iv = new IntegerInterval(values[i], values[j]);
                    fail("Assertion not thrown: " + values[i] + ", " + values[j]);
                }
                catch (AssertionError e)
                {
                    // expected
                }
            }
        }
    }

    @Test
    public void testExpandToCoverSingleThread()
    {
        IntegerInterval iv;
        for (int i = 0; i < values.length; ++i)
        {
            for (int j = i; j < values.length; ++j)
            {
                iv = new IntegerInterval(values[i], values[j]);
                int k = 0;
                for (; k < i; ++k)
                {
                    IntegerInterval v = new IntegerInterval(iv);
                    v.expandToCover(values[k]);
                    assertEquals(values[k], v.lower());
                    assertEquals(values[j], v.upper());
                }
                for (; k < j; ++k)
                {
                    IntegerInterval v = new IntegerInterval(iv);
                    v.expandToCover(values[k]);
                    assertEquals(values[i], v.lower());
                    assertEquals(values[j], v.upper());
                }
                for (; k < values.length; ++k)
                {
                    IntegerInterval v = new IntegerInterval(iv);
                    v.expandToCover(values[k]);
                    assertEquals(values[i], v.lower());
                    assertEquals(values[k], v.upper());
                }
            }
        }
    }

    @Test
    public void testExpandToCoverMultiThread() throws InterruptedException
    {
        Random r = new Random();
        int threads = 16;
        int streamSize = 1000000;
        List<Callable<Void>> tasks = new ArrayList<>(threads);
        final IntegerInterval interval = new IntegerInterval(0, 0);
        int min = 0;
        int max = 0;
        for (int i = 0; i < threads; ++i)
        {
            final int seed = r.nextInt();
            tasks.add(() -> {
                new Random(seed).ints(streamSize).forEach(v -> interval.expandToCover(v));
                return null;
            });
            min = Math.min(min, new Random(seed).ints(streamSize).min().getAsInt());
            max = Math.max(max, new Random(seed).ints(streamSize).max().getAsInt());
        }
        for (Future<?> f : Executors.newFixedThreadPool(threads).invokeAll(tasks))
            Futures.getUnchecked(f);
        assertEquals(min, interval.lower());
        assertEquals(max, interval.upper());
    }

    void testSetAdd(int l, int r, Integer... expected)
    {
        Set s = new Set();
        s.add(-3, -1);
        s.add(1, 3);
        s.add(l, r);
        assertArrayEquals(expected, s
                                    .intervals()
                                    .stream()
                                    .flatMap(x -> ImmutableList.of(x.lower(), x.upper()).stream())
                                    .toArray());
    }

    void testSetAdd(int l, int r, String expected)
    {
        Set s = new Set();
        s.add(-3, -1);
        s.add(1, 3);
        s.add(l, r);
        assertEquals(expected, s.toString());
    }

    @Test
    public void testSetAdd()
    {
        testSetAdd(Integer.MIN_VALUE, -4, Integer.MIN_VALUE, -4, -3, -1, 1, 3);
        testSetAdd(Integer.MIN_VALUE, -3, Integer.MIN_VALUE, -1, 1, 3);
        testSetAdd(Integer.MIN_VALUE, -2, Integer.MIN_VALUE, -1, 1, 3);
        testSetAdd(Integer.MIN_VALUE, -1, Integer.MIN_VALUE, -1, 1, 3);
        testSetAdd(Integer.MIN_VALUE, 0, Integer.MIN_VALUE, 0, 1, 3);
        testSetAdd(Integer.MIN_VALUE, 1, Integer.MIN_VALUE, 3);
        testSetAdd(Integer.MIN_VALUE, 2, Integer.MIN_VALUE, 3);
        testSetAdd(Integer.MIN_VALUE, 3, Integer.MIN_VALUE, 3);
        testSetAdd(Integer.MIN_VALUE, Integer.MAX_VALUE, Integer.MIN_VALUE, Integer.MAX_VALUE);

        testSetAdd(-5, -4, "[[-5,-4], [-3,-1], [1,3]]");
        testSetAdd(-5, -3, -5, -1, 1, 3);
        testSetAdd(-5, -2, -5, -1, 1, 3);
        testSetAdd(-5, -1, -5, -1, 1, 3);
        testSetAdd(-5, 0, -5, 0, 1, 3);
        testSetAdd(-5, 1, -5, 3);
        testSetAdd(-5, 2, -5, 3);
        testSetAdd(-5, 3, -5, 3);
        testSetAdd(-5, 4, -5, 4);
        testSetAdd(-5, Integer.MAX_VALUE, -5, Integer.MAX_VALUE);

        testSetAdd(-3, -3, -3, -1, 1, 3);
        testSetAdd(-3, -2, -3, -1, 1, 3);
        testSetAdd(-3, -1, -3, -1, 1, 3);
        testSetAdd(-3, 0, -3, 0, 1, 3);
        testSetAdd(-3, 1, "[[-3,3]]");
        testSetAdd(-3, 2, -3, 3);
        testSetAdd(-3, 3, -3, 3);
        testSetAdd(-3, 4, -3, 4);
        testSetAdd(-3, Integer.MAX_VALUE, -3, Integer.MAX_VALUE);

        testSetAdd(-2, -2, -3, -1, 1, 3);
        testSetAdd(-2, -1, -3, -1, 1, 3);
        testSetAdd(-2, 0, "[[-3,0], [1,3]]");
        testSetAdd(-2, 1, -3, 3);
        testSetAdd(-2, 2, -3, 3);
        testSetAdd(-2, 3, -3, 3);
        testSetAdd(-2, 4, -3, 4);
        testSetAdd(-2, Integer.MAX_VALUE, -3, Integer.MAX_VALUE);

        testSetAdd(-1, -1, -3, -1, 1, 3);
        testSetAdd(-1, 0, -3, 0, 1, 3);
        testSetAdd(-1, 1, -3, 3);
        testSetAdd(-1, 2, -3, 3);
        testSetAdd(-1, 3, -3, 3);
        testSetAdd(-1, 4, -3, 4);
        testSetAdd(-1, Integer.MAX_VALUE, -3, Integer.MAX_VALUE);

        testSetAdd(0, 0, -3, -1, 0, 0, 1, 3);
        testSetAdd(0, 1, -3, -1, 0, 3);
        testSetAdd(0, 2, -3, -1, 0, 3);
        testSetAdd(0, 3, -3, -1, 0, 3);
        testSetAdd(0, 4, -3, -1, 0, 4);
        testSetAdd(0, Integer.MAX_VALUE, -3, -1, 0, Integer.MAX_VALUE);

        testSetAdd(1, 1, -3, -1, 1, 3);
        testSetAdd(1, 2, -3, -1, 1, 3);
        testSetAdd(1, 3, -3, -1, 1, 3);
        testSetAdd(1, 4, -3, -1, 1, 4);
        testSetAdd(1, Integer.MAX_VALUE, -3, -1, 1, Integer.MAX_VALUE);

        testSetAdd(2, 2, -3, -1, 1, 3);
        testSetAdd(2, 3, -3, -1, 1, 3);
        testSetAdd(2, 4, -3, -1, 1, 4);
        testSetAdd(2, Integer.MAX_VALUE, -3, -1, 1, Integer.MAX_VALUE);

        testSetAdd(3, 3, "[[-3,-1], [1,3]]");
        testSetAdd(3, 4, -3, -1, 1, 4);
        testSetAdd(3, Integer.MAX_VALUE, -3, -1, 1, Integer.MAX_VALUE);

        testSetAdd(4, 5, -3, -1, 1, 3, 4, 5);
        testSetAdd(4, Integer.MAX_VALUE, -3, -1, 1, 3, 4, Integer.MAX_VALUE);
    }

    @Test
    public void testSetAddMultiThread() throws InterruptedException
    {
        Random r = new Random();
        int threads = 16;
        int streamSize = 10000;
        List<Callable<Void>> tasks = new ArrayList<>(threads);
        final IntegerInterval.Set st = new IntegerInterval.Set();
        final IntegerInterval.Set mt = new IntegerInterval.Set();
        for (int i = 0; i < threads; ++i)
        {
            final int seed = r.nextInt();
            tasks.add(() -> {
                new Random(seed)
                    .ints(streamSize)
                    .forEach(v -> mt.add(v, v + 5));
                return null;
            });
            new Random(seed)
                .ints(streamSize)
                .forEach(v -> st.add(v, v + 5));
        }
        for (Future<?> f : Executors.newFixedThreadPool(threads).invokeAll(tasks))
            Futures.getUnchecked(f);
        assertEquals(st, mt);
    }

    void testSetCovers(int l, int r, boolean expected)
    {
        Set s = new Set();
        s.add(-3, -1);
        s.add(1, 3);
        assertEquals(expected, s.covers(new IntegerInterval(l, r)));
    }


    @Test
    public void testSetCovers()
    {
        testSetCovers(Integer.MIN_VALUE, -4, false);
        testSetCovers(Integer.MIN_VALUE, -3, false);
        testSetCovers(Integer.MIN_VALUE, -2, false);
        testSetCovers(Integer.MIN_VALUE, -1, false);
        testSetCovers(Integer.MIN_VALUE, 0, false);
        testSetCovers(Integer.MIN_VALUE, 1, false);
        testSetCovers(Integer.MIN_VALUE, 2, false);
        testSetCovers(Integer.MIN_VALUE, 3, false);
        testSetCovers(Integer.MIN_VALUE, Integer.MAX_VALUE, false);

        testSetCovers(-5, -4, false);
        testSetCovers(-5, -3, false);
        testSetCovers(-5, -2, false);
        testSetCovers(-5, -1, false);
        testSetCovers(-5, 0, false);
        testSetCovers(-5, 1, false);
        testSetCovers(-5, 2, false);
        testSetCovers(-5, 3, false);
        testSetCovers(-5, 4, false);
        testSetCovers(-5, Integer.MAX_VALUE, false);

        testSetCovers(-3, -3, true);
        testSetCovers(-3, -2, true);
        testSetCovers(-3, -1, true);
        testSetCovers(-3, 0, false);
        testSetCovers(-3, 1, false);
        testSetCovers(-3, 2, false);
        testSetCovers(-3, 3, false);
        testSetCovers(-3, 4, false);
        testSetCovers(-3, Integer.MAX_VALUE, false);

        testSetCovers(-2, -2, true);
        testSetCovers(-2, -1, true);
        testSetCovers(-2, 0, false);
        testSetCovers(-2, 1, false);
        testSetCovers(-2, 2, false);
        testSetCovers(-2, 3, false);
        testSetCovers(-2, 4, false);
        testSetCovers(-2, Integer.MAX_VALUE, false);

        testSetCovers(-1, -1, true);
        testSetCovers(-1, 0, false);
        testSetCovers(-1, 1, false);
        testSetCovers(-1, 2, false);
        testSetCovers(-1, 3, false);
        testSetCovers(-1, 4, false);
        testSetCovers(-1, Integer.MAX_VALUE, false);

        testSetCovers(0, 0, false);
        testSetCovers(0, 1, false);
        testSetCovers(0, 2, false);
        testSetCovers(0, 3, false);
        testSetCovers(0, 4, false);
        testSetCovers(0, Integer.MAX_VALUE, false);

        testSetCovers(1, 1, true);
        testSetCovers(1, 2, true);
        testSetCovers(1, 3, true);
        testSetCovers(1, 4, false);
        testSetCovers(1, Integer.MAX_VALUE, false);

        testSetCovers(2, 2, true);
        testSetCovers(2, 3, true);
        testSetCovers(2, 4, false);
        testSetCovers(2, Integer.MAX_VALUE, false);

        testSetCovers(3, 3, true);
        testSetCovers(3, 4, false);
        testSetCovers(3, Integer.MAX_VALUE, false);

        testSetCovers(4, 5, false);
        testSetCovers(4, Integer.MAX_VALUE, false);
    }
}