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