/*
 * 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.spatial.prefix.tree;

import java.util.Collection;

import org.locationtech.spatial4j.shape.Point;
import org.locationtech.spatial4j.shape.Shape;
import org.locationtech.spatial4j.shape.SpatialRelation;
import org.apache.lucene.util.BytesRef;
import org.apache.lucene.util.StringHelper;

The base for the original two SPT's: Geohash and Quad. Don't subclass this for new SPTs.
@lucene.internal
/** The base for the original two SPT's: Geohash and Quad. Don't subclass this for new SPTs. * @lucene.internal */
//public for RPT pruneLeafyBranches code public abstract class LegacyCell implements CellCanPrune { // Important: A LegacyCell doesn't share state for getNextLevelCells(), and // LegacySpatialPrefixTree assumes this in its simplify tree logic. private static final byte LEAF_BYTE = '+';//NOTE: must sort before letters & numbers //Arguably we could simply use a BytesRef, using an extra Object. protected byte[] bytes;//generally bigger to potentially hold a leaf protected int b_off; protected int b_len;//doesn't reflect leaf; same as getLevel() protected boolean isLeaf;
When set via getSubCells(filter), it is the relationship between this cell and the given shape filter. Doesn't participate in shape equality.
/** * When set via getSubCells(filter), it is the relationship between this cell * and the given shape filter. Doesn't participate in shape equality. */
protected SpatialRelation shapeRel; protected Shape shape;//cached
Warning: Refers to the same bytes (no copy). If setLeaf() is subsequently called then it may modify bytes.
/** Warning: Refers to the same bytes (no copy). If {@link #setLeaf()} is subsequently called then it * may modify bytes. */
protected LegacyCell(byte[] bytes, int off, int len) { this.bytes = bytes; this.b_off = off; this.b_len = len; readLeafAdjust(); } protected void readCell(BytesRef bytes) { shapeRel = null; shape = null; this.bytes = bytes.bytes; this.b_off = bytes.offset; this.b_len = (short) bytes.length; readLeafAdjust(); } protected void readLeafAdjust() { isLeaf = (b_len > 0 && bytes[b_off + b_len - 1] == LEAF_BYTE); if (isLeaf) b_len--; if (getLevel() == getMaxLevels()) isLeaf = true; } protected abstract SpatialPrefixTree getGrid(); protected abstract int getMaxLevels(); @Override public SpatialRelation getShapeRel() { return shapeRel; } @Override public void setShapeRel(SpatialRelation rel) { this.shapeRel = rel; } @Override public boolean isLeaf() { return isLeaf; } @Override public void setLeaf() { isLeaf = true; } @Override public BytesRef getTokenBytesWithLeaf(BytesRef result) { result = getTokenBytesNoLeaf(result); if (!isLeaf || getLevel() == getMaxLevels()) return result; if (result.bytes.length < result.offset + result.length + 1) { assert false : "Not supposed to happen; performance bug"; byte[] copy = new byte[result.length + 1]; System.arraycopy(result.bytes, result.offset, copy, 0, result.length - 1); result.bytes = copy; result.offset = 0; } result.bytes[result.offset + result.length++] = LEAF_BYTE; return result; } @Override public BytesRef getTokenBytesNoLeaf(BytesRef result) { if (result == null) return new BytesRef(bytes, b_off, b_len); result.bytes = bytes; result.offset = b_off; result.length = b_len; return result; } @Override public int getLevel() { return b_len; } @Override public CellIterator getNextLevelCells(Shape shapeFilter) { assert getLevel() < getGrid().getMaxLevels(); if (shapeFilter instanceof Point) { LegacyCell cell = getSubCell((Point) shapeFilter); cell.shapeRel = SpatialRelation.CONTAINS; return new SingletonCellIterator(cell); } else { return new FilterCellIterator(getSubCells().iterator(), shapeFilter); } }
Performant implementations are expected to implement this efficiently by considering the current cell's boundary.

Precondition: Never called when getLevel() == maxLevel. Precondition: this.getShape().relate(p) != DISJOINT.

/** * Performant implementations are expected to implement this efficiently by * considering the current cell's boundary. * <p> * Precondition: Never called when getLevel() == maxLevel. * Precondition: this.getShape().relate(p) != DISJOINT. */
protected abstract LegacyCell getSubCell(Point p);
Gets the cells at the next grid cell level that covers this cell. Precondition: Never called when getLevel() == maxLevel.
Returns:A set of cells (no dups), sorted, modifiable, not empty, not null.
/** * Gets the cells at the next grid cell level that covers this cell. * Precondition: Never called when getLevel() == maxLevel. * * @return A set of cells (no dups), sorted, modifiable, not empty, not null. */
protected abstract Collection<Cell> getSubCells(); @Override public boolean isPrefixOf(Cell c) { //Note: this only works when each level uses a whole number of bytes. LegacyCell cell = (LegacyCell)c; boolean result = sliceEquals(cell.bytes, cell.b_off, cell.b_len, bytes, b_off, b_len); assert result == StringHelper.startsWith(c.getTokenBytesNoLeaf(null), getTokenBytesNoLeaf(null)); return result; }
Copied from StringHelper.startsWith(BytesRef, BytesRef) which calls this. This is to avoid creating a BytesRef.
/** Copied from {@link org.apache.lucene.util.StringHelper#startsWith(BytesRef, BytesRef)} * which calls this. This is to avoid creating a BytesRef. */
private static boolean sliceEquals(byte[] sliceToTest_bytes, int sliceToTest_offset, int sliceToTest_length, byte[] other_bytes, int other_offset, int other_length) { if (sliceToTest_length < other_length) { return false; } int i = sliceToTest_offset; int j = other_offset; final int k = other_offset + other_length; while (j < k) { if (sliceToTest_bytes[i++] != other_bytes[j++]) { return false; } } return true; } @Override public int compareToNoLeaf(Cell fromCell) { LegacyCell b = (LegacyCell) fromCell; return compare(bytes, b_off, b_len, b.bytes, b.b_off, b.b_len); }
Copied from BytesRef.compareTo(BytesRef). This is to avoid creating a BytesRef.
/** Copied from {@link BytesRef#compareTo(BytesRef)}. * This is to avoid creating a BytesRef. */
protected static int compare(byte[] aBytes, int aUpto, int a_length, byte[] bBytes, int bUpto, int b_length) { final int aStop = aUpto + Math.min(a_length, b_length); while(aUpto < aStop) { int aByte = aBytes[aUpto++] & 0xff; int bByte = bBytes[bUpto++] & 0xff; int diff = aByte - bByte; if (diff != 0) { return diff; } } // One is a prefix of the other, or, they are equal: return a_length - b_length; } @Override public boolean equals(Object obj) { //this method isn't "normally" called; just in asserts/tests if (obj instanceof Cell) { Cell cell = (Cell) obj; return getTokenBytesWithLeaf(null).equals(cell.getTokenBytesWithLeaf(null)); } else { return false; } } @Override public int hashCode() { return getTokenBytesWithLeaf(null).hashCode(); } @Override public String toString() { //this method isn't "normally" called; just in asserts/tests return getTokenBytesWithLeaf(null).utf8ToString(); } }