h3Index.c

/*
 * Copyright 2016-2021, 2024 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 <inttypes.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

#include "alloc.h"
#include "baseCells.h"
#include "faceijk.h"
#include "h3Assert.h"
#include "iterators.h"
#include "mathExtensions.h"

/** @var H3ErrorDescriptions
 *  @brief An array of strings describing each of the H3ErrorCodes enum values
 */
static char *H3ErrorDescriptions[] = {
    /* E_SUCCESS */ "Success",
    /* E_FAILED */
    "The operation failed but a more specific error is not available",
    /* E_DOMAIN */ "Argument was outside of acceptable range",
    /* E_LATLNG_DOMAIN */
    "Latitude or longitude arguments were outside of acceptable range",
    /* E_RES_DOMAIN */ "Resolution argument was outside of acceptable range",
    /* E_CELL_INVALID */ "Cell argument was not valid",
    /* E_DIR_EDGE_INVALID */ "Directed edge argument was not valid",
    /* E_UNDIR_EDGE_INVALID */ "Undirected edge argument was not valid",
    /* E_VERTEX_INVALID */ "Vertex argument was not valid",
    /* E_PENTAGON */ "Pentagon distortion was encountered",
    /* E_DUPLICATE_INPUT */ "Duplicate input",
    /* E_NOT_NEIGHBORS */ "Cell arguments were not neighbors",
    /* E_RES_MISMATCH */ "Cell arguments had incompatible resolutions",
    /* E_MEMORY_ALLOC */ "Memory allocation failed",
    /* E_MEMORY_BOUNDS */ "Bounds of provided memory were insufficient",
    /* E_OPTION_INVALID */ "Mode or flags argument was not valid"};

/**
 * Returns the string describing the H3Error. This string is internally
 * allocated and should not be `free`d.
 * @param err The H3 error.
 * @return The string describing the H3Error
 */
const char *H3_EXPORT(describeH3Error)(H3Error err) {
    if (err >= 0 && err <= 15) {  // TODO: Better way to bounds check here?
        return H3ErrorDescriptions[err];
    } else {
        return "Invalid error code";
    }
}

/**
 * Returns the H3 resolution of an H3 index.
 * @param h The H3 index.
 * @return The resolution of the H3 index argument.
 */
int H3_EXPORT(getResolution)(H3Index h) { return H3_GET_RESOLUTION(h); }

/**
 * Returns the H3 base cell "number" of an H3 cell (hexagon or pentagon).
 *
 * Note: Technically works on H3 edges, but will return base cell of the
 * origin cell.
 *
 * @param h The H3 cell.
 * @return The base cell "number" of the H3 cell argument.
 */
int H3_EXPORT(getBaseCellNumber)(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 H3_NULL if
 * invalid.
 */
H3Error H3_EXPORT(stringToH3)(const char *str, H3Index *out) {
    H3Index h = H3_NULL;
    // If failed, h will be unmodified and we should return H3_NULL anyways.
    int read = sscanf(str, "%" PRIx64, &h);
    if (read != 1) {
        return E_FAILED;
    }
    *out = h;
    return E_SUCCESS;
}

/**
 * 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`
 */
H3Error 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 E_MEMORY_BOUNDS;
    }
    sprintf(str, "%" PRIx64, h);
    return E_SUCCESS;
}

/**
 * Returns whether or not an H3 index is a valid cell (hexagon or pentagon).
 * @param h The H3 index to validate.
 * @return 1 if the H3 index if valid, and 0 if it is not.
 */
int H3_EXPORT(isValidCell)(H3Index h) {
    if (H3_GET_HIGH_BIT(h) != 0) return 0;

    if (H3_GET_MODE(h) != H3_CELL_MODE) return 0;

    if (H3_GET_RESERVED_BITS(h) != 0) return 0;

    int baseCell = H3_GET_BASE_CELL(h);
    if (NEVER(baseCell < 0) || baseCell >= NUM_BASE_CELLS) {
        // Base cells less than zero can not be represented in an index
        return 0;
    }

    int res = H3_GET_RESOLUTION(h);
    if (NEVER(res < 0 || res > MAX_H3_RES)) {
        // Resolutions less than zero can not be represented in an index
        return 0;
    }

    bool foundFirstNonZeroDigit = false;
    for (int r = 1; r <= res; r++) {
        Direction digit = H3_GET_INDEX_DIGIT(h, r);

        if (!foundFirstNonZeroDigit && digit != CENTER_DIGIT) {
            foundFirstNonZeroDigit = true;
            if (_isBaseCellPentagon(baseCell) && digit == K_AXES_DIGIT) {
                return 0;
            }
        }

        if (NEVER(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_CELL_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;
}

/**
 * cellToParent 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 H3_NULL if you actually asked for a child
 */
H3Error H3_EXPORT(cellToParent)(H3Index h, int parentRes, H3Index *out) {
    int childRes = H3_GET_RESOLUTION(h);
    if (parentRes < 0 || parentRes > MAX_H3_RES) {
        return E_RES_DOMAIN;
    } else if (parentRes > childRes) {
        return E_RES_MISMATCH;
    } else if (parentRes == childRes) {
        *out = h;
        return E_SUCCESS;
    }
    H3Index parentH = H3_SET_RESOLUTION(h, parentRes);
    for (int i = parentRes + 1; i <= childRes; i++) {
        H3_SET_INDEX_DIGIT(parentH, i, H3_DIGIT_MASK);
    }
    *out = parentH;
    return E_SUCCESS;
}

/**
 * Determines whether one resolution is a valid child resolution for a cell.
 * Each resolution is considered a valid child resolution of itself.
 *
 * @param h         h3Index  parent cell
 * @param childRes  int      resolution of the child
 *
 * @return The validity of the child resolution
 */
static bool _hasChildAtRes(H3Index h, int childRes) {
    int parentRes = H3_GET_RESOLUTION(h);
    if (childRes < parentRes || childRes > MAX_H3_RES) {
        return false;
    }
    return true;
}

/**
 * cellToChildrenSize returns the exact number of children for a cell at a
 * given child resolution.
 *
 * @param h         H3Index to find the number of children of
 * @param childRes  The child resolution you're interested in
 *
 * @return int      Exact number of children (handles hexagons and pentagons
 *                  correctly)
 */
H3Error H3_EXPORT(cellToChildrenSize)(H3Index h, int childRes, int64_t *out) {
    if (!_hasChildAtRes(h, childRes)) return E_RES_DOMAIN;

    int n = childRes - H3_GET_RESOLUTION(h);

    if (H3_EXPORT(isPentagon)(h)) {
        *out = 1 + 5 * (_ipow(7, n) - 1) / 6;
    } else {
        *out = _ipow(7, n);
    }
    return E_SUCCESS;
}

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

/**
 * cellToChildren 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 cellToChildrenSize 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
 */
H3Error H3_EXPORT(cellToChildren)(H3Index h, int childRes, H3Index *children) {
    int64_t i = 0;
    for (IterCellsChildren iter = iterInitParent(h, childRes); iter.h;
         iterStepChild(&iter)) {
        children[i] = iter.h;
        i++;
    }
    return E_SUCCESS;
}

/**
 * Zero out index digits from start to end, inclusive.
 * No-op if start > end.
 */
H3Index _zeroIndexDigits(H3Index h, int start, int end) {
    if (start > end) return h;

    H3Index m = 0;

    m = ~m;
    m <<= H3_PER_DIGIT_OFFSET * (end - start + 1);
    m = ~m;
    m <<= H3_PER_DIGIT_OFFSET * (MAX_H3_RES - end);
    m = ~m;

    return h & m;
}

/**
 * cellToCenterChild produces the center child index for a given H3 index at
 * the specified resolution
 *
 * @param h H3Index to find center child of
 * @param childRes The resolution to switch to
 * @param child H3Index of the center child
 * @return 0 (E_SUCCESS) on success
 */
H3Error H3_EXPORT(cellToCenterChild)(H3Index h, int childRes, H3Index *child) {
    if (!_hasChildAtRes(h, childRes)) return E_RES_DOMAIN;

    h = _zeroIndexDigits(h, H3_GET_RESOLUTION(h) + 1, childRes);
    H3_SET_RESOLUTION(h, childRes);
    *child = h;
    return E_SUCCESS;
}

/**
 * compactCells 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
 */
H3Error H3_EXPORT(compactCells)(const H3Index *h3Set, H3Index *compactedSet,
                                const int64_t numHexes) {
    if (numHexes == 0) {
        return E_SUCCESS;
    }
    int res = H3_GET_RESOLUTION(h3Set[0]);
    if (res == 0) {
        // No compaction possible, just copy the set to output
        for (int64_t i = 0; i < numHexes; i++) {
            compactedSet[i] = h3Set[i];
        }
        return E_SUCCESS;
    }
    H3Index *remainingHexes = H3_MEMORY(malloc)(numHexes * sizeof(H3Index));
    if (!remainingHexes) {
        return E_MEMORY_ALLOC;
    }
    memcpy(remainingHexes, h3Set, numHexes * sizeof(H3Index));
    H3Index *hashSetArray = H3_MEMORY(calloc)(numHexes, sizeof(H3Index));
    if (!hashSetArray) {
        H3_MEMORY(free)(remainingHexes);
        return E_MEMORY_ALLOC;
    }
    H3Index *compactedSetOffset = compactedSet;
    int64_t numRemainingHexes = numHexes;
    while (numRemainingHexes) {
        res = H3_GET_RESOLUTION(remainingHexes[0]);
        int parentRes = res - 1;

        // If parentRes is less than zero, we've compacted all the way up to the
        // base cells. Time to process the remaining cells.
        if (parentRes >= 0) {
            // 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 (int64_t i = 0; i < numRemainingHexes; i++) {
                H3Index currIndex = remainingHexes[i];
                // TODO: This case is coverable (reachable by fuzzer)
                if (currIndex != 0) {
                    // If the reserved bits were set by the caller, the
                    // algorithm below may encounter undefined behavior
                    // because it expects to have set the reserved bits
                    // itself.
                    if (H3_GET_RESERVED_BITS(currIndex) != 0) {
                        H3_MEMORY(free)(remainingHexes);
                        H3_MEMORY(free)(hashSetArray);
                        return E_CELL_INVALID;
                    }

                    H3Index parent;
                    H3Error parentError =
                        H3_EXPORT(cellToParent)(currIndex, parentRes, &parent);
                    // Should never be reachable as a result of the compact
                    // algorithm. Can happen if cellToParent errors e.g.
                    // because of incompatible resolutions.
                    if (parentError) {
                        H3_MEMORY(free)(remainingHexes);
                        H3_MEMORY(free)(hashSetArray);
                        return parentError;
                    }
                    // Modulus hash the parent into the temp array
                    int64_t loc = (int64_t)(parent % numRemainingHexes);
                    int64_t loopCount = 0;
                    while (hashSetArray[loc] != 0) {
                        if (NEVER(loopCount > numRemainingHexes)) {
                            // This case should not be possible because at
                            // most one index is placed into hashSetArray
                            // per numRemainingHexes.
                            H3_MEMORY(free)(remainingHexes);
                            H3_MEMORY(free)(hashSetArray);
                            return E_FAILED;
                        }
                        H3Index tempIndex =
                            hashSetArray[loc] & H3_RESERVED_MASK_NEGATIVE;
                        if (tempIndex == parent) {
                            int count =
                                H3_GET_RESERVED_BITS(hashSetArray[loc]) + 1;
                            int limitCount = 7;
                            if (H3_EXPORT(isPentagon)(
                                    tempIndex & H3_RESERVED_MASK_NEGATIVE)) {
                                limitCount--;
                            }
                            // One is added to count for this check to match
                            // one being added to count later in this
                            // function when checking for all children being
                            // present.
                            if (count + 1 > limitCount) {
                                // Only possible on duplicate input
                                H3_MEMORY(free)(remainingHexes);
                                H3_MEMORY(free)(hashSetArray);
                                return E_DUPLICATE_INPUT;
                            }
                            H3_SET_RESERVED_BITS(parent, count);
                            hashSetArray[loc] = H3_NULL;
                        } 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
        int64_t compactableCount = 0;
        int64_t maxCompactableCount =
            numRemainingHexes / 6;  // Somehow all pentagons; conservative
        if (maxCompactableCount == 0) {
            memcpy(compactedSetOffset, remainingHexes,
                   numRemainingHexes * sizeof(remainingHexes[0]));
            break;
        }
        H3Index *compactableHexes =
            H3_MEMORY(calloc)(maxCompactableCount, sizeof(H3Index));
        if (!compactableHexes) {
            H3_MEMORY(free)(remainingHexes);
            H3_MEMORY(free)(hashSetArray);
            return E_MEMORY_ALLOC;
        }
        for (int64_t 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(isPentagon)(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
        int64_t uncompactableCount = 0;
        for (int64_t i = 0; i < numRemainingHexes; i++) {
            H3Index currIndex = remainingHexes[i];
            // TODO: This case is coverable (reachable by fuzzer)
            if (currIndex != H3_NULL) {
                bool isUncompactable = true;
                // Resolution 0 cells always uncompactable, and trying to take
                // the res -1 parent of a cell is invalid.
                if (parentRes >= 0) {
                    H3Index parent;
                    H3Error parentError =
                        H3_EXPORT(cellToParent)(currIndex, parentRes, &parent);
                    if (NEVER(parentError)) {
                        H3_MEMORY(free)(compactableHexes);
                        H3_MEMORY(free)(remainingHexes);
                        H3_MEMORY(free)(hashSetArray);
                        return parentError;
                    }
                    // Modulus hash the parent into the temp array
                    // to determine if this index was included in
                    // the compactableHexes array
                    int64_t loc = (int64_t)(parent % numRemainingHexes);
                    int64_t loopCount = 0;
                    do {
                        if (NEVER(loopCount > numRemainingHexes)) {
                            // This case should not be possible because at most
                            // one index is placed into hashSetArray per input
                            // hexagon.
                            H3_MEMORY(free)(compactableHexes);
                            H3_MEMORY(free)(remainingHexes);
                            H3_MEMORY(free)(hashSetArray);
                            return E_FAILED;
                        }
                        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;
        H3_MEMORY(free)(compactableHexes);
    }
    H3_MEMORY(free)(remainingHexes);
    H3_MEMORY(free)(hashSetArray);
    return E_SUCCESS;
}

/**
 * uncompactCells takes a compressed set of cells and expands back to the
 * original set of cells.
 *
 * Skips elements that are H3_NULL (i.e., 0).
 *
 * @param   compactSet  Set of compacted cells
 * @param   numCompact  The number of cells in the input compacted set
 * @param   outSet      Output array for decompressed cells (preallocated)
 * @param   numOut      The size of the output array to bound check against
 * @param   res         The H3 resolution to decompress to
 * @return              An error code if output array is too small or any cell
 *                      is smaller than the output resolution.
 */
H3Error H3_EXPORT(uncompactCells)(const H3Index *compactedSet,
                                  const int64_t numCompacted, H3Index *outSet,
                                  const int64_t numOut, const int res) {
    int64_t i = 0;

    for (int64_t j = 0; j < numCompacted; j++) {
        if (!_hasChildAtRes(compactedSet[j], res)) return E_RES_MISMATCH;

        for (IterCellsChildren iter = iterInitParent(compactedSet[j], res);
             iter.h; i++, iterStepChild(&iter)) {
            if (i >= numOut) return E_MEMORY_BOUNDS;  // went too far; abort!
            outSet[i] = iter.h;
        }
    }
    return E_SUCCESS;
}

/**
 * uncompactCellsSize takes a compacted set of hexagons and provides
 * the exact 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
 * @param   out           The number of hexagons to allocate memory for
 * @returns E_SUCCESS on success, or another value on error
 */
H3Error H3_EXPORT(uncompactCellsSize)(const H3Index *compactedSet,
                                      const int64_t numCompacted, const int res,
                                      int64_t *out) {
    int64_t numOut = 0;
    for (int64_t i = 0; i < numCompacted; i++) {
        if (compactedSet[i] == H3_NULL) continue;

        int64_t childrenSize;
        H3Error childrenError =
            H3_EXPORT(cellToChildrenSize)(compactedSet[i], res, &childrenSize);
        if (childrenError) {
            // The parent res does not contain `res`.
            return E_RES_MISMATCH;
        }
        numOut += childrenSize;
    }
    *out = numOut;
    return E_SUCCESS;
}

/**
 * isResClassIII 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(isResClassIII)(H3Index h) { return H3_GET_RESOLUTION(h) % 2; }

/**
 * isPentagon 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(isPentagon)(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 H3_NULL on failure).
 */
H3Index _faceIjkToH3(const FaceIJK *fijk, int res) {
    // initialize the index
    H3Index h = H3_INIT;
    H3_SET_MODE(h, H3_CELL_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_NULL;
        }

        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 indexing
    // digits
    CoordIJK *ijk = &fijkBC.coord;
    for (int r = res - 1; r >= 0; r--) {
        CoordIJK lastIJK = *ijk;
        CoordIJK lastCenter;
        if (isResolutionClassIII(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_NULL;
    }

    // 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.
 * @param out The encoded H3Index.
 * @returns E_SUCCESS (0) on success, another value otherwise
 */
H3Error H3_EXPORT(latLngToCell)(const LatLng *g, int res, H3Index *out) {
    if (res < 0 || res > MAX_H3_RES) {
        return E_RES_DOMAIN;
    }
    if (!isfinite(g->lat) || !isfinite(g->lng)) {
        return E_LATLNG_DOMAIN;
    }

    FaceIJK fijk;
    _geoToFaceIjk(g, res, &fijk);
    *out = _faceIjkToH3(&fijk, res);
    if (ALWAYS(*out)) {
        return E_SUCCESS;
    } else {
        return E_FAILED;
    }
}

/**
 * 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 (isResolutionClassIII(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.
 */
H3Error _h3ToFaceIjk(H3Index h, FaceIJK *fijk) {
    int baseCell = H3_GET_BASE_CELL(h);
    if (NEVER(baseCell < 0) || baseCell >= NUM_BASE_CELLS) {
        // Base cells less than zero can not be represented in an index
        // To prevent reading uninitialized memory, we zero the output.
        fijk->face = 0;
        fijk->coord.i = fijk->coord.j = fijk->coord.k = 0;
        return E_CELL_INVALID;
    }
    // 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 E_SUCCESS;  // 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 (isResolutionClassIII(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) != NO_OVERAGE) {
        // if the base cell is a pentagon we have the potential for secondary
        // overages
        if (_isBaseCellPentagon(baseCell)) {
            while (_adjustOverageClassII(fijk, res, 0, 0) != NO_OVERAGE)
                continue;
        }

        if (res != H3_GET_RESOLUTION(h)) _upAp7r(&fijk->coord);
    } else if (res != H3_GET_RESOLUTION(h)) {
        fijk->coord = origIJK;
    }
    return E_SUCCESS;
}

/**
 * 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.
 */
H3Error H3_EXPORT(cellToLatLng)(H3Index h3, LatLng *g) {
    FaceIJK fijk;
    H3Error e = _h3ToFaceIjk(h3, &fijk);
    if (e) {
        return e;
    }
    _faceIjkToGeo(&fijk, H3_GET_RESOLUTION(h3), g);
    return E_SUCCESS;
}

/**
 * Determines the cell boundary in spherical coordinates for an H3 index.
 *
 * @param h3 The H3 index.
 * @param cb The boundary of the H3 cell in spherical coordinates.
 */
H3Error H3_EXPORT(cellToBoundary)(H3Index h3, CellBoundary *cb) {
    FaceIJK fijk;
    H3Error e = _h3ToFaceIjk(h3, &fijk);
    if (e) {
        return e;
    }
    if (H3_EXPORT(isPentagon)(h3)) {
        _faceIjkPentToCellBoundary(&fijk, H3_GET_RESOLUTION(h3), 0,
                                   NUM_PENT_VERTS, cb);
    } else {
        _faceIjkToCellBoundary(&fijk, H3_GET_RESOLUTION(h3), 0, NUM_HEX_VERTS,
                               cb);
    }
    return E_SUCCESS;
}

/**
 * Returns the max number of possible icosahedron faces an H3 index
 * may intersect.
 *
 * @return int count of faces
 */
H3Error H3_EXPORT(maxFaceCount)(H3Index h3, int *out) {
    // a pentagon always intersects 5 faces, a hexagon never intersects more
    // than 2 (but may only intersect 1)
    *out = H3_EXPORT(isPentagon)(h3) ? 5 : 2;
    return E_SUCCESS;
}

/**
 * Find all icosahedron faces intersected by a given H3 index, represented
 * as integers from 0-19. The array is sparse; since 0 is a valid value,
 * invalid array values are represented as -1. It is the responsibility of
 * the caller to filter out invalid values.
 *
 * @param h3 The H3 index
 * @param out Output array. Must be of size maxFaceCount(h3).
 */
H3Error H3_EXPORT(getIcosahedronFaces)(H3Index h3, int *out) {
    int res = H3_GET_RESOLUTION(h3);
    int isPent = H3_EXPORT(isPentagon)(h3);

    // We can't use the vertex-based approach here for class II pentagons,
    // because all their vertices are on the icosahedron edges. Their
    // direct child pentagons cross the same faces, so use those instead.
    if (isPent && !isResolutionClassIII(res)) {
        // Note that this would not work for res 15, but this is only run on
        // Class II pentagons, it should never be invoked for a res 15 index.
        H3Index childPentagon = makeDirectChild(h3, 0);
        return H3_EXPORT(getIcosahedronFaces)(childPentagon, out);
    }

    // convert to FaceIJK
    FaceIJK fijk;
    H3Error err = _h3ToFaceIjk(h3, &fijk);
    if (err) {
        return err;
    }

    // Get all vertices as FaceIJK addresses. For simplicity, always
    // initialize the array with 6 verts, ignoring the last one for pentagons
    FaceIJK fijkVerts[NUM_HEX_VERTS];
    int vertexCount;

    if (isPent) {
        vertexCount = NUM_PENT_VERTS;
        _faceIjkPentToVerts(&fijk, &res, fijkVerts);
    } else {
        vertexCount = NUM_HEX_VERTS;
        _faceIjkToVerts(&fijk, &res, fijkVerts);
    }

    // We may not use all of the slots in the output array,
    // so fill with invalid values to indicate unused slots
    int faceCount;
    H3Error maxFaceCountError = H3_EXPORT(maxFaceCount)(h3, &faceCount);
    if (NEVER(maxFaceCountError != E_SUCCESS)) {
        return maxFaceCountError;
    }
    for (int i = 0; i < faceCount; i++) {
        out[i] = INVALID_FACE;
    }

    // add each vertex face, using the output array as a hash set
    for (int i = 0; i < vertexCount; i++) {
        FaceIJK *vert = &fijkVerts[i];

        // Adjust overage, determining whether this vertex is
        // on another face
        if (isPent) {
            _adjustPentVertOverage(vert, res);
        } else {
            _adjustOverageClassII(vert, res, 0, 1);
        }

        // Save the face to the output array
        int face = vert->face;
        int pos = 0;
        // Find the first empty output position, or the first position
        // matching the current face
        while (out[pos] != INVALID_FACE && out[pos] != face) {
            pos++;
            if (pos >= faceCount) {
                // Mismatch between the heuristic used in maxFaceCount and
                // calculation here - indicates an invalid index.
                return E_FAILED;
            }
        }
        out[pos] = face;
    }
    return E_SUCCESS;
}

/**
 * pentagonCount returns the number of pentagons (same at any resolution)
 *
 * @return int count of pentagon indexes
 */
int H3_EXPORT(pentagonCount)(void) { return NUM_PENTAGONS; }

/**
 * Generates all pentagons at the specified resolution
 *
 * @param res The resolution to produce pentagons at.
 * @param out Output array. Must be of size pentagonCount().
 */
H3Error H3_EXPORT(getPentagons)(int res, H3Index *out) {
    if (res < 0 || res > MAX_H3_RES) {
        return E_RES_DOMAIN;
    }
    int i = 0;
    for (int bc = 0; bc < NUM_BASE_CELLS; bc++) {
        if (_isBaseCellPentagon(bc)) {
            H3Index pentagon;
            setH3Index(&pentagon, res, bc, 0);
            out[i++] = pentagon;
        }
    }
    return E_SUCCESS;
}

/**
 * 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 isResolutionClassIII(int res) { return res % 2; }

/**
 * Validate a child position in the context of a given parent, returning
 * an error if validation fails.
 */
static H3Error validateChildPos(int64_t childPos, H3Index parent,
                                int childRes) {
    int64_t maxChildCount;
    H3Error sizeError =
        H3_EXPORT(cellToChildrenSize)(parent, childRes, &maxChildCount);
    if (NEVER(sizeError)) {
        return sizeError;
    }
    if (childPos < 0 || childPos >= maxChildCount) {
        return E_DOMAIN;
    }
    return E_SUCCESS;
}

/**
 * Returns the position of the cell within an ordered list of all children of
 * the cell's parent at the specified resolution
 */
H3Error H3_EXPORT(cellToChildPos)(H3Index child, int parentRes, int64_t *out) {
    int childRes = H3_GET_RESOLUTION(child);
    // Get the parent at res. This will catch any resolution errors
    H3Index originalParent;
    H3Error parentError =
        H3_EXPORT(cellToParent(child, parentRes, &originalParent));
    if (parentError) {
        return parentError;
    }

    // Define the initial parent. Note that these variables are reassigned
    // within the loop.
    H3Index parent = originalParent;
    int parentIsPentagon = H3_EXPORT(isPentagon)(parent);

    // Walk up the resolution digits, incrementing the index
    *out = 0;
    if (parentIsPentagon) {
        // Pentagon logic. Pentagon parents skip the 1 digit, so the offsets are
        // different from hexagons
        for (int res = childRes; res > parentRes; res--) {
            H3Error parentError =
                H3_EXPORT(cellToParent(child, res - 1, &parent));
            if (NEVER(parentError)) {
                return parentError;
            }

            parentIsPentagon = H3_EXPORT(isPentagon)(parent);
            int rawDigit = H3_GET_INDEX_DIGIT(child, res);
            // Validate the digit before proceeding
            if (rawDigit == INVALID_DIGIT ||
                (parentIsPentagon && rawDigit == K_AXES_DIGIT)) {
                return E_CELL_INVALID;
            }
            int digit =
                parentIsPentagon && rawDigit > 0 ? rawDigit - 1 : rawDigit;
            if (digit != CENTER_DIGIT) {
                int64_t hexChildCount = _ipow(7, childRes - res);
                // The offset for the 0-digit slot depends on whether the
                // current index is the child of a pentagon. If so, the offset
                // is based on the count of pentagon children, otherwise,
                // hexagon children.
                *out += (parentIsPentagon
                             ?  // pentagon children. See the explanation
                                // for getNumCells in h3api.h.in
                             1 + (5 * (hexChildCount - 1)) / 6
                             :  // one hexagon's children
                             hexChildCount) +
                        // the other hexagon children
                        (digit - 1) * hexChildCount;
            }
        }
    } else {
        // Hexagon logic. Offsets are simple powers of 7
        for (int res = childRes; res > parentRes; res--) {
            int digit = H3_GET_INDEX_DIGIT(child, res);
            if (digit == INVALID_DIGIT) {
                return E_CELL_INVALID;
            }
            *out += digit * _ipow(7, childRes - res);
        }
    }

    if (NEVER(validateChildPos(*out, originalParent, childRes))) {
        // This is the result of an internal error, so return E_FAILED
        // instead of the validation error
        return E_FAILED;
    }

    return E_SUCCESS;
}

/**
 * Returns the child cell at a given position within an ordered list of all
 * children at the specified resolution */
H3Error H3_EXPORT(childPosToCell)(int64_t childPos, H3Index parent,
                                  int childRes, H3Index *child) {
    // Validate resolution
    if (childRes < 0 || childRes > MAX_H3_RES) {
        return E_RES_DOMAIN;
    }
    // Validate parent resolution
    int parentRes = H3_GET_RESOLUTION(parent);
    if (childRes < parentRes) {
        return E_RES_MISMATCH;
    }
    // Validate child pos
    H3Error childPosErr = validateChildPos(childPos, parent, childRes);
    if (childPosErr) {
        return childPosErr;
    }

    int resOffset = childRes - parentRes;

    *child = parent;
    int64_t idx = childPos;

    H3_SET_RESOLUTION(*child, childRes);

    if (H3_EXPORT(isPentagon)(parent)) {
        // Pentagon tile logic. Pentagon tiles skip the 1 digit, so the offsets
        // are different
        bool inPent = true;
        for (int res = 1; res <= resOffset; res++) {
            int64_t resWidth = _ipow(7, resOffset - res);
            if (inPent) {
                // While we are inside a parent pentagon, we need to check if
                // this cell is a pentagon, and if not, we need to offset its
                // digit to account for the skipped direction
                int64_t pentWidth = 1 + (5 * (resWidth - 1)) / 6;
                if (idx < pentWidth) {
                    H3_SET_INDEX_DIGIT(*child, parentRes + res, 0);
                } else {
                    idx -= pentWidth;
                    inPent = false;
                    H3_SET_INDEX_DIGIT(*child, parentRes + res,
                                       (idx / resWidth) + 2);
                    idx %= resWidth;
                }
            } else {
                // We're no longer inside a pentagon, continue as for hex
                H3_SET_INDEX_DIGIT(*child, parentRes + res, idx / resWidth);
                idx %= resWidth;
            }
        }
    } else {
        // Hexagon tile logic. Offsets are simple powers of 7
        for (int res = 1; res <= resOffset; res++) {
            int64_t resWidth = _ipow(7, resOffset - res);
            H3_SET_INDEX_DIGIT(*child, parentRes + res, idx / resWidth);
            idx %= resWidth;
        }
    }

    return E_SUCCESS;
}