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
9 License, or (at your option) any later version.
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 
37 namespace 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;
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  }
cadabra::Algorithm::locate_single_object
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
cadabra::Algorithm::suppress_normal_output
bool suppress_normal_output
Definition: Algorithm.hh:103
Compare.hh
cadabra::Algorithm::number_of_calls
unsigned int number_of_calls
Definition: Algorithm.hh:101
cadabra::Algorithm::get_dummy_sw
Stopwatch get_dummy_sw
Definition: Algorithm.hh:115
cadabra::Algorithm::iterator
Ex::iterator iterator
Definition: Algorithm.hh:70
ProgressMonitor
Definition: ProgressMonitor.hh:10
cadabra::Algorithm::discard_command_node
bool discard_command_node
Definition: Algorithm.hh:104
cadabra::Algorithm::prod_unwrap_single_term
bool prod_unwrap_single_term(iterator &)
Definition: Algorithm.cc:900
cadabra::Algorithm::sum_unwrap_single_term
bool sum_unwrap_single_term(iterator &)
Definition: Algorithm.cc:915
cadabra::Algorithm::check_degree_consistency
bool check_degree_consistency(iterator) const
Given an expression top node, check differential form degree consistency.
Definition: Algorithm.cc:524
cadabra::Algorithm::force_node_wrap
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
cadabra::index_iterator
Definition: IndexIterator.hh:16
cadabra::Kernel
Definition: Kernel.hh:14
cadabra::Algorithm::result_t
Ex::result_t result_t
Definition: Algorithm.hh:73
cadabra::Algorithm::less_without_numbers
static bool less_without_numbers(nset_t::iterator, nset_t::iterator)
Definition: Algorithm.cc:1093
cadabra::Ex::result_t
result_t
Keeping track of what algorithms have done to this expression.
Definition: Storage.hh:159
IndexIterator.hh
cadabra::Algorithm::apply
virtual result_t apply(iterator &)=0
cadabra::IndexClassifier
Definition: IndexClassifier.hh:13
cadabra::Algorithm::locate_object_set
bool locate_object_set(const Ex &objs, Ex::iterator st, Ex::iterator nd, std::vector< unsigned int > &store)
Definition: Algorithm.cc:1029
cadabra::Algorithm::is_nonprod_factor_in_prod
bool is_nonprod_factor_in_prod(iterator)
Definition: Algorithm.cc:854
cadabra::Algorithm::contains
bool contains(sibling_iterator from, sibling_iterator to, sibling_iterator arg)
Definition: Algorithm.cc:757
cadabra::Algorithm::number_of_indices
unsigned int number_of_indices(iterator it)
Definition: Algorithm.cc:480
cadabra::Algorithm::get_index_set_name
std::string get_index_set_name(iterator it) const
Definition: Algorithm.cc:491
cadabra::Algorithm::traverse_ldots
bool traverse_ldots
Definition: Algorithm.hh:231
cadabra::Algorithm::check_consistency
bool check_consistency(iterator) const
Given an expression top node, check index consistency.
Definition: Algorithm.cc:529
cadabra::Algorithm::node_zero
void node_zero(iterator)
Definition: Algorithm.cc:445
Stopwatch
Definition: Stopwatch.hh:107
Exceptions.hh
cadabra::Algorithm::begin_index
index_iterator begin_index(iterator it) const
Definition: Algorithm.cc:504
cadabra::Algorithm::post_order_iterator
Ex::post_order_iterator post_order_iterator
Definition: Algorithm.hh:71
ProgressMonitor.hh
cadabra::Algorithm::compare_
static bool compare_(const str_node &, const str_node &)
Definition: Algorithm.cc:1139
cadabra::Algorithm::report_progress
void report_progress(const std::string &, int todo, int done, int count=2)
Definition: Algorithm.cc:613
cadabra::Algorithm::number_of_direct_indices
static unsigned int number_of_direct_indices(iterator it)
Definition: Algorithm.cc:1081
cadabra::Algorithm::intersection_number
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
cadabra::Algorithm::find_argument_lists
void find_argument_lists(range_vector_t &, bool only_comma_lists=true) const
cadabra::Algorithm::~Algorithm
virtual ~Algorithm()
Definition: Algorithm.cc:58
Stopwatch.hh
cadabra::Algorithm
Definition: Algorithm.hh:59
cadabra::Algorithm::node_one
void node_one(iterator)
Definition: Algorithm.cc:452
cadabra::Algorithm::Algorithm
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
cadabra::Algorithm::apply_pre_order
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
cadabra::Algorithm::apply_once
result_t apply_once(Ex::iterator &it)
Definition: Algorithm.cc:196
cadabra::Algorithm::apply_generic
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
cadabra::Algorithm::rename_replacement_dummies
bool rename_replacement_dummies(iterator, bool still_inside_algo=false)
Definition: Algorithm.cc:646
cadabra::Algorithm::index_parity
int index_parity(iterator) const
Definition: Algorithm.cc:467
cadabra::Algorithm::separated_by_derivative
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
cadabra::Algorithm::report_progress_stopwatch
Stopwatch report_progress_stopwatch
Definition: Algorithm.hh:116
cadabra::Algorithm::is_factorlike
bool is_factorlike(iterator)
Determines whether the indicated node is 'like a factor in a product'.
Definition: Algorithm.cc:823
cadabra::Algorithm::propagate_zeroes
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
cadabra::Algorithm::range_vector_t
std::vector< range_t > range_vector_t
Definition: Algorithm.hh:155
cadabra::Ex
Definition: Storage.hh:140
cadabra::Algorithm::can_apply
virtual bool can_apply(iterator)=0
cadabra::Algorithm::set_progress_monitor
void set_progress_monitor(ProgressMonitor *)
Provide the algorithm with a ProgressMonitor object on which to register (nested) progress informatio...
Definition: Algorithm.cc:62
cadabra::Algorithm::check_index_consistency
bool check_index_consistency(iterator) const
Definition: Algorithm.cc:517
cadabra::Algorithm::is_single_term
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
cadabra
Functions to handle the exchange properties of two or more symbols in a product.
Definition: Adjform.cc:80
cadabra::Algorithm::sum_wrap_single_term
bool sum_wrap_single_term(iterator &)
Definition: Algorithm.cc:876
Props.hh
cadabra::Algorithm::pm
ProgressMonitor * pm
Definition: Algorithm.hh:140
cadabra::Algorithm::end_index
index_iterator end_index(iterator it) const
Definition: Algorithm.cc:509
cadabra::Properties
Definition: Props.hh:233
fun
void fun(int *&p)
Definition: passing.cc:6
cadabra::Algorithm::prod_wrap_single_term
bool prod_wrap_single_term(iterator &)
Definition: Algorithm.cc:867
cadabra::Algorithm::tr
Ex & tr
Definition: Algorithm.hh:139
cadabra::str_node
Definition: Storage.hh:55
cadabra::Algorithm::node_integer
void node_integer(iterator, int)
Definition: Algorithm.cc:459
cadabra::Algorithm::equal_without_numbers
static bool equal_without_numbers(nset_t::iterator, nset_t::iterator)
Definition: Algorithm.cc:1114
cadabra::Algorithm::number_of_modifications
unsigned int number_of_modifications
Definition: Algorithm.hh:102
Kernel.hh
IndexClassifier.hh
cadabra::Algorithm::sibling_iterator
Ex::sibling_iterator sibling_iterator
Definition: Algorithm.hh:72
cadabra::Algorithm::pushup_multiplier
void pushup_multiplier(iterator)
Definition: Algorithm.cc:406
cadabra::Algorithm::index_sw
Stopwatch index_sw
Definition: Algorithm.hh:114
cadabra::Algorithm::apply_deep
result_t apply_deep(Ex::iterator &it)
Definition: Algorithm.cc:213
cadabra::Algorithm::is_termlike
bool is_termlike(iterator)
Determines whether the indicated node is 'like a term in a sum'.
Definition: Algorithm.cc:811
cadabra::Algorithm::interrupted
bool interrupted
Definition: Algorithm.hh:75
cadabra::Algorithm::find_arg_superset
range_vector_t::iterator find_arg_superset(range_vector_t &, Iter st, Iter nd)
Definition: Algorithm.cc:790
cadabra::Algorithm::range_t
std::pair< sibling_iterator, sibling_iterator > range_t
Finding objects in sets.
Definition: Algorithm.hh:154