Позиционные списки в TypeScript

Работа со списками без работы с индексами

Списки - это структуры данных, которые сохраняют последовательность элементов по порядку. Благодаря этому мы можем работать с индексами и изменять их, чтобы получать элементы со смещением к некоторому индексу. Это замечательно, но может привести к созданию кода, который изменяет множество целых чисел только для того, чтобы получить и установить элементы в списке на определенную позицию. В этой статье мы рассмотрим позиционные списки, своего рода список, который абстрагирует концепцию индексов и позволяет нам рассуждать только о концепции предыдущих и следующих элементов.

Позиционные списки - это списки, в которых элементы хранятся в контейнере Position. На основе этого контейнера вы можете получить предыдущий и следующий элемент (ы) из списка, не имея дело с индексами (однако индексы по-прежнему являются вариантом для получения позиции). Это может помочь создать более элегантный код, поскольку мы абстрагируем концепцию «следующий элемент по индексу + 1» в структуре данных. Так что больше никаких переменных типа currentIndex и indexLastProcessedItem. Это также позволяет нам упростить работу с круговыми структурами данных, потому что внешний мир больше не делает предположений об индексах.

Позиционный список

Позиционные списки во многом похожи на обычные списки, но есть некоторые вещи, которые следует учитывать:

• Каждое значение из списка возвращается в Position контейнере.
• В списках есть методы before и after, которые возвращают Position на основе другого Position
• Удаление происходит по Position, а не по индексу
• Поддерживающая структура данных может быть любой, возможен любой тип списка, но также возможны массивы, кольцевые буферы и индексированные деревья.

Основываясь на этой информации, мы можем определить интерфейс для методов, которые позиционные списки должны реализовать, чтобы фактически работать как позиционный список. Конечно, можно (и очень часто) добавить больше методов, которые сделают позиционный список более мощным и гибким.

Обратите внимание, что мы все еще можем использовать наш позиционный список как обычный список с помощью методов elementAt, first и last, чтобы получить Position по индексу и использовать его с другими методами.

Реализация с двусвязным списком

Самый простой и распространенный способ реализации позиционных списков - это список с двойной связью. Это потому, что в двусвязных списках просто получить предыдущий и следующий узлы узла. Он также уже реализует все перечисленные выше функции, поэтому для адаптации PositionalList интерфейса требуются лишь небольшие изменения. Возможную реализацию можно найти ниже:

Основная «хитрость» здесь состоит в том, чтобы Node интерфейс расширял Position интерфейс и выполнял повышающее и понижающее преобразование при передаче узлов в список и из него. Внешний мир знает только о позициях, мы внутри списка знаем об узлах с предыдущими и последующими элементами.

Увидев эту реализацию, можно было бы задаться вопросом, почему методы before и after находятся в списке, а не на позиции. Конечно, было бы удобнее, если бы мы могли делать myPosition.before().before() вместо того, чтобы каждый раз ссылаться на список? Ответ состоит из двух частей:

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

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

Другие реализации

Позиционный список также может быть реализован с помощью массива. Для этого мы сохраняем массив внутри нашего PostionalList, и все методы изменяют и запрашивают этот массив. Здесь мы видим, почему лучше оставить before и after в списке, поскольку у них есть легкий доступ к переменной data. В этой реализации у нас все еще есть Node интерфейс, но теперь он сохраняет индекс как дополнительные скрытые данные вместо хранения предыдущего и следующего узлов. Полную реализацию можно найти здесь.

Здесь мы видим, что на языке с динамическими массивами изменения размера (например, JavaScript) позиционные списки на самом деле короче для реализации с массивом, чем с более традиционным списком с двойной связью. Например, в Java или C # вам придется использовать ArrayList с автоматическим изменением размера, чтобы получить тот же результат.

Функциональное программирование и позиционные списки

Все определения и реализации, которые я вам до сих пор показывал, были очень простыми и традиционными ООП, чтобы все было как можно проще. Но на самом деле почти каждый вносит функциональное программирование в свою базу кода, особенно при изменении коллекций. Реализация функции как filter и map вполне возможна для позиционного списка, но есть некоторые подводные камни. Давайте начнем с расширения нашего PositionalList интерфейса, добавив определений для некоторых из этих функциональных возможностей:

Как видите, мы не используем позиции для элементов внутри функций map, filter и bind. Это потому, что мы не должны заботиться о должностях в этих функциях. функция, которую мы передаем map, должна просто превратить T в U, не учитывая ничего, кроме значения этого T.

Теперь мы начинаем вводить методы, которые создают новые позиционные списки, и нам действительно стоит задуматься об одном вопросе: что, если мы передадим в before или after позицию, которая не принадлежит этому списку? В нашей предыдущей реализации он либо работал, либо выдавал чушь, либо возвращал ноль. Мы можем добавить проверку для этого, поместив ссылку на списки в позиции и проверив, равна ли эта ссылка this, прежде чем мы сочтем позицию действительной.

Заключение

В этой статье мы остановились на одном из редко используемых вариантов списков - позиционных списках. Это немного похоже на позор, потому что позиционные списки на самом деле довольно крутые и мощные. Дайте мне знать, что вы о них думаете!

Хотите узнать больше о функциональном программировании с помощью TypeScript? Я пишу серию статей о расширенном семействе функторов в TypeScript, первые две части вы можете прочитать здесь: