/*
 * 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.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.NoSuchElementException;

import org.apache.lucene.util.BytesRef;
import org.apache.lucene.util.Version;
import org.locationtech.spatial4j.context.SpatialContext;
import org.locationtech.spatial4j.shape.Point;
import org.locationtech.spatial4j.shape.Rectangle;
import org.locationtech.spatial4j.shape.Shape;
import org.locationtech.spatial4j.shape.SpatialRelation;
import org.locationtech.spatial4j.shape.impl.RectangleImpl;

Uses a compact binary representation of 8 bytes to encode a spatial quad trie.
The binary representation is as follows:
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDL
Where C = Cell bits (2 per quad)
      D = Depth bits (5 with max of 29 levels)
      L = isLeaf bit
 It includes a built-in "pruneLeafyBranches" setting (true by default) similar to RecursivePrefixTreeStrategy.setPruneLeafyBranches(boolean) although this one only prunes at the target detail level (where it has the most effect). Usually you should disable RPT's prune, since it is very memory in-efficient. 
@lucene.experimental
/**
 * Uses a compact binary representation of 8 bytes to encode a spatial quad trie.
 *
 * The binary representation is as follows:
 * <pre>
 * CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDL
 *
 * Where C = Cell bits (2 per quad)
 *       D = Depth bits (5 with max of 29 levels)
 *       L = isLeaf bit
 * </pre>
 *
 * It includes a built-in "pruneLeafyBranches" setting (true by default) similar to
 * {@link org.apache.lucene.spatial.prefix.RecursivePrefixTreeStrategy#setPruneLeafyBranches(boolean)} although
 * this one only prunes at the target detail level (where it has the most effect).  Usually you should disable RPT's
 * prune, since it is very memory in-efficient.
 *
 * @lucene.experimental
 */
public class PackedQuadPrefixTree extends QuadPrefixTree {
  public static final int MAX_LEVELS_POSSIBLE = 29;
  protected static final byte[] QUAD = new byte[] {0x00, 0x01, 0x02, 0x03};

  protected boolean leafyPrune = true;

  
Factory for creating PackedQuadPrefixTree instances with useful defaults. /**
   * Factory for creating {@link PackedQuadPrefixTree} instances with useful defaults.
   */
  public static class Factory extends QuadPrefixTree.Factory {
    @Override
    protected SpatialPrefixTree newSPT() {
      PackedQuadPrefixTree tree = new PackedQuadPrefixTree(ctx, maxLevels != null ? maxLevels : MAX_LEVELS_POSSIBLE);
      tree.robust = getVersion().onOrAfter(Version.LUCENE_8_3_0);
      return tree;
    }
  }

  public PackedQuadPrefixTree(SpatialContext ctx, int maxLevels) {
    super(ctx, maxLevels);
    if (maxLevels > MAX_LEVELS_POSSIBLE) {
      throw new IllegalArgumentException("maxLevels of " + maxLevels + " exceeds limit of " + MAX_LEVELS_POSSIBLE);
    }
  }

  @Override
  public String toString() {
    return getClass().getSimpleName() + "(maxLevels:" + maxLevels + ",ctx:" + ctx + ",prune:" + leafyPrune + ")";
  }

  @Override
  public Cell getWorldCell() {
    return new PackedQuadCell(0x0L);
  }

  @Override
  public Cell getCell(Point p, int level) {
    if (!robust) { // old method
      List<Cell> cells = new ArrayList<>(1);
      buildNotRobustly(xmid, ymid, 0, cells, 0x0L, ctx.makePoint(p.getX(), p.getY()), level);
      if (!cells.isEmpty()) {
        return cells.get(0);//note cells could be longer if p on edge
      }
    }

    double currentXmid = xmid;
    double currentYmid = ymid;
    double xp = p.getX();
    double yp = p.getY();
    long  term = 0L;
    int levelLimit = level > maxLevels ? maxLevels : level;
    SpatialRelation rel = SpatialRelation.CONTAINS;
    for (int lvl = 0; lvl < levelLimit; lvl++){
      int quad = battenberg(currentXmid, currentYmid, xp, yp);
      double halfWidth = levelW[lvl + 1];
      double halfHeight = levelH[lvl + 1];
      switch(quad){
        case 0:
          currentXmid -= halfWidth;
          currentYmid += halfHeight;
          break;
        case 1:
          currentXmid += halfWidth;
          currentYmid += halfHeight;
          break;
        case 2:
          currentXmid -= halfWidth;
          currentYmid -= halfHeight;
          break;
        case 3:
          currentXmid += halfWidth;
          currentYmid -= halfHeight;
          break;
        default:
      }
      // set bits for next level
      term |= (((long)(quad))<<(64-((lvl + 1)<<1)));
      // increment level
      term = ((term>>>1)+1)<<1;
    }
    return new PackedQuadCell(term, rel);
  }

