The Lawrence Livermore National Laboratory published a nice article that shows how to use the GNU Profiler gprof.

Design a linked-list based algorithm for sorting the particles and compare its performance against its array-based counterpart (MP Allen and DJ Tildesley, Computer Simulation of Liquids) as a function of the system size and particle number density.

There's a TODO list that needs to be updated. All the tasks there have been completed so it's time to remove it from the source.

NOTE:
Do not remove the tutorial-like comments at the end of the source until you find a nice way to document the project.

create the node class --- the underlying type for a linked-list

Consider using a vector of nodes to implement a random-access iterator.

Provides the user/developer with a uniform interface for allocating some types

NOTE:
Might need to define derived-types in a typedefs module to implement these (de)allocators. The existing modules will have to import these type definitions (not defined in the respective modules as in the present case).

I am not sure yet how beneficial this might be in the long run.

Here's an interesting article on OO like programing in C.

generic programming examples in C

methods
implement a vector class with the basic features: push_back, size, clear, addressing operator( )

indexing
you can providelbound and rbound methods for users wishing to use these for traversing the elements of the vector.

growing
The vector grows as needed and it starts as empty. If the user wishes to push a value then it initializes the vector size to 8 (or 16) and then it grows twice as large so that the sequence 0, 8, 16, 32, 64, etc. delimits the possible vector sizes.

one past the end
You can always allocate one more element to compute the size as: end - begin, where end is an index value one past the end of the vector. This means that the user could address the value delimited by index by mistake. However, just like in c++ the user is responsible for addressing elements within the bounds of the container.

clearing elements
Clearing the vector only affects the iterator/index data so that it goes back to the beginning. So that pushing new values overwrites existing values until limit is reached. In that case the vector grows.

neighbor-lists
This is the ideal type to implement the neighbor-list which could be implemented as an array of vectors. It's analogous to the original implementation (2nd-rank array) but with the benefit that the neighbor-list size is not fixed.

The worst scenario for a simple BST algorithm is to be given a sorted data set.

If you store the last two values you could rearrange a branch that has grown in one direction two times in a row (example, 0 -> 1 -> 2 would be arranged as 0 <- 1 -> 2).

Vector is no longer a target in the create subroutines.

implement a fill constructor based on the c++ fill constructor which takes as argument the number of copies and a value.

Note that some work has been done before creating the issue. What's pending is setting the internal error message which is displayed to user when trying to push mixed types to a vector of built-in type.

TODO

• set the internal error message #87
• partition the code further #89
• test for aliasing #91
• handle filling the vector with empty vectors #90

a snippet which shows how to write data to a file having a Hierarchical Data Format HDF

various classes of boxes can be implemented (infinite or unbounded, 1d, 2d, 3d, cube, parallelepiped, and non-orthogonal boxes)

some possible names for member functions:
spawn: applies periodic boundary conditions
shrink: compresses the box incrementally (might be of some use for initialization of the system)
sort: sorts particles into subdomains (for classes that support domain decomposition techniques)

set it up so that the method forwards its work to the subroutine that already does this

Consider implementing an array class whose underlying data is an array of some type having fixed size:

type :: array_t
integer(kind = int64) :: value
end type

Try defining an iterator type for the class where ary.begin() returns an iterator that points at the beginning and ary.end() returns an (effective) off-the-end iterator. An effective off-the-end iterator because it could be set up to point to an element of the underlying data that's not accessible to the user which serves the purpose of computing the size of the array.

The GNU extension loc can help you index and compute the size of the underlying data. (Note that we can index the underlying data as usual since we have a fortran array and we also know the size of the array upon instantiation.)

This is just an experiment, I want to see whether it can be done or not in fortran.

implement a chronometer class defined in the chronos module, it should prove useful for profiling the code

Define a data structure that hides the implementation from its user:
type chrono
int begins
int ends
double clock_period
end type

And define a member function that returns the elapsed-time in milliseconds

a basic map class could be implemented as an array of vectors, the key would be of integer type and the value would be any of the values supported by the vector class.

Indexing of map can be achieved by setting the bounds of the array lb:ub, where lb is the minkey and ub is the maxkey value. This means that one has to store all the key values in another array. Note that this need not to be done if one knows the key values ahead of time. As for applying the particle sorting by cells technique.

Later the map class can be implemented using binary search trees to have some fun.

Consider adding support for pushing an array into vectors

Comments
The size of the vector follows the sequence: 8, 16, 32, 64, ..., 2 ^ (n - 1), 2 ^ n

Make it so that pushing an array to leads to a vector having a size that can be represented by two to the nth power (integer). The proposed approach is to use bitwise operations and intrinsics when the array size is greater than the current vector size:

• find the number of elements in the array by the size intrinsic
• obtain the MSB and left-shift to create a mask
• Bitwise AND the array-size with itself (all 64-bits will be set LOW) or assign a value of zero
• Bitwise OR with the mask to set left-shifted bit HIGH so that the new vector size is two to the power of some power n, 2^n

Note that we always ask for twice the array-size by left-shifting the MSB so that another array of the same size can be pushed to the vector without having to reallocate it.

If the array can be pushed without resizing the vector, then no memory reallocation will take place.

TODO

• complete task #68
• partition by methods (examples: push_back, erase, etc. methods in their own submodule) so that you can omit committing anything related to the experimental erase methods when you push to the main branch. This has been assigned in task #70
• partition grow method #72
• refactor writing data into vector #73
• refactor string allocations #76
• use bit operations to double the size of the vector
• implement the fill constructor #88
• int32 types
• int64 types
• real64 types
• vector type (push array of vectors)

Forgot to define the error message stored in vector to display it as a diagnostic when trying to push mixed types into a vector.

the following code snippet shows what needs to be avoided:

vectors = f()

where f() is a function that returns a vector and vectors is an array of vectors

As a result the iterators point to the same memory address unless the iterator of vector is NULL.

workaround until the bug is fixed is the following:

do i = first:last
    vectors(i) = f()
end do

TODO

• Try defining what it means to copy a vector into an array of vectors and overload the type-bound assign operator with the method. (Did not work see comment below.)
• Try doing the pointer association after the vector_vector_t_copy subroutine returns. And do it in a subroutine where only the vector itself is passed as an argument.
• implement validate method to validate the iterators whenever needed #103
• check if this is a bug of the compiler and report it if it has not been reported already

declare the vector with the allocatable attribute for consistency with other constructors (to be implemented)

constructs a vector from a given array of any supported type by the class

Consider creating a string class which uses the vector and the underlying container.

This means that the vector needs to be extended to contain an array of characters.

The subroutine does not doubles the vector size but it increases its capacity for storage. Choose a more appropriate name.

Note that when the vector is empty the bounds in the selected line of code b = 0 and e = -1 so that the iterator would point to an invalid memory location. Nullify the iterator instead.

There's also the issue that no memory is actually allocated for vector % array % values when the vector is empty. This is also something that needs fixing.

In addition to checking for aliasing for vectors nested at the same level sharing the same intermediate vector host, do so for vectors having different hosts.

Also extend the test to check that there's no aliasing among the hosts (or intermediate vectors).

The expected result is that there's no aliasing but I just want to be thorough.

Applies to the sources that implement the push-back method.

there's a plethora of pseudo-random number generators PRNGs to choose from. I have used Marsaglia's xorshift:32 before but it's worthwhile to explore this aspect in more detail to find PRNGs suitable for Brownian Dynamic Simulations. The TestU01 library might be a good place to look for statistical tests to determine the reliability of the PRNGs

Some functions have long names and long argument lists so to improve the presentation the indentation is going to be modified. I could change the naming convention but the easiest approach is to adjust the indentation.

So far the following commands have been used to adjust indentation of Vector.for:

$ sed -i 's/^  \(  interface.*\)/\1/' Vector.for 
$ sed -i 's/^  \(  end interface.*\)/\1/' Vector.for 
$ sed -i 's/^    \(    module sub.*\)/\1/' Vector.for
$ sed -i 's/^    \(    end sub.*\)/\1/' Vector.for
$ sed -i 's/^    \(    module fun.*\)/\1/' Vector.for
$ sed -i 's/^    \(    end fun.*\)/\1/' Vector.for
$ sed -i 's/^    \(    module elem.*\)/\1/' Vector.for
$ sed -i 's/^    \(    module recur.*\)/\1/' Vector.for
$ sed -i 's/^    \(        class.*\)/\1/' Vector.for
$ sed -i 's/^    \(        real.*\)/\1/' Vector.for
$ sed -i 's/^    \(        integer.*\)/\1/' Vector.for
$ sed -i 's/^    \(        ! Syn.*\)/\1/' Vector.for
$ sed -i 's/^    \(        type.*\)/\1/' Vector.for
$ sed -i 's/^    \(        char.*\)/\1/' Vector.for
$ sed -i 's/^    \(        logical.*\)/\1/' Vector.for
$ sed -i 's/^  \(  [uipt].*\)/\1/' Vector.for
$ sed -i 's/^  \(  end type.*\)/\1/' Vector.for
$ sed -i '90,142s/^  \(      [ptcil].*\)/\1/' Vector.for
$ sed -i '112,141s/^    \(        [pfg].*\)/\1/' Vector.for

commands used to indent the methods of vector<int32_t>:

$ sed -i 's/      \(  [me].*\)/\1/' Vector_int32_t_methods.for 
$ sed -i '31,87s/      \(      ..*\)/\1/' Vector_int32_t_methods.for

The idea here is to improve organization by breaking down the makefiles to make development of the vector class more manageable.

implement the erase method for the vector class it could take a either a value or an index as its input. It could also take two indexes first:last, the data pointed to by the inclusive range is deleted from the vector.

When a value is supplied all instances of the value are removed. This means that you cannot use the findloc intrinsic since it only finds the first or the last instance. You will have to define a function that masks the elements to be retained.

• conduct additional tests on erasing by bounds
• perform even more tests on erasing by bounds
• do more tests on erasing by values
• implement flipping the logic (erases those but the selected values)
• implement for int64 types

Freeing memory allocated for the internal data structure can be handled by the generic allocator which is called by vector_vector_t_copy to instantiate the (destination) vector.

What you need to do is to setup the allocators to free any memory that has been allocated already. This should destroy any data and nullify the iterator gracefully.

There's some repetition whenever a value is copied into a vector. See for example the insert-back and create subroutines:

insert:

      associate (begin  => vector % begin % idx,  &
               & avail  => vector % avail % idx,  &
               & values => vector % array % values)

          select type (values)
              type is ( integer(kind = int32) )
                  values (avail) = value
              class default
                  ! caters inserting mixed-types
                  error stop vector % state % errmsg
          end select

          vector % deref % it => vector % array % values(begin:avail)
          avail = avail + 1_int64

      end associate

create:

associate (begin  => vector % begin % idx,  &
               & avail  => vector % avail % idx,  &
               & limit  => vector % limit % idx,  &
               & state  => vector % state % init, &
               & values => vector % array % values)


          begin = lb
          avail = lb
          limit = ub


          select type (values)
              type is ( integer(kind = int32) )
                  values         = 0
                  values (avail) = value
              class default
                  error stop "dynamic::vector.create: unexpected err"
          end select

          vector % deref % it => vector % array % values(begin:avail)
          avail = avail + 1_int64
          state = .true.

      end associate

The minor differences in create can be conducted elsewhere.

The referenced line of code is just one example. Example: the preferred name for a vector of vectors is vofvec.

TODO

• apply naming convention
• limit the modified source lines to 75 chars

implement the pull-back method for the vector class to remove the last element

it's going to be useful if when updating the random-access iterator of the linked-list, especially when freeing the resources allocated for the list (the list is destroyed from tail to head).

system defines a data structure for unary, binary, and multi-component systems

In order to define the data structures of system (unary_t, binary_t, etc.) type the data members of particle_t must be public. One may choose to hide the particle data from the user in the system type.

Even though I do not yet have a full picture of what will end up implemented here I think it's a plausible design to define a system type. One may implement methods that spawn particles in the box to meet the parameters of the simulation.

Even though pushing mixed-types into a vector containing built-in types has been accounted for, it is still possible to push vectors of different types into another vector. The idea here is to prevent that under certain circumstances. I still would like to be able to push vectors of different types whenever doing so would simplify my work.

So what I would like to do is allow it when a vector of empty vectors is created with the fill constructor or when an empty vector is pushed into another.

For all the other cases, the object being pushed must be the same as the objected contained in the vector.

A possible way to do this is to add a new (or extend an existing) component that stores the "type" the vector contains. Easy way to do this is to define an integral whose values signal a specific type (say 0 for class(*), 1 for int32_t, 2 for int64_t, etc.)

The constructor generates a vector of integral type given a begin, end, and step, both the begin and step are optional. Sort of like Python's built-in range

This feature can be useful for quick generation of vector-subscripts.

It's a good practice to partition modules into submodules, especially for large projects. If setup correctly, it might reduce the compilation time. Need to think about how to do this with gnu make.

Now the pressing issue is to partition otherwise big modules into smaller source files, each implementing a feature such as the interactions of spheres via the Lennard-Jones potential or the displacement of such particles. There would be a submodule for the interactions and another for the computation of the displacement.

A similar partitioning could be used for particles of different type. For example spheroidal particles interacting via the Gay-Berne potential. There would be a submodule that computes the interactions and another for the displacement of such particles.

The module could only define an abstract particle type. A submodule could define what it means to be a sphere and another what it means to be a spheroid and so on. Then one can use submodules to implement the mentioned interactions, displacements, and anything else specific to that particle type.

So start small by partitioning small submodules to familiarize yourself with this approach.

