Cadabra Computer algebra system for field theory problems
Algorithm.hh
Go to the documentation of this file.
1 /*
2
3 Cadabra: a field-theory motivated computer algebra system.
4 Copyright (C) 2001-2014 Kasper Peeters <kasper.peeters@phi-sci.com>
5
6 This program is free software: you can redistribute it and/or
7  modify it under the terms of the GNU General Public License as
8 published by the Free Software Foundation, either version 3 of the
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along 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
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;
108  bool check_index_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
149
150  protected:
151  Ex& tr;
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;
158  virtual result_t 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
170  void find_argument_lists(range_vector_t&, bool only_comma_lists=true) const;
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
187  bool is_single_term(iterator);
193
199  void force_node_wrap(iterator&, std::string);
200
205  bool separated_by_derivative(iterator, iterator, iterator check_dependence) const;
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>
223  sibling_iterator, sibling_iterator, BinaryPredicate) const;
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;
261  sibling_iterator it1=from1;
262  while(it1!=to1) {
263  sibling_iterator it2=from2;
264  while(it2!=to2) {
265  if(fun(*it1,*it2))
266  ++ret;
267  ++it2;
268  }
269  ++it1;
270  }
271  return ret;
272  }
273
274
275  }
Ex::sibling_iterator sibling_iterator
Definition: Algorithm.hh:72
bool sum_wrap_single_term(iterator &)
Definition: Algorithm.cc:883
void node_zero(iterator)
Definition: Algorithm.cc:445
bool check_degree_consistency(iterator) const
Given an expression top node, check differential form degree consistency.
Definition: Algorithm.cc:524
void pushup_multiplier(iterator)
Definition: Algorithm.cc:405
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:839
Exceptions.hh
Stopwatch report_progress_stopwatch
Definition: Algorithm.hh:116
Definition: IndexIterator.hh:16
unsigned int number_of_indices(iterator it)
Definition: Algorithm.cc:480
Definition: Kernel.hh:15
static unsigned int number_of_direct_indices(iterator it)
Definition: Algorithm.cc:1088
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
std::string get_index_set_name(iterator it) const
Definition: Algorithm.cc:491
virtual bool can_apply(iterator)=0
std::vector< range_t > range_vector_t
Definition: Algorithm.hh:167
void find_argument_lists(range_vector_t &, bool only_comma_lists=true) const
Stopwatch.hh
result_t apply_once(Ex::iterator &it)
Definition: Algorithm.cc:191
void node_one(iterator)
Definition: Algorithm.cc:452
Definition: Props.hh:234
bool sum_unwrap_single_term(iterator &)
Definition: Algorithm.cc:922
void node_integer(iterator, int)
Definition: Algorithm.cc:459
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:937
bool check_index_consistency(iterator) const
Definition: Algorithm.cc:517
ProgressMonitor
Definition: ProgressMonitor.hh:17
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
index_iterator end_index(iterator it) const
Definition: Algorithm.cc:509
unsigned int locate_single_object(Ex::iterator obj_to_find, Ex::iterator st, Ex::iterator nd, std::vector< unsigned int > &store)
Definition: Algorithm.cc:1016
static bool less_without_numbers(nset_t::iterator, nset_t::iterator)
Definition: Algorithm.cc:1100
IndexClassifier.hh
unsigned int number_of_calls
Definition: Algorithm.hh:101
Storage.hh
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:47
bool suppress_normal_output
Definition: Algorithm.hh:103
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
Compare.hh
IndexIterator.hh
result_t apply_deep(Ex::iterator &it)
Definition: Algorithm.cc:208
static bool is_factorlike(iterator)
Determines whether the indicated node is 'like a factor in a product'.
Definition: Algorithm.cc:828
unsigned int number_of_modifications
Definition: Algorithm.hh:102
bool contains(sibling_iterator from, sibling_iterator to, sibling_iterator arg)
Definition: Algorithm.cc:762
Definition: Algorithm.hh:104
bool check_consistency(iterator) const
Given an expression top node, check index consistency.
Definition: Algorithm.cc:529
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:892
Props.hh
void report_progress(const std::string &, int todo, int done, int count=2)
Definition: Algorithm.cc:613
bool interrupted
Definition: Algorithm.hh:75
static bool equal_without_numbers(nset_t::iterator, nset_t::iterator)
Definition: Algorithm.cc:1121
Ex::iterator iterator
Definition: Algorithm.hh:70
Ex::post_order_iterator post_order_iterator
Definition: Algorithm.hh:71
range_vector_t::iterator find_arg_superset(range_vector_t &, Iter st, Iter nd)
Definition: Algorithm.cc:795
void set_progress_monitor(ProgressMonitor *)
Provide the algorithm with a ProgressMonitor object on which to register (nested) progress informatio...
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:68
Definition: Algorithm.hh:59
index_iterator begin_index(iterator it) const
Definition: Algorithm.cc:504
Ex::result_t result_t
Definition: Algorithm.hh:73
Functions to handle the exchange properties of two or more symbols in a product.
Definition: Storage.hh:141
bool prod_wrap_single_term(iterator &)
Definition: Algorithm.cc:874
Stopwatch index_sw
Definition: Algorithm.hh:114
bool locate_object_set(const Ex &objs, Ex::iterator st, Ex::iterator nd, std::vector< unsigned int > &store)
Definition: Algorithm.cc:1036
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:646
bool prod_unwrap_single_term(iterator &)
Definition: Algorithm.cc:907
std::pair< sibling_iterator, sibling_iterator > range_t
Finding objects in sets.
Definition: Algorithm.hh:166
fun
void fun(int *&p)
Definition: passing.cc:6
Definition: Storage.hh:56
result_t
Keeping track of what algorithms have done to this expression.
Definition: Storage.hh:160
Definition: IndexClassifier.hh:13
Ex & tr
Definition: Algorithm.hh:151
bool traverse_ldots
Definition: Algorithm.hh:233
Stopwatch get_dummy_sw
Definition: Algorithm.hh:115
int index_parity(iterator) const
Definition: Algorithm.cc:467
Kernel.hh
virtual result_t apply(iterator &)=0
static bool compare_(const str_node &, const str_node &)
Definition: Algorithm.cc:1146
static bool is_termlike(iterator)
Determines whether the indicated node is 'like a term in a sum'.
Definition: Algorithm.cc:816