tem_PosOfId Function

public pure function tem_PosOfId(sTreeID, treeIDlist, lower, upper) result(IdPos)

This subroutine does a binary search on a given (sparse) list of elements. The result is the position of the given tree ID in the list, 0 if no corresponding node is found, or the negative of the found ID, if it is a virtual node.

Build the path to the searched TreeID from the leaf to the root.

Arguments

Type IntentOptional Attributes Name
integer(kind=long_k), intent(in) :: sTreeID

tree ID to search for
integer(kind=long_k), intent(in) :: treeIDlist(:)

List to search in
integer, intent(in), optional :: lower

lowerbound of search interval
integer, intent(in), optional :: upper

upperbound of search interval

Return Value integer

position of sTreeID in the list of elements


Calls

proc~~tem_posofid~~CallsGraph proc~tem_posofid tem_PosOfId proc~tem_pathof tem_PathOf proc~tem_posofid->proc~tem_pathof proc~tem_pathcomparison tem_PathComparison proc~tem_posofid->proc~tem_pathcomparison

Called by

proc~~tem_posofid~~CalledByGraph proc~tem_posofid tem_PosOfId proc~evaluate_add_spacetime_scalarbycoordinate evaluate_add_spacetime_scalarByCoordinate proc~evaluate_add_spacetime_scalarbycoordinate->proc~tem_posofid proc~evaluate_add_spacetime_vectorbycoordinate evaluate_add_spacetime_vectorByCoordinate proc~evaluate_add_spacetime_vectorbycoordinate->proc~tem_posofid proc~evaluate_first_spacetime_scalarbycoordinate evaluate_first_spacetime_scalarByCoordinate proc~evaluate_first_spacetime_scalarbycoordinate->proc~tem_posofid proc~tem_cano_initsubtree tem_cano_initSubTree proc~tem_cano_initsubtree->proc~tem_posofid proc~setup_indices_spacetime setup_indices_spacetime proc~setup_indices_spacetime->proc~tem_posofid proc~tem_cano_storepntsinsubtree tem_cano_storePntsInSubTree proc~tem_cano_storepntsinsubtree->proc~tem_posofid proc~tem_unify_vrtx tem_unify_vrtx proc~tem_unify_vrtx->proc~tem_posofid proc~evaluate_first_spacetime_vectorbycoordinate evaluate_first_spacetime_vectorByCoordinate proc~evaluate_first_spacetime_vectorbycoordinate->proc~tem_posofid proc~tem_cano_checkneigh tem_cano_checkNeigh proc~tem_cano_checkneigh->proc~tem_posofid proc~tem_findelement tem_findElement proc~tem_findelement->proc~tem_posofid proc~tem_findelement->proc~tem_findelement proc~tem_shape_subtreefromgeominters tem_shape_subTreeFromGeomInters proc~tem_shape_subtreefromgeominters->proc~tem_cano_initsubtree proc~tem_shape_subtreefromgeominters->proc~tem_cano_storepntsinsubtree proc~tem_shape_subtreefromgeominters->proc~tem_cano_checkneigh proc~tem_calc_vrtx_coord tem_calc_vrtx_coord proc~tem_calc_vrtx_coord->proc~tem_unify_vrtx proc~tem_shape2subtree tem_shape2subTree proc~tem_shape2subtree->proc~tem_shape_subtreefromgeominters proc~hvs_output_init hvs_output_init proc~hvs_output_init->proc~tem_calc_vrtx_coord proc~tem_create_subtree_of tem_create_subTree_of proc~tem_create_subtree_of->proc~tem_shape2subtree proc~tem_init_tracker tem_init_tracker proc~tem_init_tracker->proc~hvs_output_init

Contents

Source Code

tem_PosOfId

Source Code

  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