// Copyright 2005 Google Inc. All Rights Reserved.

//

// Licensed 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.

//

// Author: ericv@google.com (Eric Veach)

#ifndef S2_S2REGION_COVERER_H_

#define S2_S2REGION_COVERER_H_

#include <algorithm>

#include <cstddef>

#include <new>

#include <queue>

#include <utility>

#include <vector>

#include "absl/base/casts.h"

#include "absl/base/macros.h"

#include "s2/_fp_contract_off.h"  // IWYU pragma: keep

#include "s2/s2cell.h"

#include "s2/s2cell_id.h"

#include "s2/s2cell_union.h"

#include "s2/s2point.h"

#include "s2/s2region.h"

class S2Region;

// An S2RegionCoverer is a class that allows arbitrary regions to be

// approximated as unions of cells (S2CellUnion).  This is useful for

// implementing various sorts of search and precomputation operations.

//

// Typical usage:

//

// S2RegionCoverer::Options options;

// options.set_max_cells(5);

// S2RegionCoverer coverer(options);

// S2Cap cap(center, radius);

// S2CellUnion covering = coverer.GetCovering(cap);

//

// This yields a vector of at most 5 cells that is guaranteed to cover the

// given cap (a disc-shaped region on the sphere).

//

// The approximation algorithm is not optimal but does a pretty good job in

// practice.  The output does not always use the maximum number of cells

// allowed, both because this would not always yield a better approximation,

// and because max_cells() is a limit on how much work is done exploring the

// possible covering as well as a limit on the final output size.

//

// Because it is an approximation algorithm, one should not rely on the

// stability of the output.  In particular, the output of the covering algorithm

// may change across different versions of the library.

//

// One can also generate interior coverings, which are sets of cells which

// are entirely contained within a region.  Interior coverings can be

// empty, even for non-empty regions, if there are no cells that satisfy

// the provided constraints and are contained by the region.  Note that for

// performance reasons, it is wise to specify a max_level when computing

// interior coverings - otherwise for regions with small or zero area, the

// algorithm may spend a lot of time subdividing cells all the way to leaf

// level to try to find contained cells.

class S2RegionCoverer {

 public:

  class Options {

   public:

    // Sets the desired maximum number of cells in the approximation.  Note

    // the following:

    //

    //  - For any setting of max_cells(), up to 6 cells may be returned if

    //    that is the minimum number required (e.g. if the region intersects

    //    all six cube faces).  Even for very tiny regions, up to 3 cells may

    //    be returned if they happen to be located at the intersection of

    //    three cube faces.

    //

    //  - min_level() takes priority over max_cells(), i.e. cells below the

    //    given level will never be used even if this causes a large number of

    //    cells to be returned.

    //

    //  - If max_cells() is less than 4, the area of the covering may be

    //    arbitrarily large compared to the area of the original region even

    //    if the region is convex (e.g. an S2Cap or S2LatLngRect).

    //

    // Accuracy is measured by dividing the area of the covering by the area

    // of the original region.  The following table shows the median and worst

    // case values for this area ratio on a test case consisting of 100,000

    // spherical caps of random size (generated using s2region_coverer_test):

    //

    //   max_cells:        3      4     5     6     8    12    20   100   1000

    //   median ratio:  5.33   3.32  2.73  2.34  1.98  1.66  1.42  1.11   1.01

    //   worst case:  215518  14.41  9.72  5.26  3.91  2.75  1.92  1.20   1.02

    //

    // The default value of 8 gives a reasonable tradeoff between the number

    // of cells used and the accuracy of the approximation.

    //

    // DEFAULT: kDefaultMaxCells

    static constexpr int kDefaultMaxCells = 8;

    int max_cells() const { return max_cells_; }

    void set_max_cells(int max_cells);

    // Sets the minimum and maximum cell levels to be used.  The default is to

    // use all cell levels.

    //

    // To find the cell level corresponding to a given physical distance, use

    // the S2Cell metrics defined in s2metrics.h.  For example, to find the

    // cell level that corresponds to an average edge length of 10km, use:

    //

    //   int level =

    //       S2::kAvgEdge.GetClosestLevel(S2Earth::KmToRadians(length_km));

    //

    // Note that min_level() takes priority over max_cells(), i.e. cells below

    // the given level will never be used even if this causes a large number

    // of cells to be returned.  (This doesn't apply to interior coverings,

    // since interior coverings make no completeness guarantees -- the result

    // is simply a set of cells that covers as much of the interior as

    // possible while satisfying the given restrictions.)

    //

    // REQUIRES: min_level() <= max_level()

    // DEFAULT: 0

    int min_level() const { return min_level_; }

    void set_min_level(int min_level);

    // REQUIRES: min_level() <= max_level()

    // DEFAULT: S2CellId::kMaxLevel

    int max_level() const { return max_level_; }

    void set_max_level(int max_level);

    // Convenience function that sets both the maximum and minimum cell levels.

    void set_fixed_level(int level);

    // If specified, then only cells where (level - min_level) is a multiple

    // of "level_mod" will be used (default 1).  This effectively allows the

    // branching factor of the S2CellId hierarchy to be increased.  Currently

    // the only parameter values allowed are 1, 2, or 3, corresponding to

    // branching factors of 4, 16, and 64 respectively.

    //

    // DEFAULT: 1

    int level_mod() const { return level_mod_; }

    void set_level_mod(int level_mod);

    // Convenience function that returns the maximum level such that

    //

    //   (level <= max_level()) && (level - min_level()) % level_mod() == 0.

    //

    // This is the maximum level that will actually be used in coverings.

    int true_max_level() const;

   protected:

    int max_cells_ = kDefaultMaxCells;

    int min_level_ = 0;

    int max_level_ = S2CellId::kMaxLevel;

    int level_mod_ = 1;

  };

  // Constructs an S2RegionCoverer with the given options.

  explicit S2RegionCoverer(const Options& options);

  // S2RegionCoverer is movable but not copyable.

  S2RegionCoverer(const S2RegionCoverer&) = delete;

  S2RegionCoverer& operator=(const S2RegionCoverer&) = delete;

  S2RegionCoverer(S2RegionCoverer&&) noexcept;

  S2RegionCoverer& operator=(S2RegionCoverer&&) noexcept;

  // Default constructor.  Options can be set using mutable_options().

  S2RegionCoverer();

  ~S2RegionCoverer();

  // Returns the current options.  Options can be modified between calls.

  const Options& options() const { return options_; }

  Options* mutable_options() { return &options_; }

  // Returns an S2CellUnion that covers (GetCovering) or is contained within

  // (GetInteriorCovering) the given region and satisfies the current options.

  //

  // Note that if options().min_level() > 0 or options().level_mod() > 1, then

  // by definition the S2CellUnion may not be normalized, i.e. there may be

  // groups of four child cells that can be replaced by their parent cell.

  S2CellUnion GetCovering(const S2Region& region);

  S2CellUnion GetInteriorCovering(const S2Region& region);

  // Like the methods above, but works directly with a vector of S2CellIds.

  // This version can be more efficient when this method is called many times,

  // since it does not require allocating a new vector on each call.

  void GetCovering(const S2Region& region, std::vector<S2CellId>* covering);

  void GetInteriorCovering(const S2Region& region,

                           std::vector<S2CellId>* interior);

  // Like GetCovering(), except that this method is much faster and the

  // coverings are not as tight.  All of the usual parameters are respected

  // (max_cells, min_level, max_level, and level_mod), except that the

  // implementation makes no attempt to take advantage of large values of

  // max_cells().  (A small number of cells will always be returned.)

  //

  // This function is useful as a starting point for algorithms that

  // recursively subdivide cells.

  void GetFastCovering(const S2Region& region, std::vector<S2CellId>* covering);

  // Given a connected region and a starting point on the boundary or inside the

  // region, returns a set of cells at the given level that cover the region.

  // The output cells are returned in arbitrary order.

  //

  // Note that this method is *not* faster than the regular GetCovering()

  // method for most region types, such as S2Cap or S2Polygon, and in fact it

  // can be much slower when the output consists of a large number of cells.

  // Currently it can be faster at generating coverings of long narrow regions

  // such as polylines, but this may change in the future, in which case this

  // method will most likely be removed.

  static void GetSimpleCovering(const S2Region& region, const S2Point& start,

                                int level, std::vector<S2CellId>* output);

  // Like GetSimpleCovering(), but accepts a starting S2CellId rather than a

  // starting point and cell level.  Returns all edge-connected cells at the

  // same level as "start" that intersect "region", in arbitrary order.

  static void FloodFill(const S2Region& region, S2CellId start,

                        std::vector<S2CellId>* output);

  // Returns true if the given S2CellId vector represents a valid covering

  // that conforms to the current covering parameters.  In particular:

  //

  //  - All S2CellIds must be valid.

  //

  //  - S2CellIds must be sorted and non-overlapping.

  //

  //  - S2CellId levels must satisfy min_level(), max_level(), and level_mod().

  //

  //  - If covering.size() > max_cells(), there must be no two cells with

  //    a common ancestor at min_level() or higher.

  //

  //  - There must be no sequence of cells that could be replaced by an

  //    ancestor (i.e. with level_mod() == 1, the 4 child cells of a parent).

  bool IsCanonical(const S2CellUnion& covering) const;

  bool IsCanonical(const std::vector<S2CellId>& covering) const;

  // Modify "covering" if necessary so that it conforms to the current

  // covering parameters (max_cells, min_level, max_level, and level_mod).

  // There are no restrictions on the input S2CellIds (they may be unsorted,

  // overlapping, etc).

  S2CellUnion CanonicalizeCovering(const S2CellUnion& covering);

  void CanonicalizeCovering(std::vector<S2CellId>* covering);

 private:

  struct Candidate {

    void* operator new(std::size_t size, std::size_t max_children) {

      return ::operator new (size + max_children * sizeof(Candidate *));

    }

    void operator delete(void* p) {

      ::operator delete (p);

    }

    Candidate(const S2Cell& cell, const std::size_t max_children)

        : cell(cell), is_terminal(max_children == 0) {

      std::fill_n(&children[0], max_children,

                  absl::implicit_cast<Candidate*>(nullptr));

    }

    // Default destructor is fine; Candidate* is trivially destructible.

    // children must be deleted by DeleteCandidate.

    ~Candidate() = default;

    S2Cell cell;

    bool is_terminal;        // Cell should not be expanded further.

    int num_children = 0;    // Number of children that intersect the region.

    Candidate* children[0];  // Actual size may be 0, 4, 16, or 64 elements.

  };

  // If the cell intersects the given region, return a new candidate with no

  // children, otherwise return nullptr.  Also marks the candidate as "terminal"

  // if it should not be expanded further.

  Candidate* NewCandidate(const S2Cell& cell);

  // Returns the log base 2 of the maximum number of children of a candidate.

  int max_children_shift() const { return 2 * options().level_mod(); }

  // Frees the memory associated with a candidate.

  static void DeleteCandidate(Candidate* candidate, bool delete_children);

  // Processes a candidate by either adding it to the result_ vector or

  // expanding its children and inserting it into the priority queue.

  // Passing an argument of nullptr does nothing.

  void AddCandidate(Candidate* candidate);

  // Populates the children of "candidate" by expanding the given number of

  // levels from the given cell.  Returns the number of children that were

  // marked "terminal".

  int ExpandChildren(Candidate* candidate, const S2Cell& cell, int num_levels);

  // Computes a set of initial candidates that cover the given region.

  void GetInitialCandidates();

  // Generates a covering and stores it in result_.

  void GetCoveringInternal(const S2Region& region);

  // If level > min_level(), then reduces "level" if necessary so that it also

  // satisfies level_mod().  Levels smaller than min_level() are not affected

  // (since cells at these levels are eventually expanded).

  int AdjustLevel(int level) const;

  // Ensures that all cells with level > min_level() also satisfy level_mod(),

  // by replacing them with an ancestor if necessary.  Cell levels smaller

  // than min_level() are not modified (see AdjustLevel).  The output is

  // then normalized to ensure that no redundant cells are present.

  void AdjustCellLevels(std::vector<S2CellId>* cells) const;

  // Returns true if "covering" contains all children of "id" at level

  // (id.level() + options_.level_mod()).

  bool ContainsAllChildren(const std::vector<S2CellId>& covering,

                           S2CellId id) const;

  // Replaces all descendants of "id" in "covering" with "id".

  // REQUIRES: "covering" contains at least one descendant of "id".

  void ReplaceCellsWithAncestor(std::vector<S2CellId>* covering,

                                S2CellId id) const;

  Options options_;

  // We save a temporary copy of the pointer passed to GetCovering() in order

  // to avoid passing this parameter around internally.  It is only used (and

  // only valid) for the duration of a single GetCovering() call.

  const S2Region* region_ = nullptr;

  // The set of S2CellIds that have been added to the covering so far.

  std::vector<S2CellId> result_;

  // We keep the candidates in a priority queue.  We specify a vector to hold

  // the queue entries since for some reason priority_queue<> uses a deque by

  // default.  We define our own own comparison function on QueueEntries in

  // order to make the results deterministic.  (Using the default

  // less<QueueEntry>, entries of equal priority would be sorted according to

  // the memory address of the candidate.)

  typedef std::pair<int, Candidate*> QueueEntry;

  struct CompareQueueEntries {

    bool operator()(const QueueEntry& x, const QueueEntry& y) const {

      return x.first < y.first;

    }

  };

  typedef std::priority_queue<QueueEntry, std::vector<QueueEntry>,

                              CompareQueueEntries> CandidateQueue;

  CandidateQueue pq_;

  // True if we're computing an interior covering.

  bool interior_covering_;

  // Counter of number of candidates created, for performance evaluation.

  int candidates_created_counter_;

};

#endif  // S2_S2REGION_COVERER_H_