/*****************************************************************//**
 * \file   BestFirstStrategy.h
 * \brief  Searches the branch and bound tree by best first policy where the subproblems are ranked on the basis of the best (lower or lower ?) bound.
 * 
 * \author talmefta
 * \date   June 2022
 *********************************************************************/
#ifndef BESTFIRSTSTRATEGY_H
#define BESTFIRSTSTRATEGY_H

#include "SearchStrategy.h"


/**
 * \class BestFirstStrategy
 * \brief  Searches the branch and bound tree by best first policy where the subproblems are ranked on the basis of the best (lower or lower ?) bound.
 * \details Inherets from SearchStrategy.
 */
template<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration, class ConstraintType>
class BestFirstStrategy :

    public SearchStrategy<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType> {

private:
    bool is_maximisation;

public:
    BestFirstStrategy(bool isMaximisation = false) : is_maximisation(isMaximisation) {

    }

    /**
     * The node list is sorted by increasing dual bound, in case of minimisation
     * The node list is sorted by decreasing dual bound, in case of maximisation
     *
     * \param node_list
     * \param new_node
     * \return
     */
    bool is_position_found(const double& new_node_dual_bound, const double& node_in_list_dual_bound) const {
        if (this->is_maximisation) {
            return ::strictly_greater(new_node_dual_bound, node_in_list_dual_bound);
        }
        return ::strictly_less(new_node_dual_bound, node_in_list_dual_bound);
    }

    /**
     * Adds the new node to the list of nodes in the branch and price tree. The node list is sorted by increasing lower bound.
     *
     * \param node_list
     * \param new_node
     * \return 
     */
    void add_node(list<Node< RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType>>& node_list,
        Node<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType>& new_node) const override {
        typename list<Node<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType>>::iterator where_to_insert = node_list.begin();
        int position = 0;
        if (!node_list.empty()) {
            for (typename list<Node<RestrictedMasterProblem, PricingSubProblem, ColumnGeneration, ConstraintType>>::iterator node = node_list.begin(); node != node_list.end(); node++)
                if (is_position_found(new_node.get_dual_bound(), node->get_dual_bound()))
                    break;
                else
                    position++;
        }
        advance(where_to_insert, position);
        where_to_insert = node_list.insert(where_to_insert, new_node);
        where_to_insert->add_me_to_the_list_observers();
    }
};

#endif // !BESTFIRSTSTRATEGY_H