priority_collection

#include "test_runner.h"
#include <algorithm>
#include <iostream>
#include <iterator>
#include <memory>
#include <set>
#include <utility>
#include <vector>

using namespace std;

template <typename T>
class PriorityCollection {
public:
  using Id = typename vector<T>::reference;
  // Добавить объект с нулевым приоритетом
  // с помощью перемещения и вернуть его идентификатор
  Id Add(T object){
      obj.push_back(move(object));
      Id res(ref(*obj.rbegin()));
      priorities.insert(make_pair(ref(*obj.rbegin()),0));
      return res;
  }

  // Добавить все элементы диапазона [range_begin, range_end)
  // с помощью перемещения, записав выданные им идентификаторы
  // в диапазон [ids_begin, ...)
  template <typename ObjInputIt, typename IdOutputIt>
  void Add(ObjInputIt range_begin, ObjInputIt range_end,
           IdOutputIt ids_begin){
      while(range_begin!=range_end){
          ids_begin++ = ref(*obj.insert(move(range_begin++)).first);
      }
  }

  // Определить, принадлежит ли идентификатор какому-либо
  // хранящемуся в контейнере объекту
  bool IsValid(Id id) const{
      return obj.find(id)!=obj.end();
  }

  // Получить объект по идентификатору
  const T& Get(Id id) const{
      return id;
  }

  // Увеличить приоритет объекта на 1
  void Promote(Id id){
      int space2;
      for(auto &&it:priorities){
          if(it.first == id){
              space2 = it.second;
              priorities.erase(it);
              break;
          }
      }
      pair<Id,int> res(id,space2);
      priorities.insert(res);

  }

  // Получить объект с максимальным приоритетом и его приоритет
  pair<const T&, int> GetMax() const{
      return *priorities.rbegin();
  }

  // Аналогично GetMax, но удаляет элемент из контейнера
  pair<T, int> PopMax(){
      pair<Id,int> space(*priorities.rbegin());
      vector<T> res;
      res.push_back(move(space.first));
      return make_pair(move(res[0]),space.second);
  }

  struct classcomp {
      bool operator() (const pair<Id,int>& lhs, const pair<Id,int>& rhs) const
      {return lhs.second<rhs.second;}
    };

private:
  vector<T> obj;
  set<pair<Id,int>,classcomp> priorities;
  // Приватные поля и методы
};


class StringNonCopyable : public string {
public:
  using string::string;  // Позволяет использовать конструкторы строки
  StringNonCopyable(const StringNonCopyable&) = delete;
  StringNonCopyable(StringNonCopyable&&) = default;
  StringNonCopyable& operator=(const StringNonCopyable&) = delete;
  StringNonCopyable& operator=(StringNonCopyable&&) = default;
};

void TestNoCopy() {
  PriorityCollection<StringNonCopyable> strings;
  const auto white_id = strings.Add("white");
  const auto yellow_id = strings.Add("yellow");
  const auto red_id = strings.Add("red");

  strings.Promote(yellow_id);
  for (int i = 0; i < 2; ++i) {
    strings.Promote(red_id);
  }
  strings.Promote(yellow_id);
  {
    const auto item = strings.PopMax();
    ASSERT_EQUAL(item.first, "red");
    ASSERT_EQUAL(item.second, 2);
  }
  {
    const auto item = strings.PopMax();
    ASSERT_EQUAL(item.first, "yellow");
    ASSERT_EQUAL(item.second, 2);
  }
  {
    const auto item = strings.PopMax();
    ASSERT_EQUAL(item.first, "white");
    ASSERT_EQUAL(item.second, 0);
  }
}

int main() {
  TestRunner tr;
  RUN_TEST(tr, TestNoCopy);
  return 0;
}