flibs/datastructures(n) 1.0 "flibs"
flibs/datastructures - Unordered sets
TABLE OF CONTENTS
SYNOPSIS
DESCRIPTION
ROUTINES
COPYRIGHT
The sets.f90 source file allows you to implement
unordered sets of any (derived) type without having to
edit the supplied source code. To this end a simple technique is used,
which is best illustrated by an example:
| |
!
! The data that will be stored in the sets
!
type MYDATA
integer :: value
end type MYDATA
!
! As derived types are compared, we need to define
! how to compare them
!
interface operator(.eq.)
module procedure mydata_isequal
end interface
contains
logical function mydata_isequal( v1, v2 )
type(MYDATA), intent(in) :: v1
type(MYDATA), intent(in) :: v2
mydata_isequal = v1%value .eq. v2%value
end function mydata_isequal
end module MYDATA_MODULE
module MYDATA_SET_STRUCTS
use MYDATA_MODULE, SET_DATA => MYDATA
include "data_for_sets.f90"
end module MYDATA_SET_STRUCTS
module MYDATA_SETS
use MYDATA_SET_STRUCTS
include "sets.f90"
end module MYDATA_SETS
|
The above code defines a module MYDATA_MODULE with the derived
type that is to be stored in the sets. The name of that derived
type can be anything.
It also defines a module MYDATA_SET_STRUCTS which prepares the
underlying data structure. The reason for this two-layer process is that
you need to be able to define the name of the modules that are involved
yourself. (Otherwise it would be impossible to use two or more
sets holding different types of data in one program.
It finally defines a module MYDATA_SETS which will be the
module that holds the functionality to use unordered sets:
-
The module MYDATA_MODULE is used, but the derived type
MYDATA is renamed to the (fixed) name SET_DATA. (This
is the name used in the generic source file.)
-
The source code for the actual routines is simply included via the
INCLUDE statement.
-
Nothing more is required, we can close the source text for the module.
To use a single type of sets in a program, we can just use the
MYDATA_SETS module. If you need more than one type of data in sets,
then apply the same renaming trick on using the specific set
modules.
In fact the example in the source file "two_lists.f90" shows the general
technique of how to accomplish this.
The source file sets.f90 provides the following
routines:
- call set_create( dataset )
-
Create a new empty set.
- type(SET) dataset
-
The variable that will be used for accessing the set
- call set_destroy( dataset )
-
Destroy the set. All elements contained in it will be destroyed as
well.
- type(SET) dataset
-
The set to be destroyed
- size = set_size( dataset )
-
Function to return the number of elements in the set.
- type(SET) dataset
-
The set in question
- call set_add( dataset, elem )
-
Insert a new element in the set. If the element is already present,
nothing is done.
- type(SET) dataset
-
The dataset to add the element to.
- type(SET_DATA), intent(in) elem
-
The element to be stored
- call set_delete_element( dataset, elem )
-
Delete the given element from the set.
- type(SET) dataset
-
The list in question
- type(SET_DATA) elem
-
The element to be deleted
- has = set_haselement( dataset, elem )
-
Returns whether or not the given element is in the set.
- type(SET) dataset
-
The set in question
- type(SET_DATA) elem
-
The element to be checked
- has = elem .elementof. dataset
-
Returns whether or not the given element is in the set.
(The operator version)
- type(SET) dataset
-
The set in question
- type(SET_DATA) elem
-
The element to be checked
- equal = set_equal( set1, set2 )
-
Returns whether or not the two sets contain the same elements.
- type(SET) set1
-
The first set
- type(SET) set2
-
The second set
- equal = set1 .eq. set2
-
Returns whether or not the two sets contain the same elements.
(The operator version)
- notequal = set_notequal( set1, set2 )
-
Returns whether or not the two sets do not contain the same elements.
(The operator version)
- type(SET) set1
-
The first set
- type(SET) set2
-
The second set
- notequal = set1 .ne. set2
-
Returns whether or not the two sets do not contain the same elements.
(The operator version)
- has = set_hassubset( dataset, subset )
-
Returns whether or not one set is contained in the other set.
- type(SET) dataset
-
The set that may hold the second one
- type(SET) subset
-
The set that may be a subset of the fist
- has = subset .subsetof. dataset
-
Returns whether or not one set is contained in the other set.
(The operator version)
- type(SET) subset
-
The set that may be a subset of the other
- type(SET) dataset
-
The set that may hold the first one
- newset = set_union( set1, set2 )
-
Returns the union of two sets.
- type(SET) set1
-
The first set
- type(SET) set2
-
The second set
- newset = set1 .union. set2
-
Returns the union of two sets - operator version.
- newset = set_intersection( set1, set2 )
-
Returns the intersection of two sets.
- type(SET) set1
-
The first set
- type(SET) set2
-
The second set
- newset = set1 .intersect. set2
-
Returns the intersection of two sets - operator version.
- newset = set_exclusion( set1, set2 )
-
Returns a copy of the first set with the elements of the second set
excluded.
- type(SET) set1
-
The first set
- type(SET) set2
-
The second set
- newset = set1 .intersect. set2
-
Returns a copy of the first set with the elements of the second set
excluded - operator version.
Notes:
-
The sets can only store data of the same derived type. In that sense
the code is not generic.
-
Currently, the sets can only store derived types that do not require
an explicit destruction. If you want to store a derived type with
pointers to allocated memory, you can do that however, by supplying an
assignment operator. This would lead to a memory leak though. It is best
to wait for the next version which will allow such derived types to be
stored.
Copyright © 2006 Arjen Markus <arjenmarkus@sourceforge.net>