#ifndef EXERCISES_HH
#define EXERCISES_HH

#include <algorithm>
#include <list>
#include <map>
#include <queue>
#include <set>

// Exercise 1 - Using std::priority_queue

typedef std::pair<int, double> Element;

struct ElementGreater {
  bool operator() (Element const &e1, Element const &e2) const {
    return e1.first > e2.first;
  }
};

double add_subtract(std::list<Element> const &lst)
{
  std::priority_queue<Element, std::vector<Element>, ElementGreater> queue;
  for(std::list<Element>::const_iterator i = lst.begin(); i != lst.end(); ++i)
    queue.push(*i);
  double result = 0.0, sign = 1.0;
  while(!queue.empty()) {
    result += sign * queue.top().second;
    queue.pop();
    sign *= -1.0;
  }
  return result;
}

// Exercise 1 - Using algorithm (std::copy & std::sort) [better]

typedef std::pair<int, double> Element;

inline
bool elementLess(Element const &e1, Element const &e2) {
  return e1.first < e2.first;
}

double add_subtract(std::list<Element> const &lst)
{
  std::vector<Element> sorted;
  std::copy(lst.begin(), lst.end(), std::back_inserter(sorted));
  std::sort(sorted.begin(), sorted.end(), &elementLess);
  double result = 0.0, sign = 1.0;
  for(std::vector<Element>::const_iterator i = sorted.begin();
      i != sorted.end(); ++i, sign *= -1.0)
    result += sign * i->second;
  return result;
}

// Exercise 2

struct MyType {
  int priority;
  std::string data;
  MyType(int p, std::string d) : priority(p), data(d) { }
};

struct MyTypeLess {
  bool operator() (MyType const &a, MyType const &b) const
  {
    return a.priority < b.priority;
  }
};

typedef std::multiset<MyType, MyTypeLess> MyMSet;
typedef std::map<int, std::string> MyMap;

inline
bool myLess(MyType const &a, MyType const &b)
{
  return a.data < b.data;
}

MyMap minimum_value(MyMSet const &ms)
{
  MyMap result;
  for(MyMSet::const_iterator i = ms.begin(); i != ms.end();
      i = ms.upper_bound(*i)) {
    std::pair<MyMSet::iterator, MyMSet::iterator> p = ms.equal_range(*i);
    result[i->priority] = std::min_element(p.first, p.second, &myLess)->data;
  }
  return result;
}

#endif // EXERCISES_HH