text: /*
   * Copyright 2017-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  h3UniEdge.c
   * @brief H3UniEdge functions for manipulating unidirectional edge indexes.
   */
  
  #include <inttypes.h>
  #include <stdbool.h>
  
  #include "algos.h"
  #include "constants.h"
  #include "coordijk.h"
  #include "geoCoord.h"
  #include "h3Index.h"
  
  /**
   * Returns whether or not the provided H3Indexes are neighbors.
   * @param origin The origin H3 index.
   * @param destination The destination H3 index.
   * @return 1 if the indexes are neighbors, 0 otherwise;
   */
  int H3_EXPORT(h3IndexesAreNeighbors)(H3Index origin, H3Index destination) {
      // Make sure they're hexagon indexes
      if (H3_GET_MODE(origin) != H3_HEXAGON_MODE ||
          H3_GET_MODE(destination) != H3_HEXAGON_MODE) {
          return 0;
      }
  
      // Hexagons cannot be neighbors with themselves
      if (origin == destination) {
          return 0;
      }
  
      // Only hexagons in the same resolution can be neighbors
      if (H3_GET_RESOLUTION(origin) != H3_GET_RESOLUTION(destination)) {
          return 0;
      }
  
      // H3 Indexes that share the same parent are very likely to be neighbors
      // Child 0 is neighbor with all of its parent's 'offspring', the other
      // children are neighbors with 3 of the 7 children. So a simple comparison
      // of origin and destination parents and then a lookup table of the children
      // is a super-cheap way to possibly determine they are neighbors.
      int parentRes = H3_GET_RESOLUTION(origin) - 1;
      if (parentRes > 0 && (H3_EXPORT(h3ToParent)(origin, parentRes) ==
                            H3_EXPORT(h3ToParent)(destination, parentRes))) {
          Direction originResDigit = H3_GET_INDEX_DIGIT(origin, parentRes + 1);
          Direction destinationResDigit =
              H3_GET_INDEX_DIGIT(destination, parentRes + 1);
          if (originResDigit == CENTER_DIGIT ||
              destinationResDigit == CENTER_DIGIT) {
              return 1;
          }
          // These sets are the relevant neighbors in the clockwise
          // and counter-clockwise
          const Direction neighborSetClockwise[] = {
              CENTER_DIGIT,  JK_AXES_DIGIT, IJ_AXES_DIGIT, J_AXES_DIGIT,
              IK_AXES_DIGIT, K_AXES_DIGIT,  I_AXES_DIGIT};
          const Direction neighborSetCounterclockwise[] = {
              CENTER_DIGIT,  IK_AXES_DIGIT, JK_AXES_DIGIT, K_AXES_DIGIT,
              IJ_AXES_DIGIT, I_AXES_DIGIT,  J_AXES_DIGIT};
          if (neighborSetClockwise[originResDigit] == destinationResDigit ||
              neighborSetCounterclockwise[originResDigit] ==
                  destinationResDigit) {
              return 1;
          }
      }
  
      // Otherwise, we have to determine the neighbor relationship the "hard" way.
      H3Index neighborRing[7] = {0};
      H3_EXPORT(kRing)(origin, 1, neighborRing);
      for (int i = 0; i < 7; i++) {
          if (neighborRing[i] == destination) {
              return 1;
          }
      }
  
      // Made it here, they definitely aren't neighbors
      return 0;
  }
  
  /**
   * Returns a unidirectional edge H3 index based on the provided origin and
   * destination
   * @param origin The origin H3 hexagon index
   * @param destination The destination H3 hexagon index
   * @return The unidirectional edge H3Index, or 0 on failure.
   */
  H3Index H3_EXPORT(getH3UnidirectionalEdge)(H3Index origin,
                                             H3Index destination) {
      // Short-circuit and return an invalid index value if they are not neighbors
      if (H3_EXPORT(h3IndexesAreNeighbors)(origin, destination) == 0) {
          return H3_INVALID_INDEX;
      }
  
      // Otherwise, determine the IJK direction from the origin to the destination
      H3Index output = origin;
      H3_SET_MODE(output, H3_UNIEDGE_MODE);
  
      // Checks each neighbor, in order, to determine which direction the
      // destination neighbor is located. Skips CENTER_DIGIT since that
      // would be this index.
      H3Index neighbor;
      for (Direction direction = K_AXES_DIGIT; direction < NUM_DIGITS;
           direction++) {
          int rotations = 0;
          neighbor = h3NeighborRotations(origin, direction, &rotations);
          if (neighbor == destination) {
              H3_SET_RESERVED_BITS(output, direction);
              return output;
          }
      }
  
      // This should be impossible, return an invalid H3Index in this case;
      return H3_INVALID_INDEX;  // LCOV_EXCL_LINE
  }
  
  /**
   * Returns the origin hexagon from the unidirectional edge H3Index
   * @param edge The edge H3 index
   * @return The origin H3 hexagon index
   */
  H3Index H3_EXPORT(getOriginH3IndexFromUnidirectionalEdge)(H3Index edge) {
      if (H3_GET_MODE(edge) != H3_UNIEDGE_MODE) {
          return H3_INVALID_INDEX;
      }
      H3Index origin = edge;
      H3_SET_MODE(origin, H3_HEXAGON_MODE);
      H3_SET_RESERVED_BITS(origin, 0);
      return origin;
  }
  
  /**
   * Returns the destination hexagon from the unidirectional edge H3Index
   * @param edge The edge H3 index
   * @return The destination H3 hexagon index
   */
  H3Index H3_EXPORT(getDestinationH3IndexFromUnidirectionalEdge)(H3Index edge) {
      if (H3_GET_MODE(edge) != H3_UNIEDGE_MODE) {
          return H3_INVALID_INDEX;
      }
      Direction direction = H3_GET_RESERVED_BITS(edge);
      int rotations = 0;
      H3Index destination = h3NeighborRotations(
          H3_EXPORT(getOriginH3IndexFromUnidirectionalEdge)(edge), direction,
          &rotations);
      return destination;
  }
  
  /**
   * Determines if the provided H3Index is a valid unidirectional edge index
   * @param edge The unidirectional edge H3Index
   * @return 1 if it is a unidirectional edge H3Index, otherwise 0.
   */
  int H3_EXPORT(h3UnidirectionalEdgeIsValid)(H3Index edge) {
      if (H3_GET_MODE(edge) != H3_UNIEDGE_MODE) {
          return 0;
      }
  
      Direction neighborDirection = H3_GET_RESERVED_BITS(edge);
      if (neighborDirection <= CENTER_DIGIT || neighborDirection >= NUM_DIGITS) {
          return 0;
      }
  
      H3Index origin = H3_EXPORT(getOriginH3IndexFromUnidirectionalEdge)(edge);
      if (H3_EXPORT(h3IsPentagon)(origin) && neighborDirection == K_AXES_DIGIT) {
          return 0;
      }
  
      return H3_EXPORT(h3IsValid)(origin);
  }
  
  /**
   * Returns the origin, destination pair of hexagon IDs for the given edge ID
   * @param edge The unidirectional edge H3Index
   * @param originDestination Pointer to memory to store origin and destination
   * IDs
   */
  void H3_EXPORT(getH3IndexesFromUnidirectionalEdge)(H3Index edge,
                                                     H3Index* originDestination) {
      originDestination[0] =
          H3_EXPORT(getOriginH3IndexFromUnidirectionalEdge)(edge);
      originDestination[1] =
          H3_EXPORT(getDestinationH3IndexFromUnidirectionalEdge)(edge);
  }
  
  /**
   * Provides all of the unidirectional edges from the current H3Index.
   * @param origin The origin hexagon H3Index to find edges for.
   * @param edges The memory to store all of the edges inside.
   */
  void H3_EXPORT(getH3UnidirectionalEdgesFromHexagon)(H3Index origin,
                                                      H3Index* edges) {
      // Determine if the origin is a pentagon and special treatment needed.
      int isPentagon = H3_EXPORT(h3IsPentagon)(origin);
  
      // This is actually quite simple. Just modify the bits of the origin
      // slightly for each direction, except the 'k' direction in pentagons,
      // which is zeroed.
      for (int i = 0; i < 6; i++) {
          if (isPentagon && i == 0) {
              edges[i] = H3_INVALID_INDEX;
          } else {
              edges[i] = origin;
              H3_SET_MODE(edges[i], H3_UNIEDGE_MODE);
              H3_SET_RESERVED_BITS(edges[i], i + 1);
          }
      }
  }
  
  /**
   * Whether the given coordinate has a matching vertex in the given geo boundary.
   * @param  vertex   Coordinate to check
   * @param  boundary Geo boundary to look in
   * @return          Whether a match was found
   */
  static bool _hasMatchingVertex(const GeoCoord* vertex,
                                 const GeoBoundary* boundary) {
      for (int i = 0; i < boundary->numVerts; i++) {
          if (geoAlmostEqualThreshold(vertex, &boundary->verts[i], 0.000001)) {
              return true;
          }
      }
      return false;
  }
  
  /**
   * Provides the coordinates defining the unidirectional edge.
   * @param edge The unidirectional edge H3Index
   * @param gb The geoboundary object to store the edge coordinates.
   */
  void H3_EXPORT(getH3UnidirectionalEdgeBoundary)(H3Index edge, GeoBoundary* gb) {
      // TODO: More efficient solution :)
      GeoBoundary origin = {0};
      GeoBoundary destination = {0};
      GeoCoord postponedVertex = {0,0};
      bool hasPostponedVertex = false;
  
      H3_EXPORT(h3ToGeoBoundary)
      (H3_EXPORT(getOriginH3IndexFromUnidirectionalEdge)(edge), &origin);
      H3_EXPORT(h3ToGeoBoundary)
      (H3_EXPORT(getDestinationH3IndexFromUnidirectionalEdge)(edge),
       &destination);
  
      int k = 0;
      for (int i = 0; i < origin.numVerts; i++) {
          if (_hasMatchingVertex(&origin.verts[i], &destination)) {
              // If we are on vertex 0, we need to handle the case where it's the
              // end of the edge, not the beginning.
              if (i == 0 &&
                  !_hasMatchingVertex(&origin.verts[i + 1], &destination)) {
                  postponedVertex = origin.verts[i];
                  hasPostponedVertex = true;
              } else {
                  gb->verts[k] = origin.verts[i];
                  k++;
              }
          }
      }
      // If we postponed adding the last vertex, add it now
      if (hasPostponedVertex) {
          gb->verts[k] = postponedVertex;
          k++;
      }
      gb->numVerts = k;
  }
  