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 "Compare.hh"
26#include "Props.hh"
27#include "Exceptions.hh"
28#include "Kernel.hh"
29#include "IndexIterator.hh"
30#include "ProgressMonitor.hh"
31#include "IndexClassifier.hh"
32
33#include <map>
34#include <fstream>
35#include <cstddef>
36
37namespace cadabra {
38
58
59 class Algorithm : public IndexClassifier {
60 public:
65
66 Algorithm(const Kernel&, Ex&);
67
68 virtual ~Algorithm();
69
70 typedef Ex::iterator iterator;
71 typedef Ex::post_order_iterator post_order_iterator;
72 typedef Ex::sibling_iterator sibling_iterator;
74
76
79
81
89
90 result_t apply_generic(bool deep=true, bool repeat=false, unsigned int depth=0);
91 result_t apply_generic(iterator&, bool deep, bool repeat, unsigned int depth);
92
97
98 result_t apply_pre_order(bool repeat=false);
99
100 // Global information
101 unsigned int number_of_calls;
105
107 bool check_consistency(iterator) const;
111
112 void report_progress(const std::string&, int todo, int done, int count=2);
113
117
120
121 // The number of indices of a node, taking into account IndexInherit-ance. These
122 // indices do therefore not all have to be direct child nodes of 'it', they can
123 // sit deeper down the tree.
124 unsigned int number_of_indices(iterator it);
125 static unsigned int number_of_indices(const Properties&, iterator it);
126
127 // The number of indices of a node, counting only the direct ones (i.e. not those
128 // inherited from child nodes).
129 static unsigned int number_of_direct_indices(iterator it);
130
131 // The set to which the first index belongs..
132 std::string get_index_set_name(iterator it) const;
133
137 bool rename_replacement_dummies(iterator, bool still_inside_algo=false);
138
143 static bool is_termlike(iterator);
144
147 static bool is_factorlike(iterator);
148
152 static bool is_noncommuting(const Properties&, iterator);
153
154 protected:
155 Ex& tr;
156 ProgressMonitor *pm;
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;
162 virtual result_t 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
173 bool contains(sibling_iterator from, sibling_iterator to, sibling_iterator arg);
174 void find_argument_lists(range_vector_t&, bool only_comma_lists=true) const;
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
189 bool is_single_term(iterator);
190 bool is_nonprod_factor_in_prod(iterator);
191
194 bool prod_wrap_single_term(iterator&);
195 bool prod_unwrap_single_term(iterator&);
196 bool sum_wrap_single_term(iterator&);
197 bool sum_unwrap_single_term(iterator&);
198
204 void force_node_wrap(iterator&, std::string);
205
210 bool separated_by_derivative(iterator, iterator, iterator check_dependence) const;
211
212 // Given a node with non-zero multiplier, distribute this
213 // multiplier up the tree when the node is a \sum node, or push it into the
214 // `\prod` node if that is the parent. Do this recursively
215 // in case a child is a sum as well. Note that 'pushup' is actually 'pushdown'
216 // in the case of sums.
217 // This never changes the tree structure, only the distribution of multipliers.
218
219 // FIXME: this is now superseded by code in Cleanup.cc, and the generic way
220 // to make a tree consistent is to call cleanup_dispatch, not pick-and-match from
221 // the various algorithms.
223
224 // Return the number of elements in the first range for which an identical element
225 // is present in the second range.
226 template<class BinaryPredicate>
228 sibling_iterator, sibling_iterator, BinaryPredicate) const;
229
230 // Turn a node into a '1' or '0' node.
231 void node_zero(iterator);
232 void node_one(iterator);
233 void node_integer(iterator, int);
234
235
236
237 protected:
239
240 private:
241
242 // Single or deep-scan apply operations. Do not call directly.
243 result_t apply_once(Ex::iterator& it);
244 result_t apply_deep(Ex::iterator& it);
245
253
254 // bool cleanup_anomalous_products(Ex& tr, Ex::iterator& it);
255 };
256
257
260 template<class BinaryPredicate>
263 BinaryPredicate fun) const
264 {
265 unsigned int ret=0;
266 sibling_iterator it1=from1;
267 while(it1!=to1) {
268 sibling_iterator it2=from2;
269 while(it2!=to2) {
270 if(fun(*it1,*it2))
271 ++ret;
272 ++it2;
273 }
274 ++it1;
275 }
276 return ret;
277 }
278
279
280 }
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
Ex::iterator iterator
Definition Algorithm.hh:70
Algorithm(const Kernel &, Ex &)
Initialise the algorithm with a reference to the expression tree, but do not yet do anything with thi...
Definition Algorithm.cc:51
void report_progress(const std::string &, int todo, int done, int count=2)
Definition Algorithm.cc:622
bool interrupted
Definition Algorithm.hh:75
static unsigned int number_of_direct_indices(iterator it)
Definition Algorithm.cc:1114
bool check_degree_consistency(iterator) const
Given an expression top node, check differential form degree consistency.
Definition Algorithm.cc:533
void propagate_zeroes(post_order_iterator &, const iterator &)
Given a node with zero multiplier, propagate this zero upwards in the tree.
Definition Algorithm.cc:321
static bool is_termlike(iterator)
Determines whether the indicated node is 'like a term in a sum'.
Definition Algorithm.cc:825
index_iterator end_index(iterator it) const
Definition Algorithm.cc:518
Ex::sibling_iterator sibling_iterator
Definition Algorithm.hh:72
void node_zero(iterator)
Definition Algorithm.cc:454
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:655
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:261
unsigned int number_of_calls
Definition Algorithm.hh:101
bool check_consistency(iterator) const
Given an expression top node, check index consistency.
Definition Algorithm.cc:538
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:109
void node_one(iterator)
Definition Algorithm.cc:461
void set_progress_monitor(ProgressMonitor *)
Provide the algorithm with a ProgressMonitor object on which to register (nested) progress informatio...
Definition Algorithm.cc:67
bool check_index_consistency(iterator) const
Definition Algorithm.cc:526
Ex::result_t result_t
Definition Algorithm.hh:73
bool traverse_ldots
Definition Algorithm.hh:238
Stopwatch index_sw
Definition Algorithm.hh:114
void node_integer(iterator, int)
Definition Algorithm.cc:468
bool discard_command_node
Definition Algorithm.hh:104
Ex::post_order_iterator post_order_iterator
Definition Algorithm.hh:71
Stopwatch report_progress_stopwatch
Definition Algorithm.hh:116
bool suppress_normal_output
Definition Algorithm.hh:103
void pushup_multiplier(iterator)
Determines whether the indicated node is 'like a factor in a product'.
Definition Algorithm.cc:414
index_iterator begin_index(iterator it) const
Definition Algorithm.cc:513
result_t apply_once(Ex::iterator &it)
Definition Algorithm.cc:195
result_t apply_deep(Ex::iterator &it)
Definition Algorithm.cc:212
unsigned int number_of_indices(iterator it)
Definition Algorithm.cc:489
unsigned int number_of_modifications
Definition Algorithm.hh:102
std::string get_index_set_name(iterator it) const
Definition Algorithm.cc:500
Stopwatch get_dummy_sw
Definition Algorithm.hh:115
virtual ~Algorithm()
Definition Algorithm.cc:63
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:72
Basic storage class for symbolic mathemematical expressions.
Definition Storage.hh:165
result_t
Keeping track of what algorithms have done to this expression.
Definition Storage.hh:193
IndexClassifier(const Kernel &)
Definition IndexClassifier.cc:15
Definition Kernel.hh:15
Class holding a collection of properties attached to expressions.
Definition Props.hh:237
An iterator which iterates over indices even if they are at lower levels, i.e.
Definition IndexIterator.hh:16
Elementary building block for a mathematical expression.
Definition Storage.hh:61
Functions to handle the exchange properties of two or more symbols in a product.
Definition Adjform.cc:83
void fun(int *&p)
Definition passing.cc:6