flibs/binarytree - Balanced trees
The balanced_tree.f90 and balanced_tree_string.f90 source files allow you to implement balanced trees of any (derived) type without having to edit the supplied source code. The key by which the data are stored or retrieved can be an integer value (balanced_tree.f90 or a string (balanced_tree_string.f90).
module MYDATA_MODULE
type MYDATA
character(len=20) :: string
end type MYDATA
end module
module MYDATA_BTREES
use MYDATA_MODULE, TREE_DATA => MYDATA
include "balanced_tree.f90"
end module MYDATA_BTREES
The above code defines a module MYDATA_MODULE with the derived type that is to be stored in the balanced trees. The name of that derived type can be anything.
It also defines a module MYDATA_BTREES which will be the module that holds the functionality to use balanced trees:
The module MYDATA_MODULE is used, but the derived type MYDATA is renamed to the (fixed) name TREE_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 balanced trees in a program, we can just use the MYDATA_BTREES module. If you need more than one type of data in balanced trees, then apply the same renaming trick on using the specific balanced trees modules.
In fact the example in the source file "two_lists.f90" shows the general technique of how to accomplish this for linked lists. The same applies to balanced trees.
The source files balanced_tree.f90 and balanced_tree_string.f90 provide an object-oriented interface (the difference in the interface is the type of the key):
The relevant derived type is balanced_tree in both cases. There is no need for an explicit creation.
Add a new data item to the tree. It will be stored under the given key.
The key under which the data are stored, either an integer value or a string.
The data to be stored. Note that a copy of the actual data is stored, not a pointer to them. This makes its use much easier, as you do not need to worry about the persistence. If the deallocation of the data structure requires special treatment (for instance to deallocate memory accessed via pointers), then define a final method for the data.
Get the data item from the tree stored via the given key.
The key under which the data are stored, either an integer value or a string.
The data will be copied into this argument. (Use user-defined assignment if necessary)
Indicates if the key was found or not. If not, then the "data" argument is untouched.
Returns whether the tree holsds the given key or not.
The key under which the data may be stored, either an integer value or a string.
Destroy the tree. All data (copies) contained in it will be destroyed as well.
Traverse the data items of the tree and invoke a user-defined routine on the data well.
The routine to be invoked for each data item. The interface is defined as:
interface
subroutine routine( key, data )
import tree_data
integer, intent(in) :: key
type(tree_data), intent(in) :: data
end subroutine routine
end interface
Notes:
The balanced trees can only store data of the same derived type. In that sense the code is not generic.
If explicit deallocation is required, use the final features for the derived type TREE_DATA.
If default assignment is not adequate, use defined assignment instead.
Copyright © 2019 Arjen Markus <arjenmarkus@sourceforge.net>