ftlDynArray - SCM-NV/ftl GitHub Wiki

ftlDynArray is a sequence container that encapsulates dynamic size arrays.

The storage of the dynArray is handled automatically, being expanded and contracted as needed. dynArrays usually occupy more space than static arrays, because more memory is allocated to handle future growth. This way a dynArray does not need to reallocate each time an element is inserted, but only when the additional memory is exhausted. The total amount of allocated memory can be queried using the Capacity() function. Extra memory can be returned to the system via a call to ShrinkToFit().

Reallocations are usually costly operations in terms of performance. The Reserve() function can be used to eliminate reallocations if the number of elements is known beforehand.

The complexity of common operations on dynArrays is as follows:

• Random access: constant O(1)
• Insertion or removal of elements at the end: amortized constant O(1)
• Insertion or removal of elements: linear in distance to the end of the dynArray O(n)

The Fortran array that is encapsulated by an ftlDynArray instance is available as the data member. Note that data always has the correct size, i.e. the number of elements currently stored, not the number of elements storable before reallocation happens (that would be the capacity). Here is an example snippet that prints the contents of a dynArray of type T.

type(ftlDynArrayT) :: dArr

! note that size(dArr) == dArr%Size() == size(dArr%data)

do i = 1, size(dArr)
   write (*,*) i, dArr%data(i)
enddo

ftlDynArray is basically a Fortran reimplementation of C++'s std::vector. The name was changed because std::vector is a really inappropriate name for something that does not satisfy the mathematical definition of a vector.

ftlDynArray uses the following macros for instantiation:

FTL_TEMPLATE_TYPE

The type of the objects to be stored in the container, e.g. integer(int64) or MyDerivedType. Do not add the enclosing type() for derived types.

FTL_TEMPLATE_TYPE_IS_DERIVED

This needs to be defined if FTL_TEMPLATE_TYPE is a derived type.

FTL_TEMPLATE_TYPE_MODULE

The name of the module in which FTL_TEMPLATE_TYPE is defined. Specifying this is probably only necessary if FTL_TEMPLATE_TYPE is a derived type, or uses a kind defined in another module, e.g. int64 from the iso_fortran_env module.

FTL_TEMPLATE_TYPE_NAME

A convenient user-readable name for the stored type, e.g. Int. This will be used in the type-name of the dynArray container itself and the module in which it is available, e.g. setting this to Int will result in the type ftlDynArrayInt available in module ftlDynArrayIntModule.

FTL_INSTANTIATE_TEMPLATE

If this macro is defined the template will be instantiated. If not, the template will not be instantiated, but some information about the ftlDynArray container (e.g. its name and the kind of iterator it provides) will be passed on to subsequent template instantiations (e.g. ftlAlgorithms).

FTL_TEMPLATE_TYPE_PROVIDES_FTLMOVE

This macro should be defined if the template type implements the ftlMove method. This is useful for large types containing arrays or owning pointers so that copying would be expensive. The ftlDynArray container will then use the ftlMove method of the template type to move elements around the container, e.g. when shifting everything after erasing an element in the middle.

There is a specialization of the ftlDynArray template for ftlString as the element type. It is accessed by defining FTL_TEMPLATE_TYPE_IS_FTLSTRING:

#define FTL_TEMPLATE_TYPE_IS_FTLSTRING
#define FTL_TEMPLATE_TYPE_NAME String
#define FTL_INSTANTIATE_TEMPLATE
#include "ftlDynArray.F90_template"

This adds alternative versions for all methods that accept an ftlString as input. The alternative version accepts a plain Fortran character variable as input instead of a ftlString. This in convenient when passing a string literal. Of course the normal versions accepting an ftlString are also available.

use ftlDynArrayStringModule
type(ftlDynArrayString) :: words

words = ['hello','world']
call words%PushBack('of')
call words%PushBack('Fortran')
! ... is much more convenient than ...
words = [ftlString('hello'),ftlString('world')]
call words%PushBack(ftlString('of'))
call words%PushBack(ftlString('Fortran'))
! ... but both versions are totally equivalent

The ftlDynArray template has already been instantiated for ftlStrings in src/instantiations/ftlDynArrayString.f90.

Example instantiation of a ftlDynArray for integer(int64). The resulting type ftlDynArrayInt is available in ftlDynArrayIntModule.

