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
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
138
143 static bool is_termlike(iterator);
144
147 static bool is_factorlike(iterator);
148
149
150 protected:
153
154 // The main entry point which is used by the public entry points listed
155 // above. Override these in any subclass.
156 //
157 virtual bool can_apply(iterator)=0;
159
160 // Index stuff
161 int index_parity(iterator) const;
162 static bool less_without_numbers(nset_t::iterator, nset_t::iterator);
163 static bool equal_without_numbers(nset_t::iterator, nset_t::iterator);
164
166 typedef std::pair<sibling_iterator, sibling_iterator> range_t;
167 typedef std::vector<range_t> range_vector_t;
168
171 template<class Iter>
172 range_vector_t::iterator find_arg_superset(range_vector_t&, Iter st, Iter nd);
173 range_vector_t::iterator find_arg_superset(range_vector_t&, sibling_iterator it);
174
175 // Locate objects inside the tree (formerly in the 'locate' algorithm).
176 unsigned int locate_single_object(Ex::iterator obj_to_find,
177 Ex::iterator st, Ex::iterator nd,
178 std::vector<unsigned int>& store);
179 bool locate_object_set(const Ex& objs,
180 Ex::iterator st, Ex::iterator nd,
181 std::vector<unsigned int>& store);
182 static bool compare_(const str_node&, const str_node&);
183
184
193
199 void force_node_wrap(iterator&, std::string);
200
206
207 // Given a node with non-zero multiplier, distribute this
208 // multiplier up the tree when the node is a \sum node, or push it into the
209 // `\prod` node if that is the parent. Do this recursively
210 // in case a child is a sum as well. Note that 'pushup' is actually 'pushdown'
211 // in the case of sums.
212 // This never changes the tree structure, only the distribution of multipliers.
213
214 // FIXME: this is now superseded by code in Cleanup.cc, and the generic way
215 // to make a tree consistent is to call cleanup_dispatch, not pick-and-match from
216 // the various algorithms.
218
219 // Return the number of elements in the first range for which an identical element
220 // is present in the second range.
221 template<class BinaryPredicate>
224
225 // Turn a node into a '1' or '0' node.
226 void node_zero(iterator);
227 void node_one(iterator);
228 void node_integer(iterator, int);
229
230
231
232 protected:
234
235 private:
236
237 // Single or deep-scan apply operations. Do not call directly.
238 result_t apply_once(Ex::iterator& it);
239 result_t apply_deep(Ex::iterator& it);
240
248
249 // bool cleanup_anomalous_products(Ex& tr, Ex::iterator& it);
250 };
251
252
255 template<class BinaryPredicate>
258 BinaryPredicate fun) const
259 {
260 unsigned int ret=0;
262 while(it1!=to1) {
264 while(it2!=to2) {
265 if(fun(*it1,*it2))
266 ++ret;
267 ++it2;
268 }
269 ++it1;
270 }
271 return ret;
272 }
273
274
275 }
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:59
std::pair< sibling_iterator, sibling_iterator > range_t
Finding objects in sets.
Definition Algorithm.hh:166
bool prod_unwrap_single_term(iterator &)
Definition Algorithm.cc:912
unsigned int locate_single_object(Ex::iterator obj_to_find, Ex::iterator st, Ex::iterator nd, std::vector< unsigned int > &store)
Definition Algorithm.cc:1021
void force_node_wrap(iterator &, std::string)
Wrap a term in a product or sum in a node with indicated name, irrespective of its parent (it usually...
Definition Algorithm.cc:897
static bool less_without_numbers(nset_t::iterator, nset_t::iterator)
Definition Algorithm.cc:1105
Ex::iterator iterator
Definition Algorithm.hh:70
std::vector< range_t > range_vector_t
Definition Algorithm.hh:167
virtual result_t apply(iterator &)=0
bool prod_wrap_single_term(iterator &)
Definition Algorithm.cc:879
void report_progress(const std::string &, int todo, int done, int count=2)
Definition Algorithm.cc:618
bool interrupted
Definition Algorithm.hh:75
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:833
int index_parity(iterator) const
Definition Algorithm.cc:472
static unsigned int number_of_direct_indices(iterator it)
Definition Algorithm.cc:1093
bool check_degree_consistency(iterator) const
Given an expression top node, check differential form degree consistency.
Definition Algorithm.cc:529
void propagate_zeroes(post_order_iterator &, const iterator &)
Given a node with zero multiplier, propagate this zero upwards in the tree.
Definition Algorithm.cc:317
static bool is_termlike(iterator)
Determines whether the indicated node is 'like a term in a sum'.
Definition Algorithm.cc:821
bool is_nonprod_factor_in_prod(iterator)
Definition Algorithm.cc:863
bool locate_object_set(const Ex &objs, Ex::iterator st, Ex::iterator nd, std::vector< unsigned int > &store)
Definition Algorithm.cc:1041
index_iterator end_index(iterator it) const
Definition Algorithm.cc:514
Ex::sibling_iterator sibling_iterator
Definition Algorithm.hh:72
void node_zero(iterator)
Definition Algorithm.cc:450
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:651
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:256
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:534
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:105
void node_one(iterator)
Definition Algorithm.cc:457
void set_progress_monitor(ProgressMonitor *)
Provide the algorithm with a ProgressMonitor object on which to register (nested) progress informatio...
Definition Algorithm.cc:63
static bool compare_(const str_node &, const str_node &)
Definition Algorithm.cc:1151
bool check_index_consistency(iterator) const
Definition Algorithm.cc:522
Ex::result_t result_t
Definition Algorithm.hh:73
bool traverse_ldots
Definition Algorithm.hh:233
Stopwatch index_sw
Definition Algorithm.hh:114
void node_integer(iterator, int)
Definition Algorithm.cc:464
bool discard_command_node
Definition Algorithm.hh:104
static bool equal_without_numbers(nset_t::iterator, nset_t::iterator)
Definition Algorithm.cc:1126
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
bool is_single_term(iterator)
Take a single non-product node in a sum and wrap it in a product node, so it can be handled on the sa...
Definition Algorithm.cc:844
range_vector_t::iterator find_arg_superset(range_vector_t &, Iter st, Iter nd)
Definition Algorithm.cc:800
bool contains(sibling_iterator from, sibling_iterator to, sibling_iterator arg)
Definition Algorithm.cc:767
void pushup_multiplier(iterator)
Definition Algorithm.cc:410
Ex & tr
Definition Algorithm.hh:151
bool sum_wrap_single_term(iterator &)
Definition Algorithm.cc:888
index_iterator begin_index(iterator it) const
Definition Algorithm.cc:509
bool sum_unwrap_single_term(iterator &)
Definition Algorithm.cc:927
result_t apply_once(Ex::iterator &it)
Definition Algorithm.cc:191
ProgressMonitor * pm
Definition Algorithm.hh:152
result_t apply_deep(Ex::iterator &it)
Definition Algorithm.cc:208
unsigned int number_of_indices(iterator it)
Definition Algorithm.cc:485
unsigned int number_of_modifications
Definition Algorithm.hh:102
std::string get_index_set_name(iterator it) const
Definition Algorithm.cc:496
Stopwatch get_dummy_sw
Definition Algorithm.hh:115
virtual ~Algorithm()
Definition Algorithm.cc:59
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:942
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:68
Basic storage class for symbolic mathemematical expressions.
Definition Storage.hh:142
result_t
Keeping track of what algorithms have done to this expression.
Definition Storage.hh:168
Definition IndexClassifier.hh:13
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:56
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:1063
void fun(int *&p)
Definition passing.cc:6