src/service/itm_grid_simplex_dict.f90

Go to the documentation of this file.

module itm_grid_simplex_dict

  !> A dictionary module for simplexes

  use itm_types , ITM_R8 => R8
  use itm_assert
  use itm_combinations

  use itm_grid_common
  use itm_grid_object
  use itm_grid_access
  use itm_grid_subgrid

  implicit none

  ! A dictionary structure mapping from a node to the simplexes this node is part of.
  ! A simplex is stored for the node that is part of the simplex and has the smallest index.
  type SimplexDict
      ! Dimension of the simplexes in this dictionary. 0 = nodes, 1 = edges, 2 = triangles, 3 = tetraeder
      ! Every dim-simplex then has dim+1 nodes
      integer :: dim
      ! Store for every node the simplexes this node is part of as ordered lists of nodes, with
      ! the node itself omitted. For each node, the simplexes are stored in no particular order.
      ! Dims: 1=node index, 2=local simplex index, 3=indices of other nodes in simplex, ordered
      ! Size: 1:#nodes, 2:#max simpl./node, 3:dim-1
      integer, allocatable :: sxDict(:,:,:)
      ! Global index of the simplices. If simplex slot j for node i is unused, sxInd(i,j) = GRID_UNDEFINED
      ! Dims: 1=node index, 2=local simplex index
      ! Size: 1:#nodes, 2:#max simpl./node
      integer, allocatable :: sxInd(:,:)      
      ! Number of simplexes stored for node i
      integer, allocatable :: sxNum(:)
  end type SimplexDict

  type simplexDictIterator
      integer :: iNode, iSim
  end type simplexDictIterator

contains
  
  subroutine createSimplexDict( dict, dim, nNodes, nMaxParents )
    type(SimplexDict), intent(out) :: dict
    integer, intent(in) :: dim, nNodes, nMaxParents
    
    ! internal
    dict%dim = dim
    allocate(dict%sxDict(nNodes, nMaxParents, dim))
    allocate(dict%sxInd(nNodes, nMaxParents))
    allocate(dict%sxNum(nNodes))
    dict%sxDict = GRID_UNDEFINED
    dict%sxInd = GRID_UNDEFINED
    dict%sxNum = GRID_UNDEFINED
  end subroutine createSimplexDict

  integer function countSimplexes( dict )
    type(SimplexDict), intent(in) :: dict
    
    countSimplexes = sum(dict%sxNum)
  end function countSimplexes

  function sortSimplex(simplex)
    use m_inssor
    integer, intent(in) :: simplex(:)
    integer :: sortSimplex(size(simplex))

    sortSimplex = simplex
    call inssor(sortSimplex)      
  end function sortSimplex

  subroutine insertSimplex( dict, simplex )
    type(SimplexDict), intent(inout) :: dict
    integer, intent(in) :: simplex(:)

    ! internal
    integer :: index, node

    call assert(size(simplex) == dict%dim + 1)

    if (size(simplex) == 1) then
        dict%sxNum(simplex(1)) = 1
        return
    end if

    index = simplexIndex( dict, simplex )

    if ( index == GRID_UNDEFINED ) then
        ! Store in dictionary for lowest node
        node = simplex(1)
        ! We have one more simplex for that node
        dict%sxNum(node) = dict%sxNum(node) + 1
        if ( dict%sxNum(node) > size(dict%sxDict, 2)) &
            & stop "insertSimplex: dictionary overflow"

        ! Put new simplex in dictionary (omitting redundant first node)
        dict%sxDict( node, dict%sxNum(node), 1:dict%dim) = simplex(2:dict%dim + 1)
        ! Set global index for new simplex
        dict%sxInd( node, dict%sxNum(node) ) = dict%sxInd( node, dict%sxNum(node) ) + 1
        ! Increase global indices of all simplexes further up the array
        dict%sxInd( node, dict%sxNum(node)+1:size(dict%sxInd,2) ) = dict%sxInd( node, dict%sxNum(node)+1:size(dict%sxNum,1) ) + 1
        dict%sxInd( node + 1:size(dict%sxInd, 1), :) = dict%sxInd( node + 1:size(dict%sxInd, 1), :) + 1
    end if

  end subroutine insertSimplex

  subroutine resetIterator( iterator )
    type(SimplexDictIterator), intent(inout) :: iterator

    iterator%iNode = 1
    iterator%iSim = 0        
  end subroutine resetIterator
  
  subroutine nextSimplex( dict, iter, simplex )
    type(SimplexDict), intent(in) :: dict
    type(SimplexDictIterator), intent(inout) :: iter
    integer, dimension(dict%dim + 1), intent(out) :: simplex
       
    ! internal
    integer :: inode, isim

    inode = iter%inode
    isim = iter%isim

    ! increase index
    do
        isim = isim + 1
        if (isim > dict%sxNum(inode)) then
            inode = inode + 1
            isim = 0
        else
            simplex(1) = inode
            simplex(2:dict%dim + 1) = dict%sxDict(inode, isim, :)
            exit
        end if
        if (inode > size(dict%sxNum)) then
            simplex = GRID_UNDEFINED
            inode = size(dict%sxNum)
            exit
        end if
    end do
    
    iter%inode = inode
    iter%isim = isim
  end subroutine nextSimplex

  logical function simplexUndefined(simplex)
    integer, intent(in) :: simplex(:)

    simplexUndefined = (simplex(1) == GRID_UNDEFINED)
  end function simplexUndefined
 
  !> Get global index of given sorted simplex
  integer function simplexIndex( dict, simplex )
    type(SimplexDict), intent(in) :: dict
    integer, intent(in) :: simplex(:)
    !logical, intent(in), optional :: sorted
    
    ! internal
    integer :: s

    ! Special case for 0-simplex
    if (size(simplex) == 1) then
        simplexIndex = simplex(1)
        return
    end if

    do s = 1, dict%sxNum(simplex(1))
        if ( all( simplex(2:dict%dim+1) == dict%sxDict(simplex(1), s, 1:dict%dim)) ) then
            simplexIndex = dict%sxInd(simplex(1), s)
            return
        end if
    end do

    simplexIndex = GRID_UNDEFINED
  end function simplexIndex


  function listChildren(simplex) result( children )
    integer, intent(in) :: simplex(:)
    integer :: children(size(simplex), max(size(simplex)-1, 1))
    
    ! internal
    integer :: i, n

    n = size(simplex)
    
    ! Special case: 1-dimensional simplex has only itself as child
    if (n==1) then
        children(1,1) = simplex(1)
        return
    end if

    ! leave out node -iChild
    do i = 1, n
        if (i /= n) children(i,1:n-i) = simplex(1:n-i)
        if (i /= 1) children(i,n-i+1:n-1) = simplex(n-i+2:n)
    end do

  end function listChildren    
  
end module itm_grid_simplex_dict