#include <string>
#include <map>
#include <vector>
#include <functional>
#include <unordered_map>
#include <set>
#include <utility>

template<
class Tp, template<typename>
class Compare
>
class DereferenceCompare{
    Compare < Tp > comp;
 public:
    bool operator()(const Tp* const a, const Tp* const b) const {
      return comp(*a, *b);
    }
};

class GameDatabase{
 public:
    GameDatabase() = default;

    /// вставляет в базу объект с именем [name] и позицией [x, y]
    /// если объект с таким id в базе уже есть, заменяет его новым
    void Insert(ObjectId id, string name, size_t x, size_t y) {
      GameObject *gO = new
      GameObject
      { id, name, x, y };
      dataById[id] = *gO;
      dataByName[name].insert(gO);
      dataByPos[std::make_pair(x, y)].insert(gO);
    }

    /// удаляет элемент по id
    /// если такого элемента нет, ничего не делает
    void Remove(ObjectId id) {
      if (dataById.find(id) != end(dataById)) {
        auto&gameObject = dataById[id];
        dataById.erase(gameObject.id);
        dataByName.erase(gameObject.name);
        dataByPos.erase(std::make_pair(gameObject.x, gameObject.y));
      }
    }

    /// возвращает вектор объектов c именем [name]
    /// сортировка по убыванию id
    vector<GameObject> DataByName(string name) const {
      std::vector<GameObject> result;
      auto iter = dataByName.find(name);
      if (iter == end(dataByName))
        return result;
      const auto
      &setNames = dataByName.at(name);

      for (const auto
        &elem : setNames)
        result.push_back(*elem);
      return result;
    }

    /// возвращает вектор объектов, находящихся в позиции [x, y]
    /// сортировка по убыванию id
    vector<GameObject> DataByPosition(size_t x, size_t y) const {
      std::vector<GameObject> result;
      auto iter = dataByPos.find(std::make_pair(x, y));
      if (iter == end(dataByPos))
        return result;
      const auto
      &setPoses = dataByPos.at(make_pair(x, y));
      for (const auto
        &elem : setPoses)
        result.push_back(*elem);
      return result;
    }

    /// возвращает вектор всех объектов из базы
    /// сортировка по убыванию id
    vector<GameObject> Data() const {
      std::vector<GameObject> result;
      for (const auto
        &elem : dataById)
        result.push_back(elem.second);
      return result;
    }

 private:
    std::map<
    ObjectId,
    GameObject,
    std::greater<ObjectId>
    > dataById;
    std::map<
    std::pair<size_t, size_t>,
    std::set< GameObject*, DereferenceCompare<
    GameObject,
    std::greater>
    >
    > dataByPos;
    std::unordered_map<
    string,
    std::set<
    GameObject*, DereferenceCompare<
    GameObject,
    std::greater>
    >
    > dataByName;
};