#define FTL_TEMPLATE_TYPE integer(int64)
#define FTL_TEMPLATE_TYPE_NAME Int
#define FTL_TEMPLATE_TYPE_MODULE iso_fortran_env
#define FTL_INSTANTIATE_TEMPLATE
#include "ftlDynArray.F90_template"

Example instantiation of a ftnDynArray for a derived type (Point2D) defined in module Point2DModule. The resulting type ftlDynArrayPoint2D is available in ftlDynArrayPoint2DModule.

#define FTL_TEMPLATE_TYPE Point2D
#define FTL_TEMPLATE_TYPE_IS_DERIVED
#define FTL_TEMPLATE_TYPE_MODULE Point2DModule
#define FTL_TEMPLATE_TYPE_NAME Point2D
#define FTL_INSTANTIATE_TEMPLATE
#include "ftlDynArray.F90_template"

Constructs a new ftlDynArray container from a variety of data sources:

• Default constructor. Constructs an empty container.

  subroutine New(self)
     type(ftlDynArrayT), intent(out) :: self

  Example usage:

  type(ftlDynArrayInt) :: dArr
  call dArr%New() ! empty and size(dArr) == 0

• Constructs the container with a size of n, optionally populating it with n copies of val.

  subroutine New(self, n, val)
     type(ftlDynArrayT), intent(out)           :: self
     integer           , intent(in)            :: n
     T                 , intent(in) , optional :: val

  Example usage:

  type(ftlDynArrayInt) :: dArr
  call dArr%New(5)     ! array with 5 uninitialized integers
  call dArr%New(10, 0) ! with 10 integers of value 0

• Copy constructor. Constructs the container with the copy of the contents of other.

  subroutine New(self, other)
     type(ftlDynArrayT), intent(out) :: self
     type(ftlDynArrayT), intent(in)  :: other

  Example usage:

  type(ftlDynArrayInt) :: dArr1, dArr2
  call dArr1%New(5, 1)  ! array with 5 integers of value 1
  call dArr2%New(dArr1) ! copy of dArr2

• Construction from a normal Fortran array.

  subroutine New(self, array)
     type(ftlDynArrayT), intent(out) :: self
     T                 , intent(in)  :: array(:)

  Example usage:

  type(ftlDynArrayInt) :: dArr
  call dArr%New([1,5,8,0]) ! size is now 4, values are as specified

Destructs the container. The used storage is deallocated. Note that it is not necessary to call the destructor explicitly. Memory will also be deallocated automatically whenever a dynArray goes out of scope.

subroutine Delete(self)
   type(ftlDynArrayT), intent(inout) :: self

Example usage:

type(ftlDynArrayInt) :: dArr
call dArr%New([1,2,3,4,5,6,7,8]) ! allocates memory for 8 integers
call dArr%Delete()               ! deallocates the allocated memory

Replaces the contents of the container, modifying its size accordingly. Note that unlike using the corresponding constructors, assignment will only cause a reallocation if the current capacity is not sufficient.

• Copy assignment. Replaces the contents with a copy of the contents of other.

  subroutine assignment(=)(self, other)
     type(ftlDynArrayT), intent(inout) :: self
     type(ftlDynArrayT), intent(in)    :: other

• Array assignment. Replaces the contents with a copy of a normal Fortran array.

  subroutine assignment(=)(self, array)
     type(ftlDynArrayT), intent(inout) :: self
     T                 , intent(in)    :: array(:)

Example usage:

type(ftlDynArrayInt) :: dArr1, dArr2
dArr1 = [1,2,3,4] ! assignment also works on uninitialized dynArrays
dArr2 = [5,6,7,8,9,0]
dArr2 = dArr1 ! is now [1,2,3,4] but without reallocation

Note that there is currently no assignment of normal Fortran array from ftlDynArrays. However, this can easily be done by assigning the data member:

type(ftlDynArrayInt) :: dArr
integer :: a(5)
dArr = [5,6,3,2,3]
a = dArr%data

Provides direct access to the Fortran array underlying the ftlDynArray container. Note that calling the size() intrinsic on the data member yields the same size as calling the ftlDynArray%Size() method on the container itself.

Example usage:

type(ftlDynArrayInt) :: dArr
dArr = [1,2,3,4] ! assignment also works on uninitialized dynArrays
call dArr%PushBack(42)
write (*,*) dArr%data(5) ! prints 42
write (*,*) size(dArr), dArr%Size(), size(dArr%data) ! prints 5 5 5

Provides direct access to first/last element stored in the container.

