@Override
public PointsReader fieldsReader(SegmentReadState state) {
  return new PointsReader() {
    @Override
    public void close() {
    }

    @Override
    public long ramBytesUsed() {
      return 0L;
    }

    @Override
    public void checkIntegrity() {
    }

    @Override
    public PointValues getValues(String field) {
      throw new IllegalArgumentException("field=\"" + field + "\" was not indexed with points");
    }
  };
}
 

public void testDocCountEdgeCases() {
  PointValues values = getPointValues(Long.MAX_VALUE, 1, Long.MAX_VALUE);
  long docs = values.estimateDocCount(null);
  assertEquals(1, docs);
  values = getPointValues(Long.MAX_VALUE, 1, 1);
  docs = values.estimateDocCount(null);
  assertEquals(1, docs);
  values = getPointValues(Long.MAX_VALUE, Integer.MAX_VALUE, Long.MAX_VALUE);
  docs = values.estimateDocCount(null);
  assertEquals(Integer.MAX_VALUE, docs);
  values = getPointValues(Long.MAX_VALUE, Integer.MAX_VALUE, Long.MAX_VALUE / 2);
  docs = values.estimateDocCount(null);
  assertEquals(Integer.MAX_VALUE, docs);
  values = getPointValues(Long.MAX_VALUE, Integer.MAX_VALUE, 1);
  docs = values.estimateDocCount(null);
  assertEquals(1, docs);
}
 

private void doTestRandomBinary(int count) throws Exception {
  int numDocs = TestUtil.nextInt(random(), count, count*2);
  int numBytesPerDim = TestUtil.nextInt(random(), 2, 30);

  int numDataDims = TestUtil.nextInt(random(), 1, PointValues.MAX_DIMENSIONS);
  int numIndexDims = Math.min(TestUtil.nextInt(random(), 1, numDataDims), PointValues.MAX_INDEX_DIMENSIONS);

  byte[][][] docValues = new byte[numDocs][][];

  for(int docID=0;docID<numDocs;docID++) {
    byte[][] values = new byte[numDataDims][];
    for(int dim=0;dim<numDataDims;dim++) {
      values[dim] = new byte[numBytesPerDim];
      random().nextBytes(values[dim]);
    }
    docValues[docID] = values;
  }

  verify(docValues, null, numDataDims, numIndexDims, numBytesPerDim);
}
 

public void testAllEqual() throws Exception {
  int numBytesPerDim = TestUtil.nextInt(random(), 2, 30);
  int numDataDims = TestUtil.nextInt(random(), 1, PointValues.MAX_DIMENSIONS);
  int numIndexDims = Math.min(TestUtil.nextInt(random(), 1, numDataDims), PointValues.MAX_INDEX_DIMENSIONS);

  int numDocs = atLeast(1000);
  byte[][][] docValues = new byte[numDocs][][];

  for(int docID=0;docID<numDocs;docID++) {
    if (docID == 0) {
      byte[][] values = new byte[numDataDims][];
      for(int dim=0;dim<numDataDims;dim++) {
        values[dim] = new byte[numBytesPerDim];
        random().nextBytes(values[dim]);
      }
      docValues[docID] = values;
    } else {
      docValues[docID] = docValues[0];
    }
  }

  verify(docValues, null, numDataDims, numIndexDims, numBytesPerDim);
}
 

public void testOneDimEqual() throws Exception {
  int numBytesPerDim = TestUtil.nextInt(random(), 2, 30);
  int numDataDims = TestUtil.nextInt(random(), 1, PointValues.MAX_DIMENSIONS);
  int numIndexDims = Math.min(TestUtil.nextInt(random(), 1, numDataDims), PointValues.MAX_INDEX_DIMENSIONS);

  int numDocs = atLeast(1000);
  int theEqualDim = random().nextInt(numDataDims);
  byte[][][] docValues = new byte[numDocs][][];

  for(int docID=0;docID<numDocs;docID++) {
    byte[][] values = new byte[numDataDims][];
    for(int dim=0;dim<numDataDims;dim++) {
      values[dim] = new byte[numBytesPerDim];
      random().nextBytes(values[dim]);
    }
    docValues[docID] = values;
    if (docID > 0) {
      docValues[docID][theEqualDim] = docValues[0][theEqualDim];
    }
  }

  // Use a small number of points in leaf blocks to trigger a lot of splitting
  verify(docValues, null, numDataDims, numIndexDims, numBytesPerDim, TestUtil.nextInt(random(), 20, 50));
}
 

