polymorphic_tree Module Reference

Implements trees and procedures to use them. More...

Data Types
interface	DoSomethingTo2Nodes
	Does nothing. More...
interface	DoSomethingTo2NodesWithArg
	Does nothing. More...
interface	DoSomethingToNode
	Interface to apply a one-node operation to the whole tree using DoSomethingToTree. More...
interface	DoSomethingToNodeWithArg
	Interface to apply a one-node operation to the whole tree using DoSomethingToTreeWithArg. More...
type	node
type	node_ptr

Functions/Subroutines
subroutine	copynode (someNode, copy)
	Copies every field of the node to a copy. More...
subroutine	initialize_new_tree (someValue, root, pDeallocator)
	Creates new tree. The result is a node with name 'root', of rank zero, which points to the passed value. More...
recursive subroutine	find_node_by_name (someName, tree, pNode)
	Returns a pointer to the node with the specified name. The desired node must be one of the chidren or siblings of the input node. More...
type(node) function, pointer	find_node_by_name_fn (tree, someName)
	Same as above, but can be used as a function. More...
recursive subroutine	find_node_by_value (pValue, tree, pNode)
	Returns the node with the first (depth-first) occurence of the given value in the tree. More...
type(node) function, pointer	find_node_by_value_fn (tree, pValue)
	Same as above, but can be used as a function. More...
class(*) function, pointer	get_value (pNode)
	Returns the value stored in the given node. If pNode points to null, returns a null-pointer. More...
class(*) function, pointer	get_value_by_name (someName, tree)
	Returns a pointer to the value in the node with the specified name. More...
class(*) function, pointer	get_value_by_name2 (tree, someName)
	Same as above, but changed arguments to use as type-bound procedure. More...
recursive subroutine	dosomethingtotree (tree, pSomething)
	Applies the procedure in the pSomething pointer to every child and sibling recursively. More...
recursive subroutine	dosomethingtotreewitharg (tree, pSomething, arg)
	Applies the procedure (which takes an argument) in the pSomething pointer to every child and sibling recursively. More...
recursive subroutine	dosomethingto2trees (tree1, tree2, pSomething)
recursive subroutine	dosomethingto2treeswitharg (tree1, tree2, pSomething, arg)
subroutine	dosomethingtosomenodes (tree, Names, pSomething)
	Applies the procedure in the pSomething pointer to every node with the name from the Names array. More...
subroutine	dosomethingtosomenodeswitharg (tree, Names, pSomething, arg)
subroutine	printtree (tree)
	Passes a pointer to the printNode subroutine to DoSomethingToTree. More...
subroutine	printnode (someNode)
	If the value in the node is of type real, prints the value. More...
subroutine	printnode_new (someNode)
	A prettier output for the contents of a node. More...
recursive subroutine	printtree_new (tree, line, pProcedure)
	Draws the structure of the tree. More...
subroutine	find_common_predecessor (someName1, someName2, tree, pPred)
	Finds the first common predecessor of two nodes in the tree. More...
subroutine	find_common_predecessor_for_three (someName1, someName2, someName3, tree, pPred)
	Finds the common predecessor for three nodes by calling find_common_predecessor twice. More...
recursive subroutine	update_tree_rank (this)
	Updates the ranks of a subtree's nodes based on the parent of the provided node. Useful when moving or grafting. More...
type(node) function, pointer	getroot (this)
	Returns the root of the tree, given the node. More...
subroutine	add_child_to_node (parent_node, new_name, new_value, pDeallocator, result_node)
subroutine	add_node (parentName, newName, tree, newValue, pDeallocator, result_node)
	Adds node to the tree as a new child of a specified node. More...
subroutine	add_node2 (tree, parentName, newName, newValue, pDeallocator, result_node)
	Same as above, but changed the order to use as a type-bound procedure. More...
subroutine	graft (this, new_branch)
	Grafts the new_branch node as one of the children of this and refactors the ranks of all its children. More...
type(node) function, pointer	node_from_polymorphic (x)
	Converts a polymorphic pointer to a node pointer if possible, else returns a null-pointer. More...
recursive subroutine	deallocate_tree_native (this, start)
	Destroys all data contained in the (sub)tree. Presence of start allows to remove the siblings of the starting node. Otherwise, they will be untouched. For use with pDeallocator, use deallocate_tree_poly. More...
subroutine	deallocate_tree (pTree)
	Same subroutine as deallocate_tree to pass as pDeallocator. More...
subroutine	remove_node (someName, tree, pNodeOut)
	Remove a node from the tree by rearranging the pointers. More...
subroutine	purge_node (someName, tree)
subroutine	move_node_from_one_parent_to_another (nodeName, newParentName, tree)
	Moving node with its child from one parent to another. More...

Variables
integer, parameter, public	max_char =120
character(len=4), parameter, public	key_root = 'root'

Detailed Description

Implements trees and procedures to use them.

Author

???

Note

The tree has the structure where each node in the tree has rank (starting from 0), a name, and pointers: to the value held the node, and to its parent, child, and next sibling. This means that every parent node knows only about its first child.

Remarks

Maybe we don't need the rank field of the node at all. What about creating a recursive function which returns the rank of the node when asked? It will solve the problem of updating the ranks after moving a mode between parents, but we will have to rewrite the find_common_predecessor procedure.

Todo:

Add more tests for tree functions

Function/Subroutine Documentation

add_child_to_node()

subroutine polymorphic_tree::add_child_to_node	(	class(node), intent(in), target	parent_node,
		character(len=*), intent(in)	new_name,
		class(*), intent(in), pointer	new_value,
		procedure(deallocatorprocedure), intent(in), optional, pointer	pDeallocator,
		type(node), intent(out), optional, pointer	result_node
	)

add_node()

subroutine polymorphic_tree::add_node	(	character(len=*), intent(in)	parentName,
		character(len=*), intent(in)	newName,
		type(node), intent(inout)	tree,
		class(*), intent(in), pointer	newValue,
		procedure(deallocatorprocedure), intent(in), optional, pointer	pDeallocator,
		type(node), intent(out), optional, pointer	result_node
	)

Adds node to the tree as a new child of a specified node.

Parameters

tree	of type node must contain the node with name parentName.

Here is the call graph for this function:

add_node2()

subroutine polymorphic_tree::add_node2	(	class(node), intent(inout)	tree,
		character(len=*), intent(in)	parentName,
		character(len=*), intent(in)	newName,
		class(*), intent(in), pointer	newValue,
		procedure(deallocatorprocedure), intent(in), optional, pointer	pDeallocator,
		type(node), intent(out), optional, pointer	result_node
	)

Same as above, but changed the order to use as a type-bound procedure.

Todo:

Remove add_node above and rename add_node2.

Here is the call graph for this function:

copynode()

subroutine polymorphic_tree::copynode	(	type(node), intent(in)	someNode,
		type(node), intent(out)	copy
	)

Copies every field of the node to a copy.

Attention

The pointers are copied using the = sign instead of the => sign. Is this okay?

deallocate_tree()

subroutine polymorphic_tree::deallocate_tree

(

class(*), intent(inout), pointer

pTree

)

Same subroutine as deallocate_tree to pass as pDeallocator.

Here is the call graph for this function:

deallocate_tree_native()

recursive subroutine polymorphic_tree::deallocate_tree_native	(	type(node), intent(inout), pointer	this,
		logical, intent(in), optional	start
	)

Destroys all data contained in the (sub)tree. Presence of start allows to remove the siblings of the starting node. Otherwise, they will be untouched. For use with pDeallocator, use deallocate_tree_poly.

Here is the call graph for this function:

dosomethingto2trees()

recursive subroutine polymorphic_tree::dosomethingto2trees	(	type(node), intent(inout)	tree1,
		type(node), intent(inout)	tree2,
		procedure(dosomethingto2nodes), intent(in), pointer	pSomething
	)

Here is the call graph for this function:

dosomethingto2treeswitharg()