Example usage:

type(ftlDynArrayInt) :: dArr
dArr = [1,2,3,4] ! assignment also works on uninitialized dynArrays
write (*,*) dArr%front, dArr%back ! prints 1 4

Returns a random access iterator to the first element of the container.

ftlDynArrayTIterator function Begin(self)
   type(ftlDynArrayT), intent(in) :: self

If the container is empty, the returned iterator will be equal to End(). Note that this method exists as both type-bound and as a free function.

Returns a random access iterator to the element following the last element of the container. This element acts as a placeholder; attempting to access it results in undefined behavior.

ftlDynArrayTIterator function End(self)
   type(ftlDynArrayT), intent(in) :: self

Note that this method exists as both type-bound and as a free function.

Checks if the container has no elements (i.e. its size is 0). This function does not modify the container in any way. See ftlDynArray%Clear() for a method that deletes the container's contents.

pure logical function Empty(self)
   type(ftlDynArrayT), intent(in) :: self

Returns the number of elements in the container. This is the number of elements currently stored in the container, which is not or equal to the capacity of the container. Note that this method exists as a type-bound procedure as well as a free function which mimics the Fortran size() intrinsic for arrays. This method always returns the same number as calling the size() intrinsic on the ftlDynArray%data member.

pure integer function Size(self)
   type(ftlDynArrayT), intent(in) :: self

Example usage:

type(ftlDynArrayInt) :: dArr
call dArr%New([1,2,3,4,5,6,7])
call dArr%PushBack(42)
write (*,*) dArr%Size(), size(dArr), size(dArr%data) ! prints: 8 8 8

Increase the capacity of the container to a value that's greater or equal to n. If n is greater than the current capacity, new storage is allocated, otherwise the method does nothing. If n is greater than the current capacity, all iterators and pointers to elements are invalidated. Otherwise, no iterators or pointers are invalidated.

subroutine Reserve(self, n)
   type(ftlDynArrayT), intent(inout) :: self
   integer           , intent(in)    :: n

Returns the number of elements that the container has currently allocated space for.

pure integer function Capacity(self)
   type(ftlDynArrayT), intent(in) :: self

Reduces the container's capacity to the currently stored number of elements. This releases any additional memory the container the container has allocated to accommodate future growth. If the current capacity is already the container's size, this method does nothing. If reallocation occurs, all iterators are invalidated. If no reallocation takes place, they remain valid.

subroutine ShrinkToFit(self)
   type(ftlDynArrayT), intent(inout) :: self

Removes all elements from the container. Invalidates any pointers, or iterators referring to contained elements. Any past-the-end iterators are also invalidated.

subroutine Clear(self)
   type(ftlDynArrayT), intent(inout) :: self

Resizes the container to contain n elements. If the current size is greater than n, the container is reduced to its first n elements. If the current size is less than n, additional elements are appended and optionally initialized with copies of val.

subroutine Resize(self, n, val)
   type(ftlDynArrayT), intent(inout)        :: self
   integer           , intent(in)           :: n
   T                 , intent(in), optional :: val

Appends an element to the end of the container. The new element is initialized as a copy of value.

subroutine PushBack(self, val)
   type(ftlDynArrayT), intent(inout) :: self
   T                 , intent(in)    :: val

If the new size is greater than capacity, reallocation happens and all iterators and references (including the past-the-end iterator) are invalidated. Otherwise only the past-the-end iterator is invalidated.

Returns and removes the last element of the container.

T function PopBack(self)
   type(ftlDynArrayT), intent(inout) :: self

Only the past-the-end iterator and the iterator to the removed element are invalidated, all other iterators stay valid.

Calling this method on an empty container is undefined behavior.

Inserts elements at the specified location in the container.

Causes reallocation if the new size is greater than the old capacity. If the new size is greater than capacity, all iterators and references are invalidated. Otherwise, only the iterators and references before the insertion point remain valid. The past-the-end iterator is also invalidated.

There are several versions of the insertion method:

• Inserts a copy of val before index pos, meaning data(pos) will become val and all elements behind this one are shifted by one position.

  subroutine Insert(self, pos, val)
     type(ftlDynArrayT), intent(inout) :: self
     integer           , intent(in)    :: pos
     T                 , intent(in)    :: val

• Insert a copy of val before iterator it. Basically just like the previous method but takes an iterator instead of an index as the insertion point.

  subroutine Insert(self, it, val)
     type(ftlDynArrayT)        , intent(inout) :: self
     type(ftlDynArrayTIterator), intent(in)    :: it
     T                         , intent(in)    :: val

