/*-------------------------------------------------------------------------------------*/
/*  NOMAD - Nonsmooth Optimization by Mesh Adaptive Direct search - version 3.0.0      */
/*                                                                                     */
/*  Copyright (C) 2001-2008  Mark Abramson        - the Boeing Company, Seattle        */
/*                           Charles Audet        - Ecole Polytechnique, Montreal      */
/*                           Gilles Couture       - Ecole Polytechnique, Montreal      */
/*                           John Dennis          - Rice University, Houston           */
/*                           Sebastien Le Digabel - Ecole Polytechnique, Montreal      */
/*                                                                                     */
/*  funded in part by AFOSR and Exxon Mobil                                            */
/*                                                                                     */
/*  Author: Sebastien Le Digabel                                                       */
/*                                                                                     */
/*  Contact information:                                                               */
/*    Ecole Polytechnique de Montreal - GERAD                                          */
/*    C.P. 6079, Succ. Centre-ville, Montreal (Quebec) H3C 3A7 Canada                  */
/*    e-mail: Sebastien.Le.Digabel@gerad.ca                                            */
/*    phone : 1-514-340-6053 #6673                                                     */
/*    fax   : 1-514-340-5665                                                           */
/*                                                                                     */
/*  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/>.                               */
/*                                                                                     */
/*  You can find information on the NOMAD software at www.gerad.ca/nomad               */
/*-------------------------------------------------------------------------------------*/
#include "Barrier.hpp"
using namespace std;

/*---------------------------------------------------------*/
/*                    reset the barrier                    */
/*---------------------------------------------------------*/
void Barrier::reset ( void ) {
  _prefilter.clear();
  _filter.clear();
  _h_max           = _p.get_h_max_0();
  _best_feasible   = NULL;
  _ref             = NULL;
  _rho_leaps       = 0;
  _poll_center     = NULL;
  _sec_poll_center = NULL;

  if ( _peb_changes > 0 )
    _p.reset_PEB_changes();

  _peb_changes      = 0;
  _peb_filter_reset = 0;
  _peb_lop.clear();
}

/*---------------------------------------------------------*/
/*                         display                         */
/*---------------------------------------------------------*/
void Barrier::display ( ostream & out ) const {
  if ( _p.get_barrier_type() == _EB_ ) {
    out << "\textreme\n";
    return;
  }
  out << "\ttype                        : "
      << ( (_p.get_barrier_type()==_F_) ? "filter" : "progressive"  ) << endl
      << "\th_norm                      : " << _p.get_h_norm()   << endl
      << "\th_min                       : " << _p.get_h_min()    << endl
      << "\th_max                       : " << _h_max            << endl;
  if ( _p.get_barrier_type()==_PB_ || _p.get_barrier_type()==_PEB_P_ ) {
    out << "\tpoll center  trigger rho    : " << _p.get_rho()      << endl
	<< "\tnumber of trigger leaps     : " << _rho_leaps        << endl;
    if ( _p.get_barrier_type()==_PEB_P_ )
      out << "\tnumber of PEB changes       : " << _peb_changes << endl
	  << "\tnumber of PEB filter resets : " << _peb_filter_reset << endl;
  }
  if ( _p.get_display_degree() > 3 )
    out << "\t# of pre-filter points      : " << static_cast<int>(_prefilter.size()) << endl;
  out << "\t# of filter points          : " << static_cast<int>(_filter.size())    << endl;
  if ( !_filter.empty() ) {
    out << "\tfilter points               :\n";
    set<Filter_Point>::const_iterator end = _filter.end();
    for ( set<Filter_Point>::const_iterator it = _filter.begin() ; it != end ; ++it )
      out << "\t\t" << *it->get_point() << endl;
  }
}

/*------------------------------------------------------------*/
/*  barrier update: invoked by Evaluator_Control::eval_lop()  */
/*------------------------------------------------------------*/
bool Barrier::update ( success_type last_it_success ) {

  if ( (_p.get_barrier_type()==_PB_ || _p.get_barrier_type()==_PEB_P_) &&
       last_it_success != _UNSUCCESSFUL_ ) {

    if ( last_it_success == _PARTIAL_SUCCESS_ ) {

      if ( _filter.empty() ) {
	if ( _p.get_display_degree() > 0 )
	  _out << "\nError (" << __FILE__ "," << __LINE__
	       << "): filter empty after a partial success\n";
	return false;
      }

      set<Filter_Point>::const_iterator it = _filter.end();
      --it;

      while (true) {

	if ( it->get_point()->get_h() < _h_max ) {
	  set_h_max ( it->get_point()->get_h() );
	  break;
	}
	
	if ( it == _filter.begin() ) {
	  if ( _p.get_display_degree() > 0 )
	    _out << "\nError (" << __FILE__ "," << __LINE__
		 << "): could not find a filter point with h < h_max "
		 << "after a partial success\n";
	  return false;
	}
	--it;
      }    
    }

    _ref = get_best_infeasible();
    if (_ref)
      set_h_max ( _ref->get_h() );
  }

  return true;
}

