Description

A generic tree comparison class which will take into account index contractions and will also keep track of a replacement list for all types of cadabra wildcards.

The entry point is typically 'equal_subtree' or 'match_subproduct'.

#include <Compare.hh>

Public Types
enum	match_t { match_t::node_match =0, match_t::subtree_match =1, match_t::match_index_less =2, match_t::match_index_greater =3, match_t::no_match_indexpos_less =4, match_t::no_match_indexpos_greater =5, match_t::no_match_less =6, match_t::no_match_greater =7 }

enum	useprops_t { useprops_t::always =0, useprops_t::not_at_top, useprops_t::never =2 }

typedef std::map< Ex, Ex, tree_exact_less_no_wildcards_obj >	replacement_map_t
	Map for the replacement of nodes (indices, patterns). More...

typedef std::map < nset_t::iterator, Ex::iterator, nset_it_less >	subtree_replacement_map_t
	Map for the replacement of entire subtrees (object patterns). More...

Public Member Functions
	Ex_comparator (const Properties &)

void	clear ()
	Reset the object for a new match. More...

match_t	equal_subtree (Ex::iterator i1, Ex::iterator i2, useprops_t use_props=useprops_t::always, bool ignore_parent_rel=false)
	Match two subtrees taking into account symbol properties. More...

match_t	match_subproduct (const Ex &, Ex::sibling_iterator lhs, Ex::sibling_iterator tofind, Ex::sibling_iterator st, Ex::iterator conditions)
	Find a sub-product in a product. More...

match_t	match_subsum (const Ex &, Ex::sibling_iterator lhs, Ex::sibling_iterator tofind, Ex::sibling_iterator st, Ex::iterator conditions)
	Find a sub-sum in a sum. More...

bool	satisfies_conditions (Ex::iterator conditions, std::string &error)
	Check whether the a match found by calling equal_subtree or match_subproduct satisfies the conditions as stated. More...

bool	should_swap (Ex::iterator obj, match_t subtree_comparison)
	Determine whether two objects should be swapped according to the available SortOrder properties. More...

int	can_swap (Ex::iterator one, Ex::iterator two, match_t subtree_comparison, bool ignore_implicit_indices=false)
	Determine whether obj and obj+1 be exchanged? If yes, return the sign, if no return zero. More...

int	can_move_adjacent (Ex::iterator prod, Ex::sibling_iterator one, Ex::sibling_iterator two, bool fix_one=false)
	Determine whether object 'one' and 'two' can be moved next to each other by moving either one or the other: if fix_one==true the first node is kept fixed, otherwise the second node is kept fixed. More...

Public Attributes
replacement_map_t	replacement_map

subtree_replacement_map_t	subtree_replacement_map

replacement_map_t	index_value_map
	Map for matching of index names to index values. More...

std::vector< Ex::sibling_iterator >	factor_locations
	Information to keep track of where individual factors/terms in a sub-product/sub-sum were found, and (for sub-products) whether moving them into the searched-for order leads to sign flips. More...

std::vector< int >	factor_moving_signs

multiplier_t	term_ratio

bool	lhs_contains_dummies
	Flag to indicate whether additional care must be taken to handle dummies in the lhs of the pattern. More...

Protected Member Functions
match_t	compare (const Ex::iterator &, const Ex::iterator &, bool nobrackets=false, useprops_t use_props=useprops_t::always, bool ignore_parent_rel=false)
	Internal entry point. More...

int	can_swap_prod_obj (Ex::iterator prod, Ex::iterator obj, bool)

int	can_swap_prod_prod (Ex::iterator prod1, Ex::iterator prod2, bool)

int	can_swap_sum_obj (Ex::iterator sum, Ex::iterator obj, bool)

int	can_swap_prod_sum (Ex::iterator prod, Ex::iterator sum, bool)

int	can_swap_sum_sum (Ex::iterator sum1, Ex::iterator sum2, bool)

int	can_swap_ilist_ilist (Ex::iterator obj1, Ex::iterator obj2)

std::string	tab () const

match_t	report (match_t r) const

Protected Attributes
const Properties &	properties

Static Protected Attributes
static int	offset =0

Member Typedef Documentation

typedef std::map<Ex, Ex, tree_exact_less_no_wildcards_obj> cadabra::Ex_comparator::replacement_map_t

Map for the replacement of nodes (indices, patterns).

typedef std::map<nset_t::iterator, Ex::iterator, nset_it_less> cadabra::Ex_comparator::subtree_replacement_map_t

Map for the replacement of entire subtrees (object patterns).

Member Enumeration Documentation

enum cadabra::Ex_comparator::match_t

strong

Enumerator
node_match
subtree_match
match_index_less
match_index_greater
no_match_indexpos_less
no_match_indexpos_greater
no_match_less
no_match_greater

enum cadabra::Ex_comparator::useprops_t

strong

Enumerator
always
not_at_top
never

Constructor & Destructor Documentation

cadabra::Ex_comparator::Ex_comparator ( const Properties & k )

Member Function Documentation

int cadabra::Ex_comparator::can_move_adjacent	(	Ex::iterator	prod,
		Ex::sibling_iterator	one,
		Ex::sibling_iterator	two,
		bool	fix_one = `false`
	)

Determine whether object 'one' and 'two' can be moved next to each other by moving either one or the other: if fix_one==true the first node is kept fixed, otherwise the second node is kept fixed.

int cadabra::Ex_comparator::can_swap	(	Ex::iterator	one,
		Ex::iterator	two,
		match_t	subtree_comparison,
		bool	ignore_implicit_indices = `false`
	)

Determine whether obj and obj+1 be exchanged? If yes, return the sign, if no return zero.

This is the general entry point for two arbitrary nodes (which may be a product or sum).

The last flag ('ignore_implicit_indices') is used to disable all checks dealing with implicit indices (this is useful for algorithms which re-order objects with implicit indices, which would otherwise always receive a 0 from this function).

int cadabra::Ex_comparator::can_swap_ilist_ilist	(	Ex::iterator	obj1,
		Ex::iterator	obj2
	)

protected

int cadabra::Ex_comparator::can_swap_prod_obj	(	Ex::iterator	prod,
		Ex::iterator	obj,
		bool	ignore_implicit_indices
	)

protected

int cadabra::Ex_comparator::can_swap_prod_prod	(	Ex::iterator	prod1,
		Ex::iterator	prod2,
		bool	ignore_implicit_indices
	)

protected

int cadabra::Ex_comparator::can_swap_prod_sum	(	Ex::iterator	prod,
		Ex::iterator	sum,
		bool	ignore_implicit_indices
	)

protected

int cadabra::Ex_comparator::can_swap_sum_obj	(	Ex::iterator	sum,
		Ex::iterator	obj,
		bool	ignore_implicit_indices
	)

protected

int cadabra::Ex_comparator::can_swap_sum_sum	(	Ex::iterator	sum1,
		Ex::iterator	sum2,
		bool	ignore_implicit_indices
	)

protected

void cadabra::Ex_comparator::clear ( )

Reset the object for a new match.

Ex_comparator::match_t cadabra::Ex_comparator::compare	(	const Ex::iterator &	one,
		const Ex::iterator &	two,
		bool	nobrackets = `false`,
		useprops_t	use_props = `useprops_t::always`,
		bool	ignore_parent_rel = `false`
	)

protected

Internal entry point.

This comparison function tries to match a single node in the tree, except when the node is an index. Indices are considered to be leaf-nodes, and for these a full subtree match will be attempted (using subtree_compare).

Ex_comparator::match_t cadabra::Ex_comparator::equal_subtree	(	Ex::iterator	i1,
		Ex::iterator	i2,
		useprops_t	use_props = `useprops_t::always`,
		bool	ignore_parent_rel = `false`
	)

Match two subtrees taking into account symbol properties.

'i1' can be a pattern. Returns subtree_match or one of the no_match results. You need to fill lhs_contains_dummies before calling! If use_props is false, it will not try to fetch any property information at the TOP level of the comparison. Properties will always be used at levels.

Ex_comparator::match_t cadabra::Ex_comparator::match_subproduct	(	const Ex &	tr,
		Ex::sibling_iterator	lhs,
		Ex::sibling_iterator	tofind,
		Ex::sibling_iterator	st,
		Ex::iterator	conditions
	)

Find a sub-product in a product.

The 'lhs' iterator points to the product which we want to find, the 'tofind' iterator to the current factor which we are looking for. The product in which to search is pointed to by 'st'. Once 'tofind' is found, this routine calls itself to find the next factor in 'lhs'. If the next factor cannot be found, we backtrack and try to find the previous factor again (it may have appeared multiple times).

Ex_comparator::match_t cadabra::Ex_comparator::match_subsum	(	const Ex &	tr,
		Ex::sibling_iterator	lhs,
		Ex::sibling_iterator	tofind,
		Ex::sibling_iterator	st,
		Ex::iterator	conditions
	)

Find a sub-sum in a sum.

The 'lhs' iterator points to the sum which we want to find, the 'tofind' iterator to the current term which we are looking for. The sum in which to search is pointed to by 'st'. Once 'tofind' is found, this routine calls itself to find the next term in 'lhs'. Since Cadabra assumes all terms in a sum commute, we do not need the backtracking logic of subproduct.

Ex_comparator::match_t cadabra::Ex_comparator::report ( Ex_comparator::match_t r ) const

protected

bool cadabra::Ex_comparator::satisfies_conditions	(	Ex::iterator	conditions,
		std::string &	error
	)

Check whether the a match found by calling equal_subtree or match_subproduct satisfies the conditions as stated.

FIXME: document possible conditions.

bool cadabra::Ex_comparator::should_swap	(	Ex::iterator	obj,
		match_t	subtree_comparison
	)

Determine whether two objects should be swapped according to the available SortOrder properties.

std::string cadabra::Ex_comparator::tab ( ) const

protected

Member Data Documentation

std::vector<Ex::sibling_iterator> cadabra::Ex_comparator::factor_locations

Information to keep track of where individual factors/terms in a sub-product/sub-sum were found, and (for sub-products) whether moving them into the searched-for order leads to sign flips.

std::vector<int> cadabra::Ex_comparator::factor_moving_signs

replacement_map_t cadabra::Ex_comparator::index_value_map

Map for matching of index names to index values.

Note: this is in the opposite order from replacement_map!

bool cadabra::Ex_comparator::lhs_contains_dummies

Flag to indicate whether additional care must be taken to handle dummies in the lhs of the pattern.

FIXME: would be better if this were automatic.

int cadabra::Ex_comparator::offset =0

staticprotected

const Properties& cadabra::Ex_comparator::properties

protected

replacement_map_t cadabra::Ex_comparator::replacement_map

subtree_replacement_map_t cadabra::Ex_comparator::subtree_replacement_map

multiplier_t cadabra::Ex_comparator::term_ratio

The documentation for this class was generated from the following files:

core/Compare.hh
core/Compare.cc

Description

Public Types

Public Member Functions

Public Attributes

Protected Member Functions

Protected Attributes

Static Protected Attributes

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation