HallOfFame.hh

Go to the documentation of this file.

#ifndef CASM_HallOfFame
#define CASM_HallOfFame

#include <set>

#include "casm/misc/CASM_math.hh"

namespace CASM {

  template<typename ObjectType, typename Metric, typename ObjectCompare = std::less<ObjectType> >
  class HallOfFame {

  public:

    typedef std::pair<double, ObjectType> PairType;

    class Compare {

    public:

      Compare(ObjectCompare _obj_compare, double _score_tol) :
        m_score_compare(_score_tol), m_obj_compare(_obj_compare) {}

      bool operator()(const PairType &A, const PairType &B) const {

        if(m_score_compare(A.first, B.first)) {
          return true;
        }
        if(m_score_compare(B.first, A.first)) {
          return false;
        }
        return m_obj_compare(A.second, B.second);
      }

    private:

      FloatCompare m_score_compare;
      ObjectCompare m_obj_compare;

    };

    typedef std::set<PairType, Compare> ContainerType;
    typedef typename ContainerType::const_iterator const_iterator;
    typedef typename ContainerType::const_reverse_iterator const_reverse_iterator;
    typedef Index size_type;

    struct InsertResult {

      typedef HallOfFame::const_iterator const_iterator;

      InsertResult(const_iterator _pos, bool _success, double _score, bool _excluded, const_iterator _excluded_pos) :
        pos(_pos), success(_success), score(_score), excluded(_excluded), excluded_pos(_excluded_pos) {}

      InsertResult(std::pair<const_iterator, bool> _res, double _score, bool _excluded, const_iterator _excluded_pos) :
        pos(_res.first), success(_res.second), score(_score), excluded(_excluded), excluded_pos(_excluded_pos)  {}

      const_iterator pos;
      bool success;
      double score;
      bool excluded;
      const_iterator excluded_pos;
    };

    HallOfFame(Metric _metric, ObjectCompare _obj_compare = std::less<ObjectType>(), Index _max_size = 100, double _score_tol = TOL):
      m_metric(_metric),
      m_obj_compare(_obj_compare),
      m_score_compare(_score_tol),
      m_halloffame(Compare(m_obj_compare, _score_tol)),
      m_check_exclude(false),
      m_exclude(Compare(m_obj_compare, _score_tol)),
      m_max_size(_max_size) {}

    void exclude(const ObjectType &obj) {
      m_exclude.insert(PairType(m_metric(obj), obj));
      m_check_exclude = true;
    }

    template<typename ObjectIterator>
    void exclude(ObjectIterator begin, ObjectIterator end) {
      for(auto it = begin; it != end; ++it) {
        exclude(*it);
      }
    }

    void clear_excluded() {
      m_exclude.clear();
    }

    Metric metric() const {
      return m_metric;
    }

    bool empty() const {
      return m_halloffame.empty();
    }

    size_type size() const {
      return m_halloffame.size();
    }

    size_type max_size() const {
      return m_max_size;
    }

    InsertResult insert(const ObjectType &obj) {

      auto excluded_pos = m_exclude.end();
      if(m_max_size <= 0) {
        return InsertResult(m_halloffame.end(), false, std::numeric_limits<double>::quiet_NaN(), false, excluded_pos);
      }

      double score = m_metric(obj);

      // if score is not good enough for hall of fame, do not insert
      if(m_halloffame.size() == m_max_size && m_score_compare(m_halloffame.rbegin()->first, score)) {
        return InsertResult(m_halloffame.end(), false, score, false, excluded_pos);
      }

      PairType test(score, obj);

      // insert
      auto res = m_halloffame.insert(test);

      // if not successful because it already exists in the hall of fame
      if(!res.second) {
        return InsertResult(res, score, false, excluded_pos);
      }

      // if successful, check if in exclude list
      if(m_check_exclude) {
        excluded_pos = m_exclude.find(test);
        if(excluded_pos != m_exclude.end()) {
          m_halloffame.erase(res.first);
          return InsertResult(m_halloffame.end(), false, score, true, excluded_pos);
        }
      }

      // remove any extras
      if(m_halloffame.size() > m_max_size) {
        m_halloffame.erase(std::prev(m_halloffame.end()));
      }

      return InsertResult(res, score, false, excluded_pos);
    }

    void clear() {
      m_halloffame.clear();
    }

    const_iterator begin() const {
      return m_halloffame.begin();
    }

    const_iterator cbegin() const {
      return m_halloffame.cbegin();
    }

    const_iterator end() const {
      return m_halloffame.end();
    }

    const_iterator cend() const {
      return m_halloffame.cend();
    }

    const_reverse_iterator rbegin() const {
      return m_halloffame.rbegin();
    }

    const_reverse_iterator crbegin() const {
      return m_halloffame.crbegin();
    }

    const_reverse_iterator rend() const {
      return m_halloffame.rend();
    }

    const_reverse_iterator crend() const {
      return m_halloffame.crend();
    }

    std::pair<const_iterator, const_iterator> equal_range(double key) const {
      return m_halloffame.equal_range(key);
    }

    size_type count(double key) const {
      return m_halloffame.count(key);
    }

    const_iterator find(double key) const {
      return m_halloffame.find(key);
    }

    const_iterator lower_bound(double key) const {
      return m_halloffame.lower_bound(key);
    }

    const_iterator upper_bound(double key) const {
      return m_halloffame.upper_bound(key);
    }


  private:

    Metric m_metric;
    ObjectCompare m_obj_compare;
    FloatCompare m_score_compare;
    ContainerType m_halloffame;
    bool m_check_exclude;
    ContainerType m_exclude;
    Index m_max_size;

  };

}

#endif