/* Cadabra: a field-theory motivated computer algebra system. Copyright (C) 2001-2014 Kasper Peeters This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see . */ #pragma once #include "Stopwatch.hh" #include "Storage.hh" #include "Compare.hh" #include "Props.hh" #include "Exceptions.hh" #include "Kernel.hh" #include "IndexIterator.hh" #include "ProgressMonitor.hh" #include "IndexClassifier.hh" #include #include #include namespace cadabra { /// \ingroup core /// /// Base class for all algorithms, containing generic routines and in /// particular the logic for index classification. Also contains static /// algorithms acting on Ex objects which require property /// information and can therefore not be a member of Ex. /// /// In order to implement a new algorithm, subclass Algorithm and /// implement the abstract members Algorithm::can_apply and /// Algorithm::apply (see there for further documentation). The /// general logic is that the implementation of /// Algorithm::apply(iterator&) is not allowed to make the node pointed /// at by the iterator invalid. If the algorithm makes the node vanish, /// it should indicate so by setting its multiplier to zero; the /// calling logic will then take care of cleaning up the subtree /// at the node. /// /// The algorithm is, however, allowed to change the node itself or /// replace it with another one, as long as it updates the iterator. class Algorithm : public IndexClassifier { public: /// Initialise the algorithm with a reference to the expression /// tree, but do not yet do anything with this tree. Algorithms /// are not typically allowed to mess with the settings in the /// Kernel, so it is passed const. Algorithm(const Kernel&, Ex&); virtual ~Algorithm(); typedef Ex::iterator iterator; typedef Ex::post_order_iterator post_order_iterator; typedef Ex::sibling_iterator sibling_iterator; typedef Ex::result_t result_t; bool interrupted; /// Provide the algorithm with a ProgressMonitor object on which to register /// (nested) progress information, to be reported out-of-band to a client. void set_progress_monitor(ProgressMonitor *); /// The main entry points for running algorithms, which traverse /// the tree post-order ('child before parent'). The 'deep' flag /// indicates whether sub-expressions should be acted on /// too. The 'repeat' flag indicates whether the algorithm /// should be applied until the expression no longer /// changes. The 'depth' flag, if not equal to -1, indicates the /// depth in the tree where the algorithm should start applying. result_t apply_generic(bool deep=true, bool repeat=false, unsigned int depth=0); result_t apply_generic(iterator&, bool deep, bool repeat, unsigned int depth); /// Apply algorithm with alternative traversal: starting from /// the top node, traverse the tree pre-order ('parent before /// child') and once the algorithm acts at a given node, do not /// traverse the subtree below anymore. result_t apply_pre_order(bool repeat=false); // Global information unsigned int number_of_calls; unsigned int number_of_modifications; bool suppress_normal_output; bool discard_command_node; /// Given an expression top node, check index consistency. bool check_consistency(iterator) const; bool check_index_consistency(iterator) const; /// Given an expression top node, check differential form degree consistency. bool check_degree_consistency(iterator) const; void report_progress(const std::string&, int todo, int done, int count=2); mutable Stopwatch index_sw; mutable Stopwatch get_dummy_sw; mutable Stopwatch report_progress_stopwatch; index_iterator begin_index(iterator it) const; index_iterator end_index(iterator it) const; // The number of indices of a node, taking into account IndexInherit-ance. These // indices do therefore not all have to be direct child nodes of 'it', they can // sit deeper down the tree. unsigned int number_of_indices(iterator it); static unsigned int number_of_indices(const Properties&, iterator it); // The number of indices of a node, counting only the direct ones (i.e. not those // inherited from child nodes). static unsigned int number_of_direct_indices(iterator it); // The set to which the first index belongs.. std::string get_index_set_name(iterator it) const; /// Rename the dummies in the sub-tree starting with head at the given iterator. /// Ensures that no dummies in this sub-tree overlap with the indices elsewhere /// in the tree. bool rename_replacement_dummies(iterator, bool still_inside_algo=false); /// Determines whether the indicated node is 'like a term in a /// sum'. This requires that the node is not a `\sum` node, not /// a child of a `\prod` node, and that its parent rel is of /// argument-type (p_none). static bool is_termlike(iterator); /// Determines whether the indicated node is 'like a factor in a product'. /// This requires that the parent is a `\prod' node. static bool is_factorlike(iterator); protected: Ex& tr; ProgressMonitor *pm; // The main entry point which is used by the public entry points listed // above. Override these in any subclass. // virtual bool can_apply(iterator)=0; virtual result_t apply(iterator&)=0; // Index stuff int index_parity(iterator) const; static bool less_without_numbers(nset_t::iterator, nset_t::iterator); static bool equal_without_numbers(nset_t::iterator, nset_t::iterator); /// Finding objects in sets. typedef std::pair range_t; typedef std::vector range_vector_t; bool contains(sibling_iterator from, sibling_iterator to, sibling_iterator arg); void find_argument_lists(range_vector_t&, bool only_comma_lists=true) const; template range_vector_t::iterator find_arg_superset(range_vector_t&, Iter st, Iter nd); range_vector_t::iterator find_arg_superset(range_vector_t&, sibling_iterator it); // Locate objects inside the tree (formerly in the 'locate' algorithm). unsigned int locate_single_object(Ex::iterator obj_to_find, Ex::iterator st, Ex::iterator nd, std::vector& store); bool locate_object_set(const Ex& objs, Ex::iterator st, Ex::iterator nd, std::vector& store); static bool compare_(const str_node&, const str_node&); /// Take a single non-product node in a sum and wrap it in a /// product node, so it can be handled on the same footing as a proper product. bool is_single_term(iterator); bool is_nonprod_factor_in_prod(iterator); bool prod_wrap_single_term(iterator&); bool prod_unwrap_single_term(iterator&); bool sum_wrap_single_term(iterator&); bool sum_unwrap_single_term(iterator&); /// Wrap a term in a product or sum in a node with indicated /// name, irrespective of its parent (it usually makes more /// sense to call the safer prod_wrap_single_term or /// sum_wrap_single_term above). Sets the iterator to the /// new node. void force_node_wrap(iterator&, std::string); /// Figure out whether two objects (commonly indices) are separated by a derivative /// operator, as in \f[ \partial_{a}{A_{b}} C^{b} \f]. /// If the last iterator is pointing to a valid node, check whether it is /// independent of the derivative (using the Depends property). bool separated_by_derivative(iterator, iterator, iterator check_dependence) const; // Given a node with non-zero multiplier, distribute this // multiplier up the tree when the node is a \sum node, or push it into the // `\prod` node if that is the parent. Do this recursively // in case a child is a sum as well. Note that 'pushup' is actually 'pushdown' // in the case of sums. // This never changes the tree structure, only the distribution of multipliers. // FIXME: this is now superseded by code in Cleanup.cc, and the generic way // to make a tree consistent is to call cleanup_dispatch, not pick-and-match from // the various algorithms. void pushup_multiplier(iterator); // Return the number of elements in the first range for which an identical element // is present in the second range. template unsigned int intersection_number(sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator, BinaryPredicate) const; // Turn a node into a '1' or '0' node. void node_zero(iterator); void node_one(iterator); void node_integer(iterator, int); protected: bool traverse_ldots; private: // Single or deep-scan apply operations. Do not call directly. result_t apply_once(Ex::iterator& it); result_t apply_deep(Ex::iterator& it); /// Given a node with zero multiplier, propagate this zero /// upwards in the tree. Changes the iterator so that it points /// to the next node in a post_order traversal (post_order: /// children first, then node). The second node is the topmost /// node, beyond which this routine is not allowed to touch the /// tree (i.e. the 2nd iterator will always remain valid). void propagate_zeroes(post_order_iterator&, const iterator&); // bool cleanup_anomalous_products(Ex& tr, Ex::iterator& it); }; /// Determine the number of elements in the first range which also occur in the /// second range. template unsigned int Algorithm::intersection_number(sibling_iterator from1, sibling_iterator to1, sibling_iterator from2, sibling_iterator to2, BinaryPredicate fun) const { unsigned int ret=0; sibling_iterator it1=from1; while(it1!=to1) { sibling_iterator it2=from2; while(it2!=to2) { if(fun(*it1,*it2)) ++ret; ++it2; } ++it1; } return ret; } }