public void testRandomFewDifferentValues() throws Exception {
  int numBytesPerDim = TestUtil.nextInt(random(), 2, 30);
  int numDataDims = TestUtil.nextInt(random(), 1, PointValues.MAX_DIMENSIONS);
  int numIndexDims = Math.min(TestUtil.nextInt(random(), 1, numDataDims), PointValues.MAX_INDEX_DIMENSIONS);

  int numDocs = atLeast(10000);
  int cardinality = TestUtil.nextInt(random(), 2, 100);
  byte[][][] values = new byte[cardinality][numDataDims][numBytesPerDim];
  for (int i = 0; i < cardinality; i++) {
    for (int j = 0; j < numDataDims; j++) {
      random().nextBytes(values[i][j]);
    }
  }

  byte[][][] docValues = new byte[numDocs][][];
  for(int docID = 0; docID < numDocs; docID++) {
    docValues[docID] = values[random().nextInt(cardinality)];
  }

  verify(docValues, null, numDataDims, numIndexDims, numBytesPerDim);
}
 

private static FieldType randomFieldType() throws Exception {
  // setDimensions handled special as values must be in-bounds.
  Method setDimensionsMethodA = FieldType.class.getMethod("setDimensions", int.class, int.class);
  Method setDimensionsMethodB = FieldType.class.getMethod("setDimensions", int.class, int.class, int.class);
  FieldType ft = new FieldType();
  for (Method method : FieldType.class.getMethods()) {
    if (method.getName().startsWith("set")) {
      final Class<?>[] parameterTypes = method.getParameterTypes();
      final Object[] args = new Object[parameterTypes.length];
      if (method.equals(setDimensionsMethodA)) {
        args[0] = 1 + random().nextInt(PointValues.MAX_INDEX_DIMENSIONS);
        args[1] = 1 + random().nextInt(PointValues.MAX_NUM_BYTES);
      } else if (method.equals(setDimensionsMethodB)) {
        args[0] = 1 + random().nextInt(PointValues.MAX_DIMENSIONS);
        args[1] = 1 + Math.min((Integer)args[0] - 1, random().nextInt(PointValues.MAX_INDEX_DIMENSIONS));
        args[2] = 1 + random().nextInt(PointValues.MAX_NUM_BYTES);
      } else {
        for (int i = 0; i < args.length; ++i) {
          args[i] = randomValue(parameterTypes[i]);
        }
      }
      method.invoke(ft, args);
    }
  }
  return ft;
}
 

public void testDocCountEdgeCases() {
  PointValues values = getPointValues(Long.MAX_VALUE, 1, Long.MAX_VALUE);
  long docs = values.estimateDocCount(null);
  assertEquals(1, docs);
  values = getPointValues(Long.MAX_VALUE, 1, 1);
  docs = values.estimateDocCount(null);
  assertEquals(1, docs);
  values = getPointValues(Long.MAX_VALUE, Integer.MAX_VALUE, Long.MAX_VALUE);
  docs = values.estimateDocCount(null);
  assertEquals(Integer.MAX_VALUE, docs);
  values = getPointValues(Long.MAX_VALUE, Integer.MAX_VALUE, Long.MAX_VALUE / 2);
  docs = values.estimateDocCount(null);
  assertEquals(Integer.MAX_VALUE, docs);
  values = getPointValues(Long.MAX_VALUE, Integer.MAX_VALUE, 1);
  docs = values.estimateDocCount(null);
  assertEquals(1, docs);
}
 

@Override
public PointValues getValues(String fieldName) throws IOException {
  FieldInfo fieldInfo = readState.fieldInfos.fieldInfo(fieldName);
  if (fieldInfo == null) {
    throw new IllegalArgumentException("field=\"" + fieldName + "\" is unrecognized");
  }
  if (fieldInfo.getPointDimensionCount() == 0) {
    throw new IllegalArgumentException("field=\"" + fieldName + "\" did not index points");
  }
  return readers.get(fieldName);
}
 

