lucene/core/src/test/org/apache/lucene/util/packed/TestDirectMonotonic.java - lucene-solr - 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.lucene.util.packed;


 import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.List;
 import java.util.Random;

 import org.apache.lucene.store.Directory;
 import org.apache.lucene.store.IOContext;
 import org.apache.lucene.store.IndexInput;
 import org.apache.lucene.store.IndexOutput;
 import org.apache.lucene.util.ArrayUtil;
 import org.apache.lucene.util.LongValues;
 import org.apache.lucene.util.LuceneTestCase;
 import org.apache.lucene.util.TestUtil;

 public class TestDirectMonotonic extends LuceneTestCase {

   public void testValidation() {
     IllegalArgumentException e = expectThrows(IllegalArgumentException.class,
         () -> DirectMonotonicWriter.getInstance(null, null, -1, 10));
     assertEquals("numValues can't be negative, got -1", e.getMessage());

     e = expectThrows(IllegalArgumentException.class,
         () -> DirectMonotonicWriter.getInstance(null, null, 10, 1));
     assertEquals("blockShift must be in [2-22], got 1", e.getMessage());

     e = expectThrows(IllegalArgumentException.class,
         () -> DirectMonotonicWriter.getInstance(null, null, 1L << 40, 5));
     assertEquals("blockShift is too low for the provided number of values: blockShift=5, numValues=1099511627776, MAX_ARRAY_LENGTH=" +
         ArrayUtil.MAX_ARRAY_LENGTH, e.getMessage());
   }

   public void testEmpty() throws IOException {
     Directory dir = newDirectory();
     final int blockShift = TestUtil.nextInt(random(), DirectMonotonicWriter.MIN_BLOCK_SHIFT, DirectMonotonicWriter.MAX_BLOCK_SHIFT);

     final long dataLength;
     try (IndexOutput metaOut = dir.createOutput("meta", IOContext.DEFAULT);
         IndexOutput dataOut = dir.createOutput("data", IOContext.DEFAULT)) {
       DirectMonotonicWriter w = DirectMonotonicWriter.getInstance(metaOut, dataOut, 0, blockShift);
       w.finish();
       dataLength = dataOut.getFilePointer();
     }

     try (IndexInput metaIn = dir.openInput("meta", IOContext.READONCE);
         IndexInput dataIn = dir.openInput("data", IOContext.DEFAULT)) {
       DirectMonotonicReader.Meta meta = DirectMonotonicReader.loadMeta(metaIn, 0, blockShift);
       DirectMonotonicReader.getInstance(meta, dataIn.randomAccessSlice(0, dataLength));
       // no exception
     }

     dir.close();
   }

   public void testSimple() throws IOException {
     Directory dir = newDirectory();
     final int blockShift = 2;

     List<Long> actualValues = Arrays.asList(1L, 2L, 5L, 7L, 8L, 100L);
     final int numValues = actualValues.size();

     final long dataLength;
     try (IndexOutput metaOut = dir.createOutput("meta", IOContext.DEFAULT);
         IndexOutput dataOut = dir.createOutput("data", IOContext.DEFAULT)) {
       DirectMonotonicWriter w = DirectMonotonicWriter.getInstance(metaOut, dataOut, numValues, blockShift);
       for (long v : actualValues) {
         w.add(v);
       }
       w.finish();
       dataLength = dataOut.getFilePointer();
     }

     try (IndexInput metaIn = dir.openInput("meta", IOContext.READONCE);
         IndexInput dataIn = dir.openInput("data", IOContext.DEFAULT)) {
       DirectMonotonicReader.Meta meta = DirectMonotonicReader.loadMeta(metaIn, numValues, blockShift);
       LongValues values = DirectMonotonicReader.getInstance(meta, dataIn.randomAccessSlice(0, dataLength));
       for (int i = 0; i < numValues; ++i) {
         final long v = values.get(i);
         assertEquals(actualValues.get(i).longValue(), v);
       }
     }

     dir.close();
   }

   public void testConstantSlope() throws IOException {
     Directory dir = newDirectory();
     final int blockShift = TestUtil.nextInt(random(), DirectMonotonicWriter.MIN_BLOCK_SHIFT, DirectMonotonicWriter.MAX_BLOCK_SHIFT);
     final int numValues = TestUtil.nextInt(random(), 1, 1 << 20);
     final long min = random().nextLong();
     final long inc = random().nextInt(1 << random().nextInt(20));

     List<Long> actualValues = new ArrayList<>();
     for (int i = 0; i < numValues; ++i) {
       actualValues.add(min + inc * i);
     }

     final long dataLength;
     try (IndexOutput metaOut = dir.createOutput("meta", IOContext.DEFAULT);
         IndexOutput dataOut = dir.createOutput("data", IOContext.DEFAULT)) {
       DirectMonotonicWriter w = DirectMonotonicWriter.getInstance(metaOut, dataOut, numValues, blockShift);
       for (long v : actualValues) {
         w.add(v);
       }
       w.finish();
       dataLength = dataOut.getFilePointer();
     }

     try (IndexInput metaIn = dir.openInput("meta", IOContext.READONCE);
         IndexInput dataIn = dir.openInput("data", IOContext.DEFAULT)) {
       DirectMonotonicReader.Meta meta = DirectMonotonicReader.loadMeta(metaIn, numValues, blockShift);
       LongValues values = DirectMonotonicReader.getInstance(meta, dataIn.randomAccessSlice(0, dataLength));
       for (int i = 0; i < numValues; ++i) {
         assertEquals(actualValues.get(i).longValue(), values.get(i));
       }
       assertEquals(0, dataIn.getFilePointer());
     }

     dir.close();
   }

   public void testRandom() throws IOException {
     Random random = random();
     final int iters = atLeast(random, 3);
     for (int iter = 0; iter < iters; ++iter) {
       Directory dir = newDirectory();
       final int blockShift = TestUtil.nextInt(random, DirectMonotonicWriter.MIN_BLOCK_SHIFT, DirectMonotonicWriter.MAX_BLOCK_SHIFT);
       final int maxNumValues = 1 << 20;
       final int numValues;
       if (random.nextBoolean()) {
         // random number
         numValues = TestUtil.nextInt(random, 1, maxNumValues);
       } else {
         // multiple of the block size
         final int numBlocks = TestUtil.nextInt(random, 0, maxNumValues >>> blockShift);
         numValues = TestUtil.nextInt(random, 0, numBlocks) << blockShift;
       }
       List<Long> actualValues = new ArrayList<>();
       long previous = random.nextLong();
       if (numValues > 0) {
         actualValues.add(previous);
       }
       for (int i = 1; i < numValues; ++i) {
         previous += random.nextInt(1 << random.nextInt(20));
         actualValues.add(previous);
       }

       final long dataLength;
       try (IndexOutput metaOut = dir.createOutput("meta", IOContext.DEFAULT);
           IndexOutput dataOut = dir.createOutput("data", IOContext.DEFAULT)) {
         DirectMonotonicWriter w = DirectMonotonicWriter.getInstance(metaOut, dataOut, numValues, blockShift);
         for (long v : actualValues) {
           w.add(v);
         }
         w.finish();
         dataLength = dataOut.getFilePointer();
       }

       try (IndexInput metaIn = dir.openInput("meta", IOContext.READONCE);
           IndexInput dataIn = dir.openInput("data", IOContext.DEFAULT)) {
         DirectMonotonicReader.Meta meta = DirectMonotonicReader.loadMeta(metaIn, numValues, blockShift);
         LongValues values = DirectMonotonicReader.getInstance(meta, dataIn.randomAccessSlice(0, dataLength));
         for (int i = 0; i < numValues; ++i) {
           assertEquals(actualValues.get(i).longValue(), values.get(i));
         }
       }

       dir.close();
     }
   }

   public void testMonotonicBinarySearch() throws IOException {
     try (Directory dir = newDirectory()) {
       doTestMonotonicBinarySearchAgainstLongArray(dir, new long[] {4, 7, 8, 10, 19, 30, 55, 78, 100}, 2);
     }
   }

   public void testMonotonicBinarySearchRandom() throws IOException {
     try (Directory dir = newDirectory()) {
       final int iters = atLeast(100);
       for (int iter = 0; iter < iters; ++iter) {
         final int arrayLength = random().nextInt(1 << random().nextInt(14));
         final long[] array = new long[arrayLength];
         final long base = random().nextLong();
         final int bpv = TestUtil.nextInt(random(), 4, 61);
         for (int i = 0; i < array.length; ++i) {
           array[i] = base + TestUtil.nextLong(random(), 0, (1L << bpv) - 1);
         }
         Arrays.sort(array);
         doTestMonotonicBinarySearchAgainstLongArray(dir, array, TestUtil.nextInt(random(), 2, 10));
       }
     }
   }

   private void doTestMonotonicBinarySearchAgainstLongArray(Directory dir, long[] array, int blockShift) throws IOException {
     try (IndexOutput metaOut = dir.createOutput("meta", IOContext.DEFAULT);
         IndexOutput dataOut = dir.createOutput("data", IOContext.DEFAULT)) {
       DirectMonotonicWriter writer = DirectMonotonicWriter.getInstance(metaOut, dataOut, array.length, blockShift);
       for (long l : array) {
         writer.add(l);
       }
       writer.finish();
     }

     try (IndexInput metaIn = dir.openInput("meta", IOContext.READONCE);
         IndexInput dataIn = dir.openInput("data", IOContext.READ)) {
       DirectMonotonicReader.Meta meta = DirectMonotonicReader.loadMeta(metaIn, array.length, blockShift);
       DirectMonotonicReader reader = DirectMonotonicReader.getInstance(meta, dataIn.randomAccessSlice(0L, dir.fileLength("data")));

       if (array.length == 0) {
         assertEquals(-1, reader.binarySearch(0, array.length, 42L));
       } else {
         for (int i = 0; i < array.length; ++i) {
           final long index = reader.binarySearch(0, array.length, array[i]);
           assertTrue(index >= 0);
           assertTrue(index < array.length);
           assertEquals(array[i], array[(int) index]);
         }
         if (array[0] != Long.MIN_VALUE) {
           assertEquals(-1, reader.binarySearch(0, array.length, array[0] - 1));
         }
         if (array[array.length - 1] != Long.MAX_VALUE) {
           assertEquals(-1 - array.length, reader.binarySearch(0, array.length, array[array.length - 1] + 1));
         }
         for (int i = 0; i < array.length - 2; ++i) {
           if (array[i] + 1 < array[i+1]) {
             final long intermediate = random().nextBoolean() ? array[i] + 1 : array[i+1] - 1;
             final long index = reader.binarySearch(0, array.length, intermediate);
             assertTrue(index < 0);
             final int insertionPoint = Math.toIntExact(-1 -index);
             assertTrue(insertionPoint > 0);
             assertTrue(insertionPoint < array.length);
             assertTrue(array[insertionPoint] > intermediate);
             assertTrue(array[insertionPoint-1] < intermediate);
           }
         }
       }
     }
     dir.deleteFile("meta");
     dir.deleteFile("data");
   }
 }
	/*
	* 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.lucene.util.packed;


	import java.io.IOException;
	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.List;
	import java.util.Random;

	import org.apache.lucene.store.Directory;
	import org.apache.lucene.store.IOContext;
	import org.apache.lucene.store.IndexInput;
	import org.apache.lucene.store.IndexOutput;
	import org.apache.lucene.util.ArrayUtil;
	import org.apache.lucene.util.LongValues;
	import org.apache.lucene.util.LuceneTestCase;
	import org.apache.lucene.util.TestUtil;

	public class TestDirectMonotonic extends LuceneTestCase {

	public void testValidation() {
	IllegalArgumentException e = expectThrows(IllegalArgumentException.class,
	() -> DirectMonotonicWriter.getInstance(null, null, -1, 10));
	assertEquals("numValues can't be negative, got -1", e.getMessage());

	e = expectThrows(IllegalArgumentException.class,
	() -> DirectMonotonicWriter.getInstance(null, null, 10, 1));
	assertEquals("blockShift must be in [2-22], got 1", e.getMessage());

	e = expectThrows(IllegalArgumentException.class,
	() -> DirectMonotonicWriter.getInstance(null, null, 1L << 40, 5));
	assertEquals("blockShift is too low for the provided number of values: blockShift=5, numValues=1099511627776, MAX_ARRAY_LENGTH=" +
	ArrayUtil.MAX_ARRAY_LENGTH, e.getMessage());
	}

	public void testEmpty() throws IOException {
	Directory dir = newDirectory();
	final int blockShift = TestUtil.nextInt(random(), DirectMonotonicWriter.MIN_BLOCK_SHIFT, DirectMonotonicWriter.MAX_BLOCK_SHIFT);

	final long dataLength;
	try (IndexOutput metaOut = dir.createOutput("meta", IOContext.DEFAULT);
	IndexOutput dataOut = dir.createOutput("data", IOContext.DEFAULT)) {
	DirectMonotonicWriter w = DirectMonotonicWriter.getInstance(metaOut, dataOut, 0, blockShift);
	w.finish();
	dataLength = dataOut.getFilePointer();
	}

	try (IndexInput metaIn = dir.openInput("meta", IOContext.READONCE);
	IndexInput dataIn = dir.openInput("data", IOContext.DEFAULT)) {
	DirectMonotonicReader.Meta meta = DirectMonotonicReader.loadMeta(metaIn, 0, blockShift);
	DirectMonotonicReader.getInstance(meta, dataIn.randomAccessSlice(0, dataLength));
	// no exception
	}

	dir.close();
	}

	public void testSimple() throws IOException {
	Directory dir = newDirectory();
	final int blockShift = 2;

	List<Long> actualValues = Arrays.asList(1L, 2L, 5L, 7L, 8L, 100L);
	final int numValues = actualValues.size();

	final long dataLength;
	try (IndexOutput metaOut = dir.createOutput("meta", IOContext.DEFAULT);
	IndexOutput dataOut = dir.createOutput("data", IOContext.DEFAULT)) {
	DirectMonotonicWriter w = DirectMonotonicWriter.getInstance(metaOut, dataOut, numValues, blockShift);
	for (long v : actualValues) {
	w.add(v);
	}
	w.finish();
	dataLength = dataOut.getFilePointer();
	}

	try (IndexInput metaIn = dir.openInput("meta", IOContext.READONCE);
	IndexInput dataIn = dir.openInput("data", IOContext.DEFAULT)) {
	DirectMonotonicReader.Meta meta = DirectMonotonicReader.loadMeta(metaIn, numValues, blockShift);
	LongValues values = DirectMonotonicReader.getInstance(meta, dataIn.randomAccessSlice(0, dataLength));
	for (int i = 0; i < numValues; ++i) {
	final long v = values.get(i);
	assertEquals(actualValues.get(i).longValue(), v);
	}
	}

	dir.close();
	}

	public void testConstantSlope() throws IOException {
	Directory dir = newDirectory();
	final int blockShift = TestUtil.nextInt(random(), DirectMonotonicWriter.MIN_BLOCK_SHIFT, DirectMonotonicWriter.MAX_BLOCK_SHIFT);
	final int numValues = TestUtil.nextInt(random(), 1, 1 << 20);
	final long min = random().nextLong();
	final long inc = random().nextInt(1 << random().nextInt(20));

	List<Long> actualValues = new ArrayList<>();
	for (int i = 0; i < numValues; ++i) {
	actualValues.add(min + inc * i);
	}

	final long dataLength;
	try (IndexOutput metaOut = dir.createOutput("meta", IOContext.DEFAULT);
	IndexOutput dataOut = dir.createOutput("data", IOContext.DEFAULT)) {
	DirectMonotonicWriter w = DirectMonotonicWriter.getInstance(metaOut, dataOut, numValues, blockShift);
	for (long v : actualValues) {
	w.add(v);
	}
	w.finish();
	dataLength = dataOut.getFilePointer();
	}

	try (IndexInput metaIn = dir.openInput("meta", IOContext.READONCE);
	IndexInput dataIn = dir.openInput("data", IOContext.DEFAULT)) {
	DirectMonotonicReader.Meta meta = DirectMonotonicReader.loadMeta(metaIn, numValues, blockShift);
	LongValues values = DirectMonotonicReader.getInstance(meta, dataIn.randomAccessSlice(0, dataLength));
	for (int i = 0; i < numValues; ++i) {
	assertEquals(actualValues.get(i).longValue(), values.get(i));
	}
	assertEquals(0, dataIn.getFilePointer());
	}

	dir.close();
	}

	public void testRandom() throws IOException {
	Random random = random();
	final int iters = atLeast(random, 3);
	for (int iter = 0; iter < iters; ++iter) {
	Directory dir = newDirectory();
	final int blockShift = TestUtil.nextInt(random, DirectMonotonicWriter.MIN_BLOCK_SHIFT, DirectMonotonicWriter.MAX_BLOCK_SHIFT);
	final int maxNumValues = 1 << 20;
	final int numValues;
	if (random.nextBoolean()) {
	// random number
	numValues = TestUtil.nextInt(random, 1, maxNumValues);
	} else {
	// multiple of the block size
	final int numBlocks = TestUtil.nextInt(random, 0, maxNumValues >>> blockShift);
	numValues = TestUtil.nextInt(random, 0, numBlocks) << blockShift;
	}
	List<Long> actualValues = new ArrayList<>();
	long previous = random.nextLong();
	if (numValues > 0) {
	actualValues.add(previous);
	}
	for (int i = 1; i < numValues; ++i) {
	previous += random.nextInt(1 << random.nextInt(20));
	actualValues.add(previous);
	}

	final long dataLength;
	try (IndexOutput metaOut = dir.createOutput("meta", IOContext.DEFAULT);
	IndexOutput dataOut = dir.createOutput("data", IOContext.DEFAULT)) {
	DirectMonotonicWriter w = DirectMonotonicWriter.getInstance(metaOut, dataOut, numValues, blockShift);
	for (long v : actualValues) {
	w.add(v);
	}
	w.finish();
	dataLength = dataOut.getFilePointer();
	}

	try (IndexInput metaIn = dir.openInput("meta", IOContext.READONCE);
	IndexInput dataIn = dir.openInput("data", IOContext.DEFAULT)) {
	DirectMonotonicReader.Meta meta = DirectMonotonicReader.loadMeta(metaIn, numValues, blockShift);
	LongValues values = DirectMonotonicReader.getInstance(meta, dataIn.randomAccessSlice(0, dataLength));
	for (int i = 0; i < numValues; ++i) {
	assertEquals(actualValues.get(i).longValue(), values.get(i));
	}
	}

	dir.close();
	}
	}

	public void testMonotonicBinarySearch() throws IOException {
	try (Directory dir = newDirectory()) {
	doTestMonotonicBinarySearchAgainstLongArray(dir, new long[] {4, 7, 8, 10, 19, 30, 55, 78, 100}, 2);
	}
	}

	public void testMonotonicBinarySearchRandom() throws IOException {
	try (Directory dir = newDirectory()) {
	final int iters = atLeast(100);
	for (int iter = 0; iter < iters; ++iter) {
	final int arrayLength = random().nextInt(1 << random().nextInt(14));
	final long[] array = new long[arrayLength];
	final long base = random().nextLong();
	final int bpv = TestUtil.nextInt(random(), 4, 61);
	for (int i = 0; i < array.length; ++i) {
	array[i] = base + TestUtil.nextLong(random(), 0, (1L << bpv) - 1);
	}
	Arrays.sort(array);
	doTestMonotonicBinarySearchAgainstLongArray(dir, array, TestUtil.nextInt(random(), 2, 10));
	}
	}
	}

	private void doTestMonotonicBinarySearchAgainstLongArray(Directory dir, long[] array, int blockShift) throws IOException {
	try (IndexOutput metaOut = dir.createOutput("meta", IOContext.DEFAULT);
	IndexOutput dataOut = dir.createOutput("data", IOContext.DEFAULT)) {
	DirectMonotonicWriter writer = DirectMonotonicWriter.getInstance(metaOut, dataOut, array.length, blockShift);
	for (long l : array) {
	writer.add(l);
	}
	writer.finish();
	}

	try (IndexInput metaIn = dir.openInput("meta", IOContext.READONCE);
	IndexInput dataIn = dir.openInput("data", IOContext.READ)) {
	DirectMonotonicReader.Meta meta = DirectMonotonicReader.loadMeta(metaIn, array.length, blockShift);
	DirectMonotonicReader reader = DirectMonotonicReader.getInstance(meta, dataIn.randomAccessSlice(0L, dir.fileLength("data")));

	if (array.length == 0) {
	assertEquals(-1, reader.binarySearch(0, array.length, 42L));
	} else {
	for (int i = 0; i < array.length; ++i) {
	final long index = reader.binarySearch(0, array.length, array[i]);
	assertTrue(index >= 0);
	assertTrue(index < array.length);
	assertEquals(array[i], array[(int) index]);
	}
	if (array[0] != Long.MIN_VALUE) {
	assertEquals(-1, reader.binarySearch(0, array.length, array[0] - 1));
	}
	if (array[array.length - 1] != Long.MAX_VALUE) {
	assertEquals(-1 - array.length, reader.binarySearch(0, array.length, array[array.length - 1] + 1));
	}
	for (int i = 0; i < array.length - 2; ++i) {
	if (array[i] + 1 < array[i+1]) {
	final long intermediate = random().nextBoolean() ? array[i] + 1 : array[i+1] - 1;
	final long index = reader.binarySearch(0, array.length, intermediate);
	assertTrue(index < 0);
	final int insertionPoint = Math.toIntExact(-1 -index);
	assertTrue(insertionPoint > 0);
	assertTrue(insertionPoint < array.length);
	assertTrue(array[insertionPoint] > intermediate);
	assertTrue(array[insertionPoint-1] < intermediate);
	}
	}
	}
	}
	dir.deleteFile("meta");
	dir.deleteFile("data");
	}
	}