Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  package it.unimi.dsi.sux4j.bits;
  
  import static org.junit.Assert.assertEquals;
  
  import java.util.Random;
  
  import org.junit.Test;
 
 public class SimpleSelectTest extends RankSelectTestCase {
 
 	@Test
 	public void testEmpty() {
 		SimpleSelect select;
 
 		select = new SimpleSelectnew long[ 1 ], 64 );
 		assertEquals( -1, select.select( 0 ) );
 		assertEquals( -1, select.select( 1 ) );
 
 		select = new SimpleSelectnew long[ 2 ], 128 );
 		assertEquals( -1, select.select( 0 ) );
 		assertEquals( -1, select.select( 1 ) );
 
 		select = new SimpleSelectnew long[ 1 ], 63 );
 		assertEquals( -1, select.select( 0 ) );
 		assertEquals( -1, select.select( 1 ) );
 
 		select = new SimpleSelectnew long[ 2 ], 65 );
 		assertEquals( -1, select.select( 0 ) );
 		assertEquals( -1, select.select( 1 ) );
 
 		select = new SimpleSelectnew long[ 3 ], 129 );
 		assertEquals( -1, select.select( 0 ) );
 		assertEquals( -1, select.select( 1 ) );
 
 	}
 
 	@Test
 	public void testSingleton() {
 		SimpleSelect select;
 
 		select = new SimpleSelectnew long[] { 1L << 63, 0 }, 64 );
 		assertSelectselect );
 		assertEquals( 63, select.select( 0 ) );
 		assertEquals( -1, select.select( 1 ) );
 
 		select = new SimpleSelectnew long[] { 1 }, 64 );
 		assertSelectselect );
 		assertEquals( 0, select.select( 0 ) );
 		assertEquals( -1, select.select( 1 ) );
 
 		select = new SimpleSelectnew long[] { 1L << 63, 0 }, 128 );
 		assertSelectselect );
 		assertEquals( 63, select.select( 0 ) );
 		assertEquals( -1, select.select( 1 ) );
 
 		select = new SimpleSelectnew long[] { 1L << 63, 0 }, 65 );
 		assertSelectselect );
 		assertEquals( 63, select.select( 0 ) );
 		assertEquals( -1, select.select( 1 ) );
 
 		select = new SimpleSelectnew long[] { 1L << 63, 0, 0 }, 129 );
 		assertSelectselect );
 		assertEquals( 63, select.select( 0 ) );
 		assertEquals( -1, select.select( 1 ) );
 	}
 
 	@Test
 	public void testDoubleton() {
 		SimpleSelect select;
 
 		select = new SimpleSelectnew long[] { 1 | 1L << 32 }, 64 );
 		assertSelectselect );
 		assertEquals( 0, select.select( 0 ) );
 		assertEquals( 32, select.select( 1 ) );
 		assertEquals( -1, select.select( 2 ) );
 
 		select = new SimpleSelectnew long[] { 1, 1 }, 128 );
 		assertSelectselect );
 		assertEquals( 0, select.select( 0 ) );
 		assertEquals( 64, select.select( 1 ) );
 		assertEquals( -1, select.select( 2 ) );
 
 		select = new SimpleSelectnew long[] { 1 | 1L << 32, 0 }, 63 );
 		assertSelectselect );
 		assertEquals( 0, select.select( 0 ) );
 		assertEquals( 32, select.select( 1 ) );
 		assertEquals( -1, select.select( 2 ) );
 
 		select = new SimpleSelectnew long[] { 1, 1, 0 }, 129 );
 		assertSelectselect );
 		assertEquals( 0, select.select( 0 ) );
 		assertEquals( 64, select.select( 1 ) );
 		assertEquals( -1, select.select( 2 ) );
 	}
 
 	@Test
 	public void testAlternating() {
		SimpleSelect select;
		int i;
		select = new SimpleSelectnew long[] { 0xAAAAAAAAAAAAAAAAL }, 64 );
		assertSelectselect );
		for ( i = 32; i-- != 1; )
			assertEqualsi * 2 + 1, select.selecti ) );
		select = new SimpleSelectnew long[] { 0xAAAAAAAAAAAAAAAAL, 0xAAAAAAAAAAAAAAAAL }, 128 );
		assertSelectselect );
		for ( i = 64; i-- != 1; )
			assertEqualsi * 2 + 1, select.selecti ) );
		select = new SimpleSelectnew long[] { 0xAAAAAAAAAAAAAAAAL, 0xAAAAAAAAAAAAAAAAL, 0xAAAAAAAAAAAAAAAAL, 0xAAAAAAAAAAAAAAAAL, 0xAAAAAAAAAAAAAAAAL }, 64 * 5 );
		assertSelectselect );
		for ( i = 32 * 5; i-- != 1; )
			assertEqualsi * 2 + 1, select.selecti ) );
		select = new SimpleSelectnew long[] { 0xAAAAAAAAL }, 33 );
		assertSelectselect );
		for ( i = 16; i-- != 1; )
			assertEqualsi * 2 + 1, select.selecti ) );
		select = new SimpleSelectnew long[] { 0xAAAAAAAAAAAAAAAAL, 0xAAAAAAAAAAAAL }, 128 );
		assertSelectselect );
		for ( i = 56; i-- != 1; )
			assertEqualsi * 2 + 1, select.selecti ) );
	}
	public void testSelect() {
		SimpleSelect select;
		select = new SimpleSelect( LongArrayBitVector.of( 1, 0, 1, 1, 0, 0, 0 ).bits(), 7 );
		assertSelectselect );
		assertEquals( 0, select.select( 0 ) );
	}
	public void testSparse() {
		LongArrayBitVector bitVector = LongArrayBitVector.getInstance().length( 256 * 1024 );
		bitVector.set( 1 );
		bitVector.set( 100000 );
		bitVector.set( 199999 );
		SimpleSelect select;
		select = new SimpleSelectbitVector );
		assertSelectselect );
		bitVector = LongArrayBitVector.getInstance().length( 64 * 1024 );
		bitVector.set( 1 );
		bitVector.set( 40000 );
		bitVector.set( 49999 );
		select = new SimpleSelectbitVector );
		assertSelectselect );
		bitVector = LongArrayBitVector.getInstance().length( 32 * 1024 );
		bitVector.set( 1 );
		bitVector.set( 20000 );
		bitVector.set( 29999 );
		select = new SimpleSelectbitVector );
		assertSelectselect );
	}
	public void testAllOnes() {
		LongArrayBitVector bitVector = LongArrayBitVector.getInstance().length( 257 );
		bitVector.filltrue );
		SimpleSelect simpleSelect = new SimpleSelectbitVector );
		assertEquals( 0, simpleSelect.select( 0 ) );
	}
	public void testAllZeroes() {
		LongArrayBitVector bitVector = LongArrayBitVector.getInstance().length( 257 );
		SimpleSelect simpleSelect = new SimpleSelectbitVector );
		assertEquals( -1, simpleSelect.select( 0 ) );
	}
	public void testDense() {
		LongArrayBitVector bitVector = LongArrayBitVector.getInstance().length( 16 * 1024 );
		for ( int i = 0; i <= 512; i++ )
			bitVector.seti * 2 );
		SimpleSelect select;
		select = new SimpleSelectbitVector );
		assertSelectselect );
		bitVector = LongArrayBitVector.getInstance().length( 16 * 1024 );
		for ( int i = 0; i <= 512; i++ )
			bitVector.seti * 4 );
		select = new SimpleSelectbitVector );
		assertSelectselect );
		bitVector = LongArrayBitVector.getInstance().length( 16 * 1024 );
		for ( int i = 0; i <= 512; i++ )
			bitVector.seti * 8 );
		select = new SimpleSelectbitVector );
		assertSelectselect );
		bitVector = LongArrayBitVector.getInstance().length( 16 * 1024 );
		for ( int i = 0; i <= 512; i++ )
			bitVector.seti * 16 );
		select = new SimpleSelectbitVector );
		assertSelectselect );
		bitVector = LongArrayBitVector.getInstance().length( 32 * 1024 );
		for ( int i = 0; i <= 512; i++ )
			bitVector.seti * 32 );
		select = new SimpleSelectbitVector );
		assertSelectselect );
	}
	public void testRandom() {
		Random r = new XorShift1024StarRandom( 1 );
		LongArrayBitVector bitVector = LongArrayBitVector.getInstance( 1000 );
		for ( int i = 0; i < 1000; i++ )
			bitVector.addr.nextBoolean() );
		SimpleSelect select;
		select = new SimpleSelectbitVector );
		assertSelectselect );
	}
	public void testAllSizes() {
		for ( int size = 0; size <= 4096; size++ ) {
			v = LongArrayBitVector.getInstance().lengthsize );
			for ( int i = ( size + 1 ) / 2; i-- != 0; )
				v.seti * 2 );
			r = new SimpleSelectv );
			for ( int i = size / 2; i-- != 0; )
				assertEqualsi * 2, r.selecti ) );
			v = LongArrayBitVector.getInstance().lengthsize );
			v.filltrue );
			r = new SimpleSelectv );
			for ( int i = sizei-- != 0; )
				assertEqualsir.selecti ) );
		}
	}
	public void testBulk() {
		final long[] s = new long[ 100000 ];
		forint i = s.lengthi-- != 0; ) si ] = random.nextLong() & 0xF0F0F0F088884444L;
		final SimpleSelect ef = new SimpleSelectss.length * . );
		forint i = 0; i < 1000; i++ ) {
			final int from = random.nextInts.length - 100 );
			final int to = from + random.nextInt( 100 );
			final int offset = random.nextInt( 10 );
			final long[] dest = ef.selectfromnew longto - from + offset + random.nextInt( 10 ) ], offsetto - from );
			forint j = fromj < toj++ ) assertEquals"From: " + from + " to: " + to + " j: " + jef.selectj ), destoffset + j - from ] );
		}
	}
New to GrepCode? Check out our FAQ X