s2cell_id.h

// 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_S2CELL_ID_H_
#define S2_S2CELL_ID_H_

#include <cstddef>
#include <functional>
#include <iostream>
#include <string>
#include <vector>

#include "s2/base/integral_types.h"
#include "s2/base/logging.h"
#include "s2/base/port.h"
#include "s2/_fp_contract_off.h"
#include "s2/r2.h"
#include "s2/r2rect.h"
#include "s2/s1angle.h"
#include "s2/s2coords.h"
#include "s2/third_party/absl/strings/string_view.h"
#include "s2/util/bits/bits.h"
#include "s2/util/coding/coder.h"

class S2LatLng;

#ifndef SWIG
#define IFNDEF_SWIG(x) x
#else
#define IFNDEF_SWIG(x)
#endif

// An S2CellId is a 64-bit unsigned integer that uniquely identifies a
// cell in the S2 cell decomposition.  It has the following format:
//
//   id = [face][face_pos]
//
//   face:     a 3-bit number (range 0..5) encoding the cube face.
//
//   face_pos: a 61-bit number encoding the position of the center of this
//             cell along the Hilbert curve over this face (see the Wiki
//             pages for details).
//
// Sequentially increasing cell ids follow a continuous space-filling curve
// over the entire sphere.  They have the following properties:
//
//  - The id of a cell at level k consists of a 3-bit face number followed
//    by k bit pairs that recursively select one of the four children of
//    each cell.  The next bit is always 1, and all other bits are 0.
//    Therefore, the level of a cell is determined by the position of its
//    lowest-numbered bit that is turned on (for a cell at level k, this
//    position is 2 * (kMaxLevel - k).)
//
//  - The id of a parent cell is at the midpoint of the range of ids spanned
//    by its children (or by its descendants at any level).
//
// Leaf cells are often used to represent points on the unit sphere, and
// this class provides methods for converting directly between these two
// representations.  For cells that represent 2D regions rather than
// discrete point, it is better to use the S2Cell class.
//
// This class is intended to be copied by value as desired.  It uses
// the default copy constructor and assignment operator.
class S2CellId {
 public:
  // The extra position bit (61 rather than 60) let us encode each cell as its
  // Hilbert curve position at the cell center (which is halfway along the
  // portion of the Hilbert curve that fills that cell).
  static const int kFaceBits = 3;
  static const int kNumFaces = 6;
  static const int kMaxLevel = S2::kMaxCellLevel;  // Valid levels: 0..kMaxLevel
  static const int kPosBits = 2 * kMaxLevel + 1;
  static const int kMaxSize = 1 << kMaxLevel;

  explicit IFNDEF_SWIG(constexpr) S2CellId(uint64 id) : id_(id) {}

  // Construct a leaf cell containing the given point "p".  Usually there is
  // is exactly one such cell, but for points along the edge of a cell, any
  // adjacent cell may be (deterministically) chosen.  This is because
  // S2CellIds are considered to be closed sets.  The returned cell will
  // always contain the given point, i.e.
  //
  //   S2Cell(S2CellId(p)).Contains(p)
  //
  // is always true.  The point "p" does not need to be normalized.
  //
  // If instead you want every point to be contained by exactly one S2Cell,
  // you will need to convert the S2CellIds to S2Loops (which implement point
  // containment this way).
  explicit S2CellId(const S2Point& p);

  // Construct a leaf cell containing the given normalized S2LatLng.
  explicit S2CellId(const S2LatLng& ll);

  // The default constructor returns an invalid cell id.
  IFNDEF_SWIG(constexpr) S2CellId() : id_(0) {}
  static constexpr S2CellId None() { return S2CellId(); }

  // Returns an invalid cell id guaranteed to be larger than any
  // valid cell id.  Useful for creating indexes.
  static constexpr S2CellId Sentinel() { return S2CellId(~uint64{0}); }

  // Return the cell corresponding to a given S2 cube face.
  static S2CellId FromFace(int face);

