Cadabra
Computer algebra system for field theory problems
Storage.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 <cstddef>
24 #include <iostream>
25 #include <gmpxx.h>
26 #include <string>
27 #include <vector>
28 #include <set>
29 #include <map>
30 #include <stdint.h>
31 #include <assert.h>
32 #include <initializer_list>
33 
34 #include "tree.hh"
35 
36 namespace cadabra {
37 
38  typedef mpq_class multiplier_t;
39  typedef std::set<std::string> nset_t;
40  typedef std::set<multiplier_t> rset_t;
41  typedef uintptr_t hashval_t;
42 
43  long to_long(multiplier_t);
44  std::string to_string(long);
45 
46  extern nset_t name_set;
47  extern rset_t rat_set;
48 
54 
55  class str_node { // size: 9 bytes (32 bit arch), can be reduced to 5 bytes.
56  public:
58 
62 
63  str_node(void);
64  str_node(nset_t::iterator name, bracket_t btype=b_none, parent_rel_t ptype=p_none);
65  str_node(const std::string& name, bracket_t btype=b_none, parent_rel_t ptype=p_none);
66  str_node(const std::u32string& name, bracket_t btype=b_none, parent_rel_t ptype=p_none);
67 
68  bool operator==(const str_node&) const;
69  bool operator<(const str_node&) const;
70 
71  nset_t::iterator name;
72  rset_t::iterator multiplier;
73 
74 #ifdef _WIN32
75  struct flag_t {
76  bool keep_after_eval ;
79  bool line_per_node ;
80  };
81 #else
82  struct flag_t { // kept inside 8 bits for speed and size
83  bool keep_after_eval : 1;
86  bool line_per_node : 1;
87  };
88 #endif
89 
91 
94  void flip_parent_rel();
95 
96  bool is_zero() const;
97  bool is_identity() const;
98  bool is_rational() const;
99  bool is_unsimplified_rational() const;
100  bool is_integer() const;
101  bool is_unsimplified_integer() const;
102  bool is_index() const; // _ or ^ parent_rel (does not query properties)
103  bool is_quoted_string() const;
104  bool is_command() const;
105  bool is_inert_command() const;
106  bool is_name_wildcard() const; // ?
107  bool is_object_wildcard() const; // ??
108  bool is_range_wildcard() const; // #{..}
109  bool is_siblings_wildcard() const; // a...
110  bool is_autodeclare_wildcard() const; // m#
111  bool is_indexstar_wildcard() const; // ?* in sub/super
112  bool is_indexplus_wildcard() const; // ?+ in sub/super
113  bool is_numbered_symbol() const; // [a-zA-Z]+[0-9]+
114 
115  nset_t::iterator name_only();
116 
117  static bool compare_names_only(const str_node&, const str_node&);
118  static bool compare_name_brack_par(const str_node&, const str_node&);
119  static bool compare_name_inverse_par(const str_node&, const str_node&);
120  };
121 
125  void multiply(rset_t::iterator&, multiplier_t);
126  void add(rset_t::iterator&, multiplier_t);
127  void zero(rset_t::iterator&);
128  void one(rset_t::iterator&);
129  void flip_sign(rset_t::iterator&);
130  void half(rset_t::iterator&);
131 
139 
140  class Ex : public std::enable_shared_from_this<Ex>, public tree<str_node> {
141  public:
142  Ex();
143  // Ex(const tree<str_node>&);
144  Ex(tree<str_node>::iterator);
145  Ex(const str_node&);
146  Ex(const Ex&);
148  Ex(const std::string&);
149  Ex(int);
150 
158 
160  result_t state() const;
161  void update_state(result_t);
162  void reset_state();
163 
168  bool changed_state();
169 
172  bool is_rational() const;
173  multiplier_t to_rational() const;
174  bool is_integer() const;
175  long to_integer() const;
176 
180  static std::ostream& print_python(std::ostream& str, Ex::iterator it);
181 
183  std::ostream& print_entire_tree(std::ostream& str) const;
184  static std::ostream& print_recursive_treeform(std::ostream& str, Ex::iterator it);
185  static std::ostream& print_recursive_treeform(std::ostream& str, Ex::iterator it, unsigned int& number);
186 
188  std::ostream& print_repr(std::ostream& str, Ex::iterator it) const;
189 
191  iterator named_parent(iterator it, const std::string&) const;
192  iterator erase_expression(iterator it);
193 
195  hashval_t calc_hash(iterator it) const;
196 
198  static sibling_iterator arg(iterator, unsigned int);
199  static unsigned int arg_size(sibling_iterator);
200 
201  multiplier_t arg_to_num(sibling_iterator, unsigned int) const; // shorthand for numerical arguments
202 
203  // Like 'child', but using index iterators instead.
204  // sibling_iterator tensor_index(const iterator_base& position, unsigned int) const;
205 
206  // Number of \\history nodes in an expression
207  unsigned int number_of_steps(iterator it) const;
208  // Given an iterator pointing to any node in the tree, figure
209  // out to which equation number it belongs.
210  unsigned int number_of_equations() const;
211  unsigned int equation_number(iterator it) const;
212  nset_t::iterator equation_label(iterator it) const;
213  iterator equation_by_number(unsigned int i) const;
214  iterator equation_by_name(nset_t::iterator it) const;
215  iterator equation_by_name(nset_t::iterator it, unsigned int& ) const;
216  iterator equation_by_number_or_name(iterator it, unsigned int last_used_equation) const;
217  iterator equation_by_number_or_name(iterator it, unsigned int last_used_equation,
218  unsigned int&) const;
219  std::string equation_number_or_name(iterator it, unsigned int last_used_equation) const;
220  iterator procedure_by_name(nset_t::iterator it) const;
221 
222  // Determine whether a node has an '\ldots' parent (not necessarily direct).
223  bool is_hidden(iterator) const;
224 
236  iterator replace_index(iterator position, const iterator& from, bool keep_parent_rel=false);
237 
240  iterator move_index(iterator position, const iterator& from);
241 
245  void list_wrap_single_element(iterator&);
246  void list_unwrap_single_element(iterator&);
247 
252  iterator flatten_and_erase(iterator position);
253 
256 
257  bool operator==(const Ex& other) const;
258 
263  void push_history(const std::vector<Ex::path_t>&);
264 
268  std::vector<Ex::path_t> pop_history();
269 
272  int history_size() const;
273 
274  private:
276 
277  std::vector<tree<str_node> > history;
279  std::vector<std::vector<Ex::path_t> > terms;
280  };
281 
282 
286 
287  class nset_it_less {
288  public:
289  bool operator()(nset_t::iterator first, nset_t::iterator second) const;
290  };
291 
292  template <typename T>
293  bool is_in(const T& val, const std::initializer_list<T>& list)
294  {
295  for (const auto& i : list) {
296  if (val == i) {
297  return true;
298  }
299  }
300  return false;
301  }
302 
303  }
304 
312 
313 std::ostream& operator<<(std::ostream&, const cadabra::Ex&);
314 std::ostream& operator<<(std::ostream&, cadabra::Ex::iterator);
cadabra::str_node::flag_t::keep_after_eval
bool keep_after_eval
Definition: Storage.hh:83
cadabra::str_node::is_integer
bool is_integer() const
Definition: Storage.cc:795
cadabra::str_node::b_square
@ b_square
Definition: Storage.hh:57
cadabra::nset_it_less::operator()
bool operator()(nset_t::iterator first, nset_t::iterator second) const
Definition: Storage.cc:993
cadabra::str_node::compare_names_only
static bool compare_names_only(const str_node &, const str_node &)
Definition: Storage.cc:970
cadabra::str_node::p_components
@ p_components
Definition: Storage.hh:61
cadabra::str_node::is_name_wildcard
bool is_name_wildcard() const
Definition: Storage.cc:862
cadabra::Ex::changed_state
bool changed_state()
A status query method mainly to implement a simple method to apply algorithms until they converge.
Definition: Storage.cc:112
cadabra::str_node::compare_name_inverse_par
static bool compare_name_inverse_par(const str_node &, const str_node &)
Definition: Storage.cc:984
cadabra::Ex::list_unwrap_single_element
void list_unwrap_single_element(iterator &)
Definition: Storage.cc:615
cadabra::Ex::pop_history
std::vector< Ex::path_t > pop_history()
Pop the most recent state of the expression off the history stack; returns the set of paths that we a...
Definition: Storage.cc:707
cadabra::Ex::is_integer
bool is_integer() const
Definition: Storage.cc:135
cadabra::Ex::equation_label
nset_t::iterator equation_label(iterator it) const
Definition: Storage.cc:465
cadabra::Ex::terms
std::vector< std::vector< Ex::path_t > > terms
Patterns which describe how to get from one history step to the next.
Definition: Storage.hh:279
cadabra::rset_t
std::set< multiplier_t > rset_t
Definition: Storage.hh:40
cadabra::flip_sign
void flip_sign(rset_t::iterator &num)
Definition: Storage.cc:1025
cadabra::str_node::p_none
@ p_none
Definition: Storage.hh:61
cadabra::Ex::number_of_steps
unsigned int number_of_steps(iterator it) const
cadabra::Ex::push_history
void push_history(const std::vector< Ex::path_t > &)
Push a copy of the current state of the expression onto the history stack.
Definition: Storage.cc:701
cadabra::Ex::calc_hash
hashval_t calc_hash(iterator it) const
Calculate the hash value for the subtree starting at 'it'.
Definition: Storage.cc:398
cadabra::Ex::move_index
iterator move_index(iterator position, const iterator &from)
As in replace_index, but moves the index rather than making a copy (so that iterators pointing to the...
Definition: Storage.cc:593
cadabra::str_node::str_node
str_node(void)
Definition: Storage.cc:721
cadabra::str_node::operator==
bool operator==(const str_node &) const
Definition: Storage.cc:960
cadabra::str_node::is_command
bool is_command() const
Definition: Storage.cc:840
cadabra::str_node::is_autodeclare_wildcard
bool is_autodeclare_wildcard() const
Definition: Storage.cc:902
cadabra::Ex::equation_by_number
iterator equation_by_number(unsigned int i) const
Definition: Storage.cc:502
cadabra::str_node::b_invalid
@ b_invalid
Definition: Storage.hh:57
cadabra::Ex::equation_number_or_name
std::string equation_number_or_name(iterator it, unsigned int last_used_equation) const
Definition: Storage.cc:676
cadabra::str_node::p_property
@ p_property
Definition: Storage.hh:61
cadabra::str_node::p_exponent
@ p_exponent
Definition: Storage.hh:61
cadabra::Ex::l_applied
@ l_applied
Definition: Storage.hh:159
cadabra::Ex::update_state
void update_state(result_t)
Definition: Storage.cc:92
cadabra::Ex::equation_number
unsigned int equation_number(iterator it) const
Definition: Storage.cc:444
cadabra::str_node::p_invalid
@ p_invalid
Definition: Storage.hh:61
cadabra::to_long
long to_long(multiplier_t mul)
Definition: Storage.cc:39
cadabra::str_node::b_pointy
@ b_pointy
Definition: Storage.hh:57
cadabra::str_node::b_round
@ b_round
Definition: Storage.hh:57
cadabra::str_node::flag_t::parent_rel
parent_rel_t parent_rel
Definition: Storage.hh:85
cadabra::str_node::is_inert_command
bool is_inert_command() const
Definition: Storage.cc:853
cadabra::str_node::flag_t::line_per_node
bool line_per_node
Definition: Storage.hh:86
cadabra::str_node::flip_parent_rel
void flip_parent_rel()
Change the parent relation from sub to super and vice versa (throws error when this is not an index).
Definition: Storage.cc:771
cadabra::Ex::procedure_by_name
iterator procedure_by_name(nset_t::iterator it) const
Definition: Storage.cc:561
cadabra::str_node::is_zero
bool is_zero() const
Definition: Storage.cc:778
cadabra::str_node::fl
flag_t fl
Definition: Storage.hh:90
cadabra::str_node::b_no
@ b_no
Definition: Storage.hh:57
cadabra::str_node::is_index
bool is_index() const
Definition: Storage.cc:824
cadabra::str_node::is_rational
bool is_rational() const
Definition: Storage.cc:790
cadabra::str_node::p_sub
@ p_sub
Definition: Storage.hh:61
cadabra::str_node::operator<
bool operator<(const str_node &) const
Definition: Storage.cc:1039
cadabra::Ex::history
std::vector< tree< str_node > > history
Definition: Storage.hh:277
cadabra::nset_t
std::set< std::string > nset_t
Definition: Storage.hh:39
cadabra::Ex::arg_size
static unsigned int arg_size(sibling_iterator)
Definition: Storage.cc:430
cadabra::str_node::is_indexplus_wildcard
bool is_indexplus_wildcard() const
Definition: Storage.cc:919
cadabra::str_node::flag_t::bracket
bracket_t bracket
Definition: Storage.hh:84
cadabra::Ex::is_hidden
bool is_hidden(iterator) const
Definition: Storage.cc:550
cadabra::Ex::Ex
Ex()
Definition: Storage.cc:53
cadabra::Ex::to_integer
long to_integer() const
Definition: Storage.cc:143
cadabra::Ex::reset_state
void reset_state()
Definition: Storage.cc:107
cadabra::add
void add(rset_t::iterator &num, multiplier_t fac)
Definition: Storage.cc:1008
cadabra::str_node::is_numbered_symbol
bool is_numbered_symbol() const
Definition: Storage.cc:928
cadabra::Ex::history_size
int history_size() const
Return the size of the history; 0 means no history, just the current expression.
Definition: Storage.cc:716
cadabra::Ex::print_recursive_treeform
static std::ostream & print_recursive_treeform(std::ostream &str, Ex::iterator it)
Definition: Storage.cc:264
cadabra::str_node::is_range_wildcard
bool is_range_wildcard() const
Definition: Storage.cc:884
cadabra::half
void half(rset_t::iterator &num)
Definition: Storage.cc:1032
cadabra::zero
void zero(rset_t::iterator &num)
Definition: Storage.cc:1015
cadabra::Ex::operator==
bool operator==(const Ex &other) const
Compare two Ex objects for exact equality; no dummy equivalence or other things that require property...
Definition: Storage.cc:690
cadabra::str_node::name
nset_t::iterator name
Definition: Storage.hh:71
cadabra::one
void one(rset_t::iterator &num)
Definition: Storage.cc:1020
cadabra::Ex::print_python
static std::ostream & print_python(std::ostream &str, Ex::iterator it)
Display expression in Python/Cadabra input form.
Definition: Storage.cc:150
cadabra::is_in
bool is_in(const T &val, const std::initializer_list< T > &list)
Definition: Storage.hh:293
cadabra::Ex::l_applied_no_new_dummies
@ l_applied_no_new_dummies
Definition: Storage.hh:159
cadabra::Ex::number_of_equations
unsigned int number_of_equations() const
Definition: Storage.cc:636
cadabra::Ex::arg
static sibling_iterator arg(iterator, unsigned int)
Quick access to arguments or argument lists for A(B)(C,D) type nodes.
Definition: Storage.cc:421
cadabra::str_node::is_unsimplified_integer
bool is_unsimplified_integer() const
Definition: Storage.cc:814
cadabra::Ex::state_
result_t state_
Definition: Storage.hh:275
cadabra::str_node::compare_name_brack_par
static bool compare_name_brack_par(const str_node &, const str_node &)
Definition: Storage.cc:976
cadabra::Ex::is_rational
bool is_rational() const
Test if the expression is a rational number.
Definition: Storage.cc:120
cadabra::Ex::arg_to_num
multiplier_t arg_to_num(sibling_iterator, unsigned int) const
Definition: Storage.cc:436
cadabra::str_node::b_none
@ b_none
Definition: Storage.hh:57
cadabra::Ex::l_no_action
@ l_no_action
Definition: Storage.hh:159
operator<<
std::ostream & operator<<(std::ostream &, const cadabra::Ex &)
Definition: Storage.cc:1049
cadabra
Functions to handle the exchange properties of two or more symbols in a product.
Definition: Adjform.cc:83
cadabra::Ex::equation_by_name
iterator equation_by_name(nset_t::iterator it) const
Definition: Storage.cc:520
cadabra::Ex
Definition: Storage.hh:140
cadabra::str_node::is_siblings_wildcard
bool is_siblings_wildcard() const
Definition: Storage.cc:893
cadabra::str_node::bracket_t
bracket_t
Definition: Storage.hh:57
cadabra::str_node::is_object_wildcard
bool is_object_wildcard() const
Definition: Storage.cc:875
cadabra::to_string
std::string to_string(long num)
Definition: Storage.cc:44
cadabra::Ex::to_rational
multiplier_t to_rational() const
Definition: Storage.cc:128
cadabra::multiply
void multiply(rset_t::iterator &num, multiplier_t fac)
Definition: Storage.cc:1001
cadabra::Ex::flatten_and_erase
iterator flatten_and_erase(iterator position)
Replace the node with the children of the node, useful for e.g.
Definition: Storage.cc:625
cadabra::Ex::l_error
@ l_error
Definition: Storage.hh:159
cadabra::name_set
nset_t name_set
Definition: Storage.cc:36
cadabra::multiplier_t
mpq_class multiplier_t
Definition: Storage.hh:38
cadabra::str_node::is_unsimplified_rational
bool is_unsimplified_rational() const
Definition: Storage.cc:804
cadabra::str_node::is_indexstar_wildcard
bool is_indexstar_wildcard() const
Definition: Storage.cc:910
cadabra::str_node::is_identity
bool is_identity() const
Definition: Storage.cc:784
cadabra::Ex::l_checkpointed
@ l_checkpointed
Definition: Storage.hh:159
cadabra::str_node
Definition: Storage.hh:55
cadabra::str_node::multiplier
rset_t::iterator multiplier
Definition: Storage.hh:72
cadabra::Ex::replace_index
iterator replace_index(iterator position, const iterator &from, bool keep_parent_rel=false)
Replace the index-like object (originally intended to replace indices only, but now used also for e....
Definition: Storage.cc:581
cadabra::Ex::named_parent
iterator named_parent(iterator it, const std::string &) const
Step up until matching node is found (if current node matches, do nothing)
Definition: Storage.cc:378
cadabra::Ex::state
result_t state() const
Definition: Storage.cc:87
cadabra::str_node::p_super
@ p_super
Definition: Storage.hh:61
cadabra::Ex::equation_by_number_or_name
iterator equation_by_number_or_name(iterator it, unsigned int last_used_equation) const
Definition: Storage.cc:670
cadabra::str_node::name_only
nset_t::iterator name_only()
Definition: Storage.cc:937
cadabra::Ex::result_t
result_t
Keeping track of what algorithms have done to this expression.
Definition: Storage.hh:159
cadabra::Ex::erase_expression
iterator erase_expression(iterator it)
Definition: Storage.cc:391
cadabra::Ex::list_wrap_single_element
void list_wrap_single_element(iterator &)
Make sure that the node pointed to is a \comma object, i.e.
Definition: Storage.cc:604
cadabra::nset_it_less
Definition: Storage.hh:287
cadabra::str_node::b_curly
@ b_curly
Definition: Storage.hh:57
cadabra::Ex::print_repr
std::ostream & print_repr(std::ostream &str, Ex::iterator it) const
Print a representation like Python's 'repr'.
Definition: Storage.cc:253
cadabra::str_node::parent_rel_t
parent_rel_t
Child nodes are related to their parent node by a so-called parent relation, which can be one of thes...
Definition: Storage.hh:61
cadabra::rat_set
rset_t rat_set
Definition: Storage.cc:37
cadabra::hashval_t
uintptr_t hashval_t
Definition: Storage.hh:41
cadabra::Ex::print_entire_tree
std::ostream & print_entire_tree(std::ostream &str) const
Output helpers mainly for debugging purposes.
Definition: Storage.cc:286
cadabra::str_node::flag_t
Definition: Storage.hh:82
cadabra::str_node::is_quoted_string
bool is_quoted_string() const
Definition: Storage.cc:832