Algorithm.hh

Go to the documentation of this file.

/*
 
Cadabra: a field-theory motivated computer algebra system.
Copyright (C) 2001-2014  Kasper Peeters <kasper.peeters@phi-sci.com>
 
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 <http://www.gnu.org/licenses/>.
 
*/
 
#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 <map>
#include <fstream>
#include <cstddef>
 
namespace cadabra {
 
 
    class Algorithm : public IndexClassifier {
        public:
 
            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;
 
 
            void set_progress_monitor(ProgressMonitor *);
 
 
            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);
 
 
            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;
 
            bool      check_consistency(iterator) const;
            bool      check_index_consistency(iterator) const;
            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);
 
            bool     rename_replacement_dummies(iterator, bool still_inside_algo=false);
 
 
 
        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);
 
            typedef std::pair<sibling_iterator, sibling_iterator> range_t;
            typedef std::vector<range_t>                          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<class Iter>
            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<unsigned int>& store);
            bool         locate_object_set(const Ex& objs,
                                           Ex::iterator st, Ex::iterator nd,
                                           std::vector<unsigned int>& store);
            static bool  compare_(const str_node&, const str_node&);
 
 
            bool     is_termlike(iterator);
 
            bool     is_factorlike(iterator);
 
            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&);
 
            void     force_node_wrap(iterator&, std::string);
 
            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<class BinaryPredicate>
            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);
 
            void     propagate_zeroes(post_order_iterator&, const iterator&);
 
            //      bool cleanup_anomalous_products(Ex& tr, Ex::iterator& it);
        };
 
 
    template<class BinaryPredicate>
    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;
        }
 
 
    }