Контрольная работа №1: Социальная сеть

Введение

В целях сопротивления цензуре мы разработаем собственную (хоть и простую) социальную сеть, в которой можно будет постить сообщения, быстро удалять лишние посты, а также сортировать ленту по популярности постов

Ленту довольно удобно хранить в виде односвязного списка, чтобы можно было быстро (без реаллокаций) добавлять посты в начало, и так же быстро удалять посты из середины списка

Ограничения и пожелания

Процесс сдачи:

• как обычно с дорешками

  • пушьте регулярно по ходу решения (например, каждую часть по готовности)

• тесты есть на каждый пункт задачи

• надо оформить таргеты в Makefile

Запрещено:

• Использовать контейнеры и функции STL для реализации алгоритма

• Это касается в т.ч. std::string, std::vector

• Если вы хотите что-то использовать, но сомневаетесь — спросите

• Использовать рекурсию, кроме последней задачи (6) со звездочкой

Необходимо:

• Проверять программу на утечки памяти

• Предполагается, что вы выполните вашу контрольную работу в двух файлах:

  • network.hpp - объявления структур и функций для API

  • network.cpp - реализация функций из API

• Можно пользоваться функциями из <cstring> для работы со строками

Часть 1 (1 балл)

Реализуйте API для создания постов в вашей социальной сети

API представляет собой следующие функции:

Создание и удаление постов

// network.hpp
struct Post;

// создает новый пост с сообщением message
// от имени пользователя user
// и добавляет его в начало ленты
Post* create_post(
    char const* user,
    char const* text,
    Post* head = nullptr
);

// деаллоцирует ленту
void destroy_posts(Post const* head);

Работа с постами

// возвращает указатель на предыдущий пост или nullptr,
// если его не существует
Post* previous(Post const* post);

char const* get_user(Post const* post); // возвращает автора поста
char const* get_text(Post const* post); // возвращает сообщение в посте

Замечания

• Предполагается, что create_post копирует переданные ему строки (все содержимое)

  • А методы get_user, get_text — не должны копировать строки

• Вы можете (и должны) добавлять поля к структуре Post по мере выполнения задач

Часть 2 (0.5 балла)

В случае опасности нужно уметь быстро удалять посты с определенным содержанием — например, с хештегом #ИТМО

Добавьте в ваш API функцию, очищающую ленту от постов с компрометирующим содержимым:

// удаляет все посты, в тексте которых
// хоть раз встречается подстрока content
Post* remove_by_content(Post* head, char const* content);

Замечания

• remove_by_content модифицирует ленту (удаляет из неё посты)

• remove_by_content возвращает указатель на первый пост в новой ленте

• Если в ленте не осталось постов, то возвращается nullptr

Вхождение подстроки в строку можно и нужно искать методом std::strstr из библиотеки cstring

Пожалуйста, не тратьте время на КМП, z-функцию и другие прекрасные алгоритмы

Часть 3 (1 балл)

Чтобы распределить нагрузку между серверами, запросы о созданиях постов могут приходить на разные машины. Но рано или поздно посты приходится сливать в одну общую ленту

Добавьте в ваш API метод, позволяющий сливать две ленты в одну:

// возвращает время создания поста
std::uint64_t timestamp(Post const* post);

// сливает две ленты в одну так, чтобы посты шли в хронологическом порядке
// посты из аргументов надо переиспользовать (без копирования)
Post* merge(Post* head_1, Post* head_2);

Текущее время нужно получать с помощью функции get_current_time(), которая уже определена в файле network.cpp:

Часть 4 (0.5 балла)

Иногда удалять пост - слишком подозрительно: вроде все помнят, что там что-то было, а его раз - и нет! Давайте добавим возможность правки постов:

Реализуйте функцию, позволяющую менять текст поста. timestamp поста при этом остается неизменным

// Устанавливает `new_text` как текст поста `post`
// (вместо старого текста)
void set_text(Post* post, char const* new_text);

Часть 5 (0.5 балла)

Более продвинутый вариант самоцензуры — не удалять посты с определенным текстом, и не менять текст поста целиком, а заменять интересующий текст в постах на звёздочки!

Реализуйте функцию, позволяющую менять вхождения строки в пост на звёздочки ( '*' ). timestamp поста при этом остается неизменным.

// Заменяет все вхождения `pattern` во всех постах ленты
// на число звёздочек, равное длине `pattern` в тексте поста
void replace_with_stars(Post* post, char const* pattern);

Вхождение подстроки в строку можно и нужно искать методом std::strstr из библиотеки cstring

Пожалуйста, не тратьте время на КМП, z-функцию и другие прекрасные алгоритмы

Часть 6* (опциональное задание, 1 балл)

Пора добавить в нашу соцсеть лайки и научиться упорядочивать посты по их популярности! Добавьте в ваш API следующие функции:

// увеличивает количество лайков на 1
void like_post(Post* post);

// возвращает количество лайков поста
size_t get_likes(Post* post);

// сортирует посты по убыванию количества лайков
// (посты с одинаковым количеством лайков сортируются по убыванию timestamp)
// ВАЖНО: сортировка должна иметь сложность O(n log n) операций
Post* sort_by_likes(Post* post);

// сортирует посты по убыванию значения timestamp
Post* sort_by_timestamp(Post* post);

Сортировки меняют порядок в текущей ленте (не пересоздают ее!)