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
134  bool rename_replacement_dummies(iterator, bool still_inside_algo=false);
135
136
137
138  protected:
139  Ex& tr;
141
142  // The main entry point which is used by the public entry points listed
143  // above. Override these in any subclass.
144  //
145  virtual bool can_apply(iterator)=0;
146  virtual result_t apply(iterator&)=0;
147
148  // Index stuff
149  int index_parity(iterator) const;
150  static bool less_without_numbers(nset_t::iterator, nset_t::iterator);
151  static bool equal_without_numbers(nset_t::iterator, nset_t::iterator);
152
154  typedef std::pair<sibling_iterator, sibling_iterator> range_t;
155  typedef std::vector<range_t> range_vector_t;
156
158  void find_argument_lists(range_vector_t&, bool only_comma_lists=true) const;
159  template<class Iter>
160  range_vector_t::iterator find_arg_superset(range_vector_t&, Iter st, Iter nd);
161  range_vector_t::iterator find_arg_superset(range_vector_t&, sibling_iterator it);
162
163  // Locate objects inside the tree (formerly in the 'locate' algorithm).
164  unsigned int locate_single_object(Ex::iterator obj_to_find,
165  Ex::iterator st, Ex::iterator nd,
166  std::vector<unsigned int>& store);
167  bool locate_object_set(const Ex& objs,
168  Ex::iterator st, Ex::iterator nd,
169  std::vector<unsigned int>& store);
170  static bool compare_(const str_node&, const str_node&);
171
172
177  bool is_termlike(iterator);
178
181  bool is_factorlike(iterator);
182
185  bool is_single_term(iterator);
191
197  void force_node_wrap(iterator&, std::string);
198
203  bool separated_by_derivative(iterator, iterator, iterator check_dependence) const;
204
205  // Given a node with non-zero multiplier, distribute this
206  // multiplier up the tree when the node is a \sum node, or push it into the
207  // \prod node if that is the parent. Do this recursively
208  // in case a child is a sum as well. Note that 'pushup' is actually 'pushdown'
209  // in the case of sums.
210  // This never changes the tree structure, only the distribution of multipliers.
211
212  // FIXME: this is now superseded by code in Cleanup.cc, and the generic way
213  // to make a tree consistent is to call cleanup_dispatch, not pick-and-match from
214  // the various algorithms.
216
217  // Return the number of elements in the first range for which an identical element
218  // is present in the second range.
219  template<class BinaryPredicate>
221  sibling_iterator, sibling_iterator, BinaryPredicate) const;
222
223  // Turn a node into a '1' or '0' node.
224  void node_zero(iterator);
225  void node_one(iterator);
226  void node_integer(iterator, int);
227
228
229
230  protected:
232
233  private:
234
235  // Single or deep-scan apply operations. Do not call directly.
236  result_t apply_once(Ex::iterator& it);
237  result_t apply_deep(Ex::iterator& it);
238
246
247  // bool cleanup_anomalous_products(Ex& tr, Ex::iterator& it);
248  };
249
250
253  template<class BinaryPredicate>
256  BinaryPredicate fun) const
257  {
258  unsigned int ret=0;
259  sibling_iterator it1=from1;
260  while(it1!=to1) {
261  sibling_iterator it2=from2;
262  while(it2!=to2) {
263  if(fun(*it1,*it2))
264  ++ret;
265  ++it2;
266  }
267  ++it1;
268  }
269  return ret;
270  }
271
272
273  }
unsigned int locate_single_object(Ex::iterator obj_to_find, Ex::iterator st, Ex::iterator nd, std::vector< unsigned int > &store)
Definition: Algorithm.cc:1009
Storage.hh
bool suppress_normal_output
Definition: Algorithm.hh:103
Compare.hh
unsigned int number_of_calls
Definition: Algorithm.hh:101
Stopwatch get_dummy_sw
Definition: Algorithm.hh:115
Ex::iterator iterator
Definition: Algorithm.hh:70
ProgressMonitor
Definition: ProgressMonitor.hh:10
Definition: Algorithm.hh:104
bool prod_unwrap_single_term(iterator &)
Definition: Algorithm.cc:900
bool sum_unwrap_single_term(iterator &)
Definition: Algorithm.cc:915
bool check_degree_consistency(iterator) const
Given an expression top node, check differential form degree consistency.
Definition: Algorithm.cc:524
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:885
Definition: IndexIterator.hh:16
Definition: Kernel.hh:14
Ex::result_t result_t
Definition: Algorithm.hh:73
static bool less_without_numbers(nset_t::iterator, nset_t::iterator)
Definition: Algorithm.cc:1093
result_t
Keeping track of what algorithms have done to this expression.
Definition: Storage.hh:159
IndexIterator.hh
virtual result_t apply(iterator &)=0
Definition: IndexClassifier.hh:13
bool locate_object_set(const Ex &objs, Ex::iterator st, Ex::iterator nd, std::vector< unsigned int > &store)
Definition: Algorithm.cc:1029
bool is_nonprod_factor_in_prod(iterator)
Definition: Algorithm.cc:854
bool contains(sibling_iterator from, sibling_iterator to, sibling_iterator arg)
Definition: Algorithm.cc:757
unsigned int number_of_indices(iterator it)
Definition: Algorithm.cc:480
std::string get_index_set_name(iterator it) const
Definition: Algorithm.cc:491
bool traverse_ldots
Definition: Algorithm.hh:231
bool check_consistency(iterator) const
Given an expression top node, check index consistency.
Definition: Algorithm.cc:529
void node_zero(iterator)
Definition: Algorithm.cc:445
Stopwatch
Definition: Stopwatch.hh:107
Exceptions.hh
index_iterator begin_index(iterator it) const
Definition: Algorithm.cc:504
Ex::post_order_iterator post_order_iterator
Definition: Algorithm.hh:71
ProgressMonitor.hh
static bool compare_(const str_node &, const str_node &)
Definition: Algorithm.cc:1139
void report_progress(const std::string &, int todo, int done, int count=2)
Definition: Algorithm.cc:613
static unsigned int number_of_direct_indices(iterator it)
Definition: Algorithm.cc:1081
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:254
void find_argument_lists(range_vector_t &, bool only_comma_lists=true) const
virtual ~Algorithm()
Definition: Algorithm.cc:58
Stopwatch.hh
Definition: Algorithm.hh:59
void node_one(iterator)
Definition: Algorithm.cc:452
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:46
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:67
result_t apply_once(Ex::iterator &it)
Definition: Algorithm.cc:196
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:107
bool rename_replacement_dummies(iterator, bool still_inside_algo=false)
Definition: Algorithm.cc:646
int index_parity(iterator) const
Definition: Algorithm.cc:467
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:930
Stopwatch report_progress_stopwatch
Definition: Algorithm.hh:116
bool is_factorlike(iterator)
Determines whether the indicated node is 'like a factor in a product'.
Definition: Algorithm.cc:823
void propagate_zeroes(post_order_iterator &, const iterator &)
Given a node with zero multiplier, propagate this zero upwards in the tree.
Definition: Algorithm.cc:320
std::vector< range_t > range_vector_t
Definition: Algorithm.hh:155
Definition: Storage.hh:140
virtual bool can_apply(iterator)=0
void set_progress_monitor(ProgressMonitor *)
Provide the algorithm with a ProgressMonitor object on which to register (nested) progress informatio...
Definition: Algorithm.cc:62
bool check_index_consistency(iterator) const
Definition: Algorithm.cc:517
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:835
Functions to handle the exchange properties of two or more symbols in a product.
bool sum_wrap_single_term(iterator &)
Definition: Algorithm.cc:876
Props.hh
ProgressMonitor * pm
Definition: Algorithm.hh:140
index_iterator end_index(iterator it) const
Definition: Algorithm.cc:509
Definition: Props.hh:233
fun
void fun(int *&p)
Definition: passing.cc:6
bool prod_wrap_single_term(iterator &)
Definition: Algorithm.cc:867
Ex & tr
Definition: Algorithm.hh:139
Definition: Storage.hh:55
void node_integer(iterator, int)
Definition: Algorithm.cc:459
static bool equal_without_numbers(nset_t::iterator, nset_t::iterator)
Definition: Algorithm.cc:1114
unsigned int number_of_modifications
Definition: Algorithm.hh:102
Kernel.hh
IndexClassifier.hh
Ex::sibling_iterator sibling_iterator
Definition: Algorithm.hh:72
void pushup_multiplier(iterator)
Definition: Algorithm.cc:406
Stopwatch index_sw
Definition: Algorithm.hh:114
result_t apply_deep(Ex::iterator &it)
Definition: Algorithm.cc:213