  protected void buildNotRobustly(double x, double y, int level, List<Cell> matches, long term, Shape shape, int maxLevel) {
    double w = levelW[level] / 2;
    double h = levelH[level] / 2;

    // Z-Order
    // http://en.wikipedia.org/wiki/Z-order_%28curve%29
    checkBattenbergNotRobustly(QUAD[0], x - w, y + h, level, matches, term, shape, maxLevel);
    checkBattenbergNotRobustly(QUAD[1], x + w, y + h, level, matches, term, shape, maxLevel);
    checkBattenbergNotRobustly(QUAD[2], x - w, y - h, level, matches, term, shape, maxLevel);
    checkBattenbergNotRobustly(QUAD[3], x + w, y - h, level, matches, term, shape, maxLevel);
  }

  protected void checkBattenbergNotRobustly(byte quad, double cx, double cy, int level, List<Cell> matches,
                                 long term, Shape shape, int maxLevel) {
    // short-circuit if we find a match for the point (no need to continue recursion)
    if (shape instanceof Point && !matches.isEmpty())
      return;
    double w = levelW[level] / 2;
    double h = levelH[level] / 2;

    SpatialRelation v = shape.relate(ctx.makeRectangle(cx - w, cx + w, cy - h, cy + h));

    if (SpatialRelation.DISJOINT == v) {
      return;
    }

    // set bits for next level
    term |= (((long)(quad))<<(64-(++level<<1)));
    // increment level
    term = ((term>>>1)+1)<<1;

    if (SpatialRelation.CONTAINS == v || (level >= maxLevel)) {
      matches.add(new PackedQuadCell(term, v.transpose()));
    } else {// SpatialRelation.WITHIN, SpatialRelation.INTERSECTS
      buildNotRobustly(cx, cy, level, matches, term, shape, maxLevel);
    }
  }

  @Override
  public Cell readCell(BytesRef term, Cell scratch) {
    PackedQuadCell cell = (PackedQuadCell) scratch;
    if (cell == null)
      cell = (PackedQuadCell) getWorldCell();
    cell.readCell(term);
    return cell;
  }

  @Override
  public CellIterator getTreeCellIterator(Shape shape, int detailLevel) {
    if (detailLevel > maxLevels) {
      throw new IllegalArgumentException("detailLevel:" + detailLevel +" exceed max: " + maxLevels);
    }
    return new PrefixTreeIterator(shape, (short) detailLevel);
  }

  public boolean isPruneLeafyBranches() {
    return leafyPrune;
  }

  
Like RecursivePrefixTreeStrategy.setPruneLeafyBranches(boolean) but more memory efficient and only applies to the detailLevel, where it has the most effect. /** Like {@link org.apache.lucene.spatial.prefix.RecursivePrefixTreeStrategy#setPruneLeafyBranches(boolean)}
   * but more memory efficient and only applies to the detailLevel, where it has the most effect. */
  public void setPruneLeafyBranches( boolean pruneLeafyBranches ) {
    this.leafyPrune = pruneLeafyBranches;
  }

  
See binary representation in the javadocs of PackedQuadPrefixTree. /** See binary representation in the javadocs of {@link PackedQuadPrefixTree}. */
  protected class PackedQuadCell extends QuadCell {
    private long term;

    PackedQuadCell(long term) {
      super(null, 0, 0);
      this.term = term;
      this.b_off = 0;
      this.bytes = longToByteArray(this.term, new byte[8]);
      this.b_len = 8;
      readLeafAdjust();
    }

    PackedQuadCell(long term, SpatialRelation shapeRel) {
      this(term);
      this.shapeRel = shapeRel;
    }

    @Override
    protected void readCell(BytesRef bytes) {
      shapeRel = null;
      shape = null;
      this.bytes = bytes.bytes;
      this.b_off = bytes.offset;
      this.b_len = (short) bytes.length;
      this.term = longFromByteArray(this.bytes, bytes.offset);
      readLeafAdjust();
    }

    private final int getShiftForLevel(final int level) {
      return 64 - (level<<1);
    }

