/*

 * Copyright 2020-2021 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  vertex.h

 *  @brief Functions for working with cell vertexes.

 */

#include "vertex.h"

#include <assert.h>

#include <stdbool.h>

#include "algos.h"

#include "baseCells.h"

#include "faceijk.h"

#include "h3Assert.h"

#include "h3Index.h"

#include "latLng.h"

#define DIRECTION_INDEX_OFFSET 2

/** @brief Table of direction-to-face mapping for each pentagon

 *

 * Note that faces are in directional order, starting at J_AXES_DIGIT.

 * This table is generated by the generatePentagonDirectionFaces script.

 */

static const PentagonDirectionFaces pentagonDirectionFaces[NUM_PENTAGONS] = {

    {4, {4, 0, 2, 1, 3}},       {14, {6, 11, 2, 7, 1}},

    {24, {5, 10, 1, 6, 0}},     {38, {7, 12, 3, 8, 2}},

    {49, {9, 14, 0, 5, 4}},     {58, {8, 13, 4, 9, 3}},

    {63, {11, 6, 15, 10, 16}},  {72, {12, 7, 16, 11, 17}},

    {83, {10, 5, 19, 14, 15}},  {97, {13, 8, 17, 12, 18}},

    {107, {14, 9, 18, 13, 19}}, {117, {15, 19, 17, 18, 16}},

};

/**

 * Get the number of CCW rotations of the cell's vertex numbers

 * compared to the directional layout of its neighbors.

 * @param out Number of CCW rotations for the cell

 */

static H3Error vertexRotations(H3Index cell, int *out) {

    // Get the face and other info for the origin

    FaceIJK fijk;

    H3Error err = _h3ToFaceIjk(cell, &fijk);

    if (err) {

        return err;

    }

    int baseCell = H3_EXPORT(getBaseCellNumber)(cell);

    int cellLeadingDigit = _h3LeadingNonZeroDigit(cell);

    // get the base cell face

    FaceIJK baseFijk;

    _baseCellToFaceIjk(baseCell, &baseFijk);

    int ccwRot60 = _baseCellToCCWrot60(baseCell, fijk.face);

    if (_isBaseCellPentagon(baseCell)) {

        // Find the appropriate direction-to-face mapping

        PentagonDirectionFaces dirFaces;

        // We never hit the end condition

        int p = 0;

        // Don't use a for loop here, for coverage reasons.

        while (ALWAYS(p < NUM_PENTAGONS)) {

            if (pentagonDirectionFaces[p].baseCell == baseCell) {

                dirFaces = pentagonDirectionFaces[p];

                break;

            }

            p++;

        }

        if (NEVER(p == NUM_PENTAGONS)) {

            return E_FAILED;

        }

        // additional CCW rotation for polar neighbors or IK neighbors

        if (fijk.face != baseFijk.face &&

            (_isBaseCellPolarPentagon(baseCell) ||

             fijk.face ==

                 dirFaces.faces[IK_AXES_DIGIT - DIRECTION_INDEX_OFFSET])) {

            ccwRot60 = (ccwRot60 + 1) % 6;

        }

        // Check whether the cell crosses a deleted pentagon subsequence

        if (cellLeadingDigit == JK_AXES_DIGIT &&

            fijk.face ==

                dirFaces.faces[IK_AXES_DIGIT - DIRECTION_INDEX_OFFSET]) {

            // Crosses from JK to IK: Rotate CW

            ccwRot60 = (ccwRot60 + 5) % 6;

        } else if (cellLeadingDigit == IK_AXES_DIGIT &&

                   fijk.face ==

                       dirFaces.faces[JK_AXES_DIGIT - DIRECTION_INDEX_OFFSET]) {

            // Crosses from IK to JK: Rotate CCW

            ccwRot60 = (ccwRot60 + 1) % 6;

        }

    }

    *out = ccwRot60;

    return E_SUCCESS;

}

/** @brief Hexagon direction to vertex number relationships (same face).

 *         Note that we don't use direction 0 (center).

 */

static const int directionToVertexNumHex[NUM_DIGITS] = {

    INVALID_DIGIT, 3, 1, 2, 5, 4, 0};

/** @brief Pentagon direction to vertex number relationships (same face).

 *         Note that we don't use directions 0 (center) or 1 (deleted K axis).

 */

static const int directionToVertexNumPent[NUM_DIGITS] = {

    INVALID_DIGIT, INVALID_DIGIT, 1, 2, 4, 3, 0};

/**

 * Get the first vertex number for a given direction. The neighbor in this

 * direction is located between this vertex number and the next number in

 * sequence.

 * @returns The number for the first topological vertex, or INVALID_VERTEX_NUM

 *          if the direction is not valid for this cell

 */