/*---------------------------------------------------------*/
/*         insertion of an Eval_Point in the barrier       */
/*---------------------------------------------------------*/
success_type Barrier::insert ( const Eval_Point & x ) {  

  // basic checks:
  if ( !x.is_eval_ok() || !x.is_EB_ok() ||
       !x.get_f().is_defined() || !x.get_h().is_defined() ||
       x.get_h().value() > _h_max.value() )
    return _UNSUCCESSFUL_;

  // pre-filter: if tag(x) is already in the pre-filter,
  // then return _UNSUCCESSFUL_:
  size_t size_before = _prefilter.size();
  _prefilter.insert ( x.get_tag() );
  if ( _prefilter.size() == size_before )
    return _UNSUCCESSFUL_;

  // insert_feasible or insert_infeasible:
  return ( x.is_feasible ( _p.get_h_min() ) ) ?
    insert_feasible  (x) : insert_infeasible(x);
}

/*---------------------------------------------------------*/
/*                insertion of a feasible point            */
/*---------------------------------------------------------*/
success_type Barrier::insert_feasible ( const Eval_Point & x ) {
  if ( !_best_feasible || ( x.get_f().value() < _best_feasible->get_f().value() ) ) {
    _best_feasible = &x;
    return _FULL_SUCCESS_;
  }
  return _UNSUCCESSFUL_;
}

/*---------------------------------------------------------*/
/*                    filter insertion                     */
/*---------------------------------------------------------*/
void Barrier::filter_insertion ( const Eval_Point & x , bool & insert ) {

  if ( _filter.empty() ) {
    _filter.insert (&x);
    insert = true;
  }
  else {

    insert = false;
    set<Filter_Point>::iterator it = _filter.begin();
    while ( it != _filter.end() ) {
      if ( x < *(it->get_point()) ) {
	_filter.erase(it++);
	insert = true;
	continue;
      }

      ++it;
    }

    if ( !insert ) {
      insert = true;
      set<Filter_Point>::iterator end = _filter.end();
      for ( it = _filter.begin() ; it != end ; ++it ) {
	if ( *(it->get_point()) < x ) {
	  insert = false;
	  break;
	}
      }
    }

    if ( insert )
      _filter.insert (&x);
  }
}

/*---------------------------------------------------------*/
/*             insertion of an infeasible point            */
/*---------------------------------------------------------*/
success_type Barrier::insert_infeasible ( const Eval_Point & x ) {

  const Eval_Point * old_bi = get_best_infeasible();

  // filter insertion:
  // -----------------
  bool insert;
  filter_insertion ( x , insert );

  // filter:
  // -------
  if ( _p.get_barrier_type() == _F_ ) {
    const Eval_Point * bi = get_best_infeasible();
    if ( !bi )
      return _UNSUCCESSFUL_;
    if ( old_bi ) {
      if ( bi->get_h().value() < old_bi->get_h().value() )
	return _FULL_SUCCESS_;
      if (insert)
	return _PARTIAL_SUCCESS_;
      return _UNSUCCESSFUL_;
    }
    return _FULL_SUCCESS_;
  }

  // progressive barrier:
  // --------------------

  // with PEB constraints, we remember all points that we tried to insert:
  if ( _p.get_barrier_type() == _PEB_P_ )
    _peb_lop.push_back(&x);
  
  // first infeasible successes are considered as partial successes
  // (improving iterations)
  if ( !_ref )
    return _PARTIAL_SUCCESS_;

  double hx = x.get_h().value();
  double fx = x.get_f().value();
  double hr = _ref->get_h().value();
  double fr = _ref->get_f().value();

  // failure:
  if ( hx > hr || ( hx == hr && fx >= fr ) )
    return _UNSUCCESSFUL_;

  // partial success:
  if ( fx > fr )
    return _PARTIAL_SUCCESS_;

  // full success:
  return _FULL_SUCCESS_;
}

/*---------------------------------------------------------*/
/*                    get_best_infeasible()                */
/*---------------------------------------------------------*/
const Eval_Point * Barrier::get_best_infeasible ( void ) const {
  if ( _filter.empty() || _p.get_barrier_type() == _EB_ )
    return NULL;

  if ( _p.get_barrier_type() == _F_ )
    return _filter.begin()->get_point();

  return (--_filter.end())->get_point();
}