@Override
public PointValues.Relation compare(byte[] minPackedValue, byte[] maxPackedValue) {
  if (hitQueue.size() == topN && pointToRectangleDistanceSquared(minPackedValue, maxPackedValue, origin) > bottomNearestDistanceSquared) {
    return PointValues.Relation.CELL_OUTSIDE_QUERY;
  }
  return PointValues.Relation.CELL_CROSSES_QUERY;
}
 

public static TopFieldDocs nearest(IndexSearcher searcher, String field, int topN, float... origin) throws IOException {
  if (topN < 1) {
    throw new IllegalArgumentException("topN must be at least 1; got " + topN);
  }
  if (field == null) {
    throw new IllegalArgumentException("field must not be null");
  }
  if (searcher == null) {
    throw new IllegalArgumentException("searcher must not be null");
  }
  List<BKDReader> readers = new ArrayList<>();
  List<Integer> docBases = new ArrayList<>();
  List<Bits> liveDocs = new ArrayList<>();
  int totalHits = 0;
  for (LeafReaderContext leaf : searcher.getIndexReader().leaves()) {
    PointValues points = leaf.reader().getPointValues(field);
    if (points != null) {
      if (points instanceof BKDReader == false) {
        throw new IllegalArgumentException("can only run on Lucene60PointsReader points implementation, but got " + points);
      }
      totalHits += points.getDocCount();
      readers.add((BKDReader)points);
      docBases.add(leaf.docBase);
      liveDocs.add(leaf.reader().getLiveDocs());
    }
  }

  NearestHit[] hits = nearest(readers, liveDocs, docBases, topN, origin);

  // Convert to TopFieldDocs:
  ScoreDoc[] scoreDocs = new ScoreDoc[hits.length];
  for(int i=0;i<hits.length;i++) {
    NearestHit hit = hits[i];
    scoreDocs[i] = new FieldDoc(hit.docID, 0.0f, new Object[] { (float)Math.sqrt(hit.distanceSquared) });
  }
  return new TopFieldDocs(new TotalHits(totalHits, TotalHits.Relation.EQUAL_TO), scoreDocs, null);
}
 

@Override
public PointValues getValues(String field) throws IOException {
  if (merging) {
    AssertingCodec.assertThread("PointsReader", creationThread);
  }
  PointValues values = this.in.getValues(field);
  if (values == null) {
    return null;
  }
  return new AssertingLeafReader.AssertingPointValues(values, maxDoc);
}
 

@Override
public PointValues.Relation relate(double minX, double maxX, double minY, double maxY) {
  if (Component2D.disjoint(this.minX, this.maxX, this.minY, this.maxY, minX, maxX, minY, maxY)) {
    return PointValues.Relation.CELL_OUTSIDE_QUERY;
  }
  if (Component2D.within(minX, maxX, minY, maxY, this.minX, this.maxX, this.minY, this.maxY)) {
    return PointValues.Relation.CELL_INSIDE_QUERY;
  }
  return PointValues.Relation.CELL_CROSSES_QUERY;
}
 

/**
 * Compute the relation between the provided box and distance query.
 * This only works for boxes that do not cross the dateline.
 */
public static PointValues.Relation relate(
    double minLat, double maxLat, double minLon, double maxLon,
    double lat, double lon, double distanceSortKey, double axisLat) {

  if (minLon > maxLon) {
    throw new IllegalArgumentException("Box crosses the dateline");
  }

  if ((lon < minLon || lon > maxLon) && (axisLat + Rectangle.AXISLAT_ERROR < minLat || axisLat - Rectangle.AXISLAT_ERROR > maxLat)) {
    // circle not fully inside / crossing axis
    if (SloppyMath.haversinSortKey(lat, lon, minLat, minLon) > distanceSortKey &&
        SloppyMath.haversinSortKey(lat, lon, minLat, maxLon) > distanceSortKey &&
        SloppyMath.haversinSortKey(lat, lon, maxLat, minLon) > distanceSortKey &&
        SloppyMath.haversinSortKey(lat, lon, maxLat, maxLon) > distanceSortKey) {
      // no points inside
      return Relation.CELL_OUTSIDE_QUERY;
    }
  }

  if (within90LonDegrees(lon, minLon, maxLon) &&
      SloppyMath.haversinSortKey(lat, lon, minLat, minLon) <= distanceSortKey &&
      SloppyMath.haversinSortKey(lat, lon, minLat, maxLon) <= distanceSortKey &&
      SloppyMath.haversinSortKey(lat, lon, maxLat, minLon) <= distanceSortKey &&
      SloppyMath.haversinSortKey(lat, lon, maxLat, maxLon) <= distanceSortKey) {
    // we are fully enclosed, collect everything within this subtree
    return Relation.CELL_INSIDE_QUERY;
  }

  return Relation.CELL_CROSSES_QUERY;
}
 