int vertexNumForDirection(const H3Index origin, const Direction direction) {

    int isPent = H3_EXPORT(isPentagon)(origin);

    // Check for invalid directions

    if (direction == CENTER_DIGIT || direction >= INVALID_DIGIT ||

        (isPent && direction == K_AXES_DIGIT))

        return INVALID_VERTEX_NUM;

    // Determine the vertex rotations for this cell

    int rotations;

    H3Error err = vertexRotations(origin, &rotations);

    if (err) {

        return INVALID_VERTEX_NUM;

    }

    // Find the appropriate vertex, rotating CCW if necessary

    if (isPent) {

        return (directionToVertexNumPent[direction] + NUM_PENT_VERTS -

                rotations) %

               NUM_PENT_VERTS;

    } else {

        return (directionToVertexNumHex[direction] + NUM_HEX_VERTS -

                rotations) %

               NUM_HEX_VERTS;

    }

}

/** @brief Vertex number to hexagon direction relationships (same face).

 */

static const Direction vertexNumToDirectionHex[NUM_HEX_VERTS] = {

    IJ_AXES_DIGIT, J_AXES_DIGIT,  JK_AXES_DIGIT,

    K_AXES_DIGIT,  IK_AXES_DIGIT, I_AXES_DIGIT};

/** @brief Vertex number to pentagon direction relationships (same face).

 */

static const Direction vertexNumToDirectionPent[NUM_PENT_VERTS] = {

    IJ_AXES_DIGIT, J_AXES_DIGIT, JK_AXES_DIGIT, IK_AXES_DIGIT, I_AXES_DIGIT};

/**

 * Get the direction for a given vertex number. This returns the direction for

 * the neighbor between the given vertex number and the next number in sequence.

 * @returns The direction for this vertex, or INVALID_DIGIT if the vertex

 * number is invalid.

 */

Direction directionForVertexNum(const H3Index origin, const int vertexNum) {

    int isPent = H3_EXPORT(isPentagon)(origin);

    // Check for invalid vertexes

    if (vertexNum < 0 ||

        vertexNum > (isPent ? NUM_PENT_VERTS : NUM_HEX_VERTS) - 1)

        return INVALID_DIGIT;

    // Determine the vertex rotations for this cell

    int rotations;

    H3Error err = vertexRotations(origin, &rotations);

    if (err) {

        return INVALID_DIGIT;

    }

    // Find the appropriate direction, rotating CW if necessary

    return isPent ? vertexNumToDirectionPent[(vertexNum + rotations) %

                                             NUM_PENT_VERTS]

                  : vertexNumToDirectionHex[(vertexNum + rotations) %

                                            NUM_HEX_VERTS];

}

/** @brief Directions in CCW order */

static const Direction DIRECTIONS[NUM_HEX_VERTS] = {

    J_AXES_DIGIT,  JK_AXES_DIGIT, K_AXES_DIGIT,

    IK_AXES_DIGIT, I_AXES_DIGIT,  IJ_AXES_DIGIT};

/** @brief Reverse direction from neighbor in each direction,

 *         given as an index into DIRECTIONS to facilitate rotation

 */

static const int revNeighborDirectionsHex[NUM_DIGITS] = {

    INVALID_DIGIT, 5, 3, 4, 1, 0, 2};

/**

 * Get a single vertex for a given cell, as an H3 index, or

 * H3_NULL if the vertex is invalid

 * @param cell    Cell to get the vertex for

 * @param vertexNum Number (index) of the vertex to calculate

 * @param out Output: The vertex index

 */

