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  bool rename_replacement_dummies(iterator, bool still_inside_algo=false);
132 
133 
134 
135  protected:
136  Ex& tr;
138 
139  // The main entry point which is used by the public entry points listed
140  // above. Override these in any subclass.
141  //
142  virtual bool can_apply(iterator)=0;
143  virtual result_t apply(iterator&)=0;
144 
145  // Index stuff
146  int index_parity(iterator) const;
147  static bool less_without_numbers(nset_t::iterator, nset_t::iterator);
148  static bool equal_without_numbers(nset_t::iterator, nset_t::iterator);
149 
151  typedef std::pair<sibling_iterator, sibling_iterator> range_t;
152  typedef std::vector<range_t> range_vector_t;
153 
155  void find_argument_lists(range_vector_t&, bool only_comma_lists=true) const;
156  template<class Iter>
157  range_vector_t::iterator find_arg_superset(range_vector_t&, Iter st, Iter nd);
158  range_vector_t::iterator find_arg_superset(range_vector_t&, sibling_iterator it);
159 
160  // Locate objects inside the tree (formerly in the 'locate' algorithm).
161  unsigned int locate_single_object(Ex::iterator obj_to_find,
162  Ex::iterator st, Ex::iterator nd,
163  std::vector<unsigned int>& store);
164  bool locate_object_set(const Ex& objs,
165  Ex::iterator st, Ex::iterator nd,
166  std::vector<unsigned int>& store);
167  static bool compare_(const str_node&, const str_node&);
168 
169 
171  bool is_termlike(iterator);
172  bool is_factorlike(iterator);
173 
176  bool is_single_term(iterator);
182 
187  void force_node_wrap(iterator&, std::string);
188 
193  bool separated_by_derivative(iterator, iterator, iterator check_dependence) const;
194 
195  // Given a node with non-zero multiplier, distribute this
196  // multiplier up the tree when the node is a \sum node, or push it into the
197  // \prod node if that is the parent. Do this recursively
198  // in case a child is a sum as well. Note that 'pushup' is actually 'pushdown'
199  // in the case of sums.
200  // This never changes the tree structure, only the distribution of multipliers.
201 
202  // FIXME: this is now superseded by code in Cleanup.cc, and the generic way
203  // to make a tree consistent is to call cleanup_dispatch, not pick-and-match from
204  // the various algorithms.
206 
207  // Return the number of elements in the first range for which an identical element
208  // is present in the second range.
209  template<class BinaryPredicate>
211  sibling_iterator, sibling_iterator, BinaryPredicate) const;
212 
213  // Turn a node into a '1' or '0' node.
214  void node_zero(iterator);
215  void node_one(iterator);
216  void node_integer(iterator, int);
217 
218 
219 
220  protected:
222 
223  private:
224 
225  // Single or deep-scan apply operations. Do not call directly.
226  result_t apply_once(Ex::iterator& it);
227  result_t apply_deep(Ex::iterator& it);
228 
236 
237 // bool cleanup_anomalous_products(Ex& tr, Ex::iterator& it);
238 };
239 
240 
243 template<class BinaryPredicate>
246  BinaryPredicate fun) const
247  {
248  unsigned int ret=0;
249  sibling_iterator it1=from1;
250  while(it1!=to1) {
251  sibling_iterator it2=from2;
252  while(it2!=to2) {
253  if(fun(*it1,*it2))
254  ++ret;
255  ++it2;
256  }
257  ++it1;
258  }
259  return ret;
260  }
261 
262 
263 }
void node_one(iterator)
Definition: Algorithm.cc:434
void propagate_zeroes(post_order_iterator &, const iterator &)
Given a node with zero multiplier, propagate this zero upwards in the tree.
Definition: Algorithm.cc:303
Base class for all algorithms, containing generic routines and in particular the logic for index clas...
Definition: Algorithm.hh:59
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:805
Basic storage class for symbolic mathemematical expressions.
Definition: Storage.hh:139
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:66
index_iterator end_index(iterator it) const
Definition: Algorithm.cc:479
bool prod_wrap_single_term(iterator &)
Definition: Algorithm.cc:837
bool sum_wrap_single_term(iterator &)
Definition: Algorithm.cc:846
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:993
bool traverse_ldots
Definition: Algorithm.hh:221
Definition: ProgressMonitor.hh:10
void set_progress_monitor(ProgressMonitor *)
Provide the algorithm with a ProgressMonitor object on which to register (nested) progress informatio...
Definition: Algorithm.cc:61
static bool less_without_numbers(nset_t::iterator, nset_t::iterator)
Definition: Algorithm.cc:1057
static bool equal_without_numbers(nset_t::iterator, nset_t::iterator)
Definition: Algorithm.cc:1078
static bool compare_(const str_node &, const str_node &)
Definition: Algorithm.cc:1103
void find_argument_lists(range_vector_t &, bool only_comma_lists=true) const
bool is_factorlike(iterator)
Definition: Algorithm.cc:793
The Stopwach class provides a simple interace to allow timing function calls etc...
Definition: Stopwatch.hh:107
index_iterator begin_index(iterator it) const
Definition: Algorithm.cc:474
bool rename_replacement_dummies(iterator, bool still_inside_algo=false)
Definition: Algorithm.cc:616
unsigned int locate_single_object(Ex::iterator obj_to_find, Ex::iterator st, Ex::iterator nd, std::vector< unsigned int > &store)
Definition: Algorithm.cc:975
virtual bool can_apply(iterator)=0
bool sum_unwrap_single_term(iterator &)
Definition: Algorithm.cc:883
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 (&#39;child before paren...
Definition: Algorithm.cc:96
std::pair< sibling_iterator, sibling_iterator > range_t
Finding objects in sets.
Definition: Algorithm.hh:151
Stopwatch get_dummy_sw
Definition: Algorithm.hh:115
void fun(int *&p)
Definition: passing.cc:6
void node_integer(iterator, int)
Definition: Algorithm.cc:441
std::vector< range_t > range_vector_t
Definition: Algorithm.hh:152
Elementary building block for a mathematical expression.
Definition: Storage.hh:55
static unsigned int number_of_direct_indices(iterator it)
Definition: Algorithm.cc:1045
bool is_nonprod_factor_in_prod(iterator)
Definition: Algorithm.cc:824
An iterator which iterates over indices even if they are at lower levels, i.e.
Definition: IndexIterator.hh:16
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:244
virtual result_t apply(iterator &)=0
bool is_termlike(iterator)
Determine structure (version-2)
Definition: Algorithm.cc:778
Ex::iterator iterator
Definition: Algorithm.hh:70
Ex::sibling_iterator sibling_iterator
Definition: Algorithm.hh:72
Ex::post_order_iterator post_order_iterator
Definition: Algorithm.hh:71
bool contains(sibling_iterator from, sibling_iterator to, sibling_iterator arg)
Definition: Algorithm.cc:724
result_t apply_deep(Ex::iterator &it)
Definition: Algorithm.cc:197
Stopwatch report_progress_stopwatch
Definition: Algorithm.hh:116
range_vector_t::iterator find_arg_superset(range_vector_t &, Iter st, Iter nd)
Definition: Algorithm.cc:757
bool suppress_normal_output
Definition: Algorithm.hh:103
unsigned int number_of_modifications
Definition: Algorithm.hh:102
Functions to handle the exchange properties of two or more symbols in a product.
Definition: Algorithm.cc:1030
unsigned int number_of_calls
Definition: Algorithm.hh:101
bool discard_command_node
Definition: Algorithm.hh:104
void node_zero(iterator)
Definition: Algorithm.cc:427
bool check_consistency(iterator) const
Given an expression top node, check index consistency.
Definition: Algorithm.cc:499
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:45
void report_progress(const std::string &, int todo, int done, int count=2)
Definition: Algorithm.cc:583
Ex::result_t result_t
Definition: Algorithm.hh:73
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:855
bool interrupted
Definition: Algorithm.hh:75
result_t apply_once(Ex::iterator &it)
Definition: Algorithm.cc:180
Definition: IndexClassifier.hh:13
bool prod_unwrap_single_term(iterator &)
Definition: Algorithm.cc:868
bool separated_by_derivative(iterator, iterator, iterator check_dependence) const
Figure out whether two objects (commonly indices) are separated by a derivative operator, as in .
Definition: Algorithm.cc:898
Definition: Kernel.hh:14
unsigned int number_of_indices(iterator it)
Definition: Algorithm.cc:462
result_t
Keeping track of what algorithms have done to this expression.
Definition: Storage.hh:158
bool check_index_consistency(iterator) const
Definition: Algorithm.cc:487
Ex & tr
Definition: Algorithm.hh:136
bool check_degree_consistency(iterator) const
Given an expression top node, check differential form degree consistency.
Definition: Algorithm.cc:494
ProgressMonitor * pm
Definition: Algorithm.hh:137
Class holding a collection of properties attached to expressions.
Definition: Props.hh:208
int index_parity(iterator) const
Definition: Algorithm.cc:449
void pushup_multiplier(iterator)
Definition: Algorithm.cc:388
virtual ~Algorithm()
Definition: Algorithm.cc:57