    public boolean isEnd(final int level, final int shift) {
      return (term != 0x0L && ((((0x1L<<(level<<1))-1)-(term>>>shift)) == 0x0L));
    }

    
Get the next cell in the tree without using recursion. descend parameter requests traversal to the child nodes,
setting this to false will step to the next sibling.
Note: This complies with lexicographical ordering, once you've moved to the next sibling there is no backtracking.
/**
     * Get the next cell in the tree without using recursion. descend parameter requests traversal to the child nodes,
     * setting this to false will step to the next sibling.
     * Note: This complies with lexicographical ordering, once you've moved to the next sibling there is no backtracking.
     */
    public PackedQuadCell nextCell(boolean descend) {
      final int level = getLevel();
      final int shift = getShiftForLevel(level);
      // base case: can't go further
      if ( (!descend && isEnd(level, shift)) || isEnd(maxLevels, getShiftForLevel(maxLevels))) {
        return null;
      }
      long newTerm;
      final boolean isLeaf = (term&0x1L)==0x1L;
      // if descend requested && we're not at the maxLevel
      if ((descend && !isLeaf && (level != maxLevels)) || level == 0) {
        // simple case: increment level bits (next level)
        newTerm = ((term>>>1)+0x1L)<<1;
      } else {  // we're not descending or we can't descend
        newTerm = term + (0x1L<<shift);
        // we're at the last sibling...force descend
        if (((term>>>shift)&0x3L) == 0x3L) {
          // adjust level for number popping up
          newTerm = ((newTerm>>>1) - (Long.numberOfTrailingZeros(newTerm>>>shift)>>>1))<<1;
        }
      }
      return new PackedQuadCell(newTerm);
    }

    @Override
    protected void readLeafAdjust() {
      isLeaf = ((0x1L)&term) == 0x1L;
      if (getLevel() == getMaxLevels()) {
        isLeaf = true;
      }
    }

    @Override
    public BytesRef getTokenBytesWithLeaf(BytesRef result) {
      result = getTokenBytesNoLeaf(result);
      if (isLeaf()) {
        result.bytes[8 - 1] |= 0x1L; // set leaf
      }
      return result;
    }

    @Override
    public BytesRef getTokenBytesNoLeaf(BytesRef result) {
      if (result == null) {
        result = new BytesRef(8);
      } else if (result.bytes.length < 8) {
        result.bytes = new byte[8];
      }
      result.bytes = longToByteArray(this.term, result.bytes);
      result.offset = 0;
      result.length = 8;
      // no leaf
      result.bytes[8 - 1] &= ~1; // clear last bit (leaf bit)
      return result;
    }

    @Override
    public int compareToNoLeaf(Cell fromCell) {
      PackedQuadCell b = (PackedQuadCell) fromCell;
      //TODO clear last bit without the condition
      final long thisTerm = (((0x1L)&term) == 0x1L) ? term-1 : term;
      final long fromTerm = (((0x1L)&b.term) == 0x1L) ? b.term-1 : b.term;
      final int result = Long.compareUnsigned(thisTerm, fromTerm);
      assert Math.signum(result)
          == Math.signum(compare(longToByteArray(thisTerm, new byte[8]), 0, 8, longToByteArray(fromTerm, new byte[8]), 0, 8)); // TODO remove
      return result;
    }

    @Override
    public int getLevel() {
      int l = (int)((term >>> 1)&0x1FL);
      return l;
    }

    @Override
    protected Collection<Cell> getSubCells() {
      List<Cell> cells = new ArrayList<>(4);
      PackedQuadCell pqc = (new PackedQuadCell(((term&0x1)==0x1) ? this.term-1 : this.term))
          .nextCell(true);
      cells.add(pqc);
      cells.add((pqc = pqc.nextCell(false)));
      cells.add((pqc = pqc.nextCell(false)));
      cells.add(pqc.nextCell(false));
      return cells;
    }

    @Override
    protected QuadCell getSubCell(Point p) {
      return (PackedQuadCell) PackedQuadPrefixTree.this.getCell(p, getLevel() + 1);//not performant!
    }

    @Override
    public boolean isPrefixOf(Cell c) {
      PackedQuadCell cell = (PackedQuadCell)c;
      return (this.term == 0x0L) || isInternalPrefix(cell);
    }

    protected boolean isInternalPrefix(PackedQuadCell c) {
      final int shift = 64 - (getLevel()<<1);
      return ((term>>>shift)-(c.term>>>shift)) == 0x0L;
    }

    protected long concat(byte postfix) {
      // extra leaf bit
      return this.term | (((long)(postfix))<<((getMaxLevels()-getLevel()<<1)+6));
    }

    
Constructs a bounding box shape out of the encoded cell
/**
     * Constructs a bounding box shape out of the encoded cell
     */
    @Override
    protected Rectangle makeShape() {
      double xmin = PackedQuadPrefixTree.this.xmin;
      double ymin = PackedQuadPrefixTree.this.ymin;
      int level = getLevel();

      byte b;
      for (short l=0, i=1; l<level; ++l, ++i) {
        b = (byte) ((term>>>(64-(i<<1))) & 0x3L);

        switch (b) {
          case 0x00:
            ymin += levelH[l];
            break;
          case 0x01:
            xmin += levelW[l];
            ymin += levelH[l];
            break;
          case 0x02:
            break;//nothing really
          case 0x03:
            xmin += levelW[l];
            break;
          default:
            throw new RuntimeException("unexpected quadrant");
        }
      }

      double width, height;
      if (level > 0) {
        width = levelW[level - 1];
        height = levelH[level - 1];
      } else {
        width = gridW;
        height = gridH;
      }
      return new RectangleImpl(xmin, xmin + width, ymin, ymin + height, ctx);
    }