  // Return a cell given its face (range 0..5), Hilbert curve position within
  // that face (an unsigned integer with S2CellId::kPosBits bits), and level
  // (range 0..kMaxLevel).  The given position will be modified to correspond
  // to the Hilbert curve position at the center of the returned cell.  This
  // is a static function rather than a constructor in order to indicate what
  // the arguments represent.
  static S2CellId FromFacePosLevel(int face, uint64 pos, int level);

  // Return the direction vector corresponding to the center of the given
  // cell.  The vector returned by ToPointRaw is not necessarily unit length.
  // This method returns the same result as S2Cell::GetCenter().
  //
  // The maximum directional error in ToPoint() (compared to the exact
  // mathematical result) is 1.5 * DBL_EPSILON radians, and the maximum length
  // error is 2 * DBL_EPSILON (the same as Normalize).
  S2Point ToPoint() const { return ToPointRaw().Normalize(); }
  S2Point ToPointRaw() const;

  // Return the center of the cell in (s,t) coordinates (see s2coords.h).
  R2Point GetCenterST() const;

  // Return the edge length of this cell in (s,t)-space.
  double GetSizeST() const;

  // Return the edge length in (s,t)-space of cells at the given level.
  static double GetSizeST(int level);

  // Return the bounds of this cell in (s,t)-space.
  R2Rect GetBoundST() const;

  // Return the center of the cell in (u,v) coordinates (see s2coords.h).
  // Note that the center of the cell is defined as the point at which it is
  // recursively subdivided into four children; in general, it is not at the
  // midpoint of the (u,v) rectangle covered by the cell.
  R2Point GetCenterUV() const;

  // Return the bounds of this cell in (u,v)-space.
  R2Rect GetBoundUV() const;

  // Expand a rectangle in (u,v)-space so that it contains all points within
  // the given distance of the boundary, and return the smallest such
  // rectangle.  If the distance is negative, then instead shrink this
  // rectangle so that it excludes all points within the given absolute
  // distance of the boundary.
  //
  // Distances are measured *on the sphere*, not in (u,v)-space.  For example,
  // you can use this method to expand the (u,v)-bound of an S2CellId so that
  // it contains all points within 5km of the original cell.  You can then
  // test whether a point lies within the expanded bounds like this:
  //
  //   R2Point uv;
  //   if (S2::FaceXYZtoUV(face, point, &uv) && bound.Contains(uv)) { ... }
  //
  // Limitations:
  //
  //  - Because the rectangle is drawn on one of the six cube-face planes
  //    (i.e., {x,y,z} = +/-1), it can cover at most one hemisphere.  This
  //    limits the maximum amount that a rectangle can be expanded.  For
  //    example, S2CellId bounds can be expanded safely by at most 45 degrees
  //    (about 5000 km on the Earth's surface).
  //
  //  - The implementation is not exact for negative distances.  The resulting
  //    rectangle will exclude all points within the given distance of the
  //    boundary but may be slightly smaller than necessary.
  static R2Rect ExpandedByDistanceUV(const R2Rect& uv, S1Angle distance);

  // Return the (face, si, ti) coordinates of the center of the cell.  Note
  // that although (si,ti) coordinates span the range [0,2**31] in general,
  // the cell center coordinates are always in the range [1,2**31-1] and
  // therefore can be represented using a signed 32-bit integer.
  int GetCenterSiTi(int* psi, int* pti) const;

  // Return the S2LatLng corresponding to the center of the given cell.
  S2LatLng ToLatLng() const;

  // The 64-bit unique identifier for this cell.
  uint64 id() const { return id_; }

  // Return true if id() represents a valid cell.
  //
  // All methods require is_valid() to be true unless otherwise specified
  // (although not all methods enforce this).
  bool is_valid() const;

  // Which cube face this cell belongs to, in the range 0..5.
  int face() const;

  // The position of the cell center along the Hilbert curve over this face,
  // in the range 0..(2**kPosBits-1).
  uint64 pos() const;

  // Return the subdivision level of the cell (range 0..kMaxLevel).
  int level() const;