recursive subroutine polymorphic_tree::dosomethingto2treeswitharg	(	type(node), intent(inout)	tree1,
		type(node), intent(inout)	tree2,
		procedure(dosomethingto2nodeswitharg), intent(in), pointer	pSomething,
		class(*), intent(inout), pointer	arg
	)

Here is the call graph for this function:

dosomethingtosomenodes()

subroutine polymorphic_tree::dosomethingtosomenodes	(	type(node), intent(inout)	tree,
		character(len=*), dimension(:), intent(in)	Names,
		procedure(dosomethingtonode), intent(in), pointer	pSomething
	)

Applies the procedure in the pSomething pointer to every node with the name from the Names array.

Here is the call graph for this function:

dosomethingtosomenodeswitharg()

subroutine polymorphic_tree::dosomethingtosomenodeswitharg	(	type(node), intent(inout)	tree,
		character(len=*), dimension(:), intent(in)	Names,
		procedure(dosomethingtonodewitharg), intent(in), pointer	pSomething,
		class(*), intent(inout), pointer	arg
	)

Here is the call graph for this function:

dosomethingtotree()

recursive subroutine polymorphic_tree::dosomethingtotree	(	type(node), intent(inout)	tree,
		procedure(dosomethingtonode), intent(in), pointer	pSomething
	)

Applies the procedure in the pSomething pointer to every child and sibling recursively.

Here is the call graph for this function:

dosomethingtotreewitharg()

recursive subroutine polymorphic_tree::dosomethingtotreewitharg	(	type(node), intent(inout)	tree,
		procedure(dosomethingtonodewitharg), intent(in), pointer	pSomething,
		class(*), intent(inout), pointer	arg
	)

Applies the procedure (which takes an argument) in the pSomething pointer to every child and sibling recursively.

Here is the call graph for this function:

find_common_predecessor()

subroutine polymorphic_tree::find_common_predecessor	(	character(len=*), intent(in)	someName1,
		character(len=*), intent(in)	someName2,
		type(node), intent(in)	tree,
		type(node), intent(out), pointer	pPred
	)

Finds the first common predecessor of two nodes in the tree.

Attention

There is no check for whether the two nodes belong to the same tree.

Here is the call graph for this function:

find_common_predecessor_for_three()

subroutine polymorphic_tree::find_common_predecessor_for_three	(	character(len=*), intent(in)	someName1,
		character(len=*), intent(in)	someName2,
		character(len=*), intent(in)	someName3,
		type(node), intent(in)	tree,
		type(node), intent(out), pointer	pPred
	)

Finds the common predecessor for three nodes by calling find_common_predecessor twice.

Here is the call graph for this function:

find_node_by_name()

recursive subroutine polymorphic_tree::find_node_by_name	(	character(len=*), intent(in)	someName,
		type(node), intent(in), target	tree,
		type(node), intent(inout), pointer	pNode
	)

Returns a pointer to the node with the specified name. The desired node must be one of the chidren or siblings of the input node.

Here is the call graph for this function:

find_node_by_name_fn()

type(node) function, pointer polymorphic_tree::find_node_by_name_fn	(	class(node), intent(in)	tree,
		character(len=*), intent(in)	someName
	)

Same as above, but can be used as a function.

Here is the call graph for this function:

find_node_by_value()

recursive subroutine polymorphic_tree::find_node_by_value	(	class(*), intent(in), pointer	pValue,
		type(node), intent(in), target	tree,
		type(node), intent(inout), pointer	pNode
	)

Returns the node with the first (depth-first) occurence of the given value in the tree.

Here is the call graph for this function:

find_node_by_value_fn()

type(node) function, pointer polymorphic_tree::find_node_by_value_fn	(	class(node), intent(in)	tree,
		class(*), intent(in), pointer	pValue
	)

Same as above, but can be used as a function.

Here is the call graph for this function:

get_value()

class(*) function, pointer polymorphic_tree::get_value

(

type(node), pointer

pNode

)

Returns the value stored in the given node. If pNode points to null, returns a null-pointer.

