1. Harald Klimach
  2. TreElM


TreElM / source / tem_dyn_array.fpp

! See copyright notice in the COPYRIGHT file.
!> Module to provide smart growing data structures.
!! The dynamic arrays provided by this module are
!! capable of handling lists of values, which might
!! need to grow over time.
!! Removal of entries is not possible directly.
!! A ranking list for the indices is maintained to
!! fast lookups of given values by a binary search.
!! This allows for the efficient handling of lists
!! with unique entries.
!! The complete module might be put into a CoCo Text
!! template, to create new modules of this object
!! for different types. For now, two different
!! templates are used for the declaration part and
!! the implementation part.
?? include 'arrayMacros.inc'
module tem_dyn_array_module
  use env_module, only: long_k, rk, dbgUnit, minLength, labelLen

  implicit none

! In order to define this data structure easily for several data
! type, we use the Coco text copying feature here, to duplicate
! the necessary declarations.
! tname: indicates type of dynamic array (long, int, real, ...)
! tstring: is the actual string describing the type specification

! Here the actual declarations are put in by CoCo:
?? copy :: DA_decltxt(long, integer(kind=long_k))
?? copy :: DA_decltxt(int, integer)
?? copy :: DA_decltxt(real, real(kind=rk))
?? copy :: DA_decltxt(label, character(len=labelLen))


! Also for the implementation, we use the copy feature, to provide
! the necessary duplications to deal with the various types.
! tname ... indicates type of dynamic array (long, int, real, ...)

?? copy :: DA_impltxt(long, integer(kind=long_k), integer(kind=long_k))
?? copy :: DA_impltxt(int, integer, integer)
?? copy :: DA_impltxt(real, real(kind=rk), real(kind=rk))
?? copy :: DA_impltxt(label, character(len=labelLen), character(len=*))

end module tem_dyn_array_module

!> \page tem_dyn_arrays Dynamic data structures
!! During the processing of the mesh to create the solver data structures,
!! common tasks arise.
!! These include among others
!! a unique collection of elements in lists, i.e. without duplicates,
!! a localization of a stored element,
!! sorting of a list of records.
!! As Fortran does not intrinsically include dynamically growing data structures,
!! they first have to be introduced manually.
!! \subsection tem_dyn_retrievePos Retrieving the position of a record
!! You might want to retrieve the position of a (unique) value within a list.
!! In order to achieve this efficiently, the list with \f$n\f$ entries must be ordered so we can rely on
!! the binary search, which performs with \f$\mathcal{O}( \log n )\f$.
!! \subsection tem_dyn_dataStructures {Dynamic data structures}
!! Hence we introduce a derived data type which allows an efficient and simple
!! element adding and retrieving process, as well as a sorted order of the entries.
!! A module provides the type definitions and all the related procedures to
!! act on this data type.
!! The data type includes the size of the container within, the amount of its actual entries,
!! a flag for uniqueness and then the container array itself as well as a conforming array for the
!! sorted retrieval of the entries in the value array.
!! The definition is depicted in Listing \ref{lst:tem_dyn_array} where macros are used for
!! the label of a dynamic type `?tname?`and the used data type `tstring?`.
!! The introduction of macros allow for a generic
!! definition for all data types of the container,
!! whereas the compiled source code contains the definitions for each required data type.
!! In order to use such data structures they first have to be initialized with
!! options such as the uniqueness of the entries or the initial size of the container.
!! The initialization simply allocates the container with the given options and
!! resets the number of records.
!! Correspondingly, the object can be destroyed by `destroy( me = valName )`.
!! If an object has been initialized, records can be added by simply calling
!! `append`.
!! Subsequently, checks are performed, for the existence of the entry in the list
!! and the sufficiency of the size of the container to incorporate another entry.
!! In case the size does not suffice, the array is doubled in size through a temporary array,
!! and then the record is added.
!! Information about if and where the entry was stored is returned to the caller.