  // Return the edge length of this cell in (i,j)-space.
  int GetSizeIJ() const;

  // Like the above, but return the size of cells at the given level.
  static int GetSizeIJ(int level);

  // Return true if this is a leaf cell (more efficient than checking
  // whether level() == kMaxLevel).
  bool is_leaf() const;

  // Return true if this is a top-level face cell (more efficient than
  // checking whether level() == 0).
  bool is_face() const;

  // Return the child position (0..3) of this cell within its parent.
  // REQUIRES: level() >= 1.
  int child_position() const;

  // Return the child position (0..3) of this cell's ancestor at the given
  // level within its parent.  For example, child_position(1) returns the
  // position of this cell's level-1 ancestor within its top-level face cell.
  // REQUIRES: 1 <= level <= this->level().
  int child_position(int level) const;

  // These methods return the range of cell ids that are contained within this
  // cell (including itself).  The range is *inclusive* (i.e. test using >=
  // and <=) and the return values of both methods are valid leaf cell ids.
  // In other words, a.contains(b) if and only if
  //
  //     (b >= a.range_min() && b <= a.range_max())
  //
  // If you want to iterate through all the descendants of this cell at a
  // particular level, use child_begin(level) and child_end(level) instead.
  // Also see maximum_tile(), which can be used to iterate through a range of
  // cells using S2CellIds at different levels that are as large as possible.
  //
  // If you need to convert the range to a semi-open interval [min, limit)
  // (e.g., in order to use a key-value store that only supports semi-open
  // range queries), do not attempt to define "limit" as range_max.next().
  // The problem is that leaf S2CellIds are 2 units apart, so the semi-open
  // interval [min, limit) includes an additional value (range_max.id() + 1)
  // which is happens to be a valid S2CellId about one-third of the time and
  // is *never* contained by this cell.  (It always correpsonds to a cell that
  // is larger than this one.)  You can define "limit" as (range_max.id() + 1)
  // if necessary (which is not always a valid S2CellId but can still be used
  // with FromToken/ToToken), or you can convert range_max() to the key space
  // of your key-value store and define "limit" as Successor(key).
  //
  // Note that Sentinel().range_min() == Sentinel.range_max() == Sentinel().
  S2CellId range_min() const;
  S2CellId range_max() const;

  // Return true if the given cell is contained within this one.
  bool contains(S2CellId other) const;

  // Return true if the given cell intersects this one.
  bool intersects(S2CellId other) const;

  // Return the cell at the previous level or at the given level (which must
  // be less than or equal to the current level).
  S2CellId parent() const;
  S2CellId parent(int level) const;

  // Return the immediate child of this cell at the given traversal order
  // position (in the range 0 to 3).  This cell must not be a leaf cell.
  S2CellId child(int position) const;

  // Iterator-style methods for traversing the immediate children of a cell or
  // all of the children at a given level (greater than or equal to the current
  // level).  Note that the end value is exclusive, just like standard STL
  // iterators, and may not even be a valid cell id.  You should iterate using
  // code like this:
  //
  //   for(S2CellId c = id.child_begin(); c != id.child_end(); c = c.next())
  //     ...
  //
  // The convention for advancing the iterator is "c = c.next()" rather
  // than "++c" to avoid possible confusion with incrementing the
  // underlying 64-bit cell id.
  S2CellId child_begin() const;
  S2CellId child_begin(int level) const;
  S2CellId child_end() const;
  S2CellId child_end(int level) const;

  // Return the next/previous cell at the same level along the Hilbert curve.
  // Works correctly when advancing from one face to the next, but
  // does *not* wrap around from the last face to the first or vice versa.
  S2CellId next() const;
  S2CellId prev() const;

  // This method advances or retreats the indicated number of steps along the
  // Hilbert curve at the current level, and returns the new position.  The
  // position is never advanced past End() or before Begin().
  S2CellId advance(int64 steps) const;

  // Returns the number of steps that this cell is from Begin(level()). The
  // return value is always non-negative.
  int64 distance_from_begin() const;