Here is the call graph for this function:

get_value_by_name()

class(*) function, pointer polymorphic_tree::get_value_by_name	(	character (len=*)	someName,
		class(node)	tree
	)

Returns a pointer to the value in the node with the specified name.

Here is the call graph for this function:

get_value_by_name2()

class(*) function, pointer polymorphic_tree::get_value_by_name2	(	class(node)	tree,
		character (len=*)	someName
	)

Same as above, but changed arguments to use as type-bound procedure.

Here is the call graph for this function:

getroot()

type(node) function, pointer polymorphic_tree::getroot

(

class(node), intent(in), target

this

)

Returns the root of the tree, given the node.

graft()

subroutine polymorphic_tree::graft	(	class(node), intent(inout), target	this,
		type(node), intent(inout), target	new_branch
	)

Grafts the new_branch node as one of the children of this and refactors the ranks of all its children.

initialize_new_tree()

subroutine polymorphic_tree::initialize_new_tree	(	class(*), intent(in), pointer	someValue,
		type(node), intent(out)	root,
		procedure(deallocatorprocedure), intent(in), optional, pointer	pDeallocator
	)

Creates new tree. The result is a node with name 'root', of rank zero, which points to the passed value.

move_node_from_one_parent_to_another()

subroutine polymorphic_tree::move_node_from_one_parent_to_another	(	character(len=*), intent(in)	nodeName,
		character(len=*), intent(in)	newParentName,
		type(node), intent(inout)	tree
	)

Moving node with its child from one parent to another.

Here is the call graph for this function:

node_from_polymorphic()

type(node) function, pointer polymorphic_tree::node_from_polymorphic

(

class(*), intent(in), pointer

x

)

Converts a polymorphic pointer to a node pointer if possible, else returns a null-pointer.

printnode()

subroutine polymorphic_tree::printnode

(

type(node), intent(inout)

someNode

)

If the value in the node is of type real, prints the value.

Todo:

Add functionality to print data of other types.

printnode_new()

subroutine polymorphic_tree::printnode_new

(

class(node), intent(inout)

someNode

)

A prettier output for the contents of a node.

printtree()

subroutine polymorphic_tree::printtree

(

class(node)

tree

)

Passes a pointer to the printNode subroutine to DoSomethingToTree.

Here is the call graph for this function:

printtree_new()

recursive subroutine polymorphic_tree::printtree_new	(	class(node), intent(inout)	tree,
		character(len=*), intent(in), optional, target	line,
		procedure(dosomethingtonodewitharg), intent(in), optional, pointer	pProcedure
	)

Draws the structure of the tree.

Parameters

tree	The printed tree will contain this node and all of its substructure.
line	(optional) Can be used to provide padding before every output line. Is meant to exist only as a workaround to help with pretty output.
pProcedure	(optional) If there is need to output data structures that polymorphic_tree_mod doesn't know about, you can supply your own output procedure. Note that all of the output will be forwarded to pProcedure, so make sure that it handles that well (see organicum/organicum_mod.f90:print_atomic_node_new for an example)

Here is the call graph for this function:

purge_node()

subroutine polymorphic_tree::purge_node	(	character(len=*), intent(in)	someName,
		type(node), intent(inout)	tree
	)

Here is the call graph for this function:

remove_node()

subroutine polymorphic_tree::remove_node	(	character(len=*), intent(in)	someName,
		type(node), intent(inout)	tree,
		type(node), intent(out), optional, pointer	pNodeOut
	)

Remove a node from the tree by rearranging the pointers.

Remarks

The removed node becomes a new tree's root. Optional pointer pNodeOut points to the removed node

Here is the call graph for this function:

update_tree_rank()

recursive subroutine polymorphic_tree::update_tree_rank

(

class(node), intent(inout)

this

)

Updates the ranks of a subtree's nodes based on the parent of the provided node. Useful when moving or grafting.

Variable Documentation

key_root

character(len=4), parameter, public polymorphic_tree::key_root = 'root'

max_char

integer, parameter, public polymorphic_tree::max_char =120