First of all do not undue the work done for the linked-list class

In a separate module develop an experimental list class.

Some ideas:

1. if a section of the list is popped then that section becomes another list
2. the list keeps an update accounting of how many elements it has
3. uses class(*) as the underlying data structure for storage
4. prevents creating list of mixed-types just like the c++ list container
5. the iterator provides methods for navigating the list (example it % next() which would be the analogue of it++ which advances a c++ list to the next element).
6. Experiment with an iterator that provides direct access to the values. Consider using a dynamic array of pointers, use a vector as the underlying data structure to implement it.

There are interesting open-source implementations of the list class which you may want to check out. Also do not forget to see the methods that a python list provide.

Some references:

• PGI's OOP Data Polymorphism Tutorial
• Possible implementation
• Another implementation
• other

There's a significant degree of repetition when copying the data from a vector into a suitable placeholder and vice versa. Note that only the type of the placeholder changes. Break it down into smaller subroutines that handle a single task.

Proposed change for uniformity:

call inst

subroutine inst
    call instantiate (vec)
end subroutine

The internal procedure is tasked with the call.

Examples: min, max, avg, etc.

If there's an intrinsic that already does this, implement it as a wrapper. This implies that the vector stores objects of intrinsic types (int32, real64, etc.)

What matters is how the vector is going to be used. Users might prefer to apply the intrinsic to the values pointed to by the iterator.

For derived-types you will need to think about this more in depth. Note that the user needs to define what it means to compare objects of the derived-type.

Final Comments: Implementing a fully featured vector class is a project in itself.

There are times were you may want to assign one derived-type object to another (same-type) object. For example, assigning a vector to another vector.

It turns out that if assignment is not defined the compiler might synthesize one for you. If the derived-type encompasses intrinsic types only then you may not need to supply one yourself. However you may want to check what happens when using nested derived-types (the components of the derived-type are derived-type themselves).

See the wiki of the repository for additional info.

You will have to research what happens when the components are pointers as for the linked-list class. Some information can be found from the stackoverflow posts in the wiki.

neighbor-lists can be implemented as an array of vectors

type :: list_t
type(vector_t), allocatable :: lists(:)
type(range_t), allocatable :: range

where

type :: range_t
real(kind = real64), allocatable :: radius
end type

NOTE:
If choosing to use allocatable attribute for the components of the types it will be useful to define destructors for each type that will handle freeing memory.

In such case both the range_t and list_t need a finalizer.

As the comment in the source indicates, perform that task in a subroutine elsewhere. A potential candidate is the source file that implements the utilities for the vector class.

memory may be allocated for the internal data structure but the vector may as well be empty. This can be the case if a vector is constructed so that it has predefined limits. Note that this feature has not been implemented but it might be in the near future so it's important to do it right from the onset.

There's potential for refactoring in the grow method(s) called by the push-back method. These are used to increase the vector size whenever it reaches its full capacity.

Backing up data can be partitioned into a subroutine:

      ! bounds for copying the data
      lb = vector % begin % idx
      ub = vector % avail % idx - 1_int64
      bounds(0) = lb
      bounds(1) = ub
      call allocator (bounds, array)


      ! copies existing values into placeholder
      associate (values => vector % array % values)

          select type (values)
              type is ( integer(kind = int32) )
                  array(:) = values(lb:ub)
              class default
                  error stop vector % state % errmsg
          end select

      end associate

and so is the copying of the backed up data into vector:

      bounds(0) = vector % begin % idx
      bounds(1) = vector % limit % idx
      call reallocator (bounds, vector % array % values, value)

      ! copies values in placeholder into (reallocated) vector
      associate (values => vector % array % values)

         select type (values)
              type is ( integer(kind = int32) )
                  values = 0
                  values(lb:ub) = array
              class default
                  error stop errmsg
          end select

      end associate

There are some subroutines that match this, make sure to make the change for consistency.

The original implementation exposed the data in vector by a pointer whose association was handled by the member function iter. The issue is that whenever a value is pushed to or removed from the vector the iterator becomes invalidated automatically, requiring the user to call the member function iter to update the iterator.

It might be more useful to provide an iterator as a public data member of the vector class. It gets updated whenever a new value is pushed or removed. That way the user does not need to worry about invoking the member function iter whenever he or she needs it.

Resolution:

• define a public iterator to the underlying data
• remove the iter member function

I know that the size_t in c/c++ is an unsigned integer capable of holding the size of any object.

I guess that it should have the same capacity in fortran but I have not used it before so I would like to do a some research on their usage before incorporating them in the code.

This feature is of importance for implementing dynamic structures such as vectors, linked-lists, binary-search trees, etc.