/*
 * 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;

import java.io.IOException;
import java.util.Iterator;

import org.locationtech.spatial4j.shape.Shape;
import org.locationtech.spatial4j.shape.SpatialRelation;
import org.apache.lucene.index.LeafReaderContext;
import org.apache.lucene.index.TermsEnum;
import org.apache.lucene.search.DocIdSet;
import org.apache.lucene.spatial.prefix.tree.Cell;
import org.apache.lucene.spatial.prefix.tree.CellIterator;
import org.apache.lucene.spatial.prefix.tree.SpatialPrefixTree;
import org.apache.lucene.util.BytesRef;

Traverses a SpatialPrefixTree indexed field, using the template and visitor design patterns for subclasses to guide the traversal and collect matching documents. 
 Subclasses implement AbstractPrefixTreeQuery.getDocIdSet(LeafReaderContext) by instantiating a custom VisitorTemplate subclass (i.e. an anonymous inner class) and implement the required methods. 
@lucene.internal
/**
 * Traverses a {@link SpatialPrefixTree} indexed field, using the template and
 * visitor design patterns for subclasses to guide the traversal and collect
 * matching documents.
 * <p>
 * Subclasses implement {@link #getDocIdSet(org.apache.lucene.index.LeafReaderContext)}
 * by instantiating a custom {@link VisitorTemplate} subclass (i.e. an anonymous inner class)
 * and implement the required methods.
 *
 * @lucene.internal
 */
public abstract class AbstractVisitingPrefixTreeQuery extends AbstractPrefixTreeQuery {

  //Historical note: this code resulted from a refactoring of RecursivePrefixTreeQuery,
  // which in turn came out of SOLR-2155

  //This class perhaps could have been implemented in terms of FilteredTermsEnum & MultiTermQuery.
  //  Maybe so for simple Intersects predicate but not for when we want to collect terms
  //  differently depending on cell state like IsWithin and for fuzzy/accurate collection planned improvements.  At
  //  least it would just make things more complicated.

  protected final int prefixGridScanLevel;//at least one less than grid.getMaxLevels()

  public AbstractVisitingPrefixTreeQuery(Shape queryShape, String fieldName, SpatialPrefixTree grid,
                                         int detailLevel, int prefixGridScanLevel) {
    super(queryShape, fieldName, grid, detailLevel);
    this.prefixGridScanLevel = Math.max(0, Math.min(prefixGridScanLevel, grid.getMaxLevels() - 1));
    assert detailLevel <= grid.getMaxLevels();
  }

  
An abstract class designed to make it easy to implement predicates or other operations on a SpatialPrefixTree indexed field. An instance of this class is not designed to be re-used across LeafReaderContext instances so simply create a new one per-leaf. The getDocIdSet() method here starts the work. It first checks that there are indexed terms; if not it quickly returns null. Then it calls start() so a subclass can set up a return value, like an FixedBitSet. Then it starts the traversal process, calling findSubCellsToVisit(Cell) which by default finds the top cells that intersect queryShape. If there isn't an indexed cell for a corresponding cell returned for this method then it's short-circuited until it finds one, at which point visitPrefix(Cell) is called. At some depths, of the tree, the algorithm switches to a scanning mode that calls visitScanned(Cell) for each leaf cell found. 
@lucene.internal
/**
   * An abstract class designed to make it easy to implement predicates or
   * other operations on a {@link SpatialPrefixTree} indexed field. An instance
   * of this class is not designed to be re-used across LeafReaderContext
   * instances so simply create a new one per-leaf.
   * The {@link #getDocIdSet()} method here starts the work. It first checks
   * that there are indexed terms; if not it quickly returns null. Then it calls
   * {@link #start()} so a subclass can set up a return value, like an
   * {@link org.apache.lucene.util.FixedBitSet}. Then it starts the traversal
   * process, calling {@link #findSubCellsToVisit(org.apache.lucene.spatial.prefix.tree.Cell)}
   * which by default finds the top cells that intersect {@code queryShape}. If
   * there isn't an indexed cell for a corresponding cell returned for this
   * method then it's short-circuited until it finds one, at which point
   * {@link #visitPrefix(org.apache.lucene.spatial.prefix.tree.Cell)} is called. At
   * some depths, of the tree, the algorithm switches to a scanning mode that
   * calls {@link #visitScanned(org.apache.lucene.spatial.prefix.tree.Cell)}
   * for each leaf cell found.
   *
   * @lucene.internal
   */
  public abstract class VisitorTemplate extends BaseTermsEnumTraverser {

  /* Future potential optimizations:

  * Can a polygon query shape be optimized / made-simpler at recursive depths
    (e.g. intersection of shape + cell box)

  * RE "scan" vs divide & conquer performance decision:
    We should use termsEnum.docFreq() as an estimate on the number of places at
    this depth.  It would be nice if termsEnum knew how many terms
    start with the current term without having to repeatedly next() & test to find out.

  * Perhaps don't do intermediate seek()'s to cells above detailLevel that have Intersects
    relation because we won't be collecting those docs any way.  However seeking
    does act as a short-circuit.  So maybe do some percent of the time or when the level
    is above some threshold.

  */

    //
    //  TODO MAJOR REFACTOR SIMPLIFICATION BASED ON TreeCellIterator  TODO
    //

    private VNode curVNode;//current pointer, derived from query shape
    private BytesRef curVNodeTerm = new BytesRef();//curVNode.cell's term, without leaf. in main loop only

    private BytesRef thisTerm;//the result of termsEnum.term()
    private Cell indexedCell;//Cell wrapper of thisTerm. Always updated when thisTerm is.

    public VisitorTemplate(LeafReaderContext context) throws IOException {
      super(context);
    }

    public DocIdSet getDocIdSet() throws IOException {
      assert curVNode == null : "Called more than once?";
      if (termsEnum == null)
        return null;
      if (!nextTerm()) {//advances
        return null;
      }

      curVNode = new VNode(null);
      curVNode.reset(grid.getWorldCell());

      start();

      addIntersectingChildren();

      main: while (thisTerm != null) {//terminates for other reasons too!

        //Advance curVNode pointer
        if (curVNode.children != null) {
          //-- HAVE CHILDREN: DESCEND
          assert curVNode.children.hasNext();//if we put it there then it has something
          preSiblings(curVNode);
          curVNode = curVNode.children.next();
        } else {
          //-- NO CHILDREN: ADVANCE TO NEXT SIBLING
          VNode parentVNode = curVNode.parent;
          while (true) {
            if (parentVNode == null)
              break main; // all done
            if (parentVNode.children.hasNext()) {
              //advance next sibling
              curVNode = parentVNode.children.next();
              break;
            } else {
              //reached end of siblings; pop up
              postSiblings(parentVNode);
              parentVNode.children = null;//GC
              parentVNode = parentVNode.parent;
            }
          }
        }

        //Seek to curVNode's cell (or skip if termsEnum has moved beyond)
        final int compare = indexedCell.compareToNoLeaf(curVNode.cell);
        if (compare > 0) {
          // The indexed cell is after; continue loop to next query cell
          continue;
        }
        if (compare < 0) {
          // The indexed cell is before; seek ahead to query cell:
          //      Seek !
          curVNode.cell.getTokenBytesNoLeaf(curVNodeTerm);
          TermsEnum.SeekStatus seekStatus = termsEnum.seekCeil(curVNodeTerm);
          if (seekStatus == TermsEnum.SeekStatus.END)
            break; // all done
          thisTerm = termsEnum.term();
          indexedCell = grid.readCell(thisTerm, indexedCell);
          if (seekStatus == TermsEnum.SeekStatus.NOT_FOUND) {
            // Did we find a leaf of the cell we were looking for or something after?
            if (!indexedCell.isLeaf() || indexedCell.compareToNoLeaf(curVNode.cell) != 0)
              continue; // The indexed cell is after; continue loop to next query cell
          }
        }
        // indexedCell == queryCell (disregarding leaf).

        // If indexedCell is a leaf then there's no prefix (prefix sorts before) -- just visit and continue
        if (indexedCell.isLeaf()) {
          visitLeaf(indexedCell);//TODO or query cell? Though shouldn't matter.
          if (!nextTerm()) break;
          continue;
        }
        // If a prefix (non-leaf) then visit; see if we descend.
        final boolean descend = visitPrefix(curVNode.cell);//need to use curVNode.cell not indexedCell
        if (!nextTerm()) break;
        // Check for adjacent leaf with the same prefix
        if (indexedCell.isLeaf() && indexedCell.getLevel() == curVNode.cell.getLevel()) {
          visitLeaf(indexedCell);//TODO or query cell? Though shouldn't matter.
          if (!nextTerm()) break;
        }


        if (descend) {
          addIntersectingChildren();
        }

      }//main loop

      return finish();
    }

    
Called initially, and whenever visitPrefix(Cell) returns true. /** Called initially, and whenever {@link #visitPrefix(org.apache.lucene.spatial.prefix.tree.Cell)}
     * returns true. */
    private void addIntersectingChildren() throws IOException {
      assert thisTerm != null;
      Cell cell = curVNode.cell;
      if (cell.getLevel() >= detailLevel)
        throw new IllegalStateException("Spatial logic error");

      //Decide whether to continue to divide & conquer, or whether it's time to
      // scan through terms beneath this cell.
      // Scanning is a performance optimization trade-off.

      //TODO use termsEnum.docFreq() as heuristic
      boolean scan = cell.getLevel() >= prefixGridScanLevel;//simple heuristic

      if (!scan) {
        //Divide & conquer (ultimately termsEnum.seek())

        Iterator<Cell> subCellsIter = findSubCellsToVisit(cell);
        if (!subCellsIter.hasNext())//not expected
          return;
        curVNode.children = new VNodeCellIterator(subCellsIter, new VNode(curVNode));

      } else {
        //Scan (loop of termsEnum.next())

        scan(detailLevel);
      }
    }

    
Called when doing a divide and conquer to find the next intersecting cells of the query shape that are beneath cell. cell is guaranteed to have an intersection and thus this must return some number of nodes. /**
     * Called when doing a divide and conquer to find the next intersecting cells
     * of the query shape that are beneath {@code cell}. {@code cell} is
     * guaranteed to have an intersection and thus this must return some number
     * of nodes.
     */
    protected CellIterator findSubCellsToVisit(Cell cell) {
      return cell.getNextLevelCells(queryShape);
    }

    
Scans (termsEnum.next()) terms until a term is found that does not start with curVNode's cell. If it finds a leaf cell or a cell at level scanDetailLevel then it calls visitScanned(Cell). /**
     * Scans ({@code termsEnum.next()}) terms until a term is found that does
     * not start with curVNode's cell. If it finds a leaf cell or a cell at
     * level {@code scanDetailLevel} then it calls {@link
     * #visitScanned(org.apache.lucene.spatial.prefix.tree.Cell)}.
     */
    protected void scan(int scanDetailLevel) throws IOException {
      //note: this can be a do-while instead in 6x; 5x has a back-compat with redundant leaves -- LUCENE-4942
      while (curVNode.cell.isPrefixOf(indexedCell)) {
        if (indexedCell.getLevel() == scanDetailLevel
            || (indexedCell.getLevel() < scanDetailLevel && indexedCell.isLeaf())) {
          visitScanned(indexedCell);
        }
        //advance
        if (!nextTerm()) break;
      }
    }

    private boolean nextTerm() throws IOException {
      if ((thisTerm = termsEnum.next()) == null)
        return false;
      indexedCell = grid.readCell(thisTerm, indexedCell);
      return true;
    }

    
Used for VNode.children. /** Used for {@link VNode#children}. */
    private class VNodeCellIterator implements Iterator<VNode> {

      final Iterator<Cell> cellIter;
      private final VNode vNode;

      VNodeCellIterator(Iterator<Cell> cellIter, VNode vNode) {
        this.cellIter = cellIter;
        this.vNode = vNode;
      }

      @Override
      public boolean hasNext() {
        return cellIter.hasNext();
      }

      @Override
      public VNode next() {
        assert hasNext();
        vNode.reset(cellIter.next());
        return vNode;
      }

      @Override
      public void remove() {//it always removes
      }
    }

    
Called first to setup things. /** Called first to setup things. */
    protected abstract void start() throws IOException;

    
Called last to return the result. /** Called last to return the result. */
    protected abstract DocIdSet finish() throws IOException;

    
Visit an indexed non-leaf cell. The presence of a prefix cell implies there are leaf cells at further levels. The cell passed should have it's Cell.getShapeRel() set relative to the filtered shape. 
Params:
cell – An intersecting cell; not a leaf.
Returns:
true to descend to more levels./**
     * Visit an indexed non-leaf cell. The presence of a prefix cell implies
     * there are leaf cells at further levels. The cell passed should have it's
     * {@link org.apache.lucene.spatial.prefix.tree.Cell#getShapeRel()} set
     * relative to the filtered shape.
     *
     * @param cell An intersecting cell; not a leaf.
     * @return true to descend to more levels.
     */
    protected abstract boolean visitPrefix(Cell cell) throws IOException;

    
Called when an indexed leaf cell is found. An
indexed leaf cell usually means associated documents won't be found at
further detail levels.  However, if a document has
multiple overlapping shapes at different resolutions, then this isn't true.
/**
     * Called when an indexed leaf cell is found. An
     * indexed leaf cell usually means associated documents won't be found at
     * further detail levels.  However, if a document has
     * multiple overlapping shapes at different resolutions, then this isn't true.
     */
    protected abstract void visitLeaf(Cell cell) throws IOException;

    
The cell is either indexed as a leaf or is the last level of detail. It might not even intersect the query shape, so be sure to check for that. The default implementation will check that and if passes then call visitLeaf(Cell) or visitPrefix(Cell). /**
     * The cell is either indexed as a leaf or is the last level of detail. It
     * might not even intersect the query shape, so be sure to check for that.
     * The default implementation will check that and if passes then call
     * {@link #visitLeaf(org.apache.lucene.spatial.prefix.tree.Cell)} or
     * {@link #visitPrefix(org.apache.lucene.spatial.prefix.tree.Cell)}.
     */
    protected void visitScanned(Cell cell) throws IOException {
      final SpatialRelation relate = cell.getShape().relate(queryShape);
      if (relate.intersects()) {
        cell.setShapeRel(relate);//just being pedantic
        if (cell.isLeaf()) {
          visitLeaf(cell);
        } else {
          visitPrefix(cell);
        }
      }
    }

    protected void preSiblings(VNode vNode) throws IOException {
    }

    protected void postSiblings(VNode vNode) throws IOException {
    }
  }//class VisitorTemplate

  
A visitor node/cell found via the query shape for VisitorTemplate. Sometimes these are reset(cell). It's like a LinkedList node but forms a tree. 
@lucene.internal
/**
   * A visitor node/cell found via the query shape for {@link VisitorTemplate}.
   * Sometimes these are reset(cell). It's like a LinkedList node but forms a
   * tree.
   *
   * @lucene.internal
   */
  protected static class VNode {
    //Note: The VNode tree adds more code to debug/maintain v.s. a flattened
    // LinkedList that we used to have. There is more opportunity here for
    // custom behavior (see preSiblings & postSiblings) but that's not
    // leveraged yet. Maybe this is slightly more GC friendly.

    final VNode parent;//only null at the root
    Iterator<VNode> children;//null, then sometimes set, then null
    Cell cell;//not null (except initially before reset())

    
call reset(cell) after to set the cell.
/**
     * call reset(cell) after to set the cell.
     */
    VNode(VNode parent) { // remember to call reset(cell) after
      this.parent = parent;
    }

    void reset(Cell cell) {
      assert cell != null;
      this.cell = cell;
      assert children == null;
    }

  }
}