  // Like next() and prev(), but these methods wrap around from the last face
  // to the first and vice versa.  They should *not* be used for iteration in
  // conjunction with child_begin(), child_end(), Begin(), or End().  The
  // input must be a valid cell id.
  S2CellId next_wrap() const;
  S2CellId prev_wrap() const;

  // This method advances or retreats the indicated number of steps along the
  // Hilbert curve at the current level, and returns the new position.  The
  // position wraps between the first and last faces as necessary.  The input
  // must be a valid cell id.
  S2CellId advance_wrap(int64 steps) const;

  // Return the largest cell with the same range_min() and such that
  // range_max() < limit.range_min().  Returns "limit" if no such cell exists.
  // This method can be used to generate a small set of S2CellIds that covers
  // a given range (a "tiling").  This example shows how to generate a tiling
  // for a semi-open range of leaf cells [start, limit):
  //
  //   for (S2CellId id = start.maximum_tile(limit);
  //        id != limit; id = id.next().maximum_tile(limit)) { ... }
  //
  // Note that in general the cells in the tiling will be of different sizes;
  // they gradually get larger (near the middle of the range) and then
  // gradually get smaller (as "limit" is approached).
  S2CellId maximum_tile(S2CellId limit) const;

  // Returns the level of the lowest common ancestor of this cell and "other",
  // that is, the maximum level such that parent(level) == other.parent(level).
  // Returns -1 if the two cells do not have any common ancestor (i.e., they
  // are from different faces).
  int GetCommonAncestorLevel(S2CellId other) const;

  // Iterator-style methods for traversing all the cells along the Hilbert
  // curve at a given level (across all 6 faces of the cube).  Note that the
  // end value is exclusive (just like standard STL iterators), and is not a
  // valid cell id.
  static S2CellId Begin(int level);
  static S2CellId End(int level);

  // Methods to encode and decode cell ids to compact text strings suitable
  // for display or indexing.  Cells at lower levels (i.e. larger cells) are
  // encoded into fewer characters.  The maximum token length is 16.
  //
  // Tokens preserve ordering, i.e. ToToken(x) < ToToken(y) iff x < y.
  //
  // ToToken() returns a string by value for convenience; the compiler
  // does this without intermediate copying in most cases.
  //
  // These methods guarantee that FromToken(ToToken(x)) == x even when
  // "x" is an invalid cell id.  All tokens are alphanumeric strings.
  // FromToken() returns S2CellId::None() for malformed inputs.
  string ToToken() const;
  static S2CellId FromToken(const char* token, size_t length);
  static S2CellId FromToken(const std::string& token);

  // Use encoder to generate a serialized representation of this cell id.
  // Can also encode an invalid cell.
  void Encode(Encoder* const encoder) const;

  // Decodes an S2CellId encoded by Encode(). Returns true on success.
  bool Decode(Decoder* const decoder);

  // Creates a human readable debug string.  Used for << and available for
  // direct usage as well.  The format is "f/dd..d" where "f" is a digit in
  // the range [0-5] representing the S2CellId face, and "dd..d" is a string
  // of digits in the range [0-3] representing each child's position with
  // respect to its parent.  (Note that the latter string may be empty.)
  //
  // For example "4/" represents S2CellId::FromFace(4), and "3/02" represents
  // S2CellId::FromFace(3).child(0).child(2).
  string ToString() const;

  // Converts a string in the format returned by ToString() to an S2CellId.
  // Returns S2CellId::None() if the string could not be parsed.
  //
  // The method name includes "Debug" in order to avoid possible confusion
  // with FromToken() above.
  static S2CellId FromDebugString(absl::string_view str);

  // Return the four cells that are adjacent across the cell's four edges.
  // Neighbors are returned in the order defined by S2Cell::GetEdge.  All
  // neighbors are guaranteed to be distinct.
  void GetEdgeNeighbors(S2CellId neighbors[4]) const;

