extendedset/src/test/java/org/apache/druid/extendedset/intset/ImmutableConciseSetIntersectionTest.java - druid - Git at Google

 /*
  * 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.druid.extendedset.intset;

 import junit.framework.Assert;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;

 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collections;
 import java.util.List;

 @RunWith(Parameterized.class)
 public class ImmutableConciseSetIntersectionTest
 {
   @Parameterized.Parameters
   public static List<Object[]> parameters()
   {
     return Arrays.asList(new Object[] {false}, new Object[] {true});
   }

   private boolean compact;

   public ImmutableConciseSetIntersectionTest(boolean compact)
   {
     this.compact = compact;
   }

   /**
    * Testing basic intersection of similar sets
    */
   @Test
   public void testIntersection1()
   {
     final int[] ints1 = {33, 100000};
     final int[] ints2 = {33, 100000};
     List<Integer> expected = Arrays.asList(33, 100000);

     ConciseSet set1 = new ConciseSet();
     for (int i : ints1) {
       set1.add(i);
     }
     ConciseSet set2 = new ConciseSet();
     for (int i : ints2) {
       set2.add(i);
     }

     verifyIntersection(expected, set1, set2);
   }

   /**
    * Set1: literal, zero fill with flip bit, literal
    * Set2: literal, zero fill with different flip bit, literal
    */
   @Test
   public void testIntersection2()
   {
     final int[] ints1 = {33, 100000};
     final int[] ints2 = {34, 100000};
     List<Integer> expected = Collections.singletonList(100000);

     ConciseSet set1 = new ConciseSet();
     for (int i : ints1) {
       set1.add(i);
     }
     ConciseSet set2 = new ConciseSet();
     for (int i : ints2) {
       set2.add(i);
     }

     verifyIntersection(expected, set1, set2);
   }

   /**
    * Testing intersection of one fills
    */
   @Test
   public void testIntersection3()
   {
     List<Integer> expected = new ArrayList<>();
     ConciseSet set1 = new ConciseSet();
     ConciseSet set2 = new ConciseSet();
     for (int i = 0; i < 1000; i++) {
       set1.add(i);
       set2.add(i);
       expected.add(i);
     }

     verifyIntersection(expected, set1, set2);
   }

   /**
    * Similar to previous test with one bit in the sequence set to zero
    */
   @Test
   public void testIntersection4()
   {
     List<Integer> expected = new ArrayList<>();
     ConciseSet set1 = new ConciseSet();
     ConciseSet set2 = new ConciseSet();
     for (int i = 0; i < 1000; i++) {
       set1.add(i);
       if (i != 500) {
         set2.add(i);
         expected.add(i);
       }
     }

     verifyIntersection(expected, set1, set2);
   }

   /**
    * Testing with disjoint sets
    */
   @Test
   public void testIntersection5()
   {
     final int[] ints1 = {33, 100000};
     final int[] ints2 = {34, 200000};
     List<Integer> expected = new ArrayList<>();

     ConciseSet set1 = new ConciseSet();
     for (int i : ints1) {
       set1.add(i);
     }
     ConciseSet set2 = new ConciseSet();
     for (int i : ints2) {
       set2.add(i);
     }

     verifyIntersection(expected, set1, set2);
   }

   /**
    * Set 1: literal, zero fill, literal
    * Set 2: one fill, literal that falls within the zero fill above, one fill
    */
   @Test
   public void testIntersection6()
   {
     List<Integer> expected = new ArrayList<>();
     ConciseSet set1 = new ConciseSet();
     for (int i = 0; i < 5; i++) {
       set1.add(i);
     }
     for (int i = 1000; i < 1005; i++) {
       set1.add(i);
     }

     ConciseSet set2 = new ConciseSet();
     for (int i = 800; i < 805; i++) {
       set2.add(i);
     }
     for (int i = 806; i < 1005; i++) {
       set2.add(i);
     }

     for (int i = 1000; i < 1005; i++) {
       expected.add(i);
     }

     verifyIntersection(expected, set1, set2);
   }

   @Test
   public void testIntersection7()
   {
     ConciseSet set1 = new ConciseSet();
     for (int i = 0; i < 3100; i++) {
       set1.add(i);
     }

     ConciseSet set2 = new ConciseSet();
     set2.add(100);
     set2.add(500);
     for (int i = 600; i < 700; i++) {
       set2.add(i);
     }

     List<Integer> expected = new ArrayList<>();
     expected.add(100);
     expected.add(500);
     for (int i = 600; i < 700; i++) {
       expected.add(i);
     }

     verifyIntersection(expected, set1, set2);
   }

   @Test
   public void testIntersection8()
   {
     ConciseSet set1 = new ConciseSet();
     for (int i = 0; i < 3100; i++) {
       set1.add(i);
     }
     set1.add(4001);

     ConciseSet set2 = new ConciseSet();
     set2.add(100);
     set2.add(500);
     for (int i = 600; i < 700; i++) {
       set2.add(i);
     }
     set2.add(4001);

     List<Integer> expected = new ArrayList<>();
     expected.add(100);
     expected.add(500);
     for (int i = 600; i < 700; i++) {
       expected.add(i);
     }
     expected.add(4001);

     verifyIntersection(expected, set1, set2);
   }

   @Test
   public void testIntersection9()
   {
     ConciseSet set1 = new ConciseSet();
     set1.add(2005);
     set1.add(3005);
     set1.add(3008);

     ConciseSet set2 = new ConciseSet();
     for (int i = 0; i < 3007; i++) {
       set2.add(i);
     }

     List<Integer> expected = new ArrayList<>();
     expected.add(2005);
     expected.add(3005);

     verifyIntersection(expected, set1, set2);
   }

   @Test
   public void testIntersection10()
   {
     ConciseSet set1 = new ConciseSet();
     for (int i = 0; i < 3100; i++) {
       set1.add(i);
     }

     ConciseSet set2 = new ConciseSet();

     set2.add(500);
     set2.add(600);
     set2.add(4001);

     List<Integer> expected = new ArrayList<>();
     expected.add(500);
     expected.add(600);

     verifyIntersection(expected, set1, set2);
   }

   @Test
   public void testIntersection11()
   {
     ConciseSet set1 = new ConciseSet();
     set1.add(2005);
     for (int i = 2800; i < 3500; i++) {
       set1.add(i);
     }

     ConciseSet set2 = new ConciseSet();
     for (int i = 0; i < 3007; i++) {
       set2.add(i);
     }

     List<Integer> expected = new ArrayList<>();
     expected.add(2005);
     for (int i = 2800; i < 3007; i++) {
       expected.add(i);
     }

     verifyIntersection(expected, set1, set2);
   }

   @Test
   public void testIntersection12()
   {
     ConciseSet set1 = new ConciseSet();
     set1.add(2005);
     for (int i = 2800; i < 3500; i++) {
       set1.add(i);
     }
     set1.add(10005);

     ConciseSet set2 = new ConciseSet();
     for (int i = 0; i < 3007; i++) {
       set2.add(i);
     }
     set2.add(10005);

     List<Integer> expected = new ArrayList<>();
     expected.add(2005);
     for (int i = 2800; i < 3007; i++) {
       expected.add(i);
     }
     expected.add(10005);

     verifyIntersection(expected, set1, set2);
   }

   @Test
   public void testIntersection13()
   {
     ConciseSet set1 = new ConciseSet();
     set1.add(2005);

     ConciseSet set2 = new ConciseSet();
     for (int i = 0; i < 100; i++) {
       set2.add(i);
     }

     List<Integer> expected = new ArrayList<>();

     verifyIntersection(expected, set1, set2);
   }

   @Test
   public void testIntersection14()
   {
     ConciseSet set1 = new ConciseSet();
     for (int i = 0; i < 1000; i++) {
       set1.add(i);
     }

     ConciseSet set2 = new ConciseSet();
     set2.add(0);
     set2.add(3);
     set2.add(5);
     set2.add(100);
     set2.add(101);

     List<Integer> expected = new ArrayList<>();
     expected.add(0);
     expected.add(3);
     expected.add(5);
     expected.add(100);
     expected.add(101);

     verifyIntersection(expected, set1, set2);
   }

   @Test
   public void testIntersection15()
   {
     ConciseSet set1 = new ConciseSet();
     for (int i = 0; i < 1000; i++) {
       set1.add(i);
     }

     ConciseSet set2 = new ConciseSet();
     set2.add(0);
     set2.add(3);
     set2.add(5);
     for (int i = 100; i < 500; i++) {
       set2.add(i);
     }

     List<Integer> expected = new ArrayList<>();
     expected.add(0);
     expected.add(3);
     expected.add(5);
     for (int i = 100; i < 500; i++) {
       expected.add(i);
     }

     verifyIntersection(expected, set1, set2);
   }

   @Test
   public void testIntersection16()
   {
     ConciseSet set1 = new ConciseSet();
     set1.add(2005);

     ConciseSet set2 = new ConciseSet();
     set2.add(0);
     set2.add(3);
     set2.add(5);
     set2.add(100);
     set2.add(101);

     List<Integer> expected = new ArrayList<>();

     verifyIntersection(expected, set1, set2);
   }

   @Test
   public void testIntersection17()
   {
     ConciseSet set1 = new ConciseSet();
     for (int i = 0; i < 4002; i++) {
       set1.add(i);
     }

     ConciseSet set2 = new ConciseSet();
     set2.add(4001);

     List<Integer> expected = new ArrayList<>();
     expected.add(4001);

     verifyIntersection(expected, set1, set2);
   }

   @Test
   public void testIntersection18()
   {
     ConciseSet set1 = new ConciseSet();
     for (int i = 32; i < 93; i++) {
       set1.add(i);
     }

     ConciseSet set2 = new ConciseSet();
     for (int i = 0; i < 62; i++) {
       set2.add(i);
     }

     List<Integer> expected = new ArrayList<>();
     for (int i = 32; i < 62; i++) {
       expected.add(i);
     }

     verifyIntersection(expected, set1, set2);
   }

   @Test
   public void testIntersection19()
   {
     ConciseSet set1 = new ConciseSet();
     set1.add(2005);

     ConciseSet set2 = new ConciseSet();
     for (int i = 0; i < 10000; i++) {
       set2.add(i);
     }

     List<Integer> expected = new ArrayList<>();
     expected.add(2005);

     verifyIntersection(expected, set1, set2);
   }

   @Test
   public void testIntersectionLiteralAndOneFill()
   {
     ConciseSet set1 = new ConciseSet();
     for (int i = 0; i < 31; i += 2) {
       set1.add(i);
     }
     ConciseSet set2 = new ConciseSet();
     for (int i = 0; i < 1000; i++) {
       if (i != 2) {
         set2.add(i);
       }
     }
     verifyIntersection(set1, set2);
   }

   @Test
   public void testIntersectionZeroSequenceRemovedFromQueue()
   {
     // Seems that it is impossible to test this case with naturally constructed ConciseSet, because the end of the
     // sequence is defined by the last set bit, then naturally constructed ConciseSet won't have the last word as zero
     // sequence, it will be a literal or one sequence.
     int zeroSequence = 1; // Zero sequence of length 62
     ConciseSet set1 = new ConciseSet(new int[] {zeroSequence}, false);

     ConciseSet set2 = new ConciseSet();
     for (int i = 0; i < 1000; i++) {
       set2.add(i);
     }
     verifyIntersection(set1, set2);
   }

   @Test
   public void testIntersectionOneFillAndOneFillWithFlipBit()
   {
     ConciseSet set1 = new ConciseSet();
     for (int i = 0; i < 100; i++) {
       set1.add(i);
     }
     ConciseSet set2 = new ConciseSet();
     for (int i = 0; i < 1000; i++) {
       if (i != 2) {
         set2.add(i);
       }
     }
     verifyIntersection(set1, set2);
   }

   @Test
   public void testIntersectionSecondOneFillRemovedFromQueue()
   {
     ConciseSet set1 = new ConciseSet();
     for (int i = 0; i < 31 * 2; i++) {
       set1.add(i);
     }
     set1.add(100);

     ConciseSet set2 = new ConciseSet();
     for (int i = 0; i < 31 * 3; i++) {
       set2.add(i);
     }

     verifyIntersection(set1, set2);
   }

   @Test
   public void testIntersectionFirstOneFillRemovedFromQueue()
   {
     ConciseSet set1 = new ConciseSet();
     for (int i = 0; i < 31 * 2; i++) {
       set1.add(i);
     }

     ConciseSet set2 = new ConciseSet();
     for (int i = 0; i < 31 * 3; i++) {
       set2.add(i);
     }

     verifyIntersection(set1, set2);
   }

   @Test
   public void testIntersectionTerminates()
   {
     verifyIntersection(Collections.emptyList(), Arrays.asList(new ImmutableConciseSet(), new ImmutableConciseSet()));
   }

   private static List<Integer> toList(ConciseSet set)
   {
     List<Integer> list1 = new ArrayList<>();
     for (IntSet.IntIterator it = set.iterator(); it.hasNext(); ) {
       list1.add(it.next());
     }
     return list1;
   }

   private void verifyIntersection(ConciseSet set1, ConciseSet set2)
   {
     List<Integer> expectedIntersection = toList(set1);
     expectedIntersection.retainAll(toList(set2));
     verifyIntersection(expectedIntersection, set1, set2);
   }

   private void verifyIntersection(List<Integer> expected, ConciseSet set1, ConciseSet set2)
   {
     ImmutableConciseSet immutableSet1 = ImmutableConciseSet.newImmutableFromMutable(set1);
     ImmutableConciseSet immutableSet2 = ImmutableConciseSet.newImmutableFromMutable(set2);
     if (compact) {
       immutableSet1 = ImmutableConciseSet.compact(immutableSet1);
       immutableSet2 = ImmutableConciseSet.compact(immutableSet2);
     }
     List<ImmutableConciseSet> immutableSets = Arrays.asList(immutableSet1, immutableSet2);
     verifyIntersection(expected, immutableSets);
   }

   private void verifyIntersection(List<Integer> expected, List<ImmutableConciseSet> sets)
   {
     List<Integer> actual = new ArrayList<>();
     ImmutableConciseSet set = ImmutableConciseSet.intersection(sets);
     IntSet.IntIterator itr = set.iterator();
     while (itr.hasNext()) {
       actual.add(itr.next());
     }
     Assert.assertEquals(expected, actual);
   }
 }
	/*
	* 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.druid.extendedset.intset;

	import junit.framework.Assert;
	import org.junit.Test;
	import org.junit.runner.RunWith;
	import org.junit.runners.Parameterized;

	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.Collections;
	import java.util.List;

	@RunWith(Parameterized.class)
	public class ImmutableConciseSetIntersectionTest
	{
	@Parameterized.Parameters
	public static List<Object[]> parameters()
	{
	return Arrays.asList(new Object[] {false}, new Object[] {true});
	}

	private boolean compact;

	public ImmutableConciseSetIntersectionTest(boolean compact)
	{
	this.compact = compact;
	}

	/**
	* Testing basic intersection of similar sets
	*/
	@Test
	public void testIntersection1()
	{
	final int[] ints1 = {33, 100000};
	final int[] ints2 = {33, 100000};
	List<Integer> expected = Arrays.asList(33, 100000);

	ConciseSet set1 = new ConciseSet();
	for (int i : ints1) {
	set1.add(i);
	}
	ConciseSet set2 = new ConciseSet();
	for (int i : ints2) {
	set2.add(i);
	}

	verifyIntersection(expected, set1, set2);
	}

	/**
	* Set1: literal, zero fill with flip bit, literal
	* Set2: literal, zero fill with different flip bit, literal
	*/
	@Test
	public void testIntersection2()
	{
	final int[] ints1 = {33, 100000};
	final int[] ints2 = {34, 100000};
	List<Integer> expected = Collections.singletonList(100000);

	ConciseSet set1 = new ConciseSet();
	for (int i : ints1) {
	set1.add(i);
	}
	ConciseSet set2 = new ConciseSet();
	for (int i : ints2) {
	set2.add(i);
	}

	verifyIntersection(expected, set1, set2);
	}

	/**
	* Testing intersection of one fills
	*/
	@Test
	public void testIntersection3()
	{
	List<Integer> expected = new ArrayList<>();
	ConciseSet set1 = new ConciseSet();
	ConciseSet set2 = new ConciseSet();
	for (int i = 0; i < 1000; i++) {
	set1.add(i);
	set2.add(i);
	expected.add(i);
	}

	verifyIntersection(expected, set1, set2);
	}

	/**
	* Similar to previous test with one bit in the sequence set to zero
	*/
	@Test
	public void testIntersection4()
	{
	List<Integer> expected = new ArrayList<>();
	ConciseSet set1 = new ConciseSet();
	ConciseSet set2 = new ConciseSet();
	for (int i = 0; i < 1000; i++) {
	set1.add(i);
	if (i != 500) {
	set2.add(i);
	expected.add(i);
	}
	}

	verifyIntersection(expected, set1, set2);
	}

	/**
	* Testing with disjoint sets
	*/
	@Test
	public void testIntersection5()
	{
	final int[] ints1 = {33, 100000};
	final int[] ints2 = {34, 200000};
	List<Integer> expected = new ArrayList<>();

	ConciseSet set1 = new ConciseSet();
	for (int i : ints1) {
	set1.add(i);
	}
	ConciseSet set2 = new ConciseSet();
	for (int i : ints2) {
	set2.add(i);
	}

	verifyIntersection(expected, set1, set2);
	}

	/**
	* Set 1: literal, zero fill, literal
	* Set 2: one fill, literal that falls within the zero fill above, one fill
	*/
	@Test
	public void testIntersection6()
	{
	List<Integer> expected = new ArrayList<>();
	ConciseSet set1 = new ConciseSet();
	for (int i = 0; i < 5; i++) {
	set1.add(i);
	}
	for (int i = 1000; i < 1005; i++) {
	set1.add(i);
	}

	ConciseSet set2 = new ConciseSet();
	for (int i = 800; i < 805; i++) {
	set2.add(i);
	}
	for (int i = 806; i < 1005; i++) {
	set2.add(i);
	}

	for (int i = 1000; i < 1005; i++) {
	expected.add(i);
	}

	verifyIntersection(expected, set1, set2);
	}

	@Test
	public void testIntersection7()
	{
	ConciseSet set1 = new ConciseSet();
	for (int i = 0; i < 3100; i++) {
	set1.add(i);
	}

	ConciseSet set2 = new ConciseSet();
	set2.add(100);
	set2.add(500);
	for (int i = 600; i < 700; i++) {
	set2.add(i);
	}

	List<Integer> expected = new ArrayList<>();
	expected.add(100);
	expected.add(500);
	for (int i = 600; i < 700; i++) {
	expected.add(i);
	}

	verifyIntersection(expected, set1, set2);
	}

	@Test
	public void testIntersection8()
	{
	ConciseSet set1 = new ConciseSet();
	for (int i = 0; i < 3100; i++) {
	set1.add(i);
	}
	set1.add(4001);

	ConciseSet set2 = new ConciseSet();
	set2.add(100);
	set2.add(500);
	for (int i = 600; i < 700; i++) {
	set2.add(i);
	}
	set2.add(4001);

	List<Integer> expected = new ArrayList<>();
	expected.add(100);
	expected.add(500);
	for (int i = 600; i < 700; i++) {
	expected.add(i);
	}
	expected.add(4001);

	verifyIntersection(expected, set1, set2);
	}

	@Test
	public void testIntersection9()
	{
	ConciseSet set1 = new ConciseSet();
	set1.add(2005);
	set1.add(3005);
	set1.add(3008);

	ConciseSet set2 = new ConciseSet();
	for (int i = 0; i < 3007; i++) {
	set2.add(i);
	}

	List<Integer> expected = new ArrayList<>();
	expected.add(2005);
	expected.add(3005);

	verifyIntersection(expected, set1, set2);
	}

	@Test
	public void testIntersection10()
	{
	ConciseSet set1 = new ConciseSet();
	for (int i = 0; i < 3100; i++) {
	set1.add(i);
	}

	ConciseSet set2 = new ConciseSet();

	set2.add(500);
	set2.add(600);
	set2.add(4001);

	List<Integer> expected = new ArrayList<>();
	expected.add(500);
	expected.add(600);

	verifyIntersection(expected, set1, set2);
	}

	@Test
	public void testIntersection11()
	{
	ConciseSet set1 = new ConciseSet();
	set1.add(2005);
	for (int i = 2800; i < 3500; i++) {
	set1.add(i);
	}

	ConciseSet set2 = new ConciseSet();
	for (int i = 0; i < 3007; i++) {
	set2.add(i);
	}

	List<Integer> expected = new ArrayList<>();
	expected.add(2005);
	for (int i = 2800; i < 3007; i++) {
	expected.add(i);
	}

	verifyIntersection(expected, set1, set2);
	}

	@Test
	public void testIntersection12()
	{
	ConciseSet set1 = new ConciseSet();
	set1.add(2005);
	for (int i = 2800; i < 3500; i++) {
	set1.add(i);
	}
	set1.add(10005);

	ConciseSet set2 = new ConciseSet();
	for (int i = 0; i < 3007; i++) {
	set2.add(i);
	}
	set2.add(10005);

	List<Integer> expected = new ArrayList<>();
	expected.add(2005);
	for (int i = 2800; i < 3007; i++) {
	expected.add(i);
	}
	expected.add(10005);

	verifyIntersection(expected, set1, set2);
	}

	@Test
	public void testIntersection13()
	{
	ConciseSet set1 = new ConciseSet();
	set1.add(2005);

	ConciseSet set2 = new ConciseSet();
	for (int i = 0; i < 100; i++) {
	set2.add(i);
	}

	List<Integer> expected = new ArrayList<>();

	verifyIntersection(expected, set1, set2);
	}

	@Test
	public void testIntersection14()
	{
	ConciseSet set1 = new ConciseSet();
	for (int i = 0; i < 1000; i++) {
	set1.add(i);
	}

	ConciseSet set2 = new ConciseSet();
	set2.add(0);
	set2.add(3);
	set2.add(5);
	set2.add(100);
	set2.add(101);

	List<Integer> expected = new ArrayList<>();
	expected.add(0);
	expected.add(3);
	expected.add(5);
	expected.add(100);
	expected.add(101);

	verifyIntersection(expected, set1, set2);
	}

	@Test
	public void testIntersection15()
	{
	ConciseSet set1 = new ConciseSet();
	for (int i = 0; i < 1000; i++) {
	set1.add(i);
	}

	ConciseSet set2 = new ConciseSet();
	set2.add(0);
	set2.add(3);
	set2.add(5);
	for (int i = 100; i < 500; i++) {
	set2.add(i);
	}

	List<Integer> expected = new ArrayList<>();
	expected.add(0);
	expected.add(3);
	expected.add(5);
	for (int i = 100; i < 500; i++) {
	expected.add(i);
	}

	verifyIntersection(expected, set1, set2);
	}

	@Test
	public void testIntersection16()
	{
	ConciseSet set1 = new ConciseSet();
	set1.add(2005);

	ConciseSet set2 = new ConciseSet();
	set2.add(0);
	set2.add(3);
	set2.add(5);
	set2.add(100);
	set2.add(101);

	List<Integer> expected = new ArrayList<>();

	verifyIntersection(expected, set1, set2);
	}

	@Test
	public void testIntersection17()
	{
	ConciseSet set1 = new ConciseSet();
	for (int i = 0; i < 4002; i++) {
	set1.add(i);
	}

	ConciseSet set2 = new ConciseSet();
	set2.add(4001);

	List<Integer> expected = new ArrayList<>();
	expected.add(4001);

	verifyIntersection(expected, set1, set2);
	}

	@Test
	public void testIntersection18()
	{
	ConciseSet set1 = new ConciseSet();
	for (int i = 32; i < 93; i++) {
	set1.add(i);
	}

	ConciseSet set2 = new ConciseSet();
	for (int i = 0; i < 62; i++) {
	set2.add(i);
	}

	List<Integer> expected = new ArrayList<>();
	for (int i = 32; i < 62; i++) {
	expected.add(i);
	}

	verifyIntersection(expected, set1, set2);
	}

	@Test
	public void testIntersection19()
	{
	ConciseSet set1 = new ConciseSet();
	set1.add(2005);

	ConciseSet set2 = new ConciseSet();
	for (int i = 0; i < 10000; i++) {
	set2.add(i);
	}

	List<Integer> expected = new ArrayList<>();
	expected.add(2005);

	verifyIntersection(expected, set1, set2);
	}

	@Test
	public void testIntersectionLiteralAndOneFill()
	{
	ConciseSet set1 = new ConciseSet();
	for (int i = 0; i < 31; i += 2) {
	set1.add(i);
	}
	ConciseSet set2 = new ConciseSet();
	for (int i = 0; i < 1000; i++) {
	if (i != 2) {
	set2.add(i);
	}
	}
	verifyIntersection(set1, set2);
	}

	@Test
	public void testIntersectionZeroSequenceRemovedFromQueue()
	{
	// Seems that it is impossible to test this case with naturally constructed ConciseSet, because the end of the
	// sequence is defined by the last set bit, then naturally constructed ConciseSet won't have the last word as zero
	// sequence, it will be a literal or one sequence.
	int zeroSequence = 1; // Zero sequence of length 62
	ConciseSet set1 = new ConciseSet(new int[] {zeroSequence}, false);

	ConciseSet set2 = new ConciseSet();
	for (int i = 0; i < 1000; i++) {
	set2.add(i);
	}
	verifyIntersection(set1, set2);
	}

	@Test
	public void testIntersectionOneFillAndOneFillWithFlipBit()
	{
	ConciseSet set1 = new ConciseSet();
	for (int i = 0; i < 100; i++) {
	set1.add(i);
	}
	ConciseSet set2 = new ConciseSet();
	for (int i = 0; i < 1000; i++) {
	if (i != 2) {
	set2.add(i);
	}
	}
	verifyIntersection(set1, set2);
	}

	@Test
	public void testIntersectionSecondOneFillRemovedFromQueue()
	{
	ConciseSet set1 = new ConciseSet();
	for (int i = 0; i < 31 * 2; i++) {
	set1.add(i);
	}
	set1.add(100);

	ConciseSet set2 = new ConciseSet();
	for (int i = 0; i < 31 * 3; i++) {
	set2.add(i);
	}

	verifyIntersection(set1, set2);
	}

	@Test
	public void testIntersectionFirstOneFillRemovedFromQueue()
	{
	ConciseSet set1 = new ConciseSet();
	for (int i = 0; i < 31 * 2; i++) {
	set1.add(i);
	}

	ConciseSet set2 = new ConciseSet();
	for (int i = 0; i < 31 * 3; i++) {
	set2.add(i);
	}

	verifyIntersection(set1, set2);
	}

	@Test
	public void testIntersectionTerminates()
	{
	verifyIntersection(Collections.emptyList(), Arrays.asList(new ImmutableConciseSet(), new ImmutableConciseSet()));
	}

	private static List<Integer> toList(ConciseSet set)
	{
	List<Integer> list1 = new ArrayList<>();
	for (IntSet.IntIterator it = set.iterator(); it.hasNext(); ) {
	list1.add(it.next());
	}
	return list1;
	}

	private void verifyIntersection(ConciseSet set1, ConciseSet set2)
	{
	List<Integer> expectedIntersection = toList(set1);
	expectedIntersection.retainAll(toList(set2));
	verifyIntersection(expectedIntersection, set1, set2);
	}

	private void verifyIntersection(List<Integer> expected, ConciseSet set1, ConciseSet set2)
	{
	ImmutableConciseSet immutableSet1 = ImmutableConciseSet.newImmutableFromMutable(set1);
	ImmutableConciseSet immutableSet2 = ImmutableConciseSet.newImmutableFromMutable(set2);
	if (compact) {
	immutableSet1 = ImmutableConciseSet.compact(immutableSet1);
	immutableSet2 = ImmutableConciseSet.compact(immutableSet2);
	}
	List<ImmutableConciseSet> immutableSets = Arrays.asList(immutableSet1, immutableSet2);
	verifyIntersection(expected, immutableSets);
	}

	private void verifyIntersection(List<Integer> expected, List<ImmutableConciseSet> sets)
	{
	List<Integer> actual = new ArrayList<>();
	ImmutableConciseSet set = ImmutableConciseSet.intersection(sets);
	IntSet.IntIterator itr = set.iterator();
	while (itr.hasNext()) {
	actual.add(itr.next());
	}
	Assert.assertEquals(expected, actual);
	}
	}