@Override
public PointValues.Relation relate(double minX, double maxX, double minY, double maxY) {
  if (Component2D.containsPoint(x, y, minX, maxX, minY, maxY)) {
    return PointValues.Relation.CELL_CROSSES_QUERY;
  }
  return PointValues.Relation.CELL_OUTSIDE_QUERY;
}
 

/** Returns the underlying {@link BKDReader}.
 *
 * @lucene.internal */
@Override
public PointValues getValues(String fieldName) {
  FieldInfo fieldInfo = readState.fieldInfos.fieldInfo(fieldName);
  if (fieldInfo == null) {
    throw new IllegalArgumentException("field=\"" + fieldName + "\" is unrecognized");
  }
  if (fieldInfo.getPointDimensionCount() == 0) {
    throw new IllegalArgumentException("field=\"" + fieldName + "\" did not index point values");
  }

  return readers.get(fieldInfo.number);
}
 

protected DistanceScorer(Weight weight, int maxDoc, long leadCost, float boost,
    PointValues pointValues, NumericDocValues docValues) {
  super(weight);
  this.maxDoc = maxDoc;
  this.leadCost = leadCost;
  this.boost = boost;
  this.pointValues = pointValues;
  this.docValues = docValues;
  // initially use doc values in order to iterate all documents that have
  // a value for this field
  this.it = docValues;
}
 

protected DistanceScorer(Weight weight, int maxDoc, long leadCost, float boost,
    PointValues pointValues, NumericDocValues docValues) {
  super(weight);
  this.maxDoc = maxDoc;
  this.leadCost = leadCost;
  this.boost = boost;
  this.pointValues = pointValues;
  this.docValues = docValues;
  // initially use doc values in order to iterate all documents that have
  // a value for this field
  this.it = docValues;
}
 

public void testRandomTriangles() {
  Random random = random();
  XYRectangle rectangle = ShapeTestUtil.nextBox(random);
  Component2D rectangle2D = Rectangle2D.create(rectangle);
  for (int i =0; i < 100; i++) {
    float ax = ShapeTestUtil.nextFloat(random);
    float ay = ShapeTestUtil.nextFloat(random);
    float bx = ShapeTestUtil.nextFloat(random);
    float by = ShapeTestUtil.nextFloat(random);
    float cx = ShapeTestUtil.nextFloat(random);
    float cy = ShapeTestUtil.nextFloat(random);

    float tMinX = StrictMath.min(StrictMath.min(ax, bx), cx);
    float tMaxX = StrictMath.max(StrictMath.max(ax, bx), cx);
    float tMinY = StrictMath.min(StrictMath.min(ay, by), cy);
    float tMaxY = StrictMath.max(StrictMath.max(ay, by), cy);


    PointValues.Relation r = rectangle2D.relate(tMinX, tMaxX, tMinY, tMaxY);
    if (r == PointValues.Relation.CELL_OUTSIDE_QUERY) {
      assertFalse(rectangle2D.intersectsTriangle(ax, ay, bx, by, cx, cy));
      assertFalse(rectangle2D.intersectsLine(ax, ay, bx, by));
      assertFalse(rectangle2D.containsTriangle(ax, ay, bx, by , cx, cy));
      assertFalse(rectangle2D.containsLine(ax, ay, bx, by));
      assertEquals(Component2D.WithinRelation.DISJOINT, rectangle2D.withinTriangle(ax, ay, true, bx, by, true, cx, cy, true));
    }
    else if (r == PointValues.Relation.CELL_INSIDE_QUERY) {
      assertTrue(rectangle2D.intersectsTriangle(ax, ay, bx, by, cx, cy));
      assertTrue(rectangle2D.intersectsLine(ax, ay, bx, by));
      assertTrue(rectangle2D.containsTriangle(ax, ay, bx, by , cx, cy));
      assertTrue(rectangle2D.containsLine(ax, ay, bx, by));
    }
  }
}
 

