Задача «Библиотека Аркадия»

Перед выполнением задания внимательно прочитайте:

• О всех этапах проверки задания
• О том, как отправить пулл
• О том, как пройти тесты
• Правила оформления javascript, HTML и CSS кода

Основное задание

Мы очень хотим, чтобы код вы написали сами, а не пользовались внешними библиотеками.

У Аркадия есть хобби – он обожает писать библиотеки, чтобы позже их переиспользовать. Ведь это так увлекательно! У Аркадия уже есть опыт написания библиотек, однако у него ну никак не получается достичь такой же популярности, какой достигли такие легенды как is-thirteen, thanosjs и, конечно же, left-pad.

Аркадий подумал и решил, что он напишет самую лучшую и полезную библиотеку, с важными для разработки интерфейсов вещами – со структурами данных.

А чтобы точно гарантировать популярность своей библиотеки, он будет писать её на хайповом TypeScript. К сожалению, Аркадий мало знаком с этим языком, поэтому он обратился к вам, как к специалисту по разборкам с типами.

Реализуемые структуры данных

LinkedList

⚠️ Использовать массивы не разрешается

Связный список. Поддерживает операции вставки и извлечения первого и последнего элемента.

• constructor() – инициализирует пустой связный список
• push(element) – вставляет элемент в конец списка
• pop() – извлекает последний элемент списка и возвращает его, либо undefined, если список пуст
• unshift(element) – вставляет элемент в начало списка
• shift() – извлекает первый элемент списка и возвращает его, либо undefined, если список пуст
• size – количество элементов в списке

RingBuffer

⚠️ Использовать массивы не разрешается

Кольцевой буфер. Поддерживает операции вставки в конец и извлечения из начала. Если продолжить запись в буфер, не принимая во внимание его вместимость, то новые данные начнут выталкивать старые данные.

• constructor(capacity) – инициализирует буфер вместимости capacity
• get(index) – возвращает элемент коллекции расположенный по указанному индексу, либо undefined, если индекс находится вне границ буфера
• push(element) – вставляет элемент в конец коллекции
• shift() – извлекает первый элемент из коллекции и возвращает его, либо undefined, если буфер пуст
• static concat(buffer1, buffer2, ...) – возвращает новый буфер состоящий из элементов buffer1, buffer2, ... с общей вместимостью равной сумме вместимостей переданных буферов
• capacity – вместимость буфера
• size – количество элементов в буфере

Queue

⚠️ Использовать массивы не разрешается

Очередь. Список элементов, организованных по принципу "первым пришёл – первым вышел". Элементы добавляются и извлекаются с одного конца списка.

• constructor() – инициализирует пустую очередь
• get(index) – возвращает элемент очереди расположенный по указанному индексу, либо undefined, если индекс находится вне границ буфера
• enqueue(element) – добавляет элемент в очередь
• dequeue() – извлекает элемент из очереди, либо возвращает undefined, если очередь пуста
• size – количество элементов в очереди

PriorityQueue

⚠️ Использовать массивы не разрешается

Очередь с приоритетом. Отличается от обычной очереди наличием приоритета у элементов.

Приоритет может быть одним из трех значений:

• 1 – низкий
• 2 – средний
• 3 – высокий

Магические числа в коде – плохо, поэтому рекомендуем использовать Enum

• constructor() – инициализирует пустую очередь с приоритетом
• enqueue(element, priority) – добавляет элемент с приоритетом в очередь
• dequeue() – извлекает элемент с наивысшим приоритетом из очереди. Если есть несколько элементов с одинаковым приоритетом, извлекается элемент, который был помещён в очередь первым (из элементов с наивысшим приоритетом). Либо возвращает undefined, если очередь пуста
• size – количество элементов в очереди

HashTable

Хеш таблица. Отличается от стандартного объекта тем, что в качестве ключей можно использовать объекты, а не только строки.

Использовать Map не разрешается.

• constructor() – инициализирует пустую хеш таблицу
• get(key) – возвращает элемент таблицы по указанному ключу, либо undefined, если элемент по переданному ключу не существует
• put(key, element) – добавляет элемент в словарь по указанному ключу
• clear() – очищает таблицу
• size – количество элементов в таблице

Дополнительные условия

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

В файле std.spec.ts вы можете найти примеры использования вашего кода.

Дополнительное задание (+1000 ⭐ к популярности)

Теперь LinkedList хранит указатель, который по-умолчанию указывает на первый элемент. Появляется два дополнительных метода:

• prev() – возвращает текущий элемент списка, на который указывает указатель, либо undefined, если список пуст. Устанавливает указатель на предыдущий элемент, если такой есть
• next() – возвращает текущий элемент списка, на который указывает указатель, либо undefined, если список пуст. Устанавливает указатель на следующий элемент, если такой есть

При этом расширяют свое поведение:

• pop() – если указатель указывает на последний элемент, то выполняет prev()
• shift() – если указатель указывает на первый элемент, то выполняет next()