Задача A. GameDatabase ≡

Входной файл:	Стандартный вход		Ограничение времени:	1 сек
Выходной файл:	Стандартный выход		Ограничение памяти:	4000 Мб

Условие

Необходимо реализовать класс GameDatabase cо следующим интерфейсом:

     
        class GameDatabase
        {
        public:
            GameDatabase() = default;

            /// вставляет в базу объект с именем [name] и позицией [x, y]
            /// если объект с таким id в базе уже есть, заменяет его новым
            void Insert(ObjectId id, string name, size_t x, size_t y)

            /// удаляет элемент по id
            /// если такого элемента нет, ничего не делает
            void Remove(ObjectId id);

            /// возвращает вектор объектов c именем [name]
            /// сортировка по убыванию id
            vector<GameObject> DataByName(string name) const;

            /// возвращает вектор объектов, находящихся в позиции [x, y]
            /// сортировка по убыванию id
            vector<GameObject> DataByPosition(size_t x, size_t y) const;

            /// возвращает вектор всех объектов из базы
            /// сортировка по убыванию id
            vector<GameObject> Data() const;
        };
      
   

Код для GameObject и ObjectId указан ниже.

     
        using ObjectId = unsigned long long int;

        struct GameObject
        {
            ObjectId id;
            string name;
            size_t x;
            size_t y;
        };
      
    

Рекомендуется использовать структуры данных: std::unordered_map, std::map, std::set

Отдельная сортировка не потребуется если использовать компаратор для упорядоченных контейнеров (std::set, std::map)

Пример организации данных с компаратором:

          
          bool operator>(const GameObject& a, const GameObject& b) {
              return a.id > b.id;
          }

          template<class Tp, template<class> class Compare>
          class DereferenceCompare {
                Compare<Tp> comp;
            
          public:
              bool operator()(const Tp* const a, const Tp* const b) const {
                  return comp(*a, *b);
              }
          };
          
          /// быстрый доступ по id
          std::map<ObjectId, GameObject, std::greater<ObjectId>>
          
          /// быстрый доступ по позиции
          std::map<std::pair<size_t, size_t>, std::set<GameObject*, DereferenceCompare<GameObject, std::greater>>>
          
          /// быстрый доступ по имени
          std::unordered_map<string, std::set<GameObject*, DereferenceCompare<GameObject, std::greater>>>
          
      

Материалы задачи

main.cpp

1.in

2.in

3.in

4.in

5.in

6.in

7.in

1.ans

2.ans

3.ans

4.ans

5.ans

6.ans

7.ans

Формат выходных данных

Файл с решением должен содержать только реализацию класса GameDatabase без функции main.

---

Задача B. Аллокатор для связного списка ≡

Входной файл:	Стандартный вход		Ограничение времени:	1 сек
Выходной файл:	Стандартный выход		Ограничение памяти:	4000 Мб

Условие

Аллокатор — это класс, который инкапсулирует управление памятью.

Известная проблема аллокации для связных списков состоит в том, что при интенсивных операциях вставки и удаления может возникнуть эффект фрагментации системной памяти. Чтобы снизить влияние этого эффекта, предлагается запрашивать у операционной системы память на группу объектов и оперировать полученным буфером, что также снижает количество системных вызовов.

Необходимо реализовать класс FixedAllocator, который будет использовать необходимое количество непрерывных буферов как пул памяти для элементов списка. Размер страницы (размер одного непрерывного буфера), как и размер объектов, передается аллокатору как параметр конструктора.

Определение класса должно содержать следующие методы:

FixedAllocator(size_t chunk_size, size_t page_size) — конструктор, принимающий размер страницы памяти и размер одного объекта;

void* Allocate() — возвращает указатель на свободный участок памяти для одного элемента размера chunk_size;

void Deallocate(void*) — возвращает в пул память, занимаемую элементом.

Список использует метод Allocate, когда необходимо получить память для одного элемента, и Deallocate, когда память нужно освободить.

---

Задача C. Фабрика ≡

Входной файл:	Стандартный вход		Ограничение времени:	1 сек
Выходной файл:	Стандартный выход		Ограничение памяти:	4096 Мб

Условие

Реализуйте паттерн проектирования "Фабрика".

Фабрика может создавать произвольных потомков базового класса. В нашем случае базовым классом будет Object, а сама фабрика — классом Factory. Определение класса Object должно быть в точности таким:

    
class Object {
  public:
    virtual std::string ToString() const = 0;
    virtual ~Object() {}
};
    
    

Метод ToString является абстрактным. Это означает, что все потомки Object обязаны перегрузить этот метод.

Ваша фабрика должна уметь понимать, потомка какого типа от неё хотят получить в данный момент. Это означает, что у каждого потомка должен быть некоторый идентификатор. В этом задании будем использовать строковые идентификаторы.

Фабрика поддерживает всего две операции. Одна из них:

Object* Create(const std::string& class_id) — этот метод класса Factory получает на вход идентификатор класса, создает экземпляр этого класса и возвращает указатель на созданный экземпляр.

Сразу после конструирования ваша фабрика должна уметь создавать потомков с идентификаторами "apple!", "list" и "yet another identifier". В этом задании все потомки Object при вызове ToString должны возвращать свои идентификаторы.

Например, код

    
Factory factory;
Object* apple_instance_ptr = factory.Create("apple!");
cout << apple_instance_ptr->ToString() << endl;
    
    

должен печатать "apple!".

Чтобы не было скучно, ваша фабрика должна поддерживать создание любых потомков Object. Для этого существует операция регистрации:

void Register(const std::string& class_id, Object*(*instance_creator)()) — этот метод связывает идентификатор класса class_id с порождающей функцией instance_creator.

Параметр instance_creator — это указатель на функцию, которая возвращает указатель на наследника Object.

Пример использования:

    
Factory factory;
factory.Register("smth", new_smth);
Object* smth_instance_ptr = factory.Create("smth");
cout << smth_instance_ptr->ToString() << endl;
    
    

Где new_smth это функция, объявленная как Object* new_smth();

Файл с решением должен содержать только реализацию классов Factory и Object и вспомогательных классов, если необходимы.

Материалы задачи

main.cpp

task.xml

---

Задача D. Code format visitor ≡

Входной файл:	Стандартный вход		Ограничение времени:	1 сек
Выходной файл:	Стандартный выход		Ограничение памяти:	4000 Мб

Условие

Вам заданны классы узлов синтаксического дерева программы, необходимые для описания объявления класса, методов класса и полей класса.

          
class ClassDeclarationNode;
class VarDeclarationNode;
class MethodDeclarationNode;
class BaseNode;

class BaseVisitor {
  public:
    virtual void Visit(const BaseNode* node) = 0;
    virtual void Visit(const ClassDeclarationNode* node) = 0;
    virtual void Visit(const VarDeclarationNode* node) = 0;
    virtual void Visit(const MethodDeclarationNode* node) = 0;
};

class BaseNode {
  public:
    virtual void Visit(BaseVisitor* visitor) const = 0;
};

class ClassDeclarationNode: public BaseNode {
  public:
    const std::string& ClassName() const;
    const std::vector<BaseNode*>& PublicFields() const;
    const std::vector<BaseNode*>& ProtectedFields() const;
    const std::vector<BaseNode*>& PrivateFields() const;
    void Visit(BaseVisitor* visitor) const override {
        visitor->Visit(this);
    }
};

class VarDeclarationNode: public BaseNode {
  public:
    const std::string& VarName() const;
    const std::string& TypeName() const;
    void Visit(BaseVisitor* visitor) const override {
        visitor->Visit(this);
    }
};

class MethodDeclarationNode: public BaseNode {
  public:
    const std::string& MethodName() const;
    const std::string& ReturnTypeName() const;
    const std::vector<BaseNode*>& Arguments() const;
    void Visit(BaseVisitor* visitor) const override {
        visitor->Visit(this);
    }
};
          
      

Требуется реализовать класс FormatVisitor, который будет позволять получать отформатированное представление программы в виде строки, в соответствии с синтаксисом языка C++ и Google Style Guide.

          
class FormatVisitor: public BaseVisitor {
  public:
    void Visit(const BaseNode* node) override {
        node->Visit(this);
    }

    void Visit(const ClassDeclarationNode* node) override;
    void Visit(const VarDeclarationNode* node) override;
    void Visit(const MethodDeclarationNode* node) override;

    const std::vector<std::string>& GetFormattedCode() const;
};
          
      

Материалы задачи

main.cpp

task.xml

Формат входных данных

Формат выходных данных

Файл с решением должен содержать только реализацию описанного класса, без функции main.

---