Algorithm

The flc_algorithm module wraps C++ standard algorithm routines. Instead of taking pairs of iterators, the Flibcpp algorithm subroutines accept target-qualified one-dimensional arrays. All algorithms follow the indexing convention that the first element of an array has index 1, and an index of 0 indicates “not found”.

Sorting

Sorting algorithms for numeric types default to increasing order when provided with a single array argument. Numeric sorting routines accept an optional second argument, a comparator function, which should return true if the first argument is strictly less than the right-hand side.

Warning

For every value of a and b, the comparator cmp must satisfy .not. (cmp(a, b) .and. cmp(b, a)). If this strict ordering is not satisfied, some of the algorithms below may crash the program.

All sorting algorithms are also instantiated so that they accept an array of type(C_PTR) and a generic comparator function. This enables arrays of any native Fortran object to be sorted. See the generic sorting example for a demonstration.

sort

Sorting and checking order is a single simple subroutine call:

use flc_algorithm, only : sort
implicit none
integer, dimension(5) :: iarr = [ 2, 5, -2, 3, -10000]

call sort(iarr)

is_sorted

Checking the ordering of array is just as simple:

use flc_algorithm, only : is_sorted
integer, dimension(5) :: iarr = [ 2, 5, -2, 3, -10000]
logical :: sortitude

sortitude = is_sorted(iarr)

argsort

A routine that provides the indices that correspond to a sorted array, like Numpy’s argsort , takes an array to analyze and an empty array of integers to fill:

use flc_algorithm, only : argsort, INDEX_INT
implicit none
integer, dimension(5) :: iarr = [ 2, 5, -2, 3, -10000]
integer(INDEX_INT), dimension(size(iarr)) :: idx

call argsort(iarr, idx)
write(*,*) iarr(idx) ! Prints the sorted array

Note that the index array is always a INDEX_INT, which is an alias to C_INT. On some compilers and platforms, this may be the same as native Fortran integer, but it’s not guaranteed.

The data and idx arguments to argsort must be the same size. If the index array is larger than the data, invalid entries will be filled with zero.

Searching

Like the sorting algorithms, searching algorithms are instantiated on numeric types and the C pointer type, and they provide an optional procedure pointer argument that allows the arrays to be ordered with an arbitrary comparator.

equal_range

Finds the range of elements in a sorted array equivalent to the given value. If the exact value isn’t present, the first index will point to the index at which the value could be inserted to maintain a sorted array. If searching for a value that’s in the sorted array more than once, the expression arr(first_idx:last_idx) will return the equal values. If the value isn’t present, arr(first_idx:last_idx) will be an empty array, and the first index will be the point at which the element would be located if it were present.

Example:

use flc_algorithm, only : equal_range, INDEX_INT
implicit none
integer(INDEX_INT) :: first, last
integer, dimension(6) :: iarr = [ -5, 1, 1, 2, 4, 9]

call equal_range(iarr, -6, first, last) ! (first,last) are (1,0)
call equal_range(iarr, -5, first, last) ! (first,last) are (1,1)
call equal_range(iarr,  1, first, last) ! (first,last) are (2,3)
call equal_range(iarr,  3, first, last) ! (first,last) are (5,4)
call equal_range(iarr,  9, first, last) ! (first,last) are (6,6)

minmax_element

Finds the smallest and largest element in an array. Note that the first occurrence of the minimum value is selected, and the last occurrence of the maximum value is selected. Thus, for a sorted array arr which may have duplicate elements, the expression arr(min_idx:max_idx) will always return the entire array.

Example:

use flc_algorithm, only : minmax_element, INDEX_INT
implicit none
integer, dimension(6) :: iarr = [ -5, 1000, -1000, 999, -1000, 1000]
integer(INDEX_INT) :: min_idx, max_idx

call minmax_element(iarr, min_idx, max_idx) ! min_idx == 3, max_idx == 6

Set operations

Sorted arrays can be manipulated as “sets,” supporting unions, intersections, and differences.

includes

Whether one set encloses another set: every item of the second array is present in the first array.

Example:

use flc_algorithm, only : includes
implicit none
integer, dimension(6) :: iarr = [ -5, 1, 2, 4, 9]
integer, dimension(3) :: jarr = [ 1, 2, 5]
logical :: is_superset

is_superset = includes(iarr, iarr)) ! true
is_superset = includes(iarr, iarr(:3))) ! true
is_superset = includes(iarr, iarr(3:))) ! true
is_superset = includes(iarr(3:), iarr)) ! false
is_superset = includes(iarr, jarr) ! false
is_superset = includes(iarr, jarr(1:2))) ! true

Not yet implemented

  • set_difference
  • set_intersection
  • set_symmetric_difference
  • set_union

Modifying

shuffle

The “shuffle” subroutine depends on the Random module so that it can use the default random number generator to randomly reorder an array.

Example:

use flc_algorithm, only : shuffle
use flc_random, only : Engine => MersenneEngine4
implicit none
integer :: i
integer, dimension(8) :: iarr = (/ ((i), i = -4, 3) /)
type(Engine) :: rng
rng = Engine()

call shuffle(rng, iarr)

Not yet implemented

  • unique