    private long fromBytes(byte b1, byte b2, byte b3, byte b4, byte b5, byte b6, byte b7, byte b8) {
      return ((long)b1 & 255L) << 56 | ((long)b2 & 255L) << 48 | ((long)b3 & 255L) << 40
          | ((long)b4 & 255L) << 32 | ((long)b5 & 255L) << 24 | ((long)b6 & 255L) << 16
          | ((long)b7 & 255L) << 8 | (long)b8 & 255L;
    }

    private byte[] longToByteArray(long value, byte[] result) {
      for(int i = 7; i >= 0; --i) {
        result[i] = (byte)((int)(value & 255L));
        value >>= 8;
      }
      return result;
    }

    private long longFromByteArray(byte[] bytes, int ofs) {
      assert bytes.length >= 8;
      return fromBytes(bytes[0+ofs], bytes[1+ofs], bytes[2+ofs], bytes[3+ofs],
          bytes[4+ofs], bytes[5+ofs], bytes[6+ofs], bytes[7+ofs]);
    }

    
Used for debugging, this will print the bits of the cell
/**
     * Used for debugging, this will print the bits of the cell
     */
    @Override
    public String toString() {
      StringBuilder s = new StringBuilder(64);
      final int numberOfLeadingZeros = Long.numberOfLeadingZeros(term);
      for (int i = 0; i < numberOfLeadingZeros; i++) {
        s.append('0');
      }
      if (term != 0)
        s.append(Long.toBinaryString(term));
      return s.toString();
    }
  } // PackedQuadCell

  
This is a streamlined version of TreeCellIterator, with built-in support to prune at detailLevel
(but not recursively upwards). /** This is a streamlined version of TreeCellIterator, with built-in support to prune at detailLevel
   * (but not recursively upwards). */
  protected class PrefixTreeIterator extends CellIterator {
    private Shape shape;
    private PackedQuadCell thisCell;
    private PackedQuadCell nextCell;

    private short level;
    private final short detailLevel;
    private CellIterator pruneIter;

    PrefixTreeIterator(Shape shape, short detailLevel) {
      this.shape = shape;
      this.thisCell = ((PackedQuadCell)(getWorldCell())).nextCell(true);
      this.detailLevel = detailLevel;
      this.nextCell = null;
    }

    @Override
    public boolean hasNext() {
      if (nextCell != null) {
        return true;
      }
      SpatialRelation rel;
      // loop until we're at the end of the quad tree or we hit a relation
      while (thisCell != null) {
        rel = thisCell.getShape().relate(shape);
        if (rel == SpatialRelation.DISJOINT) {
          thisCell = thisCell.nextCell(false);
        } else { // within || intersects || contains
          thisCell.setShapeRel(rel);
          nextCell = thisCell;
          if (rel == SpatialRelation.WITHIN) {
            thisCell.setLeaf();
            thisCell = thisCell.nextCell(false);
          } else {  // intersects || contains
            level = (short) (thisCell.getLevel());
            if (level == detailLevel || pruned(rel)) {
              thisCell.setLeaf();
              if (shape instanceof Point) {
                thisCell.setShapeRel(SpatialRelation.WITHIN);
                thisCell = null;
              } else {
                thisCell = thisCell.nextCell(false);
              }
              break;
            }
            thisCell = thisCell.nextCell(true);
          }
          break;
        }
      }
      return nextCell != null;
    }

    private boolean pruned(SpatialRelation rel) {
      int leaves;
      if (rel == SpatialRelation.INTERSECTS && leafyPrune && level == detailLevel - 1) {
        for (leaves=0, pruneIter=thisCell.getNextLevelCells(shape); pruneIter.hasNext(); pruneIter.next(), ++leaves);
        return leaves == 4;
      }
      return false;
    }

    @Override
    public Cell next() {
      if (nextCell == null) {
        if (!hasNext()) {
          throw new NoSuchElementException();
        }
      }
      // overriding since this implementation sets thisCell in hasNext
      Cell temp = nextCell;
      nextCell = null;
      return temp;
    }

    @Override
    public void remove() {
      //no-op
    }
  }
}