IterationPack_Algorithm.hpp

Go to the documentation of this file.
00001 // @HEADER
00002 // ***********************************************************************
00003 // 
00004 // Moocho: Multi-functional Object-Oriented arCHitecture for Optimization
00005 //                  Copyright (2003) Sandia Corporation
00006 // 
00007 // Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
00008 // license for use of this work by or on behalf of the U.S. Government.
00009 // 
00010 // This library is free software; you can redistribute it and/or modify
00011 // it under the terms of the GNU Lesser General Public License as
00012 // published by the Free Software Foundation; either version 2.1 of the
00013 // License, or (at your option) any later version.
00014 //  
00015 // This library is distributed in the hope that it will be useful, but
00016 // WITHOUT ANY WARRANTY; without even the implied warranty of
00017 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00018 // Lesser General Public License for more details.
00019 //  
00020 // You should have received a copy of the GNU Lesser General Public
00021 // License along with this library; if not, write to the Free Software
00022 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
00023 // USA
00024 // Questions? Contact Roscoe A. Bartlett (rabartl@sandia.gov) 
00025 // 
00026 // ***********************************************************************
00027 // @HEADER
00028 
00029 #ifndef ALGORITHM_H
00030 #define ALGORITHM_H
00031 
00032 #include <assert.h>
00033 
00034 #include <string>
00035 #include <deque>
00036 #include <list>
00037 #include <vector>
00038 #include <algorithm>
00039 
00040 #include "IterationPack_AlgorithmState.hpp"
00041 #include "IterationPack_AlgorithmTracker.hpp"
00042 #include "IterationPack_AlgorithmStep.hpp"
00043 #include "Teuchos_RCP.hpp"
00044 #include "Teuchos_TestForException.hpp"
00045 #include "Teuchos_StandardMemberCompositionMacros.hpp"
00046 
00047 namespace IterationPack {
00048 
00049 // ToDo: 7/31/98: Finish documentation.
00050 
00101 class Algorithm {
00102 public:
00103 
00106 
00108   typedef Teuchos::RCP<AlgorithmState>      state_ptr_t;
00110   typedef Teuchos::RCP<AlgorithmTracker>    track_ptr_t;
00112   typedef Teuchos::RCP<AlgorithmStep>       step_ptr_t;
00114   typedef size_t                                    poss_type;
00116   enum { DOES_NOT_EXIST = 1000 };  // never be that many steps
00118   enum ERunningState { NOT_RUNNING = 0, RUNNING = 1, RUNNING_BEING_CONFIGURED = 2 };
00119 
00121   class DoesNotExist : public std::logic_error
00122   {public: DoesNotExist(const std::string& what_arg) : std::logic_error(what_arg) {}};
00123 
00125   class AlreadyExists : public std::logic_error
00126   {public: AlreadyExists(const std::string& what_arg) : std::logic_error(what_arg) {}};
00127 
00129   class InvalidControlProtocal : public std::logic_error
00130   {public: InvalidControlProtocal(const std::string& what_arg) : std::logic_error(what_arg) {}};
00131 
00133   class InvalidRunningState : public std::logic_error
00134   {public: InvalidRunningState(const std::string& what_arg) : std::logic_error(what_arg) {}};
00135 
00137   class InvalidConfigChange : public std::logic_error
00138   {public: InvalidConfigChange(const std::string& what_arg) : std::logic_error(what_arg) {}};
00139 
00141   class AlgorithmInterrupted : public std::runtime_error
00142   {public: AlgorithmInterrupted(const std::string& what_arg) : std::runtime_error(what_arg) {}};
00143 
00145 
00148 
00152   Algorithm();
00153 
00155   virtual ~Algorithm();
00156 
00158 
00193   STANDARD_MEMBER_COMPOSITION_MEMBERS( std::string, interrupt_file_name );
00194 
00197 
00199   void set_state(const state_ptr_t& state);
00201   state_ptr_t& get_state();
00203   const state_ptr_t& get_state() const;
00205   AlgorithmState& state();
00207   const AlgorithmState& state() const;
00208 
00210 
00213 
00215   void set_track(const track_ptr_t& track);
00217   track_ptr_t& get_track();
00219   const track_ptr_t& get_track() const;
00221   AlgorithmTracker& track();
00223   const AlgorithmTracker& track() const;
00224 
00226 
00229   
00231   virtual void max_iter(size_t max_iter);
00233   virtual size_t max_iter() const;
00234 
00236 
00239   
00244   virtual void max_run_time(double max_iter);
00246   virtual double max_run_time() const;
00247 
00249 
00252 
00254   virtual int num_steps() const;
00255 
00261   virtual poss_type get_step_poss(const std::string& step_name) const;
00262 
00269   virtual const std::string& get_step_name(poss_type step_poss) const;
00270 
00277   virtual step_ptr_t& get_step(poss_type step_poss);
00278 
00280   virtual const step_ptr_t& get_step(poss_type step_poss) const;
00281 
00283 
00286 
00293   virtual int num_assoc_steps(poss_type step_poss, EAssocStepType type) const;
00294 
00304   virtual poss_type get_assoc_step_poss(poss_type step_poss, EAssocStepType type
00305     ,const std::string& assoc_step_name) const;
00306 
00315   virtual const std::string& get_assoc_step_name(poss_type step_poss, EAssocStepType type
00316     , poss_type assoc_step_poss) const;
00317 
00327   virtual step_ptr_t& get_assoc_step(poss_type step_poss, EAssocStepType type
00328     , poss_type assoc_step_poss);
00329 
00331   virtual const step_ptr_t& get_assoc_step(poss_type step_poss, EAssocStepType type
00332     , poss_type assoc_step_poss) const;
00333 
00335 
00338 
00351   virtual void insert_step(poss_type step_poss, const std::string& step_name, const step_ptr_t& step);
00352 
00362   virtual void change_step_name(poss_type step_poss, const std::string& new_name);
00363 
00373   virtual void replace_step(poss_type step_poss, const step_ptr_t& step);
00374 
00385   virtual void remove_step(poss_type step_poss);
00386 
00388 
00391 
00406   virtual void insert_assoc_step(poss_type step_poss, EAssocStepType type, poss_type assoc_step_poss
00407     , const std::string& assoc_step_name, const step_ptr_t& assoc_step);
00408 
00422   virtual void remove_assoc_step(poss_type step_poss, EAssocStepType type, poss_type assoc_step_poss);
00423 
00425 
00428 
00430   ERunningState running_state() const;
00431 
00444   virtual void begin_config_update();
00445 
00458   virtual void end_config_update();
00459 
00461 
00464 
00473   virtual void do_step_next(const std::string& step_name);
00474 
00483   virtual void do_step_next(poss_type step_poss);
00484 
00491   virtual const std::string& what_is_next_step_name() const;
00492 
00499   virtual poss_type what_is_next_step_poss() const;
00500 
00517   virtual bool do_step(const std::string& step_name);
00518 
00534   virtual bool do_step(poss_type step_poss);
00535 
00545   virtual void terminate(bool success);
00546 
00548 
00551 
00585   virtual EAlgoReturn do_algorithm(poss_type step_poss = 1);
00586 
00588 
00591 
00594   virtual void print_steps(std::ostream& out) const;
00595 
00598   virtual void print_algorithm(std::ostream& out) const;
00599 
00601 
00605 
00612   virtual void set_algo_timing( bool algo_timing );
00613 
00615   virtual bool algo_timing() const;
00616 
00625   virtual void print_algorithm_times( std::ostream& out ) const;
00626 
00642   void get_step_times_k( int offset, double step_times[] ) const;
00643 
00647   void get_final_step_stats( size_t step, double* total, double* average, double* min, double* max, double* percent) const;
00648 
00650 
00651 private:
00652 
00653   // /////////////////////////////////////////////////////
00654   // Private types
00655 
00657   template<class T_Step_ptr>
00658   struct step_ptr_and_name {
00660     step_ptr_and_name(const T_Step_ptr& _step_ptr
00661         , const std::string& _name )
00662       : step_ptr(_step_ptr), name(_name)
00663     {}
00665     T_Step_ptr step_ptr;
00666     //
00667     std::string name;
00668   };  // end struct step_ptr_and_name
00669 
00671   typedef step_ptr_and_name<step_ptr_t>           steps_ele_t;
00673   typedef std::deque<steps_ele_t>                 steps_t;
00674 
00676   typedef step_ptr_and_name<step_ptr_t>           assoc_steps_ele_list_ele_t;
00678   typedef std::list<assoc_steps_ele_list_ele_t>   assoc_steps_ele_list_t;
00680   struct assoc_steps_ele_t {
00682     assoc_steps_ele_list_t& operator[](int i)
00683     { return assoc_steps_lists_[i]; }
00685     const assoc_steps_ele_list_t& operator[](int i) const
00686     { return assoc_steps_lists_[i]; }
00687   private:
00688     assoc_steps_ele_list_t assoc_steps_lists_[2];
00689   };
00690 
00691   //typedef assoc_steps_ele_list_t[2]        assoc_steps_ele_t; // PRE_STEP, POST_STEP
00693   typedef std::deque<assoc_steps_ele_t>      assoc_steps_t;
00694   
00696   enum ETerminateStatus { STATUS_KEEP_RUNNING, STATUS_TERMINATE_TRUE, STATUS_TERMINATE_FALSE };
00697 
00699   template<class T_ele>
00700   class name_comp {
00701   public:
00703     name_comp(const std::string& name) : name_(name) {}
00705     bool operator()(const T_ele& ele) { return ele.name == name_; }
00706   private:
00707     const std::string& name_;
00708   };  // end class name_comp
00709 
00710   typedef std::vector<double> step_times_t;
00711   
00713   static const int
00714     TIME_STAT_TOTALS_OFFSET  = 0,
00715     TIME_STAT_AV_OFFSET    = 1,
00716     TIME_STAT_MIN_OFFSET    = 2,
00717     TIME_STAT_MAX_OFFSET    = 3,
00718     TIME_STAT_PERCENT_OFFSET  = 4;
00720   enum { NUM_STEP_TIME_STATS = 5 };
00721 
00723   typedef void (AlgorithmStep::*inform_func_ptr_t)(
00724     Algorithm&             algo
00725     ,poss_type             step_poss
00726     ,EDoStepType           type
00727     ,poss_type             assoc_step_poss
00728     );
00729 
00730   // /////////////////////////////////////////////////////
00731   // Private data members
00732 
00733   // aggregate members
00734 
00735 #ifdef DOXYGEN_COMPILE
00736   AlgorithmState       *state;
00737   AlgorithmTracker     *track;
00738   AlgorithmStep        *steps;
00739 #else
00740   state_ptr_t        state_;
00741   // RCP<...> object for the aggragate AlgorithmState object.
00742 
00743   track_ptr_t        track_;
00744   // RCP<...> object for the aggragate AlgorithmTracker object.
00745 #endif
00746 
00747   // algorithm control etc.
00748   
00749   ERunningState      running_state_;
00750   // The state this Algorithm object is in:
00751   //
00752   // NOT_RUNNING    do_algorithm() is not active.
00753   // RUNNING        do_algorithm() has been called and is active.
00754   // RUNNING_BEING_CONFIGURED
00755   //                do_algorithm() is active and begin_config_update() has been called
00756   //                but end_config_update() has not.
00757   //
00758   // Note: Only change this variable through the private function change_running_state(...)
00759   // unless you are 100% sure that you know what you are doing!
00760 
00761   size_t          first_k_;
00762   // The first iteration from state().k().
00763   
00764   size_t          max_iter_;
00765   // The maximum number of iterations that <tt>this</tt> will execute.
00766 
00767   double          max_run_time_;
00768   // The maximum amount of time the algorithm is allowed to execute.
00769 
00770   ETerminateStatus    terminate_status_;
00771   // Flag for if it is time to terminate do_algorithm().
00772 
00773   poss_type        next_step_poss_;
00774   // The next step possition that <tt>this</tt> will execute when control is returned to do_algorithm().
00775 
00776   const std::string*    next_step_name_;
00777   // The name of the next step that <tt>this</tt> will execute when control is returned to do_algorithm().
00778   
00779   bool          do_step_next_called_;
00780   // Flag for if do_step_next() was called so that <tt>do_algorithm()</tt> can validate
00781   // that if a step object returned <tt>false</tt> from its <tt>do_step()</tt> operation that it
00782   // must also call <tt>do_step_next()</tt> to specify a step to jump to.
00783 
00784   poss_type        curr_step_poss_;
00785   // The current step being executed in do_algorithm().
00786   // If the current step being executed is changed during the imp_do_step() operation, then
00787   // imp_do_step() must adjust to this step.
00788 
00789   std::string        saved_curr_step_name_;
00790   // The name of the current step that is saved when begin_config_update() is called
00791   // so that curr_step_poss_ can be reset when end_config_update() is called.
00792 
00793   std::string        saved_next_step_name_;
00794   // The name of the next step to call so that when begin_config_update() is called
00795   // so that next_step_poss_ and next_step_name_ can be reset when end_config_update()
00796   // is called.
00797 
00798   bool          reconfigured_;
00799   // A flag that is set to true when a runtime configuration has been preformed.  It
00800   // is used to flag this event for imp_do_assoc_steps().
00801 
00802   // step and associated step object data structures
00803 
00804   steps_t          steps_;
00805   // Array of std::pair<RCP<step_ptr_t>,std::string> objects.
00806   //
00807   // *steps_[step_poss].first returns the step object for step_poss = 1...steps_.size().
00808   // steps_[step_poss].second returns the name of the step for step_poss = 1...steps_.size().
00809 
00810   assoc_steps_t      assoc_steps_;
00811   // Array of two lists of std::pair<step_ptr_t,std::string> objects
00812   //
00813   // *(assoc_steps_[step_poss][PRE_STEP].begin() + pre_step_poss).first gives the pre step object.
00814   // (assoc_steps_[step_poss][PRE_STEP].begin() + pre_step_poss).second gives the name of the pre step
00815   // *(assoc_steps_[step_poss][POST_STEP].begin() + post_step_poss).first gives the post step object.
00816   // (assoc_steps_[step_poss][POST_STEP].begin() + post_step_poss).second gives the name of the post step
00817 
00818   bool algo_timing_;
00819   // If true each step will be timed.
00820 
00821   mutable step_times_t step_times_;
00822   // Array of step times ( size (max_iter() + 1 + NUM_STEP_TIME_STATS) * (num_steps() + 1) ).
00823   //  The time in sec. for step step_i (one based)
00824   // for iteration iter_k (zero based) is:
00825   //   step_times_[ iter_k + (step_i - 1) * (max_iter() + 1 + NUM_STEP_TIME_STATS) ].
00826   // Therefore the times for each step are stored by column (consecutive elements)
00827   // so that statistics will be easy to compute at the end.
00828   // The last five elements after max_iter() for each step are reserved for:
00829   // * total time for the step
00830   // * average time for the step
00831   // * min step time
00832   // * max step time
00833   // * percentage for each step to the total.
00834   // The last column is for the total times for each iteration with the last five
00835   // elements being for the statistics for each iteration.   
00836 
00837   mutable bool time_stats_computed_;
00838   // A flag for if the timing statistics have already been computed or not.
00839   
00840   mutable double total_time_;
00841   // Records the total computed time for the algorithm.
00842 
00843   // /////////////////////////////////////////////////////
00844   // Private member functions
00845 
00847   poss_type validate(poss_type step_poss, int past_end = 0) const;
00848 
00850   poss_type validate(const assoc_steps_ele_list_t& assoc_list, poss_type assoc_step_poss, int past_end = 0) const;
00851 
00853   void change_running_state(ERunningState running_state);
00854 
00856   void validate_in_state(ERunningState running_state) const;
00857 
00859   void validate_not_in_state(ERunningState running_state) const;
00860 
00862   void validate_not_curr_step(poss_type step_poss) const;
00863 
00865   void validate_not_next_step(const std::string& step_name) const;
00866 
00869   steps_t::iterator step_itr(const std::string& step_name);
00870 
00872   steps_t::const_iterator step_itr(const std::string& step_name) const;
00873 
00876   steps_t::iterator step_itr_and_assert(const std::string& step_name);
00877 
00879   steps_t::const_iterator step_itr_and_assert(const std::string& step_name) const;
00880 
00883   static assoc_steps_ele_list_t::iterator assoc_step_itr(assoc_steps_ele_list_t& assoc_list
00884     , const std::string& assoc_step_name);
00885 
00887   static assoc_steps_ele_list_t::const_iterator assoc_step_itr(const assoc_steps_ele_list_t& assoc_list
00888     , const std::string& assoc_step_name);
00889 
00891   bool imp_do_step(poss_type step_poss);
00892 
00894   bool imp_do_assoc_steps(EAssocStepType type);
00895 
00897   void imp_inform_steps(inform_func_ptr_t inform_func_ptr);
00898 
00900   void imp_print_algorithm(std::ostream& out, bool print_steps) const;
00901 
00903   EDoStepType do_step_type(EAssocStepType assoc_step_type);
00904 
00906   EAlgoReturn finalize_algorithm( EAlgoReturn algo_return );
00907 
00909   void compute_final_time_stats() const;
00910 
00911   // Look for interrup
00912   void look_for_interrupt();
00913 
00914 public:
00915 
00916   // This is put here out of need.  Not for any user to call!
00917   static void interrupt();
00918 
00919 };  // end class Algorithm
00920 
00921 // //////////////////////////////////////////////////////////////////////////////////////////////////
00922 // Inline member function definitions for Algorithm
00923 
00924 // «std comp» members for state 
00925 
00926 inline
00927 void Algorithm::set_state(const state_ptr_t& state)
00928 {  state_ = state; }
00929 
00930 inline
00931 Algorithm::state_ptr_t& Algorithm::get_state()
00932 {  return state_; }
00933 
00934 inline
00935 const Algorithm::state_ptr_t& Algorithm::get_state() const
00936 {  return state_; }
00937 
00938 inline
00939 AlgorithmState& Algorithm::state()
00940 {  TEST_FOR_EXCEPT( !( state_.get() ) ); return *state_; }
00941 
00942 inline
00943 const AlgorithmState& Algorithm::state() const
00944 {  TEST_FOR_EXCEPT( !( state_.get() ) ); return *state_; }
00945 
00946 // «std comp» members for track 
00947 
00948 inline
00949 void Algorithm::set_track(const track_ptr_t& track)
00950 {  track_ = track; }
00951 
00952 inline
00953 Algorithm::track_ptr_t& Algorithm::get_track()
00954 {  return track_; }
00955 
00956 inline
00957 const Algorithm::track_ptr_t& Algorithm::get_track() const
00958 {  return track_; }
00959 
00960 inline
00961 AlgorithmTracker& Algorithm::track()
00962 {  TEST_FOR_EXCEPT( !( track_.get() ) ); return *track_; }
00963 
00964 inline
00965 const AlgorithmTracker& Algorithm::track() const
00966 {  TEST_FOR_EXCEPT( !( track_.get() ) ); return *track_; }
00967 
00968 // running state
00969 
00970 inline
00971 Algorithm::ERunningState Algorithm::running_state() const
00972 {  return running_state_; }
00973 
00974 // lookup iterator given name
00975 
00976 inline
00977 Algorithm::steps_t::iterator Algorithm::step_itr(const std::string& step_name)
00978 {
00979   return std::find_if( steps_.begin() , steps_.end()
00980     , name_comp<steps_ele_t>(step_name) );
00981 }
00982 
00983 inline
00984 Algorithm::steps_t::const_iterator Algorithm::step_itr(const std::string& step_name) const
00985 {
00986   return std::find_if( steps_.begin() , steps_.end()
00987     , name_comp<steps_ele_t>(step_name) );
00988 }
00989 
00990 inline
00991 Algorithm::assoc_steps_ele_list_t::iterator Algorithm::assoc_step_itr(
00992   assoc_steps_ele_list_t& assoc_list, const std::string& assoc_step_name)
00993 {
00994   return std::find_if( assoc_list.begin() , assoc_list.end()
00995     , name_comp<assoc_steps_ele_list_ele_t>(assoc_step_name) );
00996 }
00997 
00998 inline
00999 Algorithm::assoc_steps_ele_list_t::const_iterator Algorithm::assoc_step_itr(
01000   const assoc_steps_ele_list_t& assoc_list, const std::string& assoc_step_name)
01001 {
01002   return std::find_if( assoc_list.begin() , assoc_list.end()
01003     , name_comp<assoc_steps_ele_list_ele_t>(assoc_step_name) );
01004 }
01005 
01006 inline
01007 EDoStepType Algorithm::do_step_type(EAssocStepType assoc_step_type) {
01008   switch(assoc_step_type) {
01009     case PRE_STEP  : return DO_PRE_STEP;
01010     case POST_STEP  : return DO_POST_STEP;
01011   }
01012   TEST_FOR_EXCEPT( !( true ) );
01013   return DO_PRE_STEP;  // will never execute.
01014 }
01015 
01016 }  // end namespace IterationPack 
01017 
01018 #endif // ALGORITHM_H

Generated on Tue Oct 20 12:51:46 2009 for MOOCHO (Single Doxygen Collection) by doxygen 1.4.7