public void testRandomDocCount() {
  for (int i = 0; i < 100; i++) {
    long size = TestUtil.nextLong(random(), 1, Long.MAX_VALUE);
    int maxDoc = (size > Integer.MAX_VALUE) ? Integer.MAX_VALUE : Math.toIntExact(size);
    int docCount = TestUtil.nextInt(random(), 1, maxDoc);
    long estimatedPointCount = TestUtil.nextLong(random(), 0, size);
    PointValues values = getPointValues(size, docCount, estimatedPointCount);
    long docs = values.estimateDocCount(null);
    assertTrue(docs <= estimatedPointCount);
    assertTrue(docs <= maxDoc);
    assertTrue(docs >= estimatedPointCount / (size/docCount));
  }
}
 

private void doTestRandomBinary(int count) throws Exception {
  int numValues = TestUtil.nextInt(random(), count, count*2);
  int numBytesPerDim = TestUtil.nextInt(random(), 2, PointValues.MAX_NUM_BYTES);
  int numDims = TestUtil.nextInt(random(), 1, PointValues.MAX_INDEX_DIMENSIONS);

  int sameValuePct = random().nextInt(100);
  if (VERBOSE) {
    System.out.println("TEST: sameValuePct=" + sameValuePct);
  }

  byte[][][] docValues = new byte[numValues][][];

  boolean singleValued = random().nextBoolean();
  int[] ids = new int[numValues];

  int id = 0;
  if (VERBOSE) {
    System.out.println("Picking values: " + numValues);
  }
  for (int ord = 0; ord < numValues; ord++) {
    if (ord > 0 && random().nextInt(100) < sameValuePct) {
      // Identical to old value
      docValues[ord] = docValues[random().nextInt(ord)];
    } else {
      // Make a new random value
      byte[][] values = new byte[numDims][];
      for(int dim=0;dim<numDims;dim++) {
        values[dim] = new byte[numBytesPerDim];
        random().nextBytes(values[dim]);
      }
      docValues[ord] = values;
    }
    ids[ord] = id;
    if (singleValued || random().nextInt(2) == 1) {
      id++;
    }
  }

  verifyBinary(docValues, ids, numBytesPerDim);
}
 

public void testIndexDimEqualDataDimDifferent() throws Exception {
  int numBytesPerDim = TestUtil.nextInt(random(), 2, 30);
  int numDataDims = TestUtil.nextInt(random(), 2, PointValues.MAX_DIMENSIONS);
  int numIndexDims = Math.min(TestUtil.nextInt(random(), 1, numDataDims - 1), PointValues.MAX_INDEX_DIMENSIONS);

  int numDocs = atLeast(1000);
  byte[][][] docValues = new byte[numDocs][][];

  byte[][] indexDimensions = new byte[numDataDims][];
  for(int dim=0;dim<numIndexDims;dim++) {
    indexDimensions[dim] = new byte[numBytesPerDim];
    random().nextBytes(indexDimensions[dim]);
  }

  for(int docID=0;docID<numDocs;docID++) {
    byte[][] values = new byte[numDataDims][];
    for(int dim=0;dim<numIndexDims;dim++) {
      values[dim] = indexDimensions[dim];
    }
    for (int dim = numIndexDims; dim < numDataDims; dim++) {
        values[dim] = new byte[numBytesPerDim];
        random().nextBytes(values[dim]);
    }
    docValues[docID] = values;
  }

  verify(docValues, null, numDataDims, numIndexDims, numBytesPerDim);
}
 

