Skip to content

ftlList

Jump to bottom
Robert Rüger edited this page Jul 25, 2018 · 5 revisions

Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions.

The ftlList is implemented as doubly-linked list. Doubly linked lists store each of the elements they contain in different and unrelated storage locations. The ordering is kept internally by the association to each element of a link to the element preceding it and a link to the element following it.

Compared to other base standard sequence containers (ftlDynArray, ftlDeque), lists perform generally better in inserting, extracting and moving elements in any position within the container for which an iterator has already been obtained.

The main drawback of lists compared to these other sequence containers is that they lack direct access to the elements by their position. For example, to access the sixth element in a list, one has to iterate from a known position (like the beginning or the end) to that position, which takes linear time in the distance between these. They also consume some extra memory to keep the linking information associated to each element (which may be an important factor for large lists of small-sized elements).

ftlList is basically a Fortran reimplementation of C++'s `std::list`_.

Instantiation

Macros

ftlList 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 list container itself and the module in which it is available, e.g. setting this to Int will result in the type ftlListInt available in module ftlListIntModule.
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 ftlList 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 ftlList container will then use the ftlMove method of the template type to move elements around instead of doing deep copies via (user defined) assignment. Currently this is only used to move the instance of the type out of the list into the return values of the PopBack or PopFront methods.

Example instantiations

Example instantiation of a ftlList for integer(int64). The resulting type ftlListInt is available in ftlListIntModule.

#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 "ftlList.F90_template"

Example instantiation of a ftnList for a derived type (Point2D) defined in module Point2DModule. The resulting type ftlListPoint2D is available in ftlListPoint2DModule.

#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 "ftlList.F90_template"

Methods and public data members

Construction, destruction & assignment

ftlList%New()

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

  • Default constructor. Constructs an empty container.

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

    Example usage:

    type(ftlListInt) :: lst
call lst%New() ! empty and size(lst) == 0

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

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

    Example usage:

    type(ftlListInt) :: lst
call lst%New(5)     ! list with 5 uninitialized integers
call lst%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(ftlListT), intent(out) :: self
   type(ftlListT), intent(in)  :: other

    Example usage:

    type(ftlListInt) :: lst1, lst2
call lst1%New(5, 1) ! list with 5 integers of value 1
call lst2%New(lst1) ! copy of lst2

  • Construction from a normal Fortran array.

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

    Example usage:

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

ftlList%Delete()

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 list goes out of scope.

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

Example usage:

type(ftlListInt) :: lst
call lst%New([1,2,3,4,5,6,7,8])
call lst%Delete() ! deallocates all memory owned by lst

ftlList assignment(=)

Replaces the contents of the container, modifying its size accordingly. For ftlList, assignment is absolutely equivalent to using the constructors directly. (This is not true for all FTL containers, see ftlDynArray)

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

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

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

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

Example usage:

type(ftlListInt) :: lst1, lst2
lst1 = [1,2,3,4] ! assignment also works on uninitialized lists
lst2 = [5,6,7,8,9,0]
lst2 = lst1 ! is now [1,2,3,4] but without reallocation

Note that unlike C++'s `std::list`_, the ftlList currently does not have the assignment method versions that take the number of arguments or iterator pairs. Just use the ftlList%New() methods instead.

Iterators & Element access

ftlList%Begin()

Begin(ftlList)

Returns a bidirectional iterator to the first element of the container.

ftlListTIterator function Begin(self)
   type(ftlListT), 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.

ftlList%End()

End(ftlList)

Returns a bidirectional 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.

ftlListTIterator function End(self)
   type(ftlListT), intent(in) :: self

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

ftlList%front

ftlList%back

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

Example usage:

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

Capacity

ftlList%Empty()

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

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

ftlList%Size()

size(ftlList)

Returns the number of elements in 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.

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

Example usage:

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

Modifiers

ftlList%Clear()

Removes all elements from the container. Invalidates any pointers, or iterators referring to contained elements. The past-the-end iterator remains valid

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

ftlList%Resize()

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(ftlListT), intent(inout)        :: self
   integer       , intent(in)           :: n
   T             , intent(in), optional :: val

ftlList%PushBack()

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

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

Note that the past-the-end iterator remains valid.

ftlList%PopBack()

Returns and removes the last element of the container.

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

The iterator to the removed element is invalidated, all other iterators stay valid.

Calling this method on an empty container is undefined behavior.

ftlList%PushFront()

Inserts an element at the beginning of the list. The new element is initialized as a copy of value.

subroutine PushFront(self, val)
   type(ftlListT), intent(inout) :: self
   T             , intent(in)    :: val

ftlList%PopFront()

Returns and removes the last element of the container.

T function PopFront(self)
   type(ftlListT), intent(inout) :: self

The iterator to the removed element is invalidated, all other iterators stay valid.

Calling this method on an empty container is undefined behavior.

ftlList%Insert()

Inserts elements at the specified location in the container. All iterators remain valid.

There are several versions of the insertion method:

  • Insert a copy of val before iterator it.

    subroutine Insert(self, it, val)
   type(ftlListT)        , intent(inout) :: self
   type(ftlListTIterator), intent(in)    :: it
   T                     , intent(in)    :: val

  • Insert n copies of val before iterator it.

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

  • Insert a copy of array before iterator it.

    subroutine Insert(self, it, array)
   type(ftlListT)        , intent(inout) :: self
   type(ftlListTIterator), intent(in)    :: it
   T                     , intent(in)    :: array(:)

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

    subroutine Insert(self, it, first, last)
   type(ftlListT)        , intent(inout) :: self
   type(ftlListTIterator), intent(in)    :: it
   type(ftlListTIterator), intent(in)    :: first, last

ftlList%Erase()

Removes specified elements from the container. Invalidates iterators to the removed elements.

Note that in contrast to the erase function of C++'s `std::list`_ (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::list`_.

There are two versions of the erase method:

  • Erase the element referenced by iterator it.

    subroutine Erase(self, pos)
   type(ftlListT)        , intent(inout) :: self
   type(ftlListTIterator), intent(in)    :: it

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

    subroutine Erase(self, first, last)
   type(ftlListT)        , intent(inout) :: self
   type(ftlListTIterator), intent(in)    :: first, last

FTL utility methods

ftlSwap()

Swaps the contents of two lists.

subroutine ftlSwap(lst1, lst2)
   type(ftlListT), intent(inout) :: lst1, lst2

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

type(ftlListInt) :: lst1, lst2, tmp
tmp = lst2
lst2 = lst1
lst1 = tmp
! ^-- same result as ftlSwap(lst1, lst2)

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 lists.

ftlMove()

Moves the contents of one list to another list.

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

This is an O(1) operation. The src list is empty after the moving.

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

Clone this wiki locally