  // Return the neighbors of closest vertex to this cell at the given level,
  // by appending them to "output".  Normally there are four neighbors, but
  // the closest vertex may only have three neighbors if it is one of the 8
  // cube vertices.
  //
  // Requires: level < this->level(), so that we can determine which vertex is
  // closest (in particular, level == kMaxLevel is not allowed).
  void AppendVertexNeighbors(int level, std::vector<S2CellId>* output) const;

  // Append all neighbors of this cell at the given level to "output".  Two
  // cells X and Y are neighbors if their boundaries intersect but their
  // interiors do not.  In particular, two cells that intersect at a single
  // point are neighbors.  Note that for cells adjacent to a face vertex, the
  // same neighbor may be appended more than once.
  //
  // REQUIRES: nbr_level >= this->level().
  void AppendAllNeighbors(int nbr_level, std::vector<S2CellId>* output) const;

  /////////////////////////////////////////////////////////////////////
  // Low-level methods.

  // Return a leaf cell given its cube face (range 0..5) and
  // i- and j-coordinates (see s2coords.h).
  static S2CellId FromFaceIJ(int face, int i, int j);

  // Return the (face, i, j) coordinates for the leaf cell corresponding to
  // this cell id.  Since cells are represented by the Hilbert curve position
  // at the center of the cell, the returned (i,j) for non-leaf cells will be
  // a leaf cell adjacent to the cell center.  If "orientation" is non-nullptr,
  // also return the Hilbert curve orientation for the current cell.
  int ToFaceIJOrientation(int* pi, int* pj, int* orientation) const;

  // Return the lowest-numbered bit that is on for this cell id, which is
  // equal to (uint64{1} << (2 * (kMaxLevel - level))).  So for example,
  // a.lsb() <= b.lsb() if and only if a.level() >= b.level(), but the
  // first test is more efficient.
  uint64 lsb() const { return id_ & (~id_ + 1); }

  // Return the lowest-numbered bit that is on for cells at the given level.
  static uint64 lsb_for_level(int level) {
    return uint64{1} << (2 * (kMaxLevel - level));
  }

  // Return the bound in (u,v)-space for the cell at the given level containing
  // the leaf cell with the given (i,j)-coordinates.
  static R2Rect IJLevelToBoundUV(int ij[2], int level);

  // When S2CellId is used as a key in one of the btree container types
  // (util/btree), indicate that linear rather than binary search should be
  // used.  This is much faster when the comparison function is cheap.
  typedef std::true_type goog_btree_prefer_linear_node_search;

 private:
  // This is the offset required to wrap around from the beginning of the
  // Hilbert curve to the end or vice versa; see next_wrap() and prev_wrap().
  // SWIG doesn't understand uint64{}, so use static_cast.
  static const uint64 kWrapOffset = static_cast<uint64>(kNumFaces) << kPosBits;

  // Given a face and a point (i,j) where either i or j is outside the valid
  // range [0..kMaxSize-1], this function first determines which neighboring
  // face "contains" (i,j), and then returns the leaf cell on that face which
  // is adjacent to the given face and whose distance from (i,j) is minimal.
  static S2CellId FromFaceIJWrap(int face, int i, int j);

  // Inline helper function that calls FromFaceIJ if "same_face" is true,
  // or FromFaceIJWrap if "same_face" is false.
  static S2CellId FromFaceIJSame(int face, int i, int j, bool same_face);

  uint64 id_;
} ABSL_ATTRIBUTE_PACKED;  // Necessary so that structures containing S2CellId's
                          // can be ABSL_ATTRIBUTE_PACKED.

inline bool operator==(S2CellId x, S2CellId y) {
  return x.id() == y.id();
}

inline bool operator!=(S2CellId x, S2CellId y) {
  return x.id() != y.id();
}

inline bool operator<(S2CellId x, S2CellId y) {
  return x.id() < y.id();
}

inline bool operator>(S2CellId x, S2CellId y) {
  return x.id() > y.id();
}

inline bool operator<=(S2CellId x, S2CellId y) {
  return x.id() <= y.id();
}

inline bool operator>=(S2CellId x, S2CellId y) {
  return x.id() >= y.id();
}

inline S2CellId S2CellId::FromFace(int face) {
  return S2CellId((static_cast<uint64>(face) << kPosBits) + lsb_for_level(0));
}

inline S2CellId S2CellId::FromFacePosLevel(int face, uint64 pos, int level) {
  S2CellId cell((static_cast<uint64>(face) << kPosBits) + (pos | 1));
  return cell.parent(level);
}

inline int S2CellId::GetCenterSiTi(int* psi, int* pti) const {
  // First we compute the discrete (i,j) coordinates of a leaf cell contained
  // within the given cell.  Given that cells are represented by the Hilbert
  // curve position corresponding at their center, it turns out that the cell
  // returned by ToFaceIJOrientation is always one of two leaf cells closest
  // to the center of the cell (unless the given cell is a leaf cell itself,
  // in which case there is only one possibility).
  //
  // Given a cell of size s >= 2 (i.e. not a leaf cell), and letting (imin,
  // jmin) be the coordinates of its lower left-hand corner, the leaf cell
  // returned by ToFaceIJOrientation() is either (imin + s/2, jmin + s/2)
  // (imin + s/2 - 1, jmin + s/2 - 1).  The first case is the one we want.
  // We can distinguish these two cases by looking at the low bit of "i" or
  // "j".  In the second case the low bit is one, unless s == 2 (i.e. the
  // level just above leaf cells) in which case the low bit is zero.
  //
  // In the code below, the expression ((i ^ (int(id_) >> 2)) & 1) is true
  // if we are in the second case described above.
  int i, j;
  int face = ToFaceIJOrientation(&i, &j, nullptr);
  int delta = is_leaf() ? 1 : ((i ^ (static_cast<int>(id_) >> 2)) & 1) ? 2 : 0;

  // Note that (2 * {i,j} + delta) will never overflow a 32-bit integer.
  *psi = 2 * i + delta;
  *pti = 2 * j + delta;
  return face;
}

inline bool S2CellId::is_valid() const {
  return (face() < kNumFaces && (lsb() & 0x1555555555555555ULL));
}

inline int S2CellId::face() const {
  return id_ >> kPosBits;
}

inline uint64 S2CellId::pos() const {
  return id_ & (~uint64{0} >> kFaceBits);
}

inline int S2CellId::level() const {
  // We can't just S2_DCHECK(is_valid()) because we want level() to be
  // defined for end-iterators, i.e. S2CellId::End(kLevel).  However there is
  // no good way to define S2CellId::None().level(), so we do prohibit that.
  S2_DCHECK(id_ != 0);

  // A special case for leaf cells is not worthwhile.
  return kMaxLevel - (Bits::FindLSBSetNonZero64(id_) >> 1);
}

inline int S2CellId::GetSizeIJ() const {
  return GetSizeIJ(level());
}

inline double S2CellId::GetSizeST() const {
  return GetSizeST(level());
}

inline int S2CellId::GetSizeIJ(int level) {
  return 1 << (kMaxLevel - level);
}

inline double S2CellId::GetSizeST(int level) {
  return S2::IJtoSTMin(GetSizeIJ(level));
}

inline bool S2CellId::is_leaf() const {
  return int(id_) & 1;
}

inline bool S2CellId::is_face() const {
  return (id_ & (lsb_for_level(0) - 1)) == 0;
}

inline int S2CellId::child_position() const {
  // No need for a special implementation; the compiler optimizes this well.
  return child_position(level());
}

inline int S2CellId::child_position(int level) const {
  S2_DCHECK(is_valid());
  S2_DCHECK_GE(level, 1);
  S2_DCHECK_LE(level, this->level());
  return static_cast<int>(id_ >> (2 * (kMaxLevel - level) + 1)) & 3;
}

inline S2CellId S2CellId::range_min() const {
  return S2CellId(id_ - (lsb() - 1));
}

