path: root/src/com/google/common/geometry/S2CellId.java

/*
 * Copyright 2005 Google Inc.
 *
 * 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.
 */
package com.google.common.geometry;

import java.util.List;
import java.util.Locale;

/**
 * An S2CellId is a 64-bit unsigned integer that uniquely identifies a cell in
 * the S2 cell decomposition. It has the following format:
 *
 * <pre>
 * id = [face][face_pos]
 * </pre>
 *
 * 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 * (MAX_LEVEL - 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.
 *
 *
 */
public final strictfp class S2CellId implements Comparable<S2CellId> {

  // Although only 60 bits are needed to represent the index of a leaf
  // cell, we need an extra bit in order to represent the position of
  // the center of the leaf cell along the Hilbert curve.
  public static final int FACE_BITS = 3;
  public static final int NUM_FACES = 6;
  public static final int MAX_LEVEL = 30; // Valid levels: 0..MAX_LEVEL
  public static final int POS_BITS = 2 * MAX_LEVEL + 1;
  public static final int MAX_SIZE = 1 << MAX_LEVEL;

  // Constant related to unsigned long's
  public static final long MAX_UNSIGNED = -1L; // Equivalent to 0xffffffffffffffffL

  // The following lookup tables are used to convert efficiently between an
  // (i,j) cell index and the corresponding position along the Hilbert curve.
  // "lookup_pos" maps 4 bits of "i", 4 bits of "j", and 2 bits representing the
  // orientation of the current cell into 8 bits representing the order in which
  // that subcell is visited by the Hilbert curve, plus 2 bits indicating the
  // new orientation of the Hilbert curve within that subcell. (Cell
  // orientations are represented as combination of kSwapMask and kInvertMask.)
  //
  // "lookup_ij" is an inverted table used for mapping in the opposite
  // direction.
  //
  // We also experimented with looking up 16 bits at a time (14 bits of position
  // plus 2 of orientation) but found that smaller lookup tables gave better
  // performance. (2KB fits easily in the primary cache.)


  // Values for these constants are *declared* in the *.h file. Even though
  // the declaration specifies a value for the constant, that declaration
  // is not a *definition* of storage for the value. Because the values are
  // supplied in the declaration, we don't need the values here. Failing to
  // define storage causes link errors for any code that tries to take the
  // address of one of these values.
  private static final int LOOKUP_BITS = 4;
  private static final int SWAP_MASK = 0x01;
  private static final int INVERT_MASK = 0x02;

  private static final int[] LOOKUP_POS = new int[1 << (2 * LOOKUP_BITS + 2)];
  private static final int[] LOOKUP_IJ = new int[1 << (2 * LOOKUP_BITS + 2)];

  /**
   * 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().
   */
  private static final long WRAP_OFFSET = (long) (NUM_FACES) << POS_BITS;

  static {
    initLookupCell(0, 0, 0, 0, 0, 0);
    initLookupCell(0, 0, 0, SWAP_MASK, 0, SWAP_MASK);
    initLookupCell(0, 0, 0, INVERT_MASK, 0, INVERT_MASK);
    initLookupCell(0, 0, 0, SWAP_MASK | INVERT_MASK, 0, SWAP_MASK | INVERT_MASK);
  }

  /**
   * The id of the cell.
   */
  private final long id;

  public S2CellId(long id) {
    this.id = id;
  }

  public S2CellId() {
    this.id = 0;
  }

  /** The default constructor returns an invalid cell id. */
  public static S2CellId none() {
    return new S2CellId();
  }

  /**
   * Returns an invalid cell id guaranteed to be larger than any valid cell id.
   * Useful for creating indexes.
   */
  public static S2CellId sentinel() {
    return new S2CellId(MAX_UNSIGNED); // -1
  }

  /**
   * Return a cell given its face (range 0..5), 61-bit Hilbert curve position
   * within that face, and level (range 0..MAX_LEVEL). 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 give names to the arguments.
   */
  public static S2CellId fromFacePosLevel(int face, long pos, int level) {
    return new S2CellId((((long) face) << POS_BITS) + (pos | 1)).parent(level);
  }

  /**
   * Return the leaf cell containing the given point (a direction vector, not
   * necessarily unit length).
   */
  public static S2CellId fromPoint(S2Point p) {
    int face = S2Projections.xyzToFace(p);
    R2Vector uv = S2Projections.validFaceXyzToUv(face, p);
    int i = stToIJ(S2Projections.uvToST(uv.x));
    int j = stToIJ(S2Projections.uvToST(uv.y));
    return fromFaceIJ(face, i, j);
  }


  /** Return the leaf cell containing the given S2LatLng. */
  public static S2CellId fromLatLng(S2LatLng ll) {
    return fromPoint(ll.toPoint());
  }

  public S2Point toPoint() {
    return S2Point.normalize(toPointRaw());
  }

  /**
   * Return the direction vector corresponding to the center of the given cell.
   * The vector returned by ToPointRaw is not necessarily unit length.
   */
  public S2Point toPointRaw() {
    // 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). We can distinguish these two cases by
    // looking at the low bit of "i" or "j". In the first case the low bit is
    // zero, unless s == 2 (i.e. the level just above leaf cells) in which case
    // the low bit is one.
    //
    // The following calculation converts (i,j) to the (si,ti) coordinates of
    // the cell center. (We need to multiply the coordinates by a factor of 2
    // so that the center of leaf cells can be represented exactly.)

    MutableInteger i = new MutableInteger(0);
    MutableInteger j = new MutableInteger(0);
    int face = toFaceIJOrientation(i, j, null);
    // System.out.println("i= " + i.intValue() + " j = " + j.intValue());
    int delta = isLeaf() ? 1 : (((i.intValue() ^ (((int) id) >>> 2)) & 1) != 0)
      ? 2 : 0;
    int si = (i.intValue() << 1) + delta - MAX_SIZE;
    int ti = (j.intValue() << 1) + delta - MAX_SIZE;
    return faceSiTiToXYZ(face, si, ti);
  }

  /** Return the S2LatLng corresponding to the center of the given cell. */
  public S2LatLng toLatLng() {
    return new S2LatLng(toPointRaw());
  }


  /** The 64-bit unique identifier for this cell. */
  public long id() {
    return id;
  }

  /** Return true if id() represents a valid cell. */
  public boolean isValid() {
    return face() < NUM_FACES && ((lowestOnBit() & (0x1555555555555555L)) != 0);
  }

  /** Which cube face this cell belongs to, in the range 0..5. */
  public int face() {
    return (int) (id >>> POS_BITS);
  }

  /**
   * The position of the cell center along the Hilbert curve over this face, in
   * the range 0..(2**kPosBits-1).
   */
  public long pos() {
    return (id & (-1L >>> FACE_BITS));
  }

  /** Return the subdivision level of the cell (range 0..MAX_LEVEL). */
  public int level() {
    // Fast path for leaf cells.
    if (isLeaf()) {
      return MAX_LEVEL;
    }
    int x = ((int) id);
    int level = -1;
    if (x != 0) {
      level += 16;
    } else {
      x = (int) (id >>> 32);
    }
    // We only need to look at even-numbered bits to determine the
    // level of a valid cell id.
    x &= -x; // Get lowest bit.
    if ((x & 0x00005555) != 0) {
      level += 8;
    }
    if ((x & 0x00550055) != 0) {
      level += 4;
    }
    if ((x & 0x05050505) != 0) {
      level += 2;
    }
    if ((x & 0x11111111) != 0) {
      level += 1;
    }
    // assert (level >= 0 && level <= MAX_LEVEL);
    return level;
  }



  /**
   * Return true if this is a leaf cell (more efficient than checking whether
   * level() == MAX_LEVEL).
   */
  public boolean isLeaf() {
    return ((int) id & 1) != 0;
  }

  /**
   * Return true if this is a top-level face cell (more efficient than checking
   * whether level() == 0).
   */
  public boolean isFace() {
    return (id & (lowestOnBitForLevel(0) - 1)) == 0;
  }

  /**
   * Return the child position (0..3) of this cell's ancestor at the given
   * level, relative to its parent. The argument should be in the range
   * 1..MAX_LEVEL. For example, child_position(1) returns the position of this
   * cell's level-1 ancestor within its top-level face cell.
   */
  public int childPosition(int level) {
    return (int) (id >>> (2 * (MAX_LEVEL - level) + 1)) & 3;
  }

  // Methods that 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.
  //
  // These methods should not be used for iteration. If you want to
  // iterate through all the leaf cells, call child_begin(MAX_LEVEL) and
  // child_end(MAX_LEVEL) instead.
  //
  // It would in fact be error-prone to define a range_end() method,
  // because (range_max().id() + 1) is not always a valid cell id, and the
  // iterator would need to be tested using "<" rather that the usual "!=".
  public S2CellId rangeMin() {
    return new S2CellId(id - (lowestOnBit() - 1));
  }

  public S2CellId rangeMax() {
    return new S2CellId(id + (lowestOnBit() - 1));
  }


  /** Return true if the given cell is contained within this one. */
  public boolean contains(S2CellId other) {
    // assert (isValid() && other.isValid());
    return other.greaterOrEquals(rangeMin()) && other.lessOrEquals(rangeMax());
  }

  /** Return true if the given cell intersects this one. */
  public boolean intersects(S2CellId other) {
    // assert (isValid() && other.isValid());
    return other.rangeMin().lessOrEquals(rangeMax())
      && other.rangeMax().greaterOrEquals(rangeMin());
  }

  public S2CellId parent() {
    // assert (isValid() && level() > 0);
    long newLsb = lowestOnBit() << 2;
    return new S2CellId((id & -newLsb) | newLsb);
  }

  /**
   * Return the cell at the previous level or at the given level (which must be
   * less than or equal to the current level).
   */
  public S2CellId parent(int level) {
    // assert (isValid() && level >= 0 && level <= this.level());
    long newLsb = lowestOnBitForLevel(level);
    return new S2CellId((id & -newLsb) | newLsb);
  }

  public S2CellId childBegin() {
    // assert (isValid() && level() < MAX_LEVEL);
    long oldLsb = lowestOnBit();
    return new S2CellId(id - oldLsb + (oldLsb >>> 2));
  }

  public S2CellId childBegin(int level) {
    // assert (isValid() && level >= this.level() && level <= MAX_LEVEL);
    return new S2CellId(id - lowestOnBit() + lowestOnBitForLevel(level));
  }

  public S2CellId childEnd() {
    // assert (isValid() && level() < MAX_LEVEL);
    long oldLsb = lowestOnBit();
    return new S2CellId(id + oldLsb + (oldLsb >>> 2));
  }

  public S2CellId childEnd(int level) {
    // assert (isValid() && level >= this.level() && level <= MAX_LEVEL);
    return new S2CellId(id + lowestOnBit() + lowestOnBitForLevel(level));
  }

  // 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.childBegin(); !c.equals(id.childEnd()); c = c.next())
  // ...
  //
  // The convention for advancing the iterator is "c = c.next()", so be sure
  // to use 'equals()' in the loop guard, or compare 64-bit cell id's,
  // rather than "c != id.childEnd()".

  /**
   * Return the next 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.
   */
  public S2CellId next() {
    return new S2CellId(id + (lowestOnBit() << 1));
  }

  /**
   * Return the 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.
   */
  public S2CellId prev() {
    return new S2CellId(id - (lowestOnBit() << 1));
  }


  /**
   * Like next(), but wraps around from the last face to the first and vice
   * versa. Should *not* be used for iteration in conjunction with
   * child_begin(), child_end(), Begin(), or End().
   */
  public S2CellId nextWrap() {
    S2CellId n = next();
    if (unsignedLongLessThan(n.id, WRAP_OFFSET)) {
      return n;
    }
    return new S2CellId(n.id - WRAP_OFFSET);
  }

  /**
   * Like prev(), but wraps around from the last face to the first and vice
   * versa. Should *not* be used for iteration in conjunction with
   * child_begin(), child_end(), Begin(), or End().
   */
  public S2CellId prevWrap() {
    S2CellId p = prev();
    if (p.id < WRAP_OFFSET) {
      return p;
    }
    return new S2CellId(p.id + WRAP_OFFSET);
  }


  public static S2CellId begin(int level) {
    return fromFacePosLevel(0, 0, 0).childBegin(level);
  }

  public static S2CellId end(int level) {
    return fromFacePosLevel(5, 0, 0).childEnd(level);
  }


  /**
   * Decodes the cell id from a compact text string suitable for display or
   * indexing. Cells at lower levels (i.e. larger cells) are encoded into
   * fewer characters. The maximum token length is 16.
   *
   * @param token the token to decode
   * @return the S2CellId for that token
   * @throws NumberFormatException if the token is not formatted correctly
   */
  public static S2CellId fromToken(String token) {
    if (token == null) {
      throw new NumberFormatException("Null string in S2CellId.fromToken");
    }
    if (token.length() == 0) {
      throw new NumberFormatException("Empty string in S2CellId.fromToken");
    }
    if (token.length() > 16 || "X".equals(token)) {
      return none();
    }

    long value = 0;
    for (int pos = 0; pos < 16; pos++) {
      int digit = 0;
      if (pos < token.length()) {
        digit = Character.digit(token.charAt(pos), 16);
        if (digit == -1) {
          throw new NumberFormatException(token);
        }
        if (overflowInParse(value, digit)) {
          throw new NumberFormatException("Too large for unsigned long: " + token);
        }
      }
      value = (value * 16) + digit;
    }

    return new S2CellId(value);
  }

  /**
   * Encodes the cell id 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.
   *
   * Simple implementation: convert the id to hex and strip trailing zeros. We
   * could use base-32 or base-64, but assuming the cells used for indexing
   * regions are at least 100 meters across (level 16 or less), the savings
   * would be at most 3 bytes (9 bytes hex vs. 6 bytes base-64).
   *
   * @return the encoded cell id
   */
  public String toToken() {
    if (id == 0) {
      return "X";
    }

    String hex = Long.toHexString(id).toLowerCase(Locale.ENGLISH);
    StringBuilder sb = new StringBuilder(16);
    for (int i = hex.length(); i < 16; i++) {
      sb.append('0');
    }
    sb.append(hex);
    for (int len = 16; len > 0; len--) {
      if (sb.charAt(len - 1) != '0') {
        return sb.substring(0, len);
      }
    }

    throw new RuntimeException("Shouldn't make it here");
  }

  /**
   * Returns true if (current * 10) + digit is a number too large to be
   * represented by an unsigned long.  This is useful for detecting overflow
   * while parsing a string representation of a number.
   */
  private static boolean overflowInParse(long current, int digit) {
    return overflowInParse(current, digit, 10);
  }

  /**
   * Returns true if (current * radix) + digit is a number too large to be
   * represented by an unsigned long.  This is useful for detecting overflow
   * while parsing a string representation of a number.
   * Does not verify whether supplied radix is valid, passing an invalid radix
   * will give undefined results or an ArrayIndexOutOfBoundsException.
   */
  private static boolean overflowInParse(long current, int digit, int radix) {
    if (current >= 0) {
      if (current < maxValueDivs[radix]) {
        return false;
      }
      if (current > maxValueDivs[radix]) {
        return true;
      }
      // current == maxValueDivs[radix]
      return (digit > maxValueMods[radix]);
    }

    // current < 0: high bit is set
    return true;
  }

  // calculated as 0xffffffffffffffff / radix
  private static final long maxValueDivs[] = {0, 0, // 0 and 1 are invalid
      9223372036854775807L, 6148914691236517205L, 4611686018427387903L, // 2-4
      3689348814741910323L, 3074457345618258602L, 2635249153387078802L, // 5-7
      2305843009213693951L, 2049638230412172401L, 1844674407370955161L, // 8-10
      1676976733973595601L, 1537228672809129301L, 1418980313362273201L, // 11-13
      1317624576693539401L, 1229782938247303441L, 1152921504606846975L, // 14-16
      1085102592571150095L, 1024819115206086200L, 970881267037344821L, // 17-19
      922337203685477580L, 878416384462359600L, 838488366986797800L, // 20-22
      802032351030850070L, 768614336404564650L, 737869762948382064L, // 23-25
      709490156681136600L, 683212743470724133L, 658812288346769700L, // 26-28
      636094623231363848L, 614891469123651720L, 595056260442243600L, // 29-31
      576460752303423487L, 558992244657865200L, 542551296285575047L, // 32-34
      527049830677415760L, 512409557603043100L }; // 35-36

  // calculated as 0xffffffffffffffff % radix
  private static final int maxValueMods[] = {0, 0, // 0 and 1 are invalid
      1, 0, 3, 0, 3, 1, 7, 6, 5, 4, 3, 2, 1, 0, 15, 0, 15, 16, 15, 15, // 2-21
      15, 5, 15, 15, 15, 24, 15, 23, 15, 15, 31, 15, 17, 15, 15 }; // 22-36

  /**
   * 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.
   */
  public void getEdgeNeighbors(S2CellId neighbors[]) {

    MutableInteger i = new MutableInteger(0);
    MutableInteger j = new MutableInteger(0);

    int level = this.level();
    int size = 1 << (MAX_LEVEL - level);
    int face = toFaceIJOrientation(i, j, null);

    // Edges 0, 1, 2, 3 are in the S, E, N, W directions.
    neighbors[0] = fromFaceIJSame(face, i.intValue(), j.intValue() - size,
      j.intValue() - size >= 0).parent(level);
    neighbors[1] = fromFaceIJSame(face, i.intValue() + size, j.intValue(),
      i.intValue() + size < MAX_SIZE).parent(level);
    neighbors[2] = fromFaceIJSame(face, i.intValue(), j.intValue() + size,
      j.intValue() + size < MAX_SIZE).parent(level);
    neighbors[3] = fromFaceIJSame(face, i.intValue() - size, j.intValue(),
      i.intValue() - size >= 0).parent(level);
  }

  /**
   * 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.evel(), so that we can determine which vertex is
   * closest (in particular, level == MAX_LEVEL is not allowed).
   */
  public void getVertexNeighbors(int level, List<S2CellId> output) {
    // "level" must be strictly less than this cell's level so that we can
    // determine which vertex this cell is closest to.
    // assert (level < this.level());
    MutableInteger i = new MutableInteger(0);
    MutableInteger j = new MutableInteger(0);
    int face = toFaceIJOrientation(i, j, null);

    // Determine the i- and j-offsets to the closest neighboring cell in each
    // direction. This involves looking at the next bit of "i" and "j" to
    // determine which quadrant of this->parent(level) this cell lies in.
    int halfsize = 1 << (MAX_LEVEL - (level + 1));
    int size = halfsize << 1;
    boolean isame, jsame;
    int ioffset, joffset;
    if ((i.intValue() & halfsize) != 0) {
      ioffset = size;
      isame = (i.intValue() + size) < MAX_SIZE;
    } else {
      ioffset = -size;
      isame = (i.intValue() - size) >= 0;
    }
    if ((j.intValue() & halfsize) != 0) {
      joffset = size;
      jsame = (j.intValue() + size) < MAX_SIZE;
    } else {
      joffset = -size;
      jsame = (j.intValue() - size) >= 0;
    }

    output.add(parent(level));
    output
      .add(fromFaceIJSame(face, i.intValue() + ioffset, j.intValue(), isame)
        .parent(level));
    output
      .add(fromFaceIJSame(face, i.intValue(), j.intValue() + joffset, jsame)
        .parent(level));
    // If i- and j- edge neighbors are *both* on a different face, then this
    // vertex only has three neighbors (it is one of the 8 cube vertices).
    if (isame || jsame) {
      output.add(fromFaceIJSame(face, i.intValue() + ioffset,
        j.intValue() + joffset, isame && jsame).parent(level));
    }
  }

  /**
   * 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.
   *
   * Requires: nbr_level >= this->level(). Note that for cells adjacent to a
   * face vertex, the same neighbor may be appended more than once.
   */
  public void getAllNeighbors(int nbrLevel, List<S2CellId> output) {
    MutableInteger i = new MutableInteger(0);
    MutableInteger j = new MutableInteger(0);

    int face = toFaceIJOrientation(i, j, null);

    // Find the coordinates of the lower left-hand leaf cell. We need to
    // normalize (i,j) to a known position within the cell because nbr_level
    // may be larger than this cell's level.
    int size = 1 << (MAX_LEVEL - level());
    i.setValue(i.intValue() & -size);
    j.setValue(j.intValue() & -size);

    int nbrSize = 1 << (MAX_LEVEL - nbrLevel);
    // assert (nbrSize <= size);

    // We compute the N-S, E-W, and diagonal neighbors in one pass.
    // The loop test is at the end of the loop to avoid 32-bit overflow.
    for (int k = -nbrSize;; k += nbrSize) {
      boolean sameFace;
      if (k < 0) {
        sameFace = (j.intValue() + k >= 0);
      } else if (k >= size) {
        sameFace = (j.intValue() + k < MAX_SIZE);
      } else {
        sameFace = true;
        // North and South neighbors.
        output.add(fromFaceIJSame(face, i.intValue() + k,
          j.intValue() - nbrSize, j.intValue() - size >= 0).parent(nbrLevel));
        output.add(fromFaceIJSame(face, i.intValue() + k, j.intValue() + size,
          j.intValue() + size < MAX_SIZE).parent(nbrLevel));
      }
      // East, West, and Diagonal neighbors.
      output.add(fromFaceIJSame(face, i.intValue() - nbrSize,
        j.intValue() + k, sameFace && i.intValue() - size >= 0).parent(
        nbrLevel));
      output.add(fromFaceIJSame(face, i.intValue() + size, j.intValue() + k,
        sameFace && i.intValue() + size < MAX_SIZE).parent(nbrLevel));
      if (k >= size) {
        break;
      }
    }
  }

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

  /**
   * Return a leaf cell given its cube face (range 0..5) and i- and
   * j-coordinates (see s2.h).
   */
  public static S2CellId fromFaceIJ(int face, int i, int j) {
    // Optimization notes:
    // - Non-overlapping bit fields can be combined with either "+" or "|".
    // Generally "+" seems to produce better code, but not always.

    // gcc doesn't have very good code generation for 64-bit operations.
    // We optimize this by computing the result as two 32-bit integers
    // and combining them at the end. Declaring the result as an array
    // rather than local variables helps the compiler to do a better job
    // of register allocation as well. Note that the two 32-bits halves
    // get shifted one bit to the left when they are combined.
    long n[] = {0, face << (POS_BITS - 33)};

    // Alternating faces have opposite Hilbert curve orientations; this
    // is necessary in order for all faces to have a right-handed
    // coordinate system.
    int bits = (face & SWAP_MASK);

    // Each iteration maps 4 bits of "i" and "j" into 8 bits of the Hilbert
    // curve position. The lookup table transforms a 10-bit key of the form
    // "iiiijjjjoo" to a 10-bit value of the form "ppppppppoo", where the
    // letters [ijpo] denote bits of "i", "j", Hilbert curve position, and
    // Hilbert curve orientation respectively.

    for (int k = 7; k >= 0; --k) {
      bits = getBits(n, i, j, k, bits);
    }

    S2CellId s = new S2CellId((((n[1] << 32) + n[0]) << 1) + 1);
    return s;
  }

  private static int getBits(long[] n, int i, int j, int k, int bits) {
    final int mask = (1 << LOOKUP_BITS) - 1;
    bits += (((i >> (k * LOOKUP_BITS)) & mask) << (LOOKUP_BITS + 2));
    bits += (((j >> (k * LOOKUP_BITS)) & mask) << 2);
    bits = LOOKUP_POS[bits];
    n[k >> 2] |= ((((long) bits) >> 2) << ((k & 3) * 2 * LOOKUP_BITS));
    bits &= (SWAP_MASK | INVERT_MASK);
    return bits;
  }


  /**
   * 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-NULL, also return
   * the Hilbert curve orientation for the current cell.
   */
  public int toFaceIJOrientation(MutableInteger pi, MutableInteger pj,
      MutableInteger orientation) {
    // System.out.println("Entering toFaceIjorientation");
    int face = this.face();
    int bits = (face & SWAP_MASK);

    // System.out.println("face = " + face + " bits = " + bits);

    // Each iteration maps 8 bits of the Hilbert curve position into
    // 4 bits of "i" and "j". The lookup table transforms a key of the
    // form "ppppppppoo" to a value of the form "iiiijjjjoo", where the
    // letters [ijpo] represents bits of "i", "j", the Hilbert curve
    // position, and the Hilbert curve orientation respectively.
    //
    // On the first iteration we need to be careful to clear out the bits
    // representing the cube face.
    for (int k = 7; k >= 0; --k) {
      bits = getBits1(pi, pj, k, bits);
      // System.out.println("pi = " + pi + " pj= " + pj + " bits = " + bits);
    }

    if (orientation != null) {
      // The position of a non-leaf cell at level "n" consists of a prefix of
      // 2*n bits that identifies the cell, followed by a suffix of
      // 2*(MAX_LEVEL-n)+1 bits of the form 10*. If n==MAX_LEVEL, the suffix is
      // just "1" and has no effect. Otherwise, it consists of "10", followed
      // by (MAX_LEVEL-n-1) repetitions of "00", followed by "0". The "10" has
      // no effect, while each occurrence of "00" has the effect of reversing
      // the kSwapMask bit.
      // assert (S2.POS_TO_ORIENTATION[2] == 0);
      // assert (S2.POS_TO_ORIENTATION[0] == S2.SWAP_MASK);
      if ((lowestOnBit() & 0x1111111111111110L) != 0) {
        bits ^= S2.SWAP_MASK;
      }
      orientation.setValue(bits);
    }
    return face;
  }

  private int getBits1(MutableInteger i, MutableInteger j, int k, int bits) {
    final int nbits = (k == 7) ? (MAX_LEVEL - 7 * LOOKUP_BITS) : LOOKUP_BITS;

    bits += (((int) (id >>> (k * 2 * LOOKUP_BITS + 1)) &
            ((1 << (2 * nbits)) - 1))) << 2;
    /*
     * System.out.println("id is: " + id_); System.out.println("bits is " +
     * bits); System.out.println("lookup_ij[bits] is " + lookup_ij[bits]);
     */
    bits = LOOKUP_IJ[bits];
    i.setValue(i.intValue()
      + ((bits >> (LOOKUP_BITS + 2)) << (k * LOOKUP_BITS)));
    /*
     * System.out.println("left is " + ((bits >> 2) & ((1 << kLookupBits) -
     * 1))); System.out.println("right is " + (k * kLookupBits));
     * System.out.println("j is: " + j.intValue()); System.out.println("addition
     * is: " + ((((bits >> 2) & ((1 << kLookupBits) - 1))) << (k *
     * kLookupBits)));
     */
    j.setValue(j.intValue()
      + ((((bits >> 2) & ((1 << LOOKUP_BITS) - 1))) << (k * LOOKUP_BITS)));
    bits &= (SWAP_MASK | INVERT_MASK);
    return bits;
  }

  /** Return the lowest-numbered bit that is on for cells at the given level. */
  public long lowestOnBit() {
    return id & -id;
  }

  /**
   * Return the lowest-numbered bit that is on for this cell id, which is equal
   * to (uint64(1) << (2 * (MAX_LEVEL - level))). So for example, a.lsb() <=
   * b.lsb() if and only if a.level() >= b.level(), but the first test is more
   * efficient.
   */
  public static long lowestOnBitForLevel(int level) {
    return 1L << (2 * (MAX_LEVEL - level));
  }


  /**
   * Return the i- or j-index of the leaf cell containing the given s- or
   * t-value.
   */
  private static int stToIJ(double s) {
    // Converting from floating-point to integers via static_cast is very slow
    // on Intel processors because it requires changing the rounding mode.
    // Rounding to the nearest integer using FastIntRound() is much faster.

    final int m = MAX_SIZE / 2; // scaling multiplier
    return (int) Math
      .max(0, Math.min(2 * m - 1, Math.round(m * s + (m - 0.5))));
  }

  /**
   * Convert (face, si, ti) coordinates (see s2.h) to a direction vector (not
   * necessarily unit length).
   */
  private static S2Point faceSiTiToXYZ(int face, int si, int ti) {
    final double kScale = 1.0 / MAX_SIZE;
    double u = S2Projections.stToUV(kScale * si);
    double v = S2Projections.stToUV(kScale * ti);
    return S2Projections.faceUvToXyz(face, u, v);
  }

  /**
   * Given (i, j) coordinates that may be out of bounds, normalize them by
   * returning the corresponding neighbor cell on an adjacent face.
   */
  private static S2CellId fromFaceIJWrap(int face, int i, int j) {
    // Convert i and j to the coordinates of a leaf cell just beyond the
    // boundary of this face. This prevents 32-bit overflow in the case
    // of finding the neighbors of a face cell, and also means that we
    // don't need to worry about the distinction between (s,t) and (u,v).
    i = Math.max(-1, Math.min(MAX_SIZE, i));
    j = Math.max(-1, Math.min(MAX_SIZE, j));

    // Find the (s,t) coordinates corresponding to (i,j). At least one
    // of these coordinates will be just outside the range [0, 1].
    final double kScale = 1.0 / MAX_SIZE;
    double s = kScale * ((i << 1) + 1 - MAX_SIZE);
    double t = kScale * ((j << 1) + 1 - MAX_SIZE);

    // Find the leaf cell coordinates on the adjacent face, and convert
    // them to a cell id at the appropriate level.
    S2Point p = S2Projections.faceUvToXyz(face, s, t);
    face = S2Projections.xyzToFace(p);
    R2Vector st = S2Projections.validFaceXyzToUv(face, p);
    return fromFaceIJ(face, stToIJ(st.x), stToIJ(st.y));
  }

  /**
   * Public helper function that calls FromFaceIJ if sameFace is true, or
   * FromFaceIJWrap if sameFace is false.
   */
  public static S2CellId fromFaceIJSame(int face, int i, int j,
      boolean sameFace) {
    if (sameFace) {
      return S2CellId.fromFaceIJ(face, i, j);
    } else {
      return S2CellId.fromFaceIJWrap(face, i, j);
    }
  }

  @Override
  public boolean equals(Object that) {
    if (!(that instanceof S2CellId)) {
      return false;
    }
    S2CellId x = (S2CellId) that;
    return id() == x.id();
  }

  /**
   * Returns true if x1 < x2, when both values are treated as unsigned.
   */
  public static boolean unsignedLongLessThan(long x1, long x2) {
    return (x1 + Long.MIN_VALUE) < (x2 + Long.MIN_VALUE);
  }

  /**
   * Returns true if x1 > x2, when both values are treated as unsigned.
   */
  public static boolean unsignedLongGreaterThan(long x1, long x2) {
    return (x1 + Long.MIN_VALUE) > (x2 + Long.MIN_VALUE);
  }

  public boolean lessThan(S2CellId x) {
    return unsignedLongLessThan(id, x.id);
  }

  public boolean greaterThan(S2CellId x) {
    return unsignedLongGreaterThan(id, x.id);
  }

  public boolean lessOrEquals(S2CellId x) {
    return unsignedLongLessThan(id, x.id) || id == x.id;
  }

  public boolean greaterOrEquals(S2CellId x) {
    return unsignedLongGreaterThan(id, x.id) || id == x.id;
  }

  @Override
  public int hashCode() {
    return (int) ((id >>> 32) + id);
  }


  @Override
  public String toString() {
    return "(face=" + face() + ", pos=" + Long.toHexString(pos()) + ", level="
      + level() + ")";
  }

  private static void initLookupCell(int level, int i, int j,
      int origOrientation, int pos, int orientation) {
    if (level == LOOKUP_BITS) {
      int ij = (i << LOOKUP_BITS) + j;
      LOOKUP_POS[(ij << 2) + origOrientation] = (pos << 2) + orientation;
      LOOKUP_IJ[(pos << 2) + origOrientation] = (ij << 2) + orientation;
    } else {
      level++;
      i <<= 1;
      j <<= 1;
      pos <<= 2;
      // Initialize each sub-cell recursively.
      for (int subPos = 0; subPos < 4; subPos++) {
        int ij = S2.posToIJ(orientation, subPos);
        int orientationMask = S2.posToOrientation(subPos);
        initLookupCell(level, i + (ij >>> 1), j + (ij & 1), origOrientation,
            pos + subPos, orientation ^ orientationMask);
      }
    }
  }

  @Override
  public int compareTo(S2CellId that) {
    return unsignedLongLessThan(this.id, that.id) ? -1 :
        unsignedLongGreaterThan(this.id, that.id) ? 1 : 0;
  }
}