/*---------------------------------------------------------*/
/*                  poll center selection                  */
/*---------------------------------------------------------*/
void Barrier::select_poll_center ( success_type last_it_success ) {

  const Eval_Point * best_infeasible = get_best_infeasible();

  _sec_poll_center = NULL;
  if ( !_best_feasible && !best_infeasible ) {
    _poll_center = NULL;
    return;
  }
  if ( !best_infeasible ) {
    _poll_center = _best_feasible;
    return;
  }
  if ( !_best_feasible ) {
    _poll_center = best_infeasible;
    return;
  }

  // filter:
  if ( _p.get_barrier_type() == _F_ ) {

    if ( !_poll_center ) {
      _poll_center = _best_feasible;
      return;
    }

    if ( last_it_success == _UNSUCCESSFUL_ )
      _poll_center = ( _poll_center==best_infeasible ) ?
	_best_feasible : best_infeasible;
    return;
  }
  
  // progressive barrier:
  if ( _p.get_barrier_type() == _PB_ || _p.get_barrier_type() == _PEB_P_ ) {
    
    const Point * last_poll_center = _poll_center;

    if ( best_infeasible->get_f() < (_best_feasible->get_f() - _p.get_rho()) ) {
      _poll_center     = best_infeasible;
      _sec_poll_center = _best_feasible;
    }
    else {
      _poll_center     = _best_feasible;
      _sec_poll_center = best_infeasible;
    }
    if ( _poll_center != last_poll_center )
      ++_rho_leaps;
  }
}

/*---------------------------------------------------------*/
/*                change the value of _h_max               */
/*---------------------------------------------------------*/
void Barrier::set_h_max ( const NOMAD::Double & h_max ) {
    
  // _h_max update:
  _h_max = h_max;

  // we remove all filter points x such that h(x) > h_max:
  if ( !_filter.empty() ) {

    if ( _filter.begin()->get_point()->get_h().value() > _h_max.value() ) {
      _filter.clear();
      return;
    }

    set<Filter_Point>::iterator it = _filter.end();
    do
      --it;
    while ( it != _filter.begin() && it->get_point()->get_h().value() > _h_max.value() );
    ++it;
    _filter.erase ( it , _filter.end() );
  }
}

/*--------------------------------------------------------*/
/*  check the PEB constraints to change eventually their  */
/*  status from _PEB_P_ to _PEB_E_                        */
/*--------------------------------------------------------*/
void Barrier::check_PEB_constraints ( const Eval_Point & x , int display_degree ) {

  const NOMAD::Double          & h_min = _p.get_h_min();
  const vector<bb_output_type> & bbot  = _p.get_bb_output_types();
  const Point                  & bbo   = x.get_bb_outputs();
  int                            nb    = static_cast<int>(bbot.size());
  list<int>                      ks;

  for ( int k = 0 ; k < nb ; ++k ) {
    if ( bbot[k]==_PEB_P_ && bbo[k] <= h_min ) {
      if ( display_degree > 2 )
	_out << "\nchange status of black-box output " << k
	     << " from progressive barrier constraint to extreme barrier constraint" << endl;
      ++_peb_changes;
      _p.change_PEB_constraint_status (k);
      ks.push_back(k);
    }
  }

  // at least one constraint changed status, so we have to update the filter
  // and remove all points that have their h value changed to infinity
  // (it can add new dominant points from the list _peb_lop):
  if ( !ks.empty() ) {

    list<int>::const_iterator it_k , end_k = ks.end() , begin_k = ks.begin();

    // we inspect the filter points if some have to be removed; if so,
    // all filter candidates (stored in _peb_lop) will be re-inserted
    // into the filter:
    bool reset_filter = false;
    set<Filter_Point>::const_iterator end = _filter.end();

    for ( set<Filter_Point>::const_iterator it = _filter.begin() ; it != end ; ++it ) {

      const Point & bbo_cur = it->get_point()->get_bb_outputs();
      for ( it_k = begin_k ; it_k != end_k ; ++it_k )
	if ( bbo_cur[*it_k] > h_min ) {
	  reset_filter = true;
	  break;
	}
      if ( reset_filter )
	break;
    }

    if ( reset_filter ) {

      if ( display_degree > 2 )
	_out << "\nPEB change of status: filter reset" << endl;

      ++_peb_filter_reset;

      _filter.clear();
      bool insert;

      list<const Eval_Point *>::const_iterator end2 = _peb_lop.end  ();
      list<const Eval_Point *>::iterator       it2  = _peb_lop.begin();

      while ( it2 != end2 ) {

 	insert = true;
 	const Point & bbo_cur = (*it2)->get_bb_outputs();

 	for ( it_k = begin_k ; it_k != end_k ; ++it_k )
 	  if ( bbo_cur[*it_k] > h_min ) {
 	    insert = false;
 	    break;
 	  }

	// if insert==true: this point is potentially a new filter point:
 	if ( insert ) {
	  filter_insertion ( **it2 , insert );
	  ++it2;
	}

	// if insert==false: it means that the current filter point
	// has to be removed from filter and from _peb_lop, and
	// in addition, its h is put to INF:
	else {
	  Cache::get_modifiable_point ( **it2 ).set_h ( NOMAD::Double() );
	  _peb_lop.erase(it2++);
	}

      }
    }
  }
}