inline S2CellId S2CellId::range_max() const {
  return S2CellId(id_ + (lsb() - 1));
}

inline bool S2CellId::contains(S2CellId other) const {
  S2_DCHECK(is_valid());
  S2_DCHECK(other.is_valid());
  return other >= range_min() && other <= range_max();
}

inline bool S2CellId::intersects(S2CellId other) const {
  S2_DCHECK(is_valid());
  S2_DCHECK(other.is_valid());
  return other.range_min() <= range_max() && other.range_max() >= range_min();
}

inline S2CellId S2CellId::parent(int level) const {
  S2_DCHECK(is_valid());
  S2_DCHECK_GE(level, 0);
  S2_DCHECK_LE(level, this->level());
  uint64 new_lsb = lsb_for_level(level);
  return S2CellId((id_ & (~new_lsb + 1)) | new_lsb);
}

inline S2CellId S2CellId::parent() const {
  S2_DCHECK(is_valid());
  S2_DCHECK(!is_face());
  uint64 new_lsb = lsb() << 2;
  return S2CellId((id_ & (~new_lsb + 1)) | new_lsb);
}

inline S2CellId S2CellId::child(int position) const {
  S2_DCHECK(is_valid());
  S2_DCHECK(!is_leaf());
  // To change the level, we need to move the least-significant bit two
  // positions downward.  We do this by subtracting (4 * new_lsb) and adding
  // new_lsb.  Then to advance to the given child cell, we add
  // (2 * position * new_lsb).
  uint64 new_lsb = lsb() >> 2;
  return S2CellId(id_ + (2 * position + 1 - 4) * new_lsb);
}

inline S2CellId S2CellId::child_begin() const {
  S2_DCHECK(is_valid());
  S2_DCHECK(!is_leaf());
  uint64 old_lsb = lsb();
  return S2CellId(id_ - old_lsb + (old_lsb >> 2));
}

inline S2CellId S2CellId::child_begin(int level) const {
  S2_DCHECK(is_valid());
  S2_DCHECK_GE(level, this->level());
  S2_DCHECK_LE(level, kMaxLevel);
  return S2CellId(id_ - lsb() + lsb_for_level(level));
}

inline S2CellId S2CellId::child_end() const {
  S2_DCHECK(is_valid());
  S2_DCHECK(!is_leaf());
  uint64 old_lsb = lsb();
  return S2CellId(id_ + old_lsb + (old_lsb >> 2));
}

inline S2CellId S2CellId::child_end(int level) const {
  S2_DCHECK(is_valid());
  S2_DCHECK_GE(level, this->level());
  S2_DCHECK_LE(level, kMaxLevel);
  return S2CellId(id_ + lsb() + lsb_for_level(level));
}

inline S2CellId S2CellId::next() const {
  return S2CellId(id_ + (lsb() << 1));
}

inline S2CellId S2CellId::prev() const {
  return S2CellId(id_ - (lsb() << 1));
}

inline S2CellId S2CellId::next_wrap() const {
  S2_DCHECK(is_valid());
  S2CellId n = next();
  if (n.id_ < kWrapOffset) return n;
  return S2CellId(n.id_ - kWrapOffset);
}

inline S2CellId S2CellId::prev_wrap() const {
  S2_DCHECK(is_valid());
  S2CellId p = prev();
  if (p.id_ < kWrapOffset) return p;
  return S2CellId(p.id_ + kWrapOffset);
}

inline S2CellId S2CellId::Begin(int level) {
  return FromFace(0).child_begin(level);
}

inline S2CellId S2CellId::End(int level) {
  return FromFace(5).child_end(level);
}

std::ostream& operator<<(std::ostream& os, S2CellId id);

// Hasher for S2CellId.
// Example use: std::unordered_map<S2CellId, int, S2CellIdHash>.
struct S2CellIdHash {
  size_t operator()(S2CellId id) const {
    return std::hash<uint64>()(id.id());
  }
};

#undef IFNDEF_SWIG

#endif  // S2_S2CELL_ID_H_