• Insert n copies of val before index pos.

  subroutine Insert(self, pos, val)
     type(ftlDynArrayT), intent(inout) :: self
     integer           , intent(in)    :: pos
     integer           , intent(in)    :: n
     T                 , intent(in)    :: val

• Insert n copies of val before iterator it. Like the previous method but takes an iterator instead of an index as the insertion point.

  subroutine Insert(self, it, n, val)
     type(ftlDynArrayT)        , intent(inout) :: self
     type(ftlDynArrayTIterator), intent(in)    :: it
     integer                   , intent(in)    :: n
     T                         , intent(in)    :: val

• Insert a copy of array before index pos.

  subroutine Insert(self, pos, array)
     type(ftlDynArrayT), intent(inout) :: self
     integer           , intent(in)    :: pos
     T                 , intent(in)    :: array(:)

• Insert a copy of array before iterator it.

  subroutine Insert(self, it, array)
     type(ftlDynArrayT)        , intent(inout) :: self
     type(ftlDynArrayTIterator), intent(in)    :: it
     T                         , intent(in)    :: array(:)

• Insert a copy of the elements in the range [first, last) before index pos.

  subroutine Insert(self, pos, first, last)
     type(ftlDynArrayT)        , intent(inout) :: self
     integer                   , intent(in)    :: pos
     type(ftlDynArrayTIterator), intent(in)    :: first, last

• Insert a copy of the elements in the range [first,``last) before iterator it.

  subroutine Insert(self, it, first, last)
     type(ftlDynArrayT)        , intent(inout) :: self
     type(ftlDynArrayTIterator), intent(in)    :: it
     type(ftlDynArrayTIterator), intent(in)    :: first, last

Removes specified elements from the container. Invalidates iterators and references at or after the point of the erase, including the end() iterator.

Note that in contrast to the erase function of C++'s std::vector (which returns an iterator to the element following the last removed) this method is a subroutine and does not return anything. This was done because on Fortran it is not possible to ignore the return value of a function.

TODO: Implement an alternative erase method which corresponds to the erase function of C++'s std::vector.

There are several versions of the erase method:

• Erase the element with index pos.

  subroutine Erase(self, pos)
     type(ftlDynArrayT), intent(inout) :: self
     integer           , intent(in)    :: pos

• Erase the element referenced by iterator it.

  subroutine Erase(self, pos)
     type(ftlDynArrayT)        , intent(inout) :: self
     type(ftlDynArrayTIterator), intent(in)    :: it

• Erase the elements in the index range [first, last).

  subroutine Erase(self, first, last)
     type(ftlDynArrayT), intent(inout) :: self
     integer           , intent(in)    :: first, last

• Erase the elements in the iterator range [first, last).

  subroutine Erase(self, first, last)
     type(ftlDynArrayT)        , intent(inout) :: self
     type(ftlDynArrayTIterator), intent(in)    :: first, last

Swaps the contents of two dynArrays.

subroutine ftlSwap(dArr1, dArr2)
   type(ftlDynArrayT), intent(inout) :: dArr1, dArr2

The same effect could also be achieved with assignment (or copy construction):

type(ftlDynArrayInt) :: dArr1, dArr2, tmp
tmp = dArr2
dArr2 = dArr1
dArr1 = tmp
! ^-- same result as ftlSwap(dArr1, dArr2)

Note however, that this way of swapping is an O(N) operation, while ftlSwap is O(1) with a really small prefactor (it only swaps some pointers). Use ftlSwap whenever you want to exchange two dynArrays.

Transfers all the data from one dynArray to another. The source array becomes uninitialized in the process. It's essentially like the Fortran 2003 intrinsic move_alloc, but for ftlDynArrays.

subroutine ftlMove(src, dest)
   type(ftlDynArrayT), intent(inout) :: src
   type(ftlDynArrayT), intent(out)   :: dest

Note that it is not necessary for the template type to implement ftlMove in order for the ftlDynArray to be movable. The ftlDynArray is always movable, no matter if the template type is movable.

It is also possible to move an allocatable Fortran array into a dynArray:

subroutine ftlMove(src, dest)
   T, allocatable    , intent(inout) :: src(:)
   type(ftlDynArrayT), intent(out)   :: dest

The allocatable src becomes deallocated in the process.