rank_keys Subroutine

public subroutine rank_keys(n, key, perm)

Rank key(1:n) ascending: perm(k) is the index of the k-th smallest key. Heapsort, so O(n log n) worst case and no scratch beyond perm itself. Local rather than the equivalent mrgrnk vendored with octree-mg, to keep the callers independent of the multigrid solver.

Arguments

Type IntentOptional Attributes Name
integer, intent(in) :: n
integer, intent(in) :: key(:)
integer, intent(out) :: perm(:)

Called by

proc~~rank_keys~~CalledByGraph proc~rank_keys rank_keys proc~layout_runs layout_runs proc~layout_runs->proc~rank_keys proc~build_message_layout build_message_layout proc~build_message_layout->proc~layout_runs proc~exchange_coarsened_blocks exchange_coarsened_blocks proc~exchange_coarsened_blocks->proc~layout_runs proc~exchange_migrated_blocks exchange_migrated_blocks proc~exchange_migrated_blocks->proc~layout_runs proc~amr_coarsen_refine amr_coarsen_refine proc~amr_coarsen_refine->proc~exchange_coarsened_blocks proc~load_balance load_balance proc~amr_coarsen_refine->proc~load_balance proc~init_comm_fix_conserve init_comm_fix_conserve proc~init_comm_fix_conserve->proc~build_message_layout proc~load_balance->proc~exchange_migrated_blocks proc~advect advect proc~advect->proc~init_comm_fix_conserve proc~recalculateb recalculateB proc~recalculateb->proc~init_comm_fix_conserve proc~resettree resettree proc~resettree->proc~amr_coarsen_refine proc~resettree_convert resettree_convert proc~resettree_convert->proc~amr_coarsen_refine proc~settree settree proc~settree->proc~amr_coarsen_refine proc~advance advance proc~advance->proc~advect proc~improve_initial_condition improve_initial_condition proc~improve_initial_condition->proc~recalculateb proc~main main proc~main->proc~resettree_convert proc~main->proc~settree proc~main->proc~improve_initial_condition proc~timeintegration timeintegration proc~main->proc~timeintegration proc~timeintegration->proc~resettree proc~timeintegration->proc~advance program~agile agile program~agile->proc~main

Source Code

  subroutine rank_keys(n, key, perm)
    integer, intent(in)  :: n, key(:)
    integer, intent(out) :: perm(:)

    integer :: i, j, l, ir, tmp

    do i = 1, n
      perm(i) = i
    end do
    if (n < 2) return

    l  = n/2 + 1
    ir = n
    do
      if (l > 1) then
        l   = l - 1
        tmp = perm(l)
      else
        tmp      = perm(ir)
        perm(ir) = perm(1)
        ir       = ir - 1
        if (ir == 1) then
          perm(1) = tmp
          exit
        end if
      end if
      i = l
      j = l + l
      do while (j <= ir)
        if (j < ir) then
          if (key(perm(j)) < key(perm(j+1))) j = j + 1
        end if
        if (key(tmp) < key(perm(j))) then
          perm(i) = perm(j)
          i = j
          j = j + j
        else
          j = ir + 1
        end if
      end do
      perm(i) = tmp
    end do

  end subroutine rank_keys