urfu-2015/javascript-tasks-8

Задача к лекции «Конструкторы» – «Стандартная библиотекаа»

Задание №8: Стандартная библиотека

Цель этого задания – разработать библиотеку, предоставляющую стандартные структуры данных.

var Queue = require('./src/standard-library.js').Queue;

var queue = new Queue();

queue.enqueue("foo");
queue.enqueue("bar");
queue.enqueue("baz");

queue.dequeue(); // "foo"
queue.dequeue(); // "bar"
queue.dequeue(); // "baz"

Для этого написать реализацию функций-конструкторов, заданных в модуле standard-library.js.

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

Скорее всего, при реализации структур данных вы будете использовать наследование. Делать методы родителя недоступными в потомке не нужно.

Заготовка модуля находится в папке src. Как обычно, тесты можно найти в папке test.

Обязательные задачи

Необходимо реализовать следующие структуры данных.

Коллекция (Collection)

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

• first – первый элемент коллекции
• last – последний элемент коллекции
• length – количество элементов в коллекции
• isEmpty – true, если коллекция пуста
• pickFirst() – извлекает первый элемент из коллекции и возвращает его
• pickLast() – извлекает последний элемент из коллекции и возвращает его
• insertFirst() – вставляет элемент в начало колекции
• insertLast() – вставляет элемент в конец коллекции
• empty() – очищает коллекцию

Очередь (Queue)

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

• length – количество элементов в очереди
• enqueue(item) – добавляет элемент в очередь
• dequeue() – извлекает элемент из очереди
• empty() – очищает очередь

Массив фиксированной длины (Fixed array)

Массив фиксированного размера. Попытка добавить или получить элемент за пределами указанного диапазона должна вызывать ошибку RangeError.

• length – количество элементов в массиве
• insertAt(index, item) – записывает элемент в массив по заданному индексу
• getAt(index) – возвращает элемент по указанному индексу.

Множество (Set)

Список, хранящий уникальные элементы.

• length - количество элементов в множестве
• insert(item) - добавляет элемент в множество
• remove(item) - удаляет элемент из множества
• has(item) - проверяет, входит ли элемент в множество
• intersect(set) – возвращает множество элементов входящих в исходное множество и в переданное множество (в оба сразу)
• union(set) – возвращает множество элементов входящих в исходное множество или в переданное множество (в любое из двух)
• empty() – очищает множество

Встроенный объект Set использовать не разрешается.

Общие требования

• код должен проходить валидацию jscs
• код должен проходить тесты

Дополнительные задачи

Выберите два любых задания из трёх.

Не использовать массив

Реализовать базовую коллекцию на основе двусвязного списка. Список структур данных

Очередь с приоритетом PriorityQueue

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

• enqueue(item, priority) – кладёт элемент с priority (целое число в интервале от 1 до 100)
• dequeue() – извлекает элемент с наивысшим приоритетом из очереди. Если есть несколько элементов с одинаковым приоритетом, извлекается элемент, который был помещён в очередь первым (из элементов с наивысшим приоритетом).

Словарь (Map)

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

В списке дополнительных материалов указана статья про преобразование объектов. Она может быть полезна.

• length – количество элементов в словаре
• addItem(key, item) – добавляет элемент в словарь по указанному ключу
• removeItem(key) – извлекает элемент из словаря по указанному ключу
• getItem(key) – возвращает элемент по указанному ключу
• empty() – очищает словарь

Встроенный объект Map использовать не разрешается.

Материалы

1. Лекция
2. Презентация
3. Список структур данных
4. Объекты как ассоциативные массивы
5. Преобразование объектов: toString и valueOf
6. ООП в прототипном стиле