H3Error H3_EXPORT(cellToVertex)(H3Index cell, int vertexNum, H3Index *out) {

    int cellIsPentagon = H3_EXPORT(isPentagon)(cell);

    int cellNumVerts = cellIsPentagon ? NUM_PENT_VERTS : NUM_HEX_VERTS;

    int res = H3_GET_RESOLUTION(cell);

    // Check for invalid vertexes

    if (vertexNum < 0 || vertexNum > cellNumVerts - 1) return E_DOMAIN;

    // Default the owner and vertex number to the input cell

    H3Index owner = cell;

    int ownerVertexNum = vertexNum;

    // Determine the owner, looking at the three cells that share the vertex.

    // By convention, the owner is the cell with the lowest numerical index.

    // If the cell is the center child of its parent, it will always have

    // the lowest index of any neighbor, so we can skip determining the owner

    if (res == 0 || H3_GET_INDEX_DIGIT(cell, res) != CENTER_DIGIT) {

        // Get the left neighbor of the vertex, with its rotations

        Direction left = directionForVertexNum(cell, vertexNum);

        if (left == INVALID_DIGIT) return E_FAILED;

        int lRotations = 0;

        H3Index leftNeighbor;

        H3Error leftNeighborError =

            h3NeighborRotations(cell, left, &lRotations, &leftNeighbor);

        if (leftNeighborError) return leftNeighborError;

        // Set to owner if lowest index

        if (leftNeighbor < owner) owner = leftNeighbor;

        // As above, skip the right neighbor if the left is known lowest

        if (res == 0 || H3_GET_INDEX_DIGIT(leftNeighbor, res) != CENTER_DIGIT) {

            // Get the right neighbor of the vertex, with its rotations

            // Note that vertex - 1 is the right side, as vertex numbers are CCW

            Direction right = directionForVertexNum(

                cell, (vertexNum - 1 + cellNumVerts) % cellNumVerts);

            // This case should be unreachable; invalid verts fail earlier

            if (NEVER(right == INVALID_DIGIT)) return E_FAILED;

            int rRotations = 0;

            H3Index rightNeighbor;

            H3Error rightNeighborError =

                h3NeighborRotations(cell, right, &rRotations, &rightNeighbor);

            if (rightNeighborError) return rightNeighborError;

            // Set to owner if lowest index

            if (rightNeighbor < owner) {

                owner = rightNeighbor;

                Direction dir =

                    H3_EXPORT(isPentagon)(owner)

                        ? directionForNeighbor(owner, cell)

                        : DIRECTIONS[(revNeighborDirectionsHex[right] +

                                      rRotations) %

                                     NUM_HEX_VERTS];

                ownerVertexNum = vertexNumForDirection(owner, dir);

            }

        }

        // Determine the vertex number for the left neighbor

        if (owner == leftNeighbor) {

            int ownerIsPentagon = H3_EXPORT(isPentagon)(owner);

            Direction dir =

                ownerIsPentagon

                    ? directionForNeighbor(owner, cell)

                    : DIRECTIONS[(revNeighborDirectionsHex[left] + lRotations) %

                                 NUM_HEX_VERTS];

            // For the left neighbor, we need the second vertex of the

            // edge, which may involve looping around the vertex nums

            ownerVertexNum = vertexNumForDirection(owner, dir) + 1;

            if (ownerVertexNum == NUM_HEX_VERTS ||

                (ownerIsPentagon && ownerVertexNum == NUM_PENT_VERTS)) {

                ownerVertexNum = 0;

            }

        }

    }

    // Create the vertex index

    H3Index vertex = owner;

    H3_SET_MODE(vertex, H3_VERTEX_MODE);

    H3_SET_RESERVED_BITS(vertex, ownerVertexNum);

    *out = vertex;

    return E_SUCCESS;

}

/**

 * Get all vertexes for the given cell

 * @param cell      Cell to get the vertexes for

 * @param vertexes  Array to hold vertex output. Must have length >= 6.

 */

H3Error H3_EXPORT(cellToVertexes)(H3Index cell, H3Index *vertexes) {

    // Get all vertexes. If the cell is a pentagon, will fill the final slot

    // with H3_NULL.

    bool isPent = H3_EXPORT(isPentagon)(cell);

    for (int i = 0; i < NUM_HEX_VERTS; i++) {

        if (i == 5 && isPent) {

            vertexes[i] = H3_NULL;

        } else {

            H3Error cellError = H3_EXPORT(cellToVertex)(cell, i, &vertexes[i]);

            if (cellError) {

                return cellError;

            }

        }

    }

    return E_SUCCESS;

}

/**

 * Get the geocoordinates of an H3 vertex

 * @param vertex H3 index describing a vertex

 * @param coord  Output geo coordinate

 */

H3Error H3_EXPORT(vertexToLatLng)(H3Index vertex, LatLng *coord) {

    // Get the vertex number and owner from the vertex

    int vertexNum = H3_GET_RESERVED_BITS(vertex);

    H3Index owner = vertex;

    H3_SET_MODE(owner, H3_CELL_MODE);

    H3_SET_RESERVED_BITS(owner, 0);

    // Get the single vertex from the boundary

    CellBoundary gb;

    FaceIJK fijk;

    H3Error fijkError = _h3ToFaceIjk(owner, &fijk);

    if (fijkError) {

        return fijkError;

    }

    int res = H3_GET_RESOLUTION(owner);

    if (H3_EXPORT(isPentagon)(owner)) {

        _faceIjkPentToCellBoundary(&fijk, res, vertexNum, 1, &gb);

    } else {

        _faceIjkToCellBoundary(&fijk, res, vertexNum, 1, &gb);

    }

    // Copy from boundary to output coord

    *coord = gb.verts[0];

    return E_SUCCESS;

}

/**

 * Whether the input is a valid H3 vertex

 * @param  vertex H3 index possibly describing a vertex

 * @return        Whether the input is valid

 */

int H3_EXPORT(isValidVertex)(H3Index vertex) {

    if (H3_GET_MODE(vertex) != H3_VERTEX_MODE) {

        return 0;

    }

    int vertexNum = H3_GET_RESERVED_BITS(vertex);

    H3Index owner = vertex;

    H3_SET_MODE(owner, H3_CELL_MODE);

    H3_SET_RESERVED_BITS(owner, 0);

    if (!H3_EXPORT(isValidCell)(owner)) {

        return 0;

    }

    // The easiest way to ensure that the owner + vertex number is valid,

    // and that the vertex is canonical, is to recreate and compare.

    H3Index canonical;

    if (H3_EXPORT(cellToVertex)(owner, vertexNum, &canonical)) {

        return 0;

    }

    return vertex == canonical ? 1 : 0;

}