public void testOneDimLowCard() throws Exception {
  int numBytesPerDim = TestUtil.nextInt(random(), 2, 30);
  int numDataDims = TestUtil.nextInt(random(), 2, PointValues.MAX_DIMENSIONS);
  int numIndexDims = Math.min(TestUtil.nextInt(random(), 2, numDataDims), PointValues.MAX_INDEX_DIMENSIONS);

  int numDocs = atLeast(10000);
  int theLowCardDim = random().nextInt(numDataDims);

  byte[] value1 = new byte[numBytesPerDim];
  random().nextBytes(value1);
  byte[] value2 = value1.clone();
  if (value2[numBytesPerDim-1] == 0 || random().nextBoolean()) {
    value2[numBytesPerDim-1]++;
  } else {
    value2[numBytesPerDim-1]--;
  }

  byte[][][] docValues = new byte[numDocs][][];

  for(int docID=0;docID<numDocs;docID++) {
    byte[][] values = new byte[numDataDims][];
    for(int dim=0;dim<numDataDims;dim++) {
      if (dim == theLowCardDim) {
        values[dim] = random().nextBoolean() ? value1 : value2;
      } else {
        values[dim] = new byte[numBytesPerDim];
        random().nextBytes(values[dim]);
      }
    }
    docValues[docID] = values;
  }

  // Use a small number of points in leaf blocks to trigger a lot of splitting
  verify(docValues, null, numDataDims, numIndexDims, numBytesPerDim, TestUtil.nextInt(random(), 20, 50));
}
 

public void testOneDimTwoValues() throws Exception {
  int numBytesPerDim = TestUtil.nextInt(random(), 2, 30);
  int numDataDims = TestUtil.nextInt(random(), 1, PointValues.MAX_DIMENSIONS);
  int numIndexDims = Math.min(TestUtil.nextInt(random(), 1, numDataDims), PointValues.MAX_INDEX_DIMENSIONS);

  int numDocs = atLeast(1000);
  int theDim = random().nextInt(numDataDims);
  byte[] value1 = new byte[numBytesPerDim];
  random().nextBytes(value1);
  byte[] value2 = new byte[numBytesPerDim];
  random().nextBytes(value2);
  byte[][][] docValues = new byte[numDocs][][];

  for(int docID=0;docID<numDocs;docID++) {
    byte[][] values = new byte[numDataDims][];
    for(int dim=0;dim<numDataDims;dim++) {
      if (dim == theDim) {
        values[dim] = random().nextBoolean() ? value1 : value2;
      } else {
        values[dim] = new byte[numBytesPerDim];
        random().nextBytes(values[dim]);
      }
    }
    docValues[docID] = values;
  }

  verify(docValues, null, numDataDims, numIndexDims, numBytesPerDim);
}
 

public void testMultiValued() throws Exception {
  int numBytesPerDim = TestUtil.nextInt(random(), 2, 30);
  int numDataDims = TestUtil.nextInt(random(), 1, PointValues.MAX_DIMENSIONS);
  int numIndexDims = Math.min(TestUtil.nextInt(random(), 1, numDataDims), PointValues.MAX_INDEX_DIMENSIONS);

  int numDocs = atLeast(1000);
  List<byte[][]> docValues = new ArrayList<>();
  List<Integer> docIDs = new ArrayList<>();

  for(int docID=0;docID<numDocs;docID++) {
    int numValuesInDoc = TestUtil.nextInt(random(), 1, 5);
    for(int ord=0;ord<numValuesInDoc;ord++) {
      docIDs.add(docID);
      byte[][] values = new byte[numDataDims][];
      for(int dim=0;dim<numDataDims;dim++) {
        values[dim] = new byte[numBytesPerDim];
        random().nextBytes(values[dim]);
      }
      docValues.add(values);
    }
  }

  byte[][][] docValuesArray = docValues.toArray(new byte[docValues.size()][][]);
  int[] docIDsArray = new int[docIDs.size()];
  for(int i=0;i<docIDsArray.length;i++) {
    docIDsArray[i] = docIDs.get(i);
  }

  verify(docValuesArray, docIDsArray, numDataDims, numIndexDims, numBytesPerDim);
}
 

/** Returns the underlying {@link BKDReader}.
 *
 * @lucene.internal */
@Override
public PointValues getValues(String fieldName) {
  FieldInfo fieldInfo = readState.fieldInfos.fieldInfo(fieldName);
  if (fieldInfo == null) {
    throw new IllegalArgumentException("field=\"" + fieldName + "\" is unrecognized");
  }
  if (fieldInfo.getPointDimensionCount() == 0) {
    throw new IllegalArgumentException("field=\"" + fieldName + "\" did not index point values");
  }

  return readers.get(fieldInfo.number);
}
 

public void testRandomDocCount() {
  for (int i = 0; i < 100; i++) {
    long size = TestUtil.nextLong(random(), 1, Long.MAX_VALUE);
    int maxDoc = (size > Integer.MAX_VALUE) ? Integer.MAX_VALUE : Math.toIntExact(size);
    int docCount = TestUtil.nextInt(random(), 1, maxDoc);
    long estimatedPointCount = TestUtil.nextLong(random(), 0, size);
    PointValues values = getPointValues(size, docCount, estimatedPointCount);
    long docs = values.estimateDocCount(null);
    assertTrue(docs <= estimatedPointCount);
    assertTrue(docs <= maxDoc);
    assertTrue(docs >= estimatedPointCount / (size/docCount));
  }
}
 

public DocSet getDocSet(IndexSearcher searcher) throws IOException {
  IndexReaderContext top = ReaderUtil.getTopLevelContext(searcher.getTopReaderContext());
  List<LeafReaderContext> segs = top.leaves();
  DocSetBuilder builder = new DocSetBuilder(top.reader().maxDoc(), Math.min(64,(top.reader().maxDoc()>>>10)+4));
  PointValues[] segPoints = new PointValues[segs.size()];
  for (int i=0; i<segPoints.length; i++) {
    segPoints[i] = segs.get(i).reader().getPointValues(field);
  }

  int maxCollect = Math.min(maxDocFreq, top.reader().maxDoc());

  PointSetQuery.CutoffPointVisitor visitor = new PointSetQuery.CutoffPointVisitor(maxCollect);
  PrefixCodedTerms.TermIterator iterator = sortedPackedPoints.iterator();
  outer: for (BytesRef point = iterator.next(); point != null; point = iterator.next()) {
    visitor.setPoint(point);
    for (int i=0; i<segs.size(); i++) {
      if (segPoints[i] == null) continue;
      visitor.setBase(segs.get(i).docBase);
      segPoints[i].intersect(visitor);
      if (visitor.getCount() > maxDocFreq) {
        continue outer;
      }
    }
    int collected = visitor.getCount();
    int[] ids = visitor.getGlobalIds();
    for (int i=0; i<collected; i++) {
      builder.add( ids[i] );
    }
  }

  FixedBitSet liveDocs = getLiveDocs(searcher);
  DocSet set = builder.build(liveDocs);
  return set;
}
 

@Override
public PointValues.Relation compare(byte[] minPackedValue, byte[] maxPackedValue) {

  boolean crosses = false;

  for(int dim=0;dim<numDims;dim++) {
    int offset = dim*bytesPerDim;

    int cmpMin = Arrays.compareUnsigned(minPackedValue, offset, offset + bytesPerDim, pointBytes, offset, offset + bytesPerDim);
    if (cmpMin > 0) {
      return PointValues.Relation.CELL_OUTSIDE_QUERY;
    }

    int cmpMax = Arrays.compareUnsigned(maxPackedValue, offset, offset + bytesPerDim, pointBytes, offset, offset + bytesPerDim);
    if (cmpMax < 0) {
      return PointValues.Relation.CELL_OUTSIDE_QUERY;
    }

    if (cmpMin != 0 || cmpMax != 0) {
      crosses = true;
    }
  }

  if (crosses) {
    return PointValues.Relation.CELL_CROSSES_QUERY;
  } else {
    // NOTE: we only hit this if we are on a cell whose min and max values are exactly equal to our point,
    // which can easily happen if many docs share this one value
    return PointValues.Relation.CELL_INSIDE_QUERY;
  }
}
 

@Override
public PointValues.Relation compare(byte[] minPackedValue, byte[] maxPackedValue) {
  int v = IntPoint.decodeDimension(maxPackedValue, 0);
  if (v >= last) {
    return PointValues.Relation.CELL_CROSSES_QUERY;
  } else {
    return PointValues.Relation.CELL_OUTSIDE_QUERY;
  }
}