text: /*
   * Copyright 2016-2018 Uber Technologies, 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.
   */
  /** @file h3Index.c
   * @brief   H3Index utility functions
   *          (see h3api.h for the main library entry functions)
   */
  #include "h3Index.h"
  #include <faceijk.h>
  #include <inttypes.h>
  #include <math.h>
  #include <stdlib.h>
  #include <string.h>
  #include "baseCells.h"
  #include "faceijk.h"
  #include "mathExtensions.h"
  #include "stackAlloc.h"
  
  /**
   * Returns the H3 resolution of an H3 index.
   * @param h The H3 index.
   * @return The resolution of the H3 index argument.
   */
  int H3_EXPORT(h3GetResolution)(H3Index h) { return H3_GET_RESOLUTION(h); }
  
  /**
   * Returns the H3 base cell number of an H3 index.
   * @param h The H3 index.
   * @return The base cell of the H3 index argument.
   */
  int H3_EXPORT(h3GetBaseCell)(H3Index h) { return H3_GET_BASE_CELL(h); }
  
  /**
   * Converts a string representation of an H3 index into an H3 index.
   * @param str The string representation of an H3 index.
   * @return The H3 index corresponding to the string argument, or 0 if invalid.
   */
  H3Index H3_EXPORT(stringToH3)(const char* str) {
      H3Index h = H3_INVALID_INDEX;
      // If failed, h will be unmodified and we should return 0 anyways.
      sscanf(str, "%" PRIx64, &h);
      return h;
  }
  
  /**
   * Converts an H3 index into a string representation.
   * @param h The H3 index to convert.
   * @param str The string representation of the H3 index.
   * @param sz Size of the buffer `str`
   */
  void H3_EXPORT(h3ToString)(H3Index h, char* str, size_t sz) {
      // An unsigned 64 bit integer will be expressed in at most
      // 16 digits plus 1 for the null terminator.
      if (sz < 17) {
          // Buffer is potentially not large enough.
          return;
      }
      sprintf(str, "%" PRIx64, h);
  }
  
  /**
   * Returns whether or not an H3 index is valid.
   * @param h The H3 index to validate.
   * @return 1 if the H3 index if valid, and 0 if it is not.
   */
  int H3_EXPORT(h3IsValid)(H3Index h) {
      if (H3_GET_MODE(h) != H3_HEXAGON_MODE) return 0;
  
      int baseCell = H3_GET_BASE_CELL(h);
      if (baseCell < 0 || baseCell >= NUM_BASE_CELLS) return 0;
  
      int res = H3_GET_RESOLUTION(h);
      if (res < 0 || res > MAX_H3_RES) return 0;
  
      for (int r = 1; r <= res; r++) {
          Direction digit = H3_GET_INDEX_DIGIT(h, r);
          if (digit < CENTER_DIGIT || digit >= NUM_DIGITS) return 0;
      }
  
      for (int r = res + 1; r <= MAX_H3_RES; r++) {
          Direction digit = H3_GET_INDEX_DIGIT(h, r);
          if (digit != INVALID_DIGIT) return 0;
      }
  
      return 1;
  }
  
  /**
   * Initializes an H3 index.
   * @param hp The H3 index to initialize.
   * @param res The H3 resolution to initialize the index to.
   * @param baseCell The H3 base cell to initialize the index to.
   * @param initDigit The H3 digit (0-7) to initialize all of the index digits to.
   */
  void setH3Index(H3Index* hp, int res, int baseCell, Direction initDigit) {
      H3Index h = H3_INIT;
      H3_SET_MODE(h, H3_HEXAGON_MODE);
      H3_SET_RESOLUTION(h, res);
      H3_SET_BASE_CELL(h, baseCell);
      for (int r = 1; r <= res; r++) H3_SET_INDEX_DIGIT(h, r, initDigit);
      *hp = h;
  }
  
  /**
   * h3ToParent produces the parent index for a given H3 index
   *
   * @param h H3Index to find parent of
   * @param parentRes The resolution to switch to (parent, grandparent, etc)
   *
   * @return H3Index of the parent, or 0 if you actually asked for a child
   */
  H3Index H3_EXPORT(h3ToParent)(H3Index h, int parentRes) {
      int childRes = H3_GET_RESOLUTION(h);
      if (parentRes > childRes) {
          return H3_INVALID_INDEX;
      } else if (parentRes == childRes) {
          return h;
      } else if (parentRes < 0 || parentRes > MAX_H3_RES) {
          return H3_INVALID_INDEX;
      }
      H3Index parentH = H3_SET_RESOLUTION(h, parentRes);
      for (int i = parentRes + 1; i <= childRes; i++) {
          H3_SET_INDEX_DIGIT(parentH, i, H3_DIGIT_MASK);
      }
      return parentH;
  }
  
  /**
   * maxH3ToChildrenSize returns the maximum number of children possible for a
   * given child level.
   *
   * @param h H3Index to find the number of children of
   * @param childRes The resolution of the child level you're interested in
   *
   * @return int count of maximum number of children (equal for hexagons, less for
   * pentagons
   */
  int H3_EXPORT(maxH3ToChildrenSize)(H3Index h, int childRes) {
      int parentRes = H3_GET_RESOLUTION(h);
      if (parentRes > childRes) {
          return 0;
      }
      return _ipow(7, (childRes - parentRes));
  }
  
  /**
   * makeDirectChild takes an index and immediately returns the immediate child
   * index based on the specified cell number. Bit operations only, could generate
   * invalid indexes if not careful (deleted cell under a pentagon).
   *
   * @param h H3Index to find the direct child of
   * @param cellNumber int id of the direct child (0-6)
   *
   * @return The new H3Index for the child
   */
  H3Index makeDirectChild(H3Index h, int cellNumber) {
      int childRes = H3_GET_RESOLUTION(h) + 1;
      H3Index childH = H3_SET_RESOLUTION(h, childRes);
      H3_SET_INDEX_DIGIT(childH, childRes, cellNumber);
      return childH;
  }
  
  /**
   * h3ToChildren takes the given hexagon id and generates all of the children
   * at the specified resolution storing them into the provided memory pointer.
   * It's assumed that maxH3ToChildrenSize was used to determine the allocation.
   *
   * @param h H3Index to find the children of
   * @param childRes int the child level to produce
   * @param children H3Index* the memory to store the resulting addresses in
   */
  void H3_EXPORT(h3ToChildren)(H3Index h, int childRes, H3Index* children) {
      int parentRes = H3_GET_RESOLUTION(h);
      if (parentRes > childRes) {
          return;
      } else if (parentRes == childRes) {
          *children = h;
          return;
      }
      int bufferSize = H3_EXPORT(maxH3ToChildrenSize)(h, childRes);
      int bufferChildStep = (bufferSize / 7);
      int isAPentagon = H3_EXPORT(h3IsPentagon)(h);
      for (int i = 0; i < 7; i++) {
          if (isAPentagon && i == K_AXES_DIGIT) {
              H3Index* nextChild = children + bufferChildStep;
              while (children < nextChild) {
                  *children = H3_INVALID_INDEX;
                  children++;
              }
          } else {
              H3_EXPORT(h3ToChildren)(makeDirectChild(h, i), childRes, children);
              children += bufferChildStep;
          }
      }
  }
  
  /**
   * compact takes a set of hexagons all at the same resolution and compresses
   * them by pruning full child branches to the parent level. This is also done
   * for all parents recursively to get the minimum number of hex addresses that
   * perfectly cover the defined space.
   * @param h3Set Set of hexagons
   * @param compactedSet The output array of compressed hexagons (preallocated)
   * @param numHexes The size of the input and output arrays (possible that no
   * contiguous regions exist in the set at all and no compression possible)
   * @return an error code on bad input data
   */
  int H3_EXPORT(compact)(const H3Index* h3Set, H3Index* compactedSet,
                         const int numHexes) {
      int res = H3_GET_RESOLUTION(h3Set[0]);
      if (res == 0) {
          // No compaction possible, just copy the set to output
          for (int i = 0; i < numHexes; i++) {
              compactedSet[i] = h3Set[i];
          }
          return 0;
      }
      H3Index* remainingHexes = malloc(numHexes * sizeof(H3Index));
      memcpy(remainingHexes, h3Set, numHexes * sizeof(H3Index));
      H3Index* hashSetArray = calloc(numHexes, sizeof(H3Index));
      H3Index* compactedSetOffset = compactedSet;
      int numRemainingHexes = numHexes;
      while (numRemainingHexes) {
          res = H3_GET_RESOLUTION(remainingHexes[0]);
          int parentRes = res - 1;
          // Put the parents of the hexagons into the temp array
          // via a hashing mechanism, and use the reserved bits
          // to track how many times a parent is duplicated
          for (int i = 0; i < numRemainingHexes; i++) {
              H3Index currIndex = remainingHexes[i];
              if (currIndex != 0) {
                  H3Index parent = H3_EXPORT(h3ToParent)(currIndex, parentRes);
                  // Modulus hash the parent into the temp array
                  int loc = (int)(parent % numRemainingHexes);
                  int loopCount = 0;
                  while (hashSetArray[loc] != 0) {
                      if (loopCount > numRemainingHexes) {
                          // LCOV_EXCL_START
                          // This case should not be possible because at most one
                          // index is placed into hashSetArray per
                          // numRemainingHexes.
                          free(remainingHexes);
                          free(hashSetArray);
                          return -1;
                          // LCOV_EXCL_STOP
                      }
                      H3Index tempIndex =
                          hashSetArray[loc] & H3_RESERVED_MASK_NEGATIVE;
                      if (tempIndex == parent) {
                          int count = H3_GET_RESERVED_BITS(hashSetArray[loc]) + 1;
                          if (count > 7) {
                              // Only possible on duplicate input
                              free(remainingHexes);
                              free(hashSetArray);
                              return -2;
                          }
                          H3_SET_RESERVED_BITS(parent, count);
                          hashSetArray[loc] = H3_INVALID_INDEX;
                      } else {
                          loc = (loc + 1) % numRemainingHexes;
                      }
                      loopCount++;
                  }
                  hashSetArray[loc] = parent;
              }
          }
          // Determine which parent hexagons have a complete set
          // of children and put them in the compactableHexes array
          int compactableCount = 0;
          int maxCompactableCount =
              numRemainingHexes / 6;  // Somehow all pentagons; conservative
          if (maxCompactableCount == 0) {
              memcpy(compactedSetOffset, remainingHexes,
                     numRemainingHexes * sizeof(remainingHexes[0]));
              break;
          }
          H3Index* compactableHexes =
              malloc(maxCompactableCount * sizeof(H3Index));
          for (int i = 0; i < numRemainingHexes; i++) {
              if (hashSetArray[i] == 0) continue;
              int count = H3_GET_RESERVED_BITS(hashSetArray[i]) + 1;
              // Include the deleted direction for pentagons as implicitly "there"
              if (H3_EXPORT(h3IsPentagon)(hashSetArray[i] &
                                          H3_RESERVED_MASK_NEGATIVE)) {
                  // We need this later on, no need to recalculate
                  H3_SET_RESERVED_BITS(hashSetArray[i], count);
                  // Increment count after setting the reserved bits,
                  // since count is already incremented above, so it
                  // will be the expected value for a complete hexagon.
                  count++;
              }
              if (count == 7) {
                  // Bingo! Full set!
                  compactableHexes[compactableCount] =
                      hashSetArray[i] & H3_RESERVED_MASK_NEGATIVE;
                  compactableCount++;
              }
          }
          // Uncompactable hexes are immediately copied into the
          // output compactedSetOffset
          int uncompactableCount = 0;
          for (int i = 0; i < numRemainingHexes; i++) {
              H3Index currIndex = remainingHexes[i];
              if (currIndex != H3_INVALID_INDEX) {
                  H3Index parent = H3_EXPORT(h3ToParent)(currIndex, parentRes);
                  // Modulus hash the parent into the temp array
                  // to determine if this index was included in
                  // the compactableHexes array
                  int loc = (int)(parent % numRemainingHexes);
                  int loopCount = 0;
                  bool isUncompactable = true;
                  do {
                      if (loopCount > numRemainingHexes) {
                          // LCOV_EXCL_START
                          // This case should not be possible because at most one
                          // index is placed into hashSetArray per input hexagon.
                          free(compactableHexes);
                          free(remainingHexes);
                          free(hashSetArray);
                          return -1;  // Only possible on duplicate input
                          // LCOV_EXCL_STOP
                      }
                      H3Index tempIndex =
                          hashSetArray[loc] & H3_RESERVED_MASK_NEGATIVE;
                      if (tempIndex == parent) {
                          int count = H3_GET_RESERVED_BITS(hashSetArray[loc]) + 1;
                          if (count == 7) {
                              isUncompactable = false;
                          }
                          break;
                      } else {
                          loc = (loc + 1) % numRemainingHexes;
                      }
                      loopCount++;
                  } while (hashSetArray[loc] != parent);
                  if (isUncompactable) {
                      compactedSetOffset[uncompactableCount] = remainingHexes[i];
                      uncompactableCount++;
                  }
              }
          }
          // Set up for the next loop
          memset(hashSetArray, 0, numHexes * sizeof(H3Index));
          compactedSetOffset += uncompactableCount;
          memcpy(remainingHexes, compactableHexes,
                 compactableCount * sizeof(H3Index));
          numRemainingHexes = compactableCount;
          free(compactableHexes);
      }
      free(remainingHexes);
      free(hashSetArray);
      return 0;
  }
  
  /**
   * uncompact takes a compressed set of hexagons and expands back to the
   * original set of hexagons.
   * @param compactedSet Set of hexagons
   * @param numHexes The number of hexes in the input set
   * @param h3Set Output array of decompressed hexagons (preallocated)
   * @param maxHexes The size of the output array to bound check against
   * @param res The hexagon resolution to decompress to
   * @return An error code if output array is too small or any hexagon is
   * smaller than the output resolution.
   */
  int H3_EXPORT(uncompact)(const H3Index* compactedSet, const int numHexes,
                           H3Index* h3Set, const int maxHexes, const int res) {
      int outOffset = 0;
      for (int i = 0; i < numHexes; i++) {
          if (outOffset >= maxHexes) {
              // We went too far, abort!
              return -1;
          }
          if (compactedSet[i] == 0) continue;
          int currentRes = H3_GET_RESOLUTION(compactedSet[i]);
          if (currentRes > res) {
              // Nonsensical. Abort.
              return -2;
          }
          if (currentRes == res) {
              // Just copy and move along
              h3Set[outOffset] = compactedSet[i];
              outOffset++;
          } else {
              // Bigger hexagon to reduce in size
              int numHexesToGen =
                  H3_EXPORT(maxH3ToChildrenSize)(compactedSet[i], res);
              if (outOffset + numHexesToGen > maxHexes) {
                  // We're about to go too far, abort!
                  return -1;
              }
              H3_EXPORT(h3ToChildren)(compactedSet[i], res, h3Set + outOffset);
              outOffset += numHexesToGen;
          }
      }
      return 0;
  }
  
  /**
   * maxUncompactSize takes a compacted set of hexagons are provides an
   * upper-bound estimate of the size of the uncompacted set of hexagons.
   * @param compactedSet Set of hexagons
   * @param numHexes The number of hexes in the input set
   * @param res The hexagon resolution to decompress to
   * @return The number of hexagons to allocate memory for, or a negative
   * number if an error occurs.
   */
  int H3_EXPORT(maxUncompactSize)(const H3Index* compactedSet, const int numHexes,
                                  const int res) {
      int maxNumHexagons = 0;
      for (int i = 0; i < numHexes; i++) {
          if (compactedSet[i] == 0) continue;
          int currentRes = H3_GET_RESOLUTION(compactedSet[i]);
          if (currentRes > res) {
              // Nonsensical. Abort.
              return -1;
          }
          if (currentRes == res) {
              maxNumHexagons++;
          } else {
              // Bigger hexagon to reduce in size
              int numHexesToGen =
                  H3_EXPORT(maxH3ToChildrenSize)(compactedSet[i], res);
              maxNumHexagons += numHexesToGen;
          }
      }
      return maxNumHexagons;
  }
  
  /**
   * h3IsResClassIII takes a hexagon ID and determines if it is in a
   * Class III resolution (rotated versus the icosahedron and subject
   * to shape distortion adding extra points on icosahedron edges, making
   * them not true hexagons).
   * @param h The H3Index to check.
   * @return Returns 1 if the hexagon is class III, otherwise 0.
   */
  int H3_EXPORT(h3IsResClassIII)(H3Index h) { return H3_GET_RESOLUTION(h) % 2; }
  
  /**
   * h3IsPentagon takes an H3Index and determines if it is actually a
   * pentagon.
   * @param h The H3Index to check.
   * @return Returns 1 if it is a pentagon, otherwise 0.
   */
  int H3_EXPORT(h3IsPentagon)(H3Index h) {
      return _isBaseCellPentagon(H3_GET_BASE_CELL(h)) &&
             !_h3LeadingNonZeroDigit(h);
  }
  
  /**
   * Returns the highest resolution non-zero digit in an H3Index.
   * @param h The H3Index.
   * @return The highest resolution non-zero digit in the H3Index.
   */
  Direction _h3LeadingNonZeroDigit(H3Index h) {
      for (int r = 1; r <= H3_GET_RESOLUTION(h); r++)
          if (H3_GET_INDEX_DIGIT(h, r)) return H3_GET_INDEX_DIGIT(h, r);
  
      // if we're here it's all 0's
      return CENTER_DIGIT;
  }
  
  /**
   * Rotate an H3Index 60 degrees counter-clockwise about a pentagonal center.
   * @param h The H3Index.
   */
  H3Index _h3RotatePent60ccw(H3Index h) {
      // rotate in place; skips any leading 1 digits (k-axis)
  
      int foundFirstNonZeroDigit = 0;
      for (int r = 1, res = H3_GET_RESOLUTION(h); r <= res; r++) {
          // rotate this digit
          H3_SET_INDEX_DIGIT(h, r, _rotate60ccw(H3_GET_INDEX_DIGIT(h, r)));
  
          // look for the first non-zero digit so we
          // can adjust for deleted k-axes sequence
          // if necessary
          if (!foundFirstNonZeroDigit && H3_GET_INDEX_DIGIT(h, r) != 0) {
              foundFirstNonZeroDigit = 1;
  
              // adjust for deleted k-axes sequence
              if (_h3LeadingNonZeroDigit(h) == K_AXES_DIGIT)
                  h = _h3Rotate60ccw(h);
          }
      }
      return h;
  }
  
  /**
   * Rotate an H3Index 60 degrees clockwise about a pentagonal center.
   * @param h The H3Index.
   */
  H3Index _h3RotatePent60cw(H3Index h) {
      // rotate in place; skips any leading 1 digits (k-axis)
  
      int foundFirstNonZeroDigit = 0;
      for (int r = 1, res = H3_GET_RESOLUTION(h); r <= res; r++) {
          // rotate this digit
          H3_SET_INDEX_DIGIT(h, r, _rotate60cw(H3_GET_INDEX_DIGIT(h, r)));
  
          // look for the first non-zero digit so we
          // can adjust for deleted k-axes sequence
          // if necessary
          if (!foundFirstNonZeroDigit && H3_GET_INDEX_DIGIT(h, r) != 0) {
              foundFirstNonZeroDigit = 1;
  
              // adjust for deleted k-axes sequence
              if (_h3LeadingNonZeroDigit(h) == K_AXES_DIGIT) h = _h3Rotate60cw(h);
          }
      }
      return h;
  }
  
  /**
   * Rotate an H3Index 60 degrees counter-clockwise.
   * @param h The H3Index.
   */
  H3Index _h3Rotate60ccw(H3Index h) {
      for (int r = 1, res = H3_GET_RESOLUTION(h); r <= res; r++) {
          Direction oldDigit = H3_GET_INDEX_DIGIT(h, r);
          H3_SET_INDEX_DIGIT(h, r, _rotate60ccw(oldDigit));
      }
  
      return h;
  }
  
  /**
   * Rotate an H3Index 60 degrees clockwise.
   * @param h The H3Index.
   */
  H3Index _h3Rotate60cw(H3Index h) {
      for (int r = 1, res = H3_GET_RESOLUTION(h); r <= res; r++) {
          H3_SET_INDEX_DIGIT(h, r, _rotate60cw(H3_GET_INDEX_DIGIT(h, r)));
      }
  
      return h;
  }
  
  /**
   * Convert an FaceIJK address to the corresponding H3Index.
   * @param fijk The FaceIJK address.
   * @param res The cell resolution.
   * @return The encoded H3Index (or 0 on failure).
   */
  H3Index _faceIjkToH3(const FaceIJK* fijk, int res) {
      // initialize the index
      H3Index h = H3_INIT;
      H3_SET_MODE(h, H3_HEXAGON_MODE);
      H3_SET_RESOLUTION(h, res);
  
      // check for res 0/base cell
      if (res == 0) {
          if (fijk->coord.i > MAX_FACE_COORD || fijk->coord.j > MAX_FACE_COORD ||
              fijk->coord.k > MAX_FACE_COORD) {
              // out of range input
              return H3_INVALID_INDEX;
          }
  
          H3_SET_BASE_CELL(h, _faceIjkToBaseCell(fijk));
          return h;
      }
  
      // we need to find the correct base cell FaceIJK for this H3 index;
      // start with the passed in face and resolution res ijk coordinates
      // in that face's coordinate system
      FaceIJK fijkBC = *fijk;
  
      // build the H3Index from finest res up
      // adjust r for the fact that the res 0 base cell offsets the index array
      CoordIJK* ijk = &fijkBC.coord;
      for (int r = res - 1; r >= 0; r--) {
          CoordIJK lastIJK = *ijk;
          CoordIJK lastCenter;
          if (isResClassIII(r + 1)) {
              // rotate ccw
              _upAp7(ijk);
              lastCenter = *ijk;
              _downAp7(&lastCenter);
          } else {
              // rotate cw
              _upAp7r(ijk);
              lastCenter = *ijk;
              _downAp7r(&lastCenter);
          }
  
          CoordIJK diff;
          _ijkSub(&lastIJK, &lastCenter, &diff);
          _ijkNormalize(&diff);
  
          H3_SET_INDEX_DIGIT(h, r + 1, _unitIjkToDigit(&diff));
      }
  
      // fijkBC should now hold the IJK of the base cell in the
      // coordinate system of the current face
  
      if (fijkBC.coord.i > MAX_FACE_COORD || fijkBC.coord.j > MAX_FACE_COORD ||
          fijkBC.coord.k > MAX_FACE_COORD) {
          // out of range input
          return H3_INVALID_INDEX;
      }
  
      // lookup the correct base cell
      int baseCell = _faceIjkToBaseCell(&fijkBC);
      H3_SET_BASE_CELL(h, baseCell);
  
      // rotate if necessary to get canonical base cell orientation
      // for this base cell
      int numRots = _faceIjkToBaseCellCCWrot60(&fijkBC);
      if (_isBaseCellPentagon(baseCell)) {
          // force rotation out of missing k-axes sub-sequence
          if (_h3LeadingNonZeroDigit(h) == K_AXES_DIGIT) {
              // check for a cw/ccw offset face; default is ccw
              if (_baseCellIsCwOffset(baseCell, fijkBC.face)) {
                  h = _h3Rotate60cw(h);
              } else {
                  h = _h3Rotate60ccw(h);
              }
          }
  
          for (int i = 0; i < numRots; i++) h = _h3RotatePent60ccw(h);
      } else {
          for (int i = 0; i < numRots; i++) {
              h = _h3Rotate60ccw(h);
          }
      }
  
      return h;
  }
  
  /**
   * Encodes a coordinate on the sphere to the H3 index of the containing cell at
   * the specified resolution.
   *
   * Returns 0 on invalid input.
   *
   * @param g The spherical coordinates to encode.
   * @param res The desired H3 resolution for the encoding.
   * @return The encoded H3Index (or 0 on failure).
   */
  H3Index H3_EXPORT(geoToH3)(const GeoCoord* g, int res) {
      if (res < 0 || res > MAX_H3_RES) {
          return H3_INVALID_INDEX;
      }
      if (!isfinite(g->lat) || !isfinite(g->lon)) {
          return H3_INVALID_INDEX;
      }
  
      FaceIJK fijk;
      _geoToFaceIjk(g, res, &fijk);
      return _faceIjkToH3(&fijk, res);
  }
  
  /**
   * Convert an H3Index to the FaceIJK address on a specified icosahedral face.
   * @param h The H3Index.
   * @param fijk The FaceIJK address, initialized with the desired face
   *        and normalized base cell coordinates.
   * @return Returns 1 if the possibility of overage exists, otherwise 0.
   */
  int _h3ToFaceIjkWithInitializedFijk(H3Index h, FaceIJK* fijk) {
      CoordIJK* ijk = &fijk->coord;
      int res = H3_GET_RESOLUTION(h);
  
      // center base cell hierarchy is entirely on this face
      int possibleOverage = 1;
      if (!_isBaseCellPentagon(H3_GET_BASE_CELL(h)) &&
          (res == 0 ||
           (fijk->coord.i == 0 && fijk->coord.j == 0 && fijk->coord.k == 0)))
          possibleOverage = 0;
  
      for (int r = 1; r <= res; r++) {
          if (isResClassIII(r)) {
              // Class III == rotate ccw
              _downAp7(ijk);
          } else {
              // Class II == rotate cw
              _downAp7r(ijk);
          }
  
          _neighbor(ijk, H3_GET_INDEX_DIGIT(h, r));
      }
  
      return possibleOverage;
  }
  
  /**
   * Convert an H3Index to a FaceIJK address.
   * @param h The H3Index.
   * @param fijk The corresponding FaceIJK address.
   */
  void _h3ToFaceIjk(H3Index h, FaceIJK* fijk) {
      int baseCell = H3_GET_BASE_CELL(h);
      // adjust for the pentagonal missing sequence; all of sub-sequence 5 needs
      // to be adjusted (and some of sub-sequence 4 below)
      if (_isBaseCellPentagon(baseCell) && _h3LeadingNonZeroDigit(h) == 5)
          h = _h3Rotate60cw(h);
  
      // start with the "home" face and ijk+ coordinates for the base cell of c
      *fijk = baseCellData[baseCell].homeFijk;
      if (!_h3ToFaceIjkWithInitializedFijk(h, fijk))
          return;  // no overage is possible; h lies on this face
  
      // if we're here we have the potential for an "overage"; i.e., it is
      // possible that c lies on an adjacent face
  
      CoordIJK origIJK = fijk->coord;
  
      // if we're in Class III, drop into the next finer Class II grid
      int res = H3_GET_RESOLUTION(h);
      if (isResClassIII(res)) {
          // Class III
          _downAp7r(&fijk->coord);
          res++;
      }
  
      // adjust for overage if needed
      // a pentagon base cell with a leading 4 digit requires special handling
      int pentLeading4 =
          (_isBaseCellPentagon(baseCell) && _h3LeadingNonZeroDigit(h) == 4);
      if (_adjustOverageClassII(fijk, res, pentLeading4, 0)) {
          // if the base cell is a pentagon we have the potential for secondary
          // overages
          if (_isBaseCellPentagon(baseCell)) {
              while (1) {
                  if (!_adjustOverageClassII(fijk, res, 0, 0)) break;
              }
          }
  
          if (res != H3_GET_RESOLUTION(h)) _upAp7r(&fijk->coord);
      } else if (res != H3_GET_RESOLUTION(h)) {
          fijk->coord = origIJK;
      }
  }
  
  /**
   * Determines the spherical coordinates of the center point of an H3 index.
   *
   * @param h3 The H3 index.
   * @param g The spherical coordinates of the H3 cell center.
   */
  void H3_EXPORT(h3ToGeo)(H3Index h3, GeoCoord* g) {
      FaceIJK fijk;
      _h3ToFaceIjk(h3, &fijk);
      _faceIjkToGeo(&fijk, H3_GET_RESOLUTION(h3), g);
  }
  
  /**
   * Determines the cell boundary in spherical coordinates for an H3 index.
   *
   * @param h3 The H3 index.
   * @param gb The boundary of the H3 cell in spherical coordinates.
   */
  void H3_EXPORT(h3ToGeoBoundary)(H3Index h3, GeoBoundary* gb) {
      FaceIJK fijk;
      _h3ToFaceIjk(h3, &fijk);
      _faceIjkToGeoBoundary(&fijk, H3_GET_RESOLUTION(h3),
                            H3_EXPORT(h3IsPentagon)(h3), gb);
  }
  
  /**
   * Returns whether or not a resolution is a Class III grid. Note that odd
   * resolutions are Class III and even resolutions are Class II.
   * @param res The H3 resolution.
   * @return 1 if the resolution is a Class III grid, and 0 if the resolution is
   *         a Class II grid.
   */
  int isResClassIII(int res) { return res % 2; }
  
  /**
   * Produces ijk+ coordinates for an index anchored by an origin.
   *
   * The coordinate space used by this function may have deleted
   * regions or warping due to pentagonal distortion.
   *
   * Coordinates are only comparable if they come from the same
   * origin index.
   *
   * @param origin An anchoring index for the ijk+ coordinate system.
   * @param index Index to find the coordinates of
   * @param out ijk+ coordinates of the index will be placed here on success
   * @return 0 on success, or another value on failure.
   */
  int h3ToIjk(H3Index origin, H3Index h3, CoordIJK* out) {
      if (H3_GET_MODE(origin) != H3_HEXAGON_MODE ||
          H3_GET_MODE(h3) != H3_HEXAGON_MODE) {
          // Only hexagon mode is relevant, since we can't
          // encode directionality in CoordIJK.
          return 1;
      }
  
      int res = H3_GET_RESOLUTION(origin);
  
      if (res != H3_GET_RESOLUTION(h3)) {
          return 1;
      }
  
      int originBaseCell = H3_GET_BASE_CELL(origin);
      int baseCell = H3_GET_BASE_CELL(h3);
  
      // Direction from origin base cell to index base cell
      Direction dir = 0;
      Direction revDir = 0;
      if (originBaseCell != baseCell) {
          dir = _getBaseCellDirection(originBaseCell, baseCell);
          if (dir == INVALID_DIGIT) {
              // Base cells are not neighbors, can't unfold.
              return 2;
          }
          revDir = _getBaseCellDirection(baseCell, originBaseCell);
          assert(revDir != INVALID_DIGIT);
      }
  
      int originOnPent = _isBaseCellPentagon(originBaseCell);
      int indexOnPent = _isBaseCellPentagon(baseCell);
  
      FaceIJK indexFijk = {0};
      if (dir != CENTER_DIGIT) {
          // Rotate index into the orientation of the origin base cell.
          // cw because we are undoing the rotation into that base cell.
          int baseCellRotations = baseCellNeighbor60CCWRots[originBaseCell][dir];
          if (indexOnPent) {
              for (int i = 0; i < baseCellRotations; i++) {
                  h3 = _h3RotatePent60cw(h3);
  
                  revDir = _rotate60cw(revDir);
                  if (revDir == K_AXES_DIGIT) revDir = _rotate60cw(revDir);
              }
          } else {
              for (int i = 0; i < baseCellRotations; i++) {
                  h3 = _h3Rotate60cw(h3);
  
                  revDir = _rotate60cw(revDir);
              }
          }
      }
      // Face is unused. This produces coordinates in base cell coordinate space.
      _h3ToFaceIjkWithInitializedFijk(h3, &indexFijk);
  
      // Origin leading digit -> index leading digit -> rotations 60 cw
      // Either being 1 (K axis) is invalid.
      // No good default at 0.
      const int PENTAGON_ROTATIONS[7][7] = {
          {0, -1, 0, 0, 0, 0, 0},        // 0
          {-1, -1, -1, -1, -1, -1, -1},  // 1
          {0, -1, 0, 0, 0, 1, 0},        // 2
          {0, -1, 0, 0, 1, 1, 0},        // 3
          {0, -1, 0, 5, 0, 0, 0},        // 4
          {0, -1, 5, 5, 0, 0, 0},        // 5
          {0, -1, 0, 0, 0, 0, 0},        // 6
      };
      // Simply prohibit many pentagon distortion cases rather than handling them.
      const bool FAILED_DIRECTIONS_II[7][7] = {
          {false, false, false, false, false, false, false},  // 0
          {false, false, false, false, false, false, false},  // 1
          {false, false, false, false, true, false, false},   // 2
          {false, false, false, false, false, false, true},   // 3
          {false, false, false, true, false, false, false},   // 4
          {false, false, true, false, false, false, false},   // 5
          {false, false, false, false, false, true, false},   // 6
      };
      const bool FAILED_DIRECTIONS_III[7][7] = {
          {false, false, false, false, false, false, false},  // 0
          {false, false, false, false, false, false, false},  // 1
          {false, false, false, false, false, true, false},   // 2
          {false, false, false, false, true, false, false},   // 3
          {false, false, true, false, false, false, false},   // 4
          {false, false, false, false, false, false, true},   // 5
          {false, false, false, true, false, false, false},   // 6
      };
  
      if (dir != CENTER_DIGIT) {
          assert(baseCell != originBaseCell);
          assert(!(originOnPent && indexOnPent));
  
          int pentagonRotations = 0;
          int directionRotations = 0;
  
          if (originOnPent) {
              int originLeadingDigit = _h3LeadingNonZeroDigit(origin);
  
              if ((isResClassIII(res) &&
                   FAILED_DIRECTIONS_III[originLeadingDigit][dir]) ||
                  (!isResClassIII(res) &&
                   FAILED_DIRECTIONS_II[originLeadingDigit][dir])) {
                  // TODO this part of the pentagon might not be unfolded
                  // correctly.
                  return 3;
              }
  
              directionRotations = PENTAGON_ROTATIONS[originLeadingDigit][dir];
              pentagonRotations = directionRotations;
          } else if (indexOnPent) {
              int indexLeadingDigit = _h3LeadingNonZeroDigit(h3);
  
              if ((isResClassIII(res) &&
                   FAILED_DIRECTIONS_III[indexLeadingDigit][revDir]) ||
                  (!isResClassIII(res) &&
                   FAILED_DIRECTIONS_II[indexLeadingDigit][revDir])) {
                  // TODO this part of the pentagon might not be unfolded
                  // correctly.
                  return 4;
              }
  
              pentagonRotations = PENTAGON_ROTATIONS[revDir][indexLeadingDigit];
          }
  
          assert(pentagonRotations >= 0);
          assert(directionRotations >= 0);
  
          for (int i = 0; i < pentagonRotations; i++) {
              _ijkRotate60cw(&indexFijk.coord);
          }
  
          CoordIJK offset = {0};
          _neighbor(&offset, dir);
          // Scale offset based on resolution
          for (int r = res - 1; r >= 0; r--) {
              if (isResClassIII(r + 1)) {
                  // rotate ccw
                  _downAp7(&offset);
              } else {
                  // rotate cw
                  _downAp7r(&offset);
              }
          }
  
          for (int i = 0; i < directionRotations; i++) {
              _ijkRotate60cw(&offset);
          }
  
          // Perform necessary translation
          _ijkAdd(&indexFijk.coord, &offset, &indexFijk.coord);
          _ijkNormalize(&indexFijk.coord);
      } else if (originOnPent && indexOnPent) {
          // If the origin and index are on pentagon, and we checked that the base
          // cells are the same or neighboring, then they must be the same base
          // cell.
          assert(baseCell == originBaseCell);
  
          int originLeadingDigit = _h3LeadingNonZeroDigit(origin);
          int indexLeadingDigit = _h3LeadingNonZeroDigit(h3);
  
          if (FAILED_DIRECTIONS_III[originLeadingDigit][indexLeadingDigit] ||
              FAILED_DIRECTIONS_II[originLeadingDigit][indexLeadingDigit]) {
              // TODO this part of the pentagon might not be unfolded
              // correctly.
              return 5;
          }
  
          int withinPentagonRotations =
              PENTAGON_ROTATIONS[originLeadingDigit][indexLeadingDigit];
  
          for (int i = 0; i < withinPentagonRotations; i++) {
              _ijkRotate60cw(&indexFijk.coord);
          }
      }
  
      *out = indexFijk.coord;
      return 0;
  }
  
  /**
   * Produces the grid distance between the two indexes.
   *
   * This function may fail to find the distance between two indexes, for
   * example if they are very far apart. It may also fail when finding
   * distances for indexes on opposite sides of a pentagon.
   *
   * @param origin Index to find the distance from.
   * @param index Index to find the distance to.
   * @return The distance, or a negative number if the library could not
   * compute the distance.
   */
  int H3_EXPORT(h3Distance)(H3Index origin, H3Index h3) {
      CoordIJK originIjk, h3Ijk;
      if (h3ToIjk(origin, origin, &originIjk)) {
          // Only possible if origin is invalid, for example if it's a
          // unidirectional edge.
          return -1;
      }
      if (h3ToIjk(origin, h3, &h3Ijk)) {
          return -1;
      }
  
      return ijkDistance(&originIjk, &h3Ijk);
  }
  