Cadabra
Computer algebra system for field theory problems
Loading...
Searching...
No Matches
Algorithm.hh
Go to the documentation of this file.
1/*
2
3Cadabra: a field-theory motivated computer algebra system.
4Copyright (C) 2001-2014 Kasper Peeters <kasper.peeters@phi-sci.com>
5
6This program is free software: you can redistribute it and/or
7 modify it under the terms of the GNU General Public License as
8published by the Free Software Foundation, either version 3 of the
9License, or (at your option) any later version.
10
11This program is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14General Public License for more details.
15
16You should have received a copy of the GNU General Public License
17along with this program. If not, see <http://www.gnu.org/licenses/>.
18
19*/
20
21#pragma once
22
23#include "Stopwatch.hh"
24#include "Storage.hh"
25#include "Props.hh"
26#include "Kernel.hh"
27#include "IndexIterator.hh"
28#include "ProgressMonitor.hh"
29#include "ExManip.hh"
30#include "Compare.hh"
31
32namespace cadabra {
33
53
54 class Algorithm : public ExManip /* , public IndexClassifier */ {
55 public:
60
61 Algorithm(const Kernel&, Ex&);
62 virtual ~Algorithm();
63
64 typedef std::set<Ex, tree_exact_less_obj> Ex_set_t;
66
68
71
73
81
82 result_t apply_generic(bool deep=true, bool repeat=false, unsigned int depth=0);
83 result_t apply_generic(iterator&, bool deep, bool repeat, unsigned int depth);
84
89
91
92 // Global information
93 unsigned int number_of_calls;
97
99 bool check_consistency(iterator) const;
103
104 void report_progress(const std::string&, int todo, int done, int count=2);
105
109
112
113 // The number of indices of a node, taking into account IndexInherit-ance. These
114 // indices do therefore not all have to be direct child nodes of 'it', they can
115 // sit deeper down the tree.
116 unsigned int number_of_indices(iterator it);
117 static unsigned int number_of_indices(const Properties&, iterator it);
118
119 // The number of indices of a node, counting only the direct ones (i.e. not those
120 // inherited from child nodes).
121 static unsigned int number_of_direct_indices(iterator it);
122
123 // The set to which the first index belongs..
124 std::string get_index_set_name(iterator it) const;
125
130
135 static bool is_termlike(iterator);
136
139 static bool is_factorlike(iterator);
140
144 static bool is_noncommuting(const Properties&, iterator);
145
151
153 bool derivative_acts_on(iterator it) const;
154
155 protected:
157
158 // The main entry point which is used by the public entry points listed
159 // above. Override these in any subclass.
160 //
161 virtual bool can_apply(iterator)=0;
163
164 // Index stuff
165 // int index_parity(iterator) const;
166 // static bool less_without_numbers(nset_t::iterator, nset_t::iterator);
167 // static bool equal_without_numbers(nset_t::iterator, nset_t::iterator);
168
170 typedef std::pair<sibling_iterator, sibling_iterator> range_t;
171 typedef std::vector<range_t> range_vector_t;
172
175 template<class Iter>
176 range_vector_t::iterator find_arg_superset(range_vector_t&, Iter st, Iter nd);
177 range_vector_t::iterator find_arg_superset(range_vector_t&, sibling_iterator it);
178
179 // Locate objects inside the tree (formerly in the 'locate' algorithm).
180 unsigned int locate_single_object(Ex::iterator obj_to_find,
181 Ex::iterator st, Ex::iterator nd,
182 std::vector<unsigned int>& store);
183 bool locate_object_set(const Ex& objs,
184 Ex::iterator st, Ex::iterator nd,
185 std::vector<unsigned int>& store);
186 static bool compare_(const str_node&, const str_node&);
187
188
194
195 // Given a node with non-zero multiplier, distribute this
196 // multiplier up the tree when the node is a \sum node, or push it into the
197 // `\prod` node if that is the parent. Do this recursively
198 // in case a child is a sum as well. Note that 'pushup' is actually 'pushdown'
199 // in the case of sums.
200 // This never changes the tree structure, only the distribution of multipliers.
201
202 // FIXME: this is now superseded by code in Cleanup.cc, and the generic way
203 // to make a tree consistent is to call cleanup_dispatch, not pick-and-match from
204 // the various algorithms.
206
207 // Return the number of elements in the first range for which an identical element
208 // is present in the second range.
209 template<class BinaryPredicate>
212
213 // Turn a node into a '1' or '0' node.
214 void node_zero(iterator);
215 void node_one(iterator);
216 void node_integer(iterator, int);
217
218
219
220 protected:
222
223 private:
224
225 // Single or deep-scan apply operations. Do not call directly.
226 result_t apply_once(Ex::iterator& it);
227 result_t apply_deep(Ex::iterator& it);
228
236
237 // bool cleanup_anomalous_products(Ex& tr, Ex::iterator& it);
238 };
239
240
243 template<class BinaryPredicate>
246 BinaryPredicate fun) const
247 {
248 unsigned int ret=0;
250 while(it1!=to1) {
252 while(it2!=to2) {
253 if(fun(*it1,*it2))
254 ++ret;
255 ++it2;
256 }
257 ++it1;
258 }
259 return ret;
260 }
261
262
263 }
Object keeping track of time spent in nested execution blocks, and keeping track of out-of-band messa...
Definition ProgressMonitor.hh:17
The Stopwach class provides a simple interace to allow timing function calls etc.....
Definition Stopwatch.hh:107
Base class for all algorithms, containing generic routines and in particular the logic for index clas...
Definition Algorithm.hh:54
std::pair< sibling_iterator, sibling_iterator > range_t
Finding objects in sets.
Definition Algorithm.hh:170
unsigned int locate_single_object(Ex::iterator obj_to_find, Ex::iterator st, Ex::iterator nd, std::vector< unsigned int > &store)
Definition Algorithm.cc:945
std::vector< range_t > range_vector_t
Definition Algorithm.hh:171
virtual result_t apply(iterator &)=0
void report_progress(const std::string &, int todo, int done, int count=2)
Definition Algorithm.cc:625
bool interrupted
Definition Algorithm.hh:67
void find_argument_lists(range_vector_t &, bool only_comma_lists=true) const
static bool is_factorlike(iterator)
Determines whether the indicated node is 'like a factor in a product'.
Definition Algorithm.cc:841
static unsigned int number_of_direct_indices(iterator it)
Definition Algorithm.cc:1101
bool check_degree_consistency(iterator) const
Given an expression top node, check differential form degree consistency.
Definition Algorithm.cc:536
static bool is_noncommuting(const Properties &, iterator)
Generic function to determine if there is any kind of non-commutativity associated to the given objec...
Definition Algorithm.cc:849
void propagate_zeroes(post_order_iterator &, const iterator &)
Given a node with zero multiplier, propagate this zero upwards in the tree.
Definition Algorithm.cc:322
static bool is_termlike(iterator)
Determines whether the indicated node is 'like a term in a sum'.
Definition Algorithm.cc:829
Ex_set_t dependencies(iterator it, bool include_derivatives_of=true) const
Determine all the Coordinate dependencies of the object at 'it'.
Definition Algorithm.cc:1010
bool derivative_acts_on(iterator it) const
Is this a symbol on which a derivative acts?
Definition Algorithm.cc:1001
bool locate_object_set(const Ex &objs, Ex::iterator st, Ex::iterator nd, std::vector< unsigned int > &store)
Definition Algorithm.cc:965
index_iterator end_index(iterator it) const
Definition Algorithm.cc:519
void node_zero(iterator)
Definition Algorithm.cc:455
bool rename_replacement_dummies(iterator, bool still_inside_algo=false)
Rename the dummies in the sub-tree starting with head at the given iterator.
Definition Algorithm.cc:658
unsigned int intersection_number(sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator, BinaryPredicate) const
Determine the number of elements in the first range which also occur in the second range.
Definition Algorithm.hh:244
unsigned int number_of_calls
Definition Algorithm.hh:93
bool check_consistency(iterator) const
Given an expression top node, check index consistency.
Definition Algorithm.cc:541
result_t apply_generic(bool deep=true, bool repeat=false, unsigned int depth=0)
The main entry points for running algorithms, which traverse the tree post-order ('child before paren...
Definition Algorithm.cc:110
void node_one(iterator)
Definition Algorithm.cc:462
void set_progress_monitor(ProgressMonitor *)
Provide the algorithm with a ProgressMonitor object on which to register (nested) progress informatio...
Definition Algorithm.cc:68
static bool compare_(const str_node &, const str_node &)
Definition Algorithm.cc:1159
bool check_index_consistency(iterator) const
Definition Algorithm.cc:527
Ex::result_t result_t
Definition Algorithm.hh:65
bool traverse_ldots
Definition Algorithm.hh:221
Stopwatch index_sw
Definition Algorithm.hh:106
void node_integer(iterator, int)
Definition Algorithm.cc:469
bool discard_command_node
Definition Algorithm.hh:96
Stopwatch report_progress_stopwatch
Definition Algorithm.hh:108
bool suppress_normal_output
Definition Algorithm.hh:95
range_vector_t::iterator find_arg_superset(range_vector_t &, Iter st, Iter nd)
Definition Algorithm.cc:808
bool contains(sibling_iterator from, sibling_iterator to, sibling_iterator arg)
Definition Algorithm.cc:775
void pushup_multiplier(iterator)
Definition Algorithm.cc:415
index_iterator begin_index(iterator it) const
Definition Algorithm.cc:514
result_t apply_once(Ex::iterator &it)
Definition Algorithm.cc:196
ProgressMonitor * pm
Definition Algorithm.hh:156
result_t apply_deep(Ex::iterator &it)
Definition Algorithm.cc:213
unsigned int number_of_indices(iterator it)
Definition Algorithm.cc:490
unsigned int number_of_modifications
Definition Algorithm.hh:94
std::string get_index_set_name(iterator it) const
Definition Algorithm.cc:501
Stopwatch get_dummy_sw
Definition Algorithm.hh:107
virtual ~Algorithm()
Definition Algorithm.cc:64
bool separated_by_derivative(iterator, iterator, iterator check_dependence) const
Figure out whether two objects (commonly indices) are separated by a derivative operator,...
Definition Algorithm.cc:866
std::set< Ex, tree_exact_less_obj > Ex_set_t
Definition Algorithm.hh:64
virtual bool can_apply(iterator)=0
result_t apply_pre_order(bool repeat=false)
Apply algorithm with alternative traversal: starting from the top node, traverse the tree pre-order (...
Definition Algorithm.cc:73
Definition Storage.hh:170
result_t
Keeping track of what algorithms have done to this expression.
Definition Storage.hh:200
Definition ExManip.hh:9
Ex::post_order_iterator post_order_iterator
Definition ExManip.hh:13
Ex::sibling_iterator sibling_iterator
Definition ExManip.hh:14
Ex::iterator iterator
Definition ExManip.hh:12
Definition Kernel.hh:15
Class holding a collection of properties attached to expressions.
Definition Props.hh:242
An iterator which iterates over indices even if they are at lower levels, i.e.
Definition IndexIterator.hh:20
Elementary building block for a mathematical expression.
Definition Storage.hh:62
Functions to handle the exchange properties of two or more symbols in a product.
Definition Adjform.cc:83
void set(rset_t::iterator &num, multiplier_t fac)
Definition Storage.cc:1179
void fun(int *&p)
Definition passing.cc:6