Перед началом:
- В этой статье предполагается общее понимание JavaScript и знакомство со структурой данных связанного списка. Если вы не знакомы со связанными списками, первая часть все равно будет легкой для понимания, но я предлагаю взглянуть на связанные списки и реализация связанных списков в Javascript.
- Этот блог не предназначен для предоставления каких-либо советов по производству, он предназначен только для изучения того, как работает JavaScript внутри.
В Javascript итераторы повсюду, и вы определенно их использовали. Они вступают в игру, если вы когда-либо использовали циклы for…of в массивах, множествах, типизированных массивах и картах. Это потому, что эти объекты являются итерируемыми. Это означает, что их можно повторять с помощью цикла for. Но что делает объект итерируемым? и можем ли мы превратить любой объект в итерируемый? и как мы можем это сделать? Именно на эти вопросы я постараюсь ответить в этой статье.
Оказывается, чтобы сделать объект итерируемым, Javascript добавляет к этим объектам специальный метод. Этот метод называется специальным только потому, что он реализует то, что называется протоколом итераций. Под внедрением протокола подразумевается, что:
- Этот метод определяется/хранится под определенным ключом или именем.
- Этот метод возвращает что-то в ранее определенной или согласованной форме.
Определение/хранение итератора:
Когда дело доходит до определения, Javascript должен гарантировать, что функция итератора может безопасно существовать в объекте и не будет перезаписана какой-либо другой парой ключ-значение. Для этого он использует Символы (примитивный тип, добавленный в ES6, который может предотвратить конфликты и случайную перезапись свойств или методов объекта). Символы имеют статическое свойство, называемое итератором, и оно используется в качестве ключа для функции итератора для любого объекта.
{
...,
[Symbol.iterator]: () => {
// iterator function implementation
}
}
Любой процесс (например, for..of), которому необходимо выполнить итерацию по элементам объекта, будет использовать Symbol.iterator для доступа к методу, используемому для получения объекта итератора. Реализация этой части протокола гарантирует, что цикл for должен искать только один ключ для любого объекта, с которым он работает, вместо того, чтобы вызывать разные ключи в зависимости от типа объекта. Это также гарантирует, что мы случайно не перезапишем итератор каким-либо другим свойством или методом.
Зная это, если мы попытаемся записать в консоль ключ итератора итерируемого объекта, такого как массив, мы получим следующее:
console.log(new Array([])[Symbol.iterator])
// f values(){ }
Но если мы попробуем то же самое в нашей реализации Linked List или попробуем использовать структуру данных в цикле for..of, мы получим:
console.log(LinkedList[Symbol.iterator])
//undefined
for(const nodeValue of LinkedList){
...
}
// in Console:
// TypeError: Invalid attempt to iterate non-iterable instance.
// In order to be iterable, non-array objects must have a
// [Symbol.iterator]() method.
Это связано с тем, что любая реализация связанного списка не реализует протокол итератора, и мы должны реализовать его сами.
Поведение итератора:
Метод/функция Iterator не принимает аргументов и возвращает объект, который реализует определенное поведение или имеет определенные методы с определенной сигнатурой.
Возвращаемый объект должен иметь функцию, называемую next(). При вызове он должен возвращать простой объект, который выглядит как «Результат итерации», определенный протоколом. Простой результат итерации должен выглядеть так:
{
value: any // the value of the current iteration
done: Boolean // whether the iteration is complete or not
}
Таким образом, когда массив или любой итерируемый объект используется в цикле for, цикл for сначала вызывает функцию, определенную в [Symbol.iterator], чтобы получить объект итератора. Затем он вызывает функцию next() для этого объекта, чтобы получить объект результата итерации. Результат итерации (содержащее значение и свойства done) позволяет нам узнать, каково текущее значение итерации и завершена ли итерация. Если он не завершен, мы можем снова вызвать next() для получения следующего результата итерации, пока не получим результат, в котором свойство done имеет значение true, и именно так цикл for узнает, что итерацию нужно прекратить.
На самом деле мы можем вручную реализовать эти шаги:
const numbers = [1, 2, 3, 4];
const iteratorObject = numbers[Symbol.iterator]() //access the function and call it
iteratorObject.next() //{value: 1, done: false}
iteratorObject.next() //{value: 2, done: false}
iteratorObject.next() //{value: 3, done: false}
iteratorObject.next() //{value: 4, done: false}
iteratorObject.next() //{value: undefined, done: true}
Как мы видим, метод next() вызывается многократно, он первоначально возвращает объект Return со значением, являющимся первым элементом массива, и значением done, равным false. При последующих вызовах значение будет ссылаться на следующий элемент массива, пока не будет достигнут последний элемент. При последующем вызове объект возврата будет иметь значение undefined и значение done равно true, чтобы код, использующий этот объект, знал, что итерация завершена. Именно так работает внутренний цикл for.
Теперь мы знаем, что любая структура объекта или данных является итерируемой, если она реализует протокол итерации. И мы знаем основы того, как выглядит этот протокол, поэтому мы можем перейти к созданию итерируемого объекта.
Реализация:
В качестве примера возьмем структуру данных Linked List. Базовые реализации связанных списков требуют набора методов, однако итератор не является одним из них. Но мы собираемся предположить, что работаем в приложении, которое требует от нас перебора связанного списка, и мы решили сделать эту итерацию простой, используя цикл for. Однако эта реализация должна работать с любой структурой данных, особенно с линейной структурой.
Сначала нам нужно создать базовую реализацию связанного списка. Нам понадобятся два класса: класс для узла списка и класс для самого связанного списка.
class ListNode {
constructor(data) {
this.value = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
}
addNode(node) {
// if the head of this linked list is empty add the node as a head
if (!this.head) {
this.head = node
return;
};
// if we have a head find the node which has null as the next node and
// set the next to our added node
let currentNode = this.head;
while(currentNode.next) {
currentNode = currentNode.next;
}
currentNode.next = node;
}
}
Для этого примера нам не нужно много методов в классе Linked List, только метод для добавления узлов. С этой реализацией мы можем начать добавлять наши узлы в связанный список:
const exampleList= new LinkedList(); exampleList.addNode(new ListNode(1)); exampleList.addNode(new ListNode(2)); exampleList.addNode(new ListNode(3)); exampleList.addNode(new ListNode(4));
Теперь у нас есть структура данных Linked List с четырьмя узлами. Наша цель — иметь возможность перебирать значения каждого узла, используя цикл for…of.
Если мы попытаемся использовать цикл for со связанным списком в этот момент, мы получим упомянутую выше ошибку. Итак, нам нужно приступить к реализации протокола итератора в связанном списке. Во-первых, нам нужно добавить метод итератора под ключ Symbol.iterator:
class LinkedList {
constructor() {
this.head = null;
}
addNode(node) {
// if the head of this linked list is empty add the node as a head
if (!this.head) {
this.head = node
return;
};
// if we have a head find the node which has null as the next node and
// set the next to our added node
let currentNode = this.head;
while(currentNode.next) {
currentNode = currentNode.next;
}
currentNode.next = node;
}
[Symbol.iterator](){
// ...
}
Затем мы можем начать добавлять поведение, которое должно соответствовать протоколу итератора:
class ListNode {
constructor(data) {
this.value = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
}
addNode(node) {
if (!this.head) {
this.head = node
return;
};
let currentNode = this.head;
while(currentNode.next) {
currentNode = currentNode.next;
}
currentNode.next = node;
}
[Symbol.iterator](){
let currentNode = this.head;
return {
next(){
if(!currentNode) return {value: undefined, done: true}
const returnValue = {
value: currentNode.value,
done: false
};
currentNode = currentNode.next;
return returnValue
}
}
}
}
Наша реализация выше делает следующее:
- Инициализируйте узел текущей итерации, чтобы он был главой связанного списка. Это значение, которое мы изменим на следующий узел по мере продвижения вперед по итерации.
- Мы возвращаем простой объект, который соответствует требованию протокола о наличии метода next().
- При вызове метод next проверит, является ли текущее значение ложным. Если это так, то мы больше не итерируем и поэтому возвращаем простой объект со значением как неопределенным и выполненным как истина.
- Если текущий узел является истинным, то подготовьте объект со значением, равным значению текущего узла, а следующий — ложным.
- Измените значение переменной currentNode на свойство .next текущего узла, которое может быть другим узлом связанного списка с нулевым значением.
- вернуть ранее подготовленный объект.
Теперь, когда в нашем связанном списке есть итератор, отвечающий требованиям протокола, мы можем использовать его в цикле for:
for(const value of exampleList){
console.log( value)
}
// 1
// 2
// 3
// 4
и мы можем поместить любую логику, которая нам нужна, внутри цикла for, которая может удовлетворить требования нашего приложения. Таким образом, у нас есть простой и семантический способ перебора значений нашей неродной структуры данных.
Важно иметь в виду, что цикл for заботится только о том, чтобы функция итератора объекта реализовывала протокол итератора. Это не связано с тем, как это реализовано. Это означает, что мы можем реализовать итератор по-разному в зависимости от структуры данных. Итерации по дереву или графу потребуют различных реализаций, но пока метод next() существует и предоставляет возвращаемый объект в ожидаемой форме, все будет работать, у нас даже может быть логика, в которой мы пропускаем определенные значения, если это необходимо.
Полный код:
class ListNode {
constructor(data) {
this.value = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
}
addNode(node) {
if (!this.head) {
this.head = node
return;
};
let currentNode = this.head;
while(currentNode.next) {
currentNode = currentNode.next;
}
currentNode.next = node;
}
[Symbol.iterator](){
let currentNode = this.head;
return {
next(){
if(!currentNode) return {value: undefined, done: true}
const returnValue = {
value: currentNode.value,
done: false
};
currentNode = currentNode.next;
return returnValue
}
}
}
}
const listExample = new LinkedList();
listExample.addNode(new ListNode(1));
listExample.addNode(new ListNode(2));
listExample.addNode(new ListNode(3));
listExample.addNode(new ListNode(4));
for(const value of listExample){
console.log('value: ', value)
}
