IterationPack: General framework for building iterative algorithms Version of the Day
IterationPack_Algorithm.hpp
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 // Redistribution and use in source and binary forms, with or without
00011 // modification, are permitted provided that the following conditions are
00012 // met:
00013 //
00014 // 1. Redistributions of source code must retain the above copyright
00015 // notice, this list of conditions and the following disclaimer.
00016 //
00017 // 2. Redistributions in binary form must reproduce the above copyright
00018 // notice, this list of conditions and the following disclaimer in the
00019 // documentation and/or other materials provided with the distribution.
00020 //
00021 // 3. Neither the name of the Corporation nor the names of the
00022 // contributors may be used to endorse or promote products derived from
00023 // this software without specific prior written permission.
00024 //
00025 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
00026 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00027 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00028 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
00029 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00030 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00031 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00032 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00033 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00034 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00035 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00036 //
00037 // Questions? Contact Roscoe A. Bartlett (rabartl@sandia.gov) 
00038 // 
00039 // ***********************************************************************
00040 // @HEADER
00041 
00042 #ifndef ALGORITHM_H
00043 #define ALGORITHM_H
00044 
00045 #include <assert.h>
00046 
00047 #include <string>
00048 #include <deque>
00049 #include <list>
00050 #include <vector>
00051 #include <algorithm>
00052 
00053 #include "IterationPack_AlgorithmState.hpp"
00054 #include "IterationPack_AlgorithmTracker.hpp"
00055 #include "IterationPack_AlgorithmStep.hpp"
00056 #include "Teuchos_RCP.hpp"
00057 #include "Teuchos_Assert.hpp"
00058 #include "Teuchos_StandardMemberCompositionMacros.hpp"
00059 
00060 namespace IterationPack {
00061 
00062 // ToDo: 7/31/98: Finish documentation.
00063 
00114 class Algorithm {
00115 public:
00116 
00119 
00121   typedef Teuchos::RCP<AlgorithmState>      state_ptr_t;
00123   typedef Teuchos::RCP<AlgorithmTracker>    track_ptr_t;
00125   typedef Teuchos::RCP<AlgorithmStep>       step_ptr_t;
00127   typedef size_t                                    poss_type;
00129   enum { DOES_NOT_EXIST = 1000 };  // never be that many steps
00131   enum ERunningState { NOT_RUNNING = 0, RUNNING = 1, RUNNING_BEING_CONFIGURED = 2 };
00132 
00134   class DoesNotExist : public std::logic_error
00135   {public: DoesNotExist(const std::string& what_arg) : std::logic_error(what_arg) {}};
00136 
00138   class AlreadyExists : public std::logic_error
00139   {public: AlreadyExists(const std::string& what_arg) : std::logic_error(what_arg) {}};
00140 
00142   class InvalidControlProtocal : public std::logic_error
00143   {public: InvalidControlProtocal(const std::string& what_arg) : std::logic_error(what_arg) {}};
00144 
00146   class InvalidRunningState : public std::logic_error
00147   {public: InvalidRunningState(const std::string& what_arg) : std::logic_error(what_arg) {}};
00148 
00150   class InvalidConfigChange : public std::logic_error
00151   {public: InvalidConfigChange(const std::string& what_arg) : std::logic_error(what_arg) {}};
00152 
00154   class AlgorithmInterrupted : public std::runtime_error
00155   {public: AlgorithmInterrupted(const std::string& what_arg) : std::runtime_error(what_arg) {}};
00156 
00158 
00161 
00165   Algorithm();
00166 
00168   virtual ~Algorithm();
00169 
00171 
00206   STANDARD_MEMBER_COMPOSITION_MEMBERS( std::string, interrupt_file_name );
00207 
00210 
00212   void set_state(const state_ptr_t& state);
00214   state_ptr_t& get_state();
00216   const state_ptr_t& get_state() const;
00218   AlgorithmState& state();
00220   const AlgorithmState& state() const;
00221 
00223 
00226 
00228   void set_track(const track_ptr_t& track);
00230   track_ptr_t& get_track();
00232   const track_ptr_t& get_track() const;
00234   AlgorithmTracker& track();
00236   const AlgorithmTracker& track() const;
00237 
00239 
00242   
00244   virtual void max_iter(size_t max_iter);
00246   virtual size_t max_iter() const;
00247 
00249 
00252   
00257   virtual void max_run_time(double max_iter);
00259   virtual double max_run_time() const;
00260 
00262 
00265 
00267   virtual int num_steps() const;
00268 
00274   virtual poss_type get_step_poss(const std::string& step_name) const;
00275 
00282   virtual const std::string& get_step_name(poss_type step_poss) const;
00283 
00290   virtual step_ptr_t& get_step(poss_type step_poss);
00291 
00293   virtual const step_ptr_t& get_step(poss_type step_poss) const;
00294 
00296 
00299 
00306   virtual int num_assoc_steps(poss_type step_poss, EAssocStepType type) const;
00307 
00317   virtual poss_type get_assoc_step_poss(poss_type step_poss, EAssocStepType type
00318     ,const std::string& assoc_step_name) const;
00319 
00328   virtual const std::string& get_assoc_step_name(poss_type step_poss, EAssocStepType type
00329     , poss_type assoc_step_poss) const;
00330 
00340   virtual step_ptr_t& get_assoc_step(poss_type step_poss, EAssocStepType type
00341     , poss_type assoc_step_poss);
00342 
00344   virtual const step_ptr_t& get_assoc_step(poss_type step_poss, EAssocStepType type
00345     , poss_type assoc_step_poss) const;
00346 
00348 
00351 
00364   virtual void insert_step(poss_type step_poss, const std::string& step_name, const step_ptr_t& step);
00365 
00375   virtual void change_step_name(poss_type step_poss, const std::string& new_name);
00376 
00386   virtual void replace_step(poss_type step_poss, const step_ptr_t& step);
00387 
00398   virtual void remove_step(poss_type step_poss);
00399 
00401 
00404 
00419   virtual void insert_assoc_step(poss_type step_poss, EAssocStepType type, poss_type assoc_step_poss
00420     , const std::string& assoc_step_name, const step_ptr_t& assoc_step);
00421 
00435   virtual void remove_assoc_step(poss_type step_poss, EAssocStepType type, poss_type assoc_step_poss);
00436 
00438 
00441 
00443   ERunningState running_state() const;
00444 
00457   virtual void begin_config_update();
00458 
00471   virtual void end_config_update();
00472 
00474 
00477 
00486   virtual void do_step_next(const std::string& step_name);
00487 
00496   virtual void do_step_next(poss_type step_poss);
00497 
00504   virtual const std::string& what_is_next_step_name() const;
00505 
00512   virtual poss_type what_is_next_step_poss() const;
00513 
00530   virtual bool do_step(const std::string& step_name);
00531 
00547   virtual bool do_step(poss_type step_poss);
00548 
00558   virtual void terminate(bool success);
00559 
00561 
00564 
00598   virtual EAlgoReturn do_algorithm(poss_type step_poss = 1);
00599 
00601 
00604 
00607   virtual void print_steps(std::ostream& out) const;
00608 
00611   virtual void print_algorithm(std::ostream& out) const;
00612 
00614 
00618 
00625   virtual void set_algo_timing( bool algo_timing );
00626 
00628   virtual bool algo_timing() const;
00629 
00638   virtual void print_algorithm_times( std::ostream& out ) const;
00639 
00655   void get_step_times_k( int offset, double step_times[] ) const;
00656 
00660   void get_final_step_stats( size_t step, double* total, double* average, double* min, double* max, double* percent) const;
00661 
00663 
00664 private:
00665 
00666   // /////////////////////////////////////////////////////
00667   // Private types
00668 
00670   template<class T_Step_ptr>
00671   struct step_ptr_and_name {
00673     step_ptr_and_name(const T_Step_ptr& _step_ptr
00674         , const std::string& _name )
00675       : step_ptr(_step_ptr), name(_name)
00676     {}
00678     T_Step_ptr step_ptr;
00679     //
00680     std::string name;
00681   };  // end struct step_ptr_and_name
00682 
00684   typedef step_ptr_and_name<step_ptr_t>           steps_ele_t;
00686   typedef std::deque<steps_ele_t>                 steps_t;
00687 
00689   typedef step_ptr_and_name<step_ptr_t>           assoc_steps_ele_list_ele_t;
00691   typedef std::list<assoc_steps_ele_list_ele_t>   assoc_steps_ele_list_t;
00693   struct assoc_steps_ele_t {
00695     assoc_steps_ele_list_t& operator[](int i)
00696     { return assoc_steps_lists_[i]; }
00698     const assoc_steps_ele_list_t& operator[](int i) const
00699     { return assoc_steps_lists_[i]; }
00700   private:
00701     assoc_steps_ele_list_t assoc_steps_lists_[2];
00702   };
00703 
00704   //typedef assoc_steps_ele_list_t[2]        assoc_steps_ele_t; // PRE_STEP, POST_STEP
00706   typedef std::deque<assoc_steps_ele_t>      assoc_steps_t;
00707   
00709   enum ETerminateStatus { STATUS_KEEP_RUNNING, STATUS_TERMINATE_TRUE, STATUS_TERMINATE_FALSE };
00710 
00712   template<class T_ele>
00713   class name_comp {
00714   public:
00716     name_comp(const std::string& name) : name_(name) {}
00718     bool operator()(const T_ele& ele) { return ele.name == name_; }
00719   private:
00720     const std::string& name_;
00721   };  // end class name_comp
00722 
00723   typedef std::vector<double> step_times_t;
00724   
00726   static const int
00727     TIME_STAT_TOTALS_OFFSET  = 0,
00728     TIME_STAT_AV_OFFSET    = 1,
00729     TIME_STAT_MIN_OFFSET    = 2,
00730     TIME_STAT_MAX_OFFSET    = 3,
00731     TIME_STAT_PERCENT_OFFSET  = 4;
00733   enum { NUM_STEP_TIME_STATS = 5 };
00734 
00736   typedef void (AlgorithmStep::*inform_func_ptr_t)(
00737     Algorithm&             algo
00738     ,poss_type             step_poss
00739     ,EDoStepType           type
00740     ,poss_type             assoc_step_poss
00741     );
00742 
00743   // /////////////////////////////////////////////////////
00744   // Private data members
00745 
00746   // aggregate members
00747 
00748 #ifdef DOXYGEN_COMPILE
00749   AlgorithmState       *state;
00750   AlgorithmTracker     *track;
00751   AlgorithmStep        *steps;
00752 #else
00753   state_ptr_t        state_;
00754   // RCP<...> object for the aggragate AlgorithmState object.
00755 
00756   track_ptr_t        track_;
00757   // RCP<...> object for the aggragate AlgorithmTracker object.
00758 #endif
00759 
00760   // algorithm control etc.
00761   
00762   ERunningState      running_state_;
00763   // The state this Algorithm object is in:
00764   //
00765   // NOT_RUNNING    do_algorithm() is not active.
00766   // RUNNING        do_algorithm() has been called and is active.
00767   // RUNNING_BEING_CONFIGURED
00768   //                do_algorithm() is active and begin_config_update() has been called
00769   //                but end_config_update() has not.
00770   //
00771   // Note: Only change this variable through the private function change_running_state(...)
00772   // unless you are 100% sure that you know what you are doing!
00773 
00774   size_t          first_k_;
00775   // The first iteration from state().k().
00776   
00777   size_t          max_iter_;
00778   // The maximum number of iterations that <tt>this</tt> will execute.
00779 
00780   double          max_run_time_;
00781   // The maximum amount of time the algorithm is allowed to execute.
00782 
00783   ETerminateStatus    terminate_status_;
00784   // Flag for if it is time to terminate do_algorithm().
00785 
00786   poss_type        next_step_poss_;
00787   // The next step possition that <tt>this</tt> will execute when control is returned to do_algorithm().
00788 
00789   const std::string*    next_step_name_;
00790   // The name of the next step that <tt>this</tt> will execute when control is returned to do_algorithm().
00791   
00792   bool          do_step_next_called_;
00793   // Flag for if do_step_next() was called so that <tt>do_algorithm()</tt> can validate
00794   // that if a step object returned <tt>false</tt> from its <tt>do_step()</tt> operation that it
00795   // must also call <tt>do_step_next()</tt> to specify a step to jump to.
00796 
00797   poss_type        curr_step_poss_;
00798   // The current step being executed in do_algorithm().
00799   // If the current step being executed is changed during the imp_do_step() operation, then
00800   // imp_do_step() must adjust to this step.
00801 
00802   std::string        saved_curr_step_name_;
00803   // The name of the current step that is saved when begin_config_update() is called
00804   // so that curr_step_poss_ can be reset when end_config_update() is called.
00805 
00806   std::string        saved_next_step_name_;
00807   // The name of the next step to call so that when begin_config_update() is called
00808   // so that next_step_poss_ and next_step_name_ can be reset when end_config_update()
00809   // is called.
00810 
00811   bool          reconfigured_;
00812   // A flag that is set to true when a runtime configuration has been preformed.  It
00813   // is used to flag this event for imp_do_assoc_steps().
00814 
00815   // step and associated step object data structures
00816 
00817   steps_t          steps_;
00818   // Array of std::pair<RCP<step_ptr_t>,std::string> objects.
00819   //
00820   // *steps_[step_poss].first returns the step object for step_poss = 1...steps_.size().
00821   // steps_[step_poss].second returns the name of the step for step_poss = 1...steps_.size().
00822 
00823   assoc_steps_t      assoc_steps_;
00824   // Array of two lists of std::pair<step_ptr_t,std::string> objects
00825   //
00826   // *(assoc_steps_[step_poss][PRE_STEP].begin() + pre_step_poss).first gives the pre step object.
00827   // (assoc_steps_[step_poss][PRE_STEP].begin() + pre_step_poss).second gives the name of the pre step
00828   // *(assoc_steps_[step_poss][POST_STEP].begin() + post_step_poss).first gives the post step object.
00829   // (assoc_steps_[step_poss][POST_STEP].begin() + post_step_poss).second gives the name of the post step
00830 
00831   bool algo_timing_;
00832   // If true each step will be timed.
00833 
00834   mutable step_times_t step_times_;
00835   // Array of step times ( size (max_iter() + 1 + NUM_STEP_TIME_STATS) * (num_steps() + 1) ).
00836   //  The time in sec. for step step_i (one based)
00837   // for iteration iter_k (zero based) is:
00838   //   step_times_[ iter_k + (step_i - 1) * (max_iter() + 1 + NUM_STEP_TIME_STATS) ].
00839   // Therefore the times for each step are stored by column (consecutive elements)
00840   // so that statistics will be easy to compute at the end.
00841   // The last five elements after max_iter() for each step are reserved for:
00842   // * total time for the step
00843   // * average time for the step
00844   // * min step time
00845   // * max step time
00846   // * percentage for each step to the total.
00847   // The last column is for the total times for each iteration with the last five
00848   // elements being for the statistics for each iteration.   
00849 
00850   mutable bool time_stats_computed_;
00851   // A flag for if the timing statistics have already been computed or not.
00852   
00853   mutable double total_time_;
00854   // Records the total computed time for the algorithm.
00855 
00856   // /////////////////////////////////////////////////////
00857   // Private member functions
00858 
00860   poss_type validate(poss_type step_poss, int past_end = 0) const;
00861 
00863   poss_type validate(const assoc_steps_ele_list_t& assoc_list, poss_type assoc_step_poss, int past_end = 0) const;
00864 
00866   void change_running_state(ERunningState running_state);
00867 
00869   void validate_in_state(ERunningState running_state) const;
00870 
00872   void validate_not_in_state(ERunningState running_state) const;
00873 
00875   void validate_not_curr_step(poss_type step_poss) const;
00876 
00878   void validate_not_next_step(const std::string& step_name) const;
00879 
00882   steps_t::iterator step_itr(const std::string& step_name);
00883 
00885   steps_t::const_iterator step_itr(const std::string& step_name) const;
00886 
00889   steps_t::iterator step_itr_and_assert(const std::string& step_name);
00890 
00892   steps_t::const_iterator step_itr_and_assert(const std::string& step_name) const;
00893 
00896   static assoc_steps_ele_list_t::iterator assoc_step_itr(assoc_steps_ele_list_t& assoc_list
00897     , const std::string& assoc_step_name);
00898 
00900   static assoc_steps_ele_list_t::const_iterator assoc_step_itr(const assoc_steps_ele_list_t& assoc_list
00901     , const std::string& assoc_step_name);
00902 
00904   bool imp_do_step(poss_type step_poss);
00905 
00907   bool imp_do_assoc_steps(EAssocStepType type);
00908 
00910   void imp_inform_steps(inform_func_ptr_t inform_func_ptr);
00911 
00913   void imp_print_algorithm(std::ostream& out, bool print_steps) const;
00914 
00916   EDoStepType do_step_type(EAssocStepType assoc_step_type);
00917 
00919   EAlgoReturn finalize_algorithm( EAlgoReturn algo_return );
00920 
00922   void compute_final_time_stats() const;
00923 
00924   // Look for interrup
00925   void look_for_interrupt();
00926 
00927 public:
00928 
00929   // This is put here out of need.  Not for any user to call!
00930   static void interrupt();
00931 
00932 };  // end class Algorithm
00933 
00934 // //////////////////////////////////////////////////////////////////////////////////////////////////
00935 // Inline member function definitions for Algorithm
00936 
00937 // «std comp» members for state 
00938 
00939 inline
00940 void Algorithm::set_state(const state_ptr_t& state)
00941 {  state_ = state; }
00942 
00943 inline
00944 Algorithm::state_ptr_t& Algorithm::get_state()
00945 {  return state_; }
00946 
00947 inline
00948 const Algorithm::state_ptr_t& Algorithm::get_state() const
00949 {  return state_; }
00950 
00951 inline
00952 AlgorithmState& Algorithm::state()
00953 {  TEUCHOS_TEST_FOR_EXCEPT( !( state_.get() ) ); return *state_; }
00954 
00955 inline
00956 const AlgorithmState& Algorithm::state() const
00957 {  TEUCHOS_TEST_FOR_EXCEPT( !( state_.get() ) ); return *state_; }
00958 
00959 // «std comp» members for track 
00960 
00961 inline
00962 void Algorithm::set_track(const track_ptr_t& track)
00963 {  track_ = track; }
00964 
00965 inline
00966 Algorithm::track_ptr_t& Algorithm::get_track()
00967 {  return track_; }
00968 
00969 inline
00970 const Algorithm::track_ptr_t& Algorithm::get_track() const
00971 {  return track_; }
00972 
00973 inline
00974 AlgorithmTracker& Algorithm::track()
00975 {  TEUCHOS_TEST_FOR_EXCEPT( !( track_.get() ) ); return *track_; }
00976 
00977 inline
00978 const AlgorithmTracker& Algorithm::track() const
00979 {  TEUCHOS_TEST_FOR_EXCEPT( !( track_.get() ) ); return *track_; }
00980 
00981 // running state
00982 
00983 inline
00984 Algorithm::ERunningState Algorithm::running_state() const
00985 {  return running_state_; }
00986 
00987 // lookup iterator given name
00988 
00989 inline
00990 Algorithm::steps_t::iterator Algorithm::step_itr(const std::string& step_name)
00991 {
00992   return std::find_if( steps_.begin() , steps_.end()
00993     , name_comp<steps_ele_t>(step_name) );
00994 }
00995 
00996 inline
00997 Algorithm::steps_t::const_iterator Algorithm::step_itr(const std::string& step_name) const
00998 {
00999   return std::find_if( steps_.begin() , steps_.end()
01000     , name_comp<steps_ele_t>(step_name) );
01001 }
01002 
01003 inline
01004 Algorithm::assoc_steps_ele_list_t::iterator Algorithm::assoc_step_itr(
01005   assoc_steps_ele_list_t& assoc_list, const std::string& assoc_step_name)
01006 {
01007   return std::find_if( assoc_list.begin() , assoc_list.end()
01008     , name_comp<assoc_steps_ele_list_ele_t>(assoc_step_name) );
01009 }
01010 
01011 inline
01012 Algorithm::assoc_steps_ele_list_t::const_iterator Algorithm::assoc_step_itr(
01013   const assoc_steps_ele_list_t& assoc_list, const std::string& assoc_step_name)
01014 {
01015   return std::find_if( assoc_list.begin() , assoc_list.end()
01016     , name_comp<assoc_steps_ele_list_ele_t>(assoc_step_name) );
01017 }
01018 
01019 inline
01020 EDoStepType Algorithm::do_step_type(EAssocStepType assoc_step_type) {
01021   switch(assoc_step_type) {
01022     case PRE_STEP  : return DO_PRE_STEP;
01023     case POST_STEP  : return DO_POST_STEP;
01024   }
01025   TEUCHOS_TEST_FOR_EXCEPT( !( true ) );
01026   return DO_PRE_STEP;  // will never execute.
01027 }
01028 
01029 }  // end namespace IterationPack 
01030 
01031 #endif // ALGORITHM_H
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends