IterationPack_Algorithm.hpp

Go to the documentation of this file.

// @HEADER
// ***********************************************************************
// 
// Moocho: Multi-functional Object-Oriented arCHitecture for Optimization
//                  Copyright (2003) Sandia Corporation
// 
// Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
// license for use of this work by or on behalf of the U.S. Government.
// 
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// 1. Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
//
// 3. Neither the name of the Corporation nor the names of the
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// Questions? Contact Roscoe A. Bartlett (rabartl@sandia.gov) 
// 
// ***********************************************************************
// @HEADER

#ifndef ALGORITHM_H
#define ALGORITHM_H

#include <assert.h>

#include <string>
#include <deque>
#include <list>
#include <vector>
#include <algorithm>

#include "IterationPack_AlgorithmState.hpp"
#include "IterationPack_AlgorithmTracker.hpp"
#include "IterationPack_AlgorithmStep.hpp"
#include "Teuchos_RCP.hpp"
#include "Teuchos_Assert.hpp"
#include "Teuchos_StandardMemberCompositionMacros.hpp"

namespace IterationPack {

// ToDo: 7/31/98: Finish documentation.

class Algorithm {
public:


  typedef Teuchos::RCP<AlgorithmState>      state_ptr_t;
  typedef Teuchos::RCP<AlgorithmTracker>    track_ptr_t;
  typedef Teuchos::RCP<AlgorithmStep>       step_ptr_t;
  typedef size_t                                    poss_type;
  enum { DOES_NOT_EXIST = 1000 };  // never be that many steps
  enum ERunningState { NOT_RUNNING = 0, RUNNING = 1, RUNNING_BEING_CONFIGURED = 2 };

  class DoesNotExist : public std::logic_error
  {public: DoesNotExist(const std::string& what_arg) : std::logic_error(what_arg) {}};

  class AlreadyExists : public std::logic_error
  {public: AlreadyExists(const std::string& what_arg) : std::logic_error(what_arg) {}};

  class InvalidControlProtocal : public std::logic_error
  {public: InvalidControlProtocal(const std::string& what_arg) : std::logic_error(what_arg) {}};

  class InvalidRunningState : public std::logic_error
  {public: InvalidRunningState(const std::string& what_arg) : std::logic_error(what_arg) {}};

  class InvalidConfigChange : public std::logic_error
  {public: InvalidConfigChange(const std::string& what_arg) : std::logic_error(what_arg) {}};

  class AlgorithmInterrupted : public std::runtime_error
  {public: AlgorithmInterrupted(const std::string& what_arg) : std::runtime_error(what_arg) {}};



  Algorithm();

  virtual ~Algorithm();


  STANDARD_MEMBER_COMPOSITION_MEMBERS( std::string, interrupt_file_name );


  void set_state(const state_ptr_t& state);
  state_ptr_t& get_state();
  const state_ptr_t& get_state() const;
  AlgorithmState& state();
  const AlgorithmState& state() const;



  void set_track(const track_ptr_t& track);
  track_ptr_t& get_track();
  const track_ptr_t& get_track() const;
  AlgorithmTracker& track();
  const AlgorithmTracker& track() const;


  
  virtual void max_iter(size_t max_iter);
  virtual size_t max_iter() const;


  
  virtual void max_run_time(double max_iter);
  virtual double max_run_time() const;



  virtual int num_steps() const;

  virtual poss_type get_step_poss(const std::string& step_name) const;

  virtual const std::string& get_step_name(poss_type step_poss) const;

  virtual step_ptr_t& get_step(poss_type step_poss);

  virtual const step_ptr_t& get_step(poss_type step_poss) const;



  virtual int num_assoc_steps(poss_type step_poss, EAssocStepType type) const;

  virtual poss_type get_assoc_step_poss(poss_type step_poss, EAssocStepType type
    ,const std::string& assoc_step_name) const;

  virtual const std::string& get_assoc_step_name(poss_type step_poss, EAssocStepType type
    , poss_type assoc_step_poss) const;

  virtual step_ptr_t& get_assoc_step(poss_type step_poss, EAssocStepType type
    , poss_type assoc_step_poss);

  virtual const step_ptr_t& get_assoc_step(poss_type step_poss, EAssocStepType type
    , poss_type assoc_step_poss) const;



  virtual void insert_step(poss_type step_poss, const std::string& step_name, const step_ptr_t& step);

  virtual void change_step_name(poss_type step_poss, const std::string& new_name);

  virtual void replace_step(poss_type step_poss, const step_ptr_t& step);

  virtual void remove_step(poss_type step_poss);



  virtual void insert_assoc_step(poss_type step_poss, EAssocStepType type, poss_type assoc_step_poss
    , const std::string& assoc_step_name, const step_ptr_t& assoc_step);

  virtual void remove_assoc_step(poss_type step_poss, EAssocStepType type, poss_type assoc_step_poss);



  ERunningState running_state() const;

  virtual void begin_config_update();

  virtual void end_config_update();



  virtual void do_step_next(const std::string& step_name);

  virtual void do_step_next(poss_type step_poss);

  virtual const std::string& what_is_next_step_name() const;

  virtual poss_type what_is_next_step_poss() const;

  virtual bool do_step(const std::string& step_name);

  virtual bool do_step(poss_type step_poss);

  virtual void terminate(bool success);



  virtual EAlgoReturn do_algorithm(poss_type step_poss = 1);



  virtual void print_steps(std::ostream& out) const;

  virtual void print_algorithm(std::ostream& out) const;



  virtual void set_algo_timing( bool algo_timing );

  virtual bool algo_timing() const;

  virtual void print_algorithm_times( std::ostream& out ) const;

  void get_step_times_k( int offset, double step_times[] ) const;

  void get_final_step_stats( size_t step, double* total, double* average, double* min, double* max, double* percent) const;


private:

  // /////////////////////////////////////////////////////
  // Private types

  template<class T_Step_ptr>
  struct step_ptr_and_name {
    step_ptr_and_name(const T_Step_ptr& _step_ptr
        , const std::string& _name )
      : step_ptr(_step_ptr), name(_name)
    {}
    T_Step_ptr step_ptr;
    //
    std::string name;
  };  // end struct step_ptr_and_name

  typedef step_ptr_and_name<step_ptr_t>           steps_ele_t;
  typedef std::deque<steps_ele_t>                 steps_t;

  typedef step_ptr_and_name<step_ptr_t>           assoc_steps_ele_list_ele_t;
  typedef std::list<assoc_steps_ele_list_ele_t>   assoc_steps_ele_list_t;
  struct assoc_steps_ele_t {
    assoc_steps_ele_list_t& operator[](int i)
    { return assoc_steps_lists_[i]; }
    const assoc_steps_ele_list_t& operator[](int i) const
    { return assoc_steps_lists_[i]; }
  private:
    assoc_steps_ele_list_t assoc_steps_lists_[2];
  };

  //typedef assoc_steps_ele_list_t[2]        assoc_steps_ele_t; // PRE_STEP, POST_STEP
  typedef std::deque<assoc_steps_ele_t>      assoc_steps_t;
  
  enum ETerminateStatus { STATUS_KEEP_RUNNING, STATUS_TERMINATE_TRUE, STATUS_TERMINATE_FALSE };

  template<class T_ele>
  class name_comp {
  public:
    name_comp(const std::string& name) : name_(name) {}
    bool operator()(const T_ele& ele) { return ele.name == name_; }
  private:
    const std::string& name_;
  };  // end class name_comp

  typedef std::vector<double> step_times_t;
  
  static const int
    TIME_STAT_TOTALS_OFFSET  = 0,
    TIME_STAT_AV_OFFSET    = 1,
    TIME_STAT_MIN_OFFSET    = 2,
    TIME_STAT_MAX_OFFSET    = 3,
    TIME_STAT_PERCENT_OFFSET  = 4;
  enum { NUM_STEP_TIME_STATS = 5 };

  typedef void (AlgorithmStep::*inform_func_ptr_t)(
    Algorithm&             algo
    ,poss_type             step_poss
    ,EDoStepType           type
    ,poss_type             assoc_step_poss
    );

  // /////////////////////////////////////////////////////
  // Private data members

  // aggregate members

#ifdef DOXYGEN_COMPILE
  AlgorithmState       *state;
  AlgorithmTracker     *track;
  AlgorithmStep        *steps;
#else
  state_ptr_t        state_;
  // RCP<...> object for the aggragate AlgorithmState object.

  track_ptr_t        track_;
  // RCP<...> object for the aggragate AlgorithmTracker object.
#endif

  // algorithm control etc.
  
  ERunningState      running_state_;
  // The state this Algorithm object is in:
  //
  // NOT_RUNNING    do_algorithm() is not active.
  // RUNNING        do_algorithm() has been called and is active.
  // RUNNING_BEING_CONFIGURED
  //                do_algorithm() is active and begin_config_update() has been called
  //                but end_config_update() has not.
  //
  // Note: Only change this variable through the private function change_running_state(...)
  // unless you are 100% sure that you know what you are doing!

  size_t          first_k_;
  // The first iteration from state().k().
  
  size_t          max_iter_;
  // The maximum number of iterations that <tt>this</tt> will execute.

  double          max_run_time_;
  // The maximum amount of time the algorithm is allowed to execute.

  ETerminateStatus    terminate_status_;
  // Flag for if it is time to terminate do_algorithm().

  poss_type        next_step_poss_;
  // The next step possition that <tt>this</tt> will execute when control is returned to do_algorithm().

  const std::string*    next_step_name_;
  // The name of the next step that <tt>this</tt> will execute when control is returned to do_algorithm().
  
  bool          do_step_next_called_;
  // Flag for if do_step_next() was called so that <tt>do_algorithm()</tt> can validate
  // that if a step object returned <tt>false</tt> from its <tt>do_step()</tt> operation that it
  // must also call <tt>do_step_next()</tt> to specify a step to jump to.

  poss_type        curr_step_poss_;
  // The current step being executed in do_algorithm().
  // If the current step being executed is changed during the imp_do_step() operation, then
  // imp_do_step() must adjust to this step.

  std::string        saved_curr_step_name_;
  // The name of the current step that is saved when begin_config_update() is called
  // so that curr_step_poss_ can be reset when end_config_update() is called.

  std::string        saved_next_step_name_;
  // The name of the next step to call so that when begin_config_update() is called
  // so that next_step_poss_ and next_step_name_ can be reset when end_config_update()
  // is called.

  bool          reconfigured_;
  // A flag that is set to true when a runtime configuration has been preformed.  It
  // is used to flag this event for imp_do_assoc_steps().

  // step and associated step object data structures

  steps_t          steps_;
  // Array of std::pair<RCP<step_ptr_t>,std::string> objects.
  //
  // *steps_[step_poss].first returns the step object for step_poss = 1...steps_.size().
  // steps_[step_poss].second returns the name of the step for step_poss = 1...steps_.size().

  assoc_steps_t      assoc_steps_;
  // Array of two lists of std::pair<step_ptr_t,std::string> objects
  //
  // *(assoc_steps_[step_poss][PRE_STEP].begin() + pre_step_poss).first gives the pre step object.
  // (assoc_steps_[step_poss][PRE_STEP].begin() + pre_step_poss).second gives the name of the pre step
  // *(assoc_steps_[step_poss][POST_STEP].begin() + post_step_poss).first gives the post step object.
  // (assoc_steps_[step_poss][POST_STEP].begin() + post_step_poss).second gives the name of the post step

  bool algo_timing_;
  // If true each step will be timed.

  mutable step_times_t step_times_;
  // Array of step times ( size (max_iter() + 1 + NUM_STEP_TIME_STATS) * (num_steps() + 1) ).
  //  The time in sec. for step step_i (one based)
  // for iteration iter_k (zero based) is:
  //   step_times_[ iter_k + (step_i - 1) * (max_iter() + 1 + NUM_STEP_TIME_STATS) ].
  // Therefore the times for each step are stored by column (consecutive elements)
  // so that statistics will be easy to compute at the end.
  // The last five elements after max_iter() for each step are reserved for:
  // * total time for the step
  // * average time for the step
  // * min step time
  // * max step time
  // * percentage for each step to the total.
  // The last column is for the total times for each iteration with the last five
  // elements being for the statistics for each iteration.   

  mutable bool time_stats_computed_;
  // A flag for if the timing statistics have already been computed or not.
  
  mutable double total_time_;
  // Records the total computed time for the algorithm.

  // /////////////////////////////////////////////////////
  // Private member functions

  poss_type validate(poss_type step_poss, int past_end = 0) const;

  poss_type validate(const assoc_steps_ele_list_t& assoc_list, poss_type assoc_step_poss, int past_end = 0) const;

  void change_running_state(ERunningState running_state);

  void validate_in_state(ERunningState running_state) const;

  void validate_not_in_state(ERunningState running_state) const;

  void validate_not_curr_step(poss_type step_poss) const;

  void validate_not_next_step(const std::string& step_name) const;

  steps_t::iterator step_itr(const std::string& step_name);

  steps_t::const_iterator step_itr(const std::string& step_name) const;

  steps_t::iterator step_itr_and_assert(const std::string& step_name);

  steps_t::const_iterator step_itr_and_assert(const std::string& step_name) const;

  static assoc_steps_ele_list_t::iterator assoc_step_itr(assoc_steps_ele_list_t& assoc_list
    , const std::string& assoc_step_name);

  static assoc_steps_ele_list_t::const_iterator assoc_step_itr(const assoc_steps_ele_list_t& assoc_list
    , const std::string& assoc_step_name);

  bool imp_do_step(poss_type step_poss);

  bool imp_do_assoc_steps(EAssocStepType type);

  void imp_inform_steps(inform_func_ptr_t inform_func_ptr);

  void imp_print_algorithm(std::ostream& out, bool print_steps) const;

  EDoStepType do_step_type(EAssocStepType assoc_step_type);

  EAlgoReturn finalize_algorithm( EAlgoReturn algo_return );

  void compute_final_time_stats() const;

  // Look for interrup
  void look_for_interrupt();

public:

  // This is put here out of need.  Not for any user to call!
  static void interrupt();

};  // end class Algorithm

// //////////////////////////////////////////////////////////////////////////////////////////////////
// Inline member function definitions for Algorithm

// «std comp» members for state 

inline
void Algorithm::set_state(const state_ptr_t& state)
{  state_ = state; }

inline
Algorithm::state_ptr_t& Algorithm::get_state()
{  return state_; }

inline
const Algorithm::state_ptr_t& Algorithm::get_state() const
{  return state_; }

inline
AlgorithmState& Algorithm::state()
{  TEUCHOS_TEST_FOR_EXCEPT( !( state_.get() ) ); return *state_; }

inline
const AlgorithmState& Algorithm::state() const
{  TEUCHOS_TEST_FOR_EXCEPT( !( state_.get() ) ); return *state_; }

// «std comp» members for track 

inline
void Algorithm::set_track(const track_ptr_t& track)
{  track_ = track; }

inline
Algorithm::track_ptr_t& Algorithm::get_track()
{  return track_; }

inline
const Algorithm::track_ptr_t& Algorithm::get_track() const
{  return track_; }

inline
AlgorithmTracker& Algorithm::track()
{  TEUCHOS_TEST_FOR_EXCEPT( !( track_.get() ) ); return *track_; }

inline
const AlgorithmTracker& Algorithm::track() const
{  TEUCHOS_TEST_FOR_EXCEPT( !( track_.get() ) ); return *track_; }

// running state

inline
Algorithm::ERunningState Algorithm::running_state() const
{  return running_state_; }

// lookup iterator given name

inline
Algorithm::steps_t::iterator Algorithm::step_itr(const std::string& step_name)
{
  return std::find_if( steps_.begin() , steps_.end()
    , name_comp<steps_ele_t>(step_name) );
}

inline
Algorithm::steps_t::const_iterator Algorithm::step_itr(const std::string& step_name) const
{
  return std::find_if( steps_.begin() , steps_.end()
    , name_comp<steps_ele_t>(step_name) );
}

inline
Algorithm::assoc_steps_ele_list_t::iterator Algorithm::assoc_step_itr(
  assoc_steps_ele_list_t& assoc_list, const std::string& assoc_step_name)
{
  return std::find_if( assoc_list.begin() , assoc_list.end()
    , name_comp<assoc_steps_ele_list_ele_t>(assoc_step_name) );
}

inline
Algorithm::assoc_steps_ele_list_t::const_iterator Algorithm::assoc_step_itr(
  const assoc_steps_ele_list_t& assoc_list, const std::string& assoc_step_name)
{
  return std::find_if( assoc_list.begin() , assoc_list.end()
    , name_comp<assoc_steps_ele_list_ele_t>(assoc_step_name) );
}

inline
EDoStepType Algorithm::do_step_type(EAssocStepType assoc_step_type) {
  switch(assoc_step_type) {
    case PRE_STEP  : return DO_PRE_STEP;
    case POST_STEP  : return DO_POST_STEP;
  }
  TEUCHOS_TEST_FOR_EXCEPT( !( true ) );
  return DO_PRE_STEP;  // will never execute.
}

}  // end namespace IterationPack 

#endif // ALGORITHM_H