distance_key Function

private pure function distance_key(x) result(key)

Map a non-negative real(dp) onto an integer(int64) heap key, preserving order exactly.

For x > 0 this reproduces the IEEE-754 bit pattern of x read as a 64-bit integer, which is monotonically increasing in x; x <= 0 maps to 0. It is computed from exponent and fraction rather than with transfer, deliberately: transfer between real and integer kinds behaves inconsistently on nvfortran and LFortran, while exponent/fraction are plain intrinsics everywhere. The arithmetic is exact - fraction(x)*2 - 1 is exact by Sterbenz and scaling it by 2**MANTISSA_BITS lands on an integer - so the mapping is injective and equal distances produce equal keys. That is what lets the heap’s FIFO tie-breaking decide ties between genuinely equal distances.

The largest key it can produce is (2*maxexponent - 2)*2**52 + 2**52 - 1, comfortably below huge(0_int64), so no encoding of a finite real(dp) overflows.

Arguments

Type IntentOptional Attributes Name
real(kind=dp), intent(in) :: x

Distance to encode; must be non-negative and finite

Return Value integer(kind=int64)

Order-preserving encoding of x


Called by

proc~~distance_key~~CalledByGraph proc~distance_key distance_key proc~a_star a_star proc~a_star->proc~distance_key proc~dijkstra dijkstra proc~dijkstra->proc~distance_key

Source Code

   pure function distance_key(x) result(key)
      !! Map a non-negative `real(dp)` onto an `integer(int64)` heap key,
      !! preserving order exactly.
      !!
      !! For `x > 0` this reproduces the IEEE-754 bit pattern of `x` read as a
      !! 64-bit integer, which is monotonically increasing in `x`; `x <= 0`
      !! maps to 0. It is computed from `exponent` and `fraction` rather than
      !! with `transfer`, deliberately: `transfer` between real and integer
      !! kinds behaves inconsistently on nvfortran and LFortran, while
      !! `exponent`/`fraction` are plain intrinsics everywhere. The arithmetic
      !! is exact - `fraction(x)*2 - 1` is exact by Sterbenz and scaling it by
      !! `2**MANTISSA_BITS` lands on an integer - so the mapping is injective
      !! and equal distances produce equal keys. That is what lets the heap's
      !! FIFO tie-breaking decide ties between genuinely equal distances.
      !!
      !! The largest key it can produce is `(2*maxexponent - 2)*2**52 +
      !! 2**52 - 1`, comfortably below `huge(0_int64)`, so no encoding of a
      !! finite `real(dp)` overflows.
      real(dp), intent(in) :: x
         !! Distance to encode; must be non-negative and finite
      integer(int64) :: key
         !! Order-preserving encoding of `x`

      if (x <= 0.0_dp) then
         key = 0_int64
         return
      end if

      key = (int(exponent(x), int64) + EXPONENT_BIAS)*MANTISSA_SCALE &
            + int((fraction(x)*2.0_dp - 1.0_dp)*real(MANTISSA_SCALE, dp), int64)
   end function distance_key