tem_PosOfId Function

  pure function tem_PosOfId(sTreeID, treeIDlist, lower, upper) result(IdPos)
    ! -------------------------------------------------------------------- !
    !> tree ID to search for
    integer(kind=long_k), intent(in)  :: sTreeID
    !> List to search in
    integer(kind=long_k), intent(in)  :: treeIDlist(:)
    !> lowerbound of search interval
    integer, intent(in), optional     :: lower
    !> upperbound of search interval
    integer, intent(in), optional     :: upper
    !> position of sTreeID in the list of elements
    integer                           :: IdPos
    ! -------------------------------------------------------------------- !
    integer :: lb, ub
    integer :: middleSearch
    type(tem_path_type) :: searched
    type(tem_path_type) :: current
    integer :: pathRelation
    ! -------------------------------------------------------------------- !

    if (present(lower)) then
      lb = lower
    else
      lb = lbound(treeIDList,1)
    end if
    if (present(upper)) then
      ub = upper
    else
      ub = ubound(treeIDList,1)
    end if

    !> Build the path to the searched TreeID from the leaf to the root.
    searched = tem_PathOf(sTreeID)

    ! Start the Binary search for the neighbor elements
    binSearchLoop: do
      middleSearch = (lb + ub) / 2
      ! Build the path to the currently investigated element from leaf to root.
      current = tem_PathOf(treeIDList(middleSearch))

      pathRelation = tem_PathComparison(searched, current)

      if ((pathRelation == 0) .or. (lb >= ub)) then
        ! Leave the loop, if element has been found, or this
        ! was the last element to investigate.
        exit binSearchLoop
      else
        halves: if (pathRelation == 1) then
          ! Continue the search in the higher half, as the looked up element is
          ! to small.
          lb = min(middleSearch + 1, ub)
        else
          ! Continue search in the lower half, as the looked up element is to
          ! large.
          ub = max(middleSearch - 1, lb)
        end if halves
      end if
    end do binSearchLoop

    if (pathRelation == 0) then
      if (current%Level <= searched%Level) then
        ! The found ID is actually a leaf
        IdPos = middleSearch
      else
        ! The found ID is a parent of the searched
        ! virtual treeID
        IdPos = -middleSearch
      end if
    else
      IdPos = 0 ! no matching element found.
    end if

  end function tem_PosOfId