Cadabra
Computer algebra system for field theory problems
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
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 
67  bool operator==(const str_node&) const;
68  bool operator<(const str_node&) const;
69 
70  nset_t::iterator name;
71  rset_t::iterator multiplier;
72 
73  struct flag_t { // kept inside 8 bits for speed and size
74  bool keep_after_eval : 1;
77  bool line_per_node : 1;
78  };
79 
81 
84  void flip_parent_rel();
85 
86  bool is_zero() const;
87  bool is_identity() const;
88  bool is_rational() const;
89  bool is_unsimplified_rational() const;
90  bool is_integer() const;
91  bool is_unsimplified_integer() const;
92  bool is_index() const; // _ or ^ parent_rel (does not query properties)
93  bool is_quoted_string() const;
94  bool is_command() const;
95  bool is_inert_command() const;
96  bool is_name_wildcard() const; // ?
97  bool is_object_wildcard() const; // ??
98  bool is_range_wildcard() const; // #{..}
99  bool is_siblings_wildcard() const; // a...
100  bool is_autodeclare_wildcard() const; // m#
101  bool is_indexstar_wildcard() const; // ?* in sub/super
102  bool is_indexplus_wildcard() const; // ?+ in sub/super
103  bool is_numbered_symbol() const; // [a-zA-Z]+[0-9]+
104 
105  nset_t::iterator name_only();
106 
107  static bool compare_names_only(const str_node&, const str_node&);
108  static bool compare_name_brack_par(const str_node&, const str_node&);
109  static bool compare_name_inverse_par(const str_node&, const str_node&);
110 };
111 
115 void multiply(rset_t::iterator&, multiplier_t);
116 void add(rset_t::iterator&, multiplier_t);
117 void zero(rset_t::iterator&);
118 void one(rset_t::iterator&);
119 void flip_sign(rset_t::iterator&);
120 void half(rset_t::iterator&);
121 
129 
130 class Ex : public tree<str_node> {
131  public:
132  Ex();
133 // Ex(const tree<str_node>&);
134  Ex(tree<str_node>::iterator);
135  Ex(const str_node&);
136  Ex(const Ex&);
138  Ex(const std::string&);
139  Ex(int);
140 
148 
150  result_t state() const;
151  void update_state(result_t);
152  void reset_state();
153 
158  bool changed_state();
159 
162  bool is_rational() const;
163  multiplier_t to_rational() const;
164 
168  static std::ostream& print_python(std::ostream& str, Ex::iterator it);
169 
171  std::ostream& print_entire_tree(std::ostream& str) const;
172  static std::ostream& print_recursive_treeform(std::ostream& str, Ex::iterator it);
173  static std::ostream& print_recursive_treeform(std::ostream& str, Ex::iterator it, unsigned int& number);
174 
176  std::ostream& print_repr(std::ostream& str, Ex::iterator it) const;
177 
179  iterator named_parent(iterator it, const std::string&) const;
180  iterator erase_expression(iterator it);
181 
183  hashval_t calc_hash(iterator it) const;
184 
186  static sibling_iterator arg(iterator, unsigned int);
187  static unsigned int arg_size(sibling_iterator);
188 
189  multiplier_t arg_to_num(sibling_iterator, unsigned int) const; // shorthand for numerical arguments
190 
191  // Like 'child', but using index iterators instead.
192 // sibling_iterator tensor_index(const iterator_base& position, unsigned int) const;
193 
194  // Number of \\history nodes in an expression
195  unsigned int number_of_steps(iterator it) const;
196  // Given an iterator pointing to any node in the tree, figure
197  // out to which equation number it belongs.
198  unsigned int number_of_equations() const;
199  unsigned int equation_number(iterator it) const;
200  nset_t::iterator equation_label(iterator it) const;
201  iterator equation_by_number(unsigned int i) const;
202  iterator equation_by_name(nset_t::iterator it) const;
203  iterator equation_by_name(nset_t::iterator it, unsigned int& ) const;
204  iterator equation_by_number_or_name(iterator it, unsigned int last_used_equation) const;
205  iterator equation_by_number_or_name(iterator it, unsigned int last_used_equation,
206  unsigned int&) const;
207  std::string equation_number_or_name(iterator it, unsigned int last_used_equation) const;
208  iterator procedure_by_name(nset_t::iterator it) const;
209 
221  iterator replace_index(iterator position, const iterator& from, bool keep_parent_rel=false);
222 
225  iterator move_index(iterator position, const iterator& from);
226 
230  void list_wrap_single_element(iterator&);
231  void list_unwrap_single_element(iterator&);
232 
237  iterator flatten_and_erase(iterator position);
238 
241 
242  bool operator==(const Ex& other) const;
243 
245  void push_history(Ex selector);
246 
249  Ex pop_history();
250 
253  int history_size() const;
254 
255  private:
257 
258  std::vector<tree<str_node> > history;
260  std::vector<tree<str_node> > selectors;
261 };
262 
263 
267 
269  public:
270  bool operator()(nset_t::iterator first, nset_t::iterator second) const;
271 };
272 
273 template <typename T>
274 bool is_in(const T& val, const std::initializer_list<T>& list)
275  {
276  for (const auto& i : list) {
277  if (val == i) {
278  return true;
279  }
280  }
281  return false;
282  }
283 
284 }
285 
293 
294 std::ostream& operator<<(std::ostream&, const cadabra::Ex&);
bool operator()(nset_t::iterator first, nset_t::iterator second) const
Definition: Storage.cc:887
std::ostream & operator<<(std::ostream &, const cadabra::Ex &)
Bare output operator for Ex objects, mainly to provide a simple way to generate debugging output...
Definition: Storage.cc:937
Definition: Storage.hh:73
Definition: Storage.hh:149
rset_t rat_set
Definition: Storage.cc:32
static bool compare_names_only(const str_node &, const str_node &)
Definition: Storage.cc:864
bool is_name_wildcard() const
Definition: Storage.cc:756
void reset_state()
Definition: Storage.cc:102
Definition: Storage.hh:57
bool is_range_wildcard() const
Definition: Storage.cc:778
Basic storage class for symbolic mathemematical expressions.
Definition: Storage.hh:130
std::ostream & print_entire_tree(std::ostream &str) const
Output helpers mainly for debugging purposes.
Definition: Storage.cc:230
bool is_object_wildcard() const
Definition: Storage.cc:769
Definition: Storage.hh:61
bool is_numbered_symbol() const
Definition: Storage.cc:822
unsigned int equation_number(iterator it) const
Definition: Storage.cc:376
bool operator==(const str_node &) const
Definition: Storage.cc:854
bool keep_after_eval
Definition: Storage.hh:74
void list_wrap_single_element(iterator &)
Make sure that the node pointed to is a \comma object, i.e.
Definition: Storage.cc:525
Definition: Storage.hh:61
static bool compare_name_inverse_par(const str_node &, const str_node &)
Definition: Storage.cc:878
std::vector< tree< str_node > > selectors
Patterns which describe how to get from one history step to the next.
Definition: Storage.hh:260
iterator procedure_by_name(nset_t::iterator it) const
Definition: Storage.cc:482
Definition: Storage.hh:61
bool is_autodeclare_wildcard() const
Definition: Storage.cc:796
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:665
Definition: Storage.hh:61
Definition: Storage.hh:149
void flip_sign(rset_t::iterator &num)
Definition: Storage.cc:917
multiplier_t arg_to_num(sibling_iterator, unsigned int) const
Definition: Storage.cc:368
Definition: Storage.hh:57
long to_long(multiplier_t mul)
Definition: Storage.cc:34
bool is_zero() const
Definition: Storage.cc:672
static std::ostream & print_python(std::ostream &str, Ex::iterator it)
Display expression in Python/Cadabra input form.
Definition: Storage.cc:130
str_node(void)
Definition: Storage.cc:636
unsigned int number_of_steps(iterator it) const
std::string equation_number_or_name(iterator it, unsigned int last_used_equation) const
Definition: Storage.cc:597
Definition: Storage.hh:57
bool is_indexplus_wildcard() const
Definition: Storage.cc:813
Definition: Storage.hh:61
bool is_siblings_wildcard() const
Definition: Storage.cc:787
bool changed_state()
A status query method mainly to implement a simple method to apply algorithms until they converge...
Definition: Storage.cc:107
bool is_inert_command() const
Definition: Storage.cc:747
static unsigned int arg_size(sibling_iterator)
Definition: Storage.cc:362
Definition: Storage.hh:61
bool is_quoted_string() const
Definition: Storage.cc:726
iterator move_index(iterator position, const iterator &from)
As in replace_index, but moves the index rather than making a copy (so that iterators.
Definition: Storage.cc:514
Definition: Storage.hh:57
iterator equation_by_name(nset_t::iterator it) const
Definition: Storage.cc:452
Definition: Storage.hh:149
void zero(rset_t::iterator &num)
Definition: Storage.cc:907
hashval_t calc_hash(iterator it) const
Calculate the hash value for the subtree starting at 'it'.
Definition: Storage.cc:332
void update_state(result_t)
Definition: Storage.cc:87
parent_rel_t parent_rel
Definition: Storage.hh:76
Definition: Storage.hh:57
bool is_index() const
Definition: Storage.cc:718
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:312
Elementary building block for a mathematical expression.
Definition: Storage.hh:55
void list_unwrap_single_element(iterator &)
Definition: Storage.cc:536
void one(rset_t::iterator &num)
Definition: Storage.cc:912
nset_t::iterator name
Definition: Storage.hh:70
bool is_rational() const
Definition: Storage.cc:684
std::set< std::string > nset_t
Definition: Storage.hh:39
static std::ostream & print_recursive_treeform(std::ostream &str, Ex::iterator it)
Definition: Storage.cc:217
flag_t fl
Definition: Storage.hh:80
bool is_integer() const
Definition: Storage.cc:689
void add(rset_t::iterator &num, multiplier_t fac)
Definition: Storage.cc:901
void half(rset_t::iterator &num)
Definition: Storage.cc:922
result_t state() const
Definition: Storage.cc:82
static sibling_iterator arg(iterator, unsigned int)
Quick access to arguments or argument lists for A(B)(C,D) type nodes.
Definition: Storage.cc:353
Ex pop_history()
Pop the most recent state of the expression off the history stack; returns the selector that got us t...
Definition: Storage.cc:622
iterator flatten_and_erase(iterator position)
Replace the node with the children of the node, useful for e.g.
Definition: Storage.cc:546
int history_size() const
Return the size of the history; 0 means no history, just the current expression.
Definition: Storage.cc:631
bool is_unsimplified_rational() const
Definition: Storage.cc:698
void multiply(rset_t::iterator &num, multiplier_t fac)
Helper functions for manipulation of multipliers.
Definition: Storage.cc:895
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:502
void push_history(Ex selector)
Push a copy of the current state of the expression onto the history stack.
Definition: Storage.cc:616
rset_t::iterator multiplier
Definition: Storage.hh:71
Definition: Storage.hh:149
std::ostream & print_repr(std::ostream &str, Ex::iterator it) const
Print a representation like Python's 'repr'.
Definition: Storage.cc:206
std::string to_string(long num)
Definition: Storage.cc:39
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:611
mpq_class multiplier_t
Definition: Storage.hh:38
Ex()
Definition: Storage.cc:48
bool is_rational() const
Test if the expression is a rational number.
Definition: Storage.cc:115
nset_t name_set
Definition: Storage.cc:31
Definition: Storage.hh:57
static bool compare_name_brack_par(const str_node &, const str_node &)
Definition: Storage.cc:870
bool is_in(const T &val, const std::initializer_list< T > &list)
Definition: Storage.hh:274
bool is_command() const
Definition: Storage.cc:734
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
bool operator<(const str_node &) const
Definition: Storage.cc:927
nset_t::iterator name_only()
Definition: Storage.cc:831
nset_t::iterator equation_label(iterator it) const
Definition: Storage.cc:397
std::vector< tree< str_node > > history
Definition: Storage.hh:258
iterator erase_expression(iterator it)
Definition: Storage.cc:325
iterator equation_by_number(unsigned int i) const
Definition: Storage.cc:434
bracket_t
Definition: Storage.hh:57
multiplier_t to_rational() const
Definition: Storage.cc:123
Definition: Storage.hh:61
result_t
Keeping track of what algorithms have done to this expression.
Definition: Storage.hh:149
bool is_unsimplified_integer() const
Definition: Storage.cc:708
bracket_t bracket
Definition: Storage.hh:75
bool is_identity() const
Definition: Storage.cc:678
bool line_per_node
Definition: Storage.hh:77
unsigned int number_of_equations() const
Definition: Storage.cc:557
Definition: Storage.hh:57
iterator equation_by_number_or_name(iterator it, unsigned int last_used_equation) const
Definition: Storage.cc:591
bool is_indexstar_wildcard() const
Definition: Storage.cc:804
Compare two nset iterators by comparing the strings to which they point.
Definition: Storage.hh:268
uintptr_t hashval_t
Definition: Storage.hh:41
result_t state_
Definition: Storage.hh:256
std::set< multiplier_t > rset_t
Definition: Storage.hh:40