Smelly Code

Data Structures with Iterable Protocol

January 26, 2019 ∙ 📖 8 min

Iterators and Generators have been around for a while. They have changed the way we loop through the values of an object. Earlier, we used to use the `for-in` loop to iterate over the values, but there was no guarantee of the order in which values will be iterated. Also, it was quite cumbersome cause we had to use keys from the `for-in` loop to get values. Generator and Iterators remove the pain of iterating objects. For an object to be iterable, it just needs to comply with iteration protocols. This post provides a quick overview of Generators and Iterators/Iterables and explains how common data structures can be made iterable.

Iteration Protocols

The advent of ES5 brought two iteration protocols to JavaScript: Iterable Protocol and Iterator Protocol.

Iterable Protocol

For an object to be iterable, it must have an iterator method. An iterator method is defined using @@iterator key i.e. the Symbol.iterator constant. Iterator method can be any javascript function which takes zero arguments and returns an object conforming Iterator Protocol(will be discussing soon). Here’s the sample code, if you are lost in jargon.

class IteratorDemo {
  // Iterator Method with @@iterator key
  // i.e. Symbol.iterator constant
  [Symbol.iterator]() {
    // Method stub which returns an iterator object.
  }
}

Iterator Protocol

The iterator protocol defines a standard way to produce a sequence of values (either finite or infinite), and potentially a return value when all values have been generated. ~MDN

For an object to be an iterator object, it needs to implement a next method which fulfils below criteria:

  1. It should take zero arguments. Although, you may pass arguments to next and there won’t be any error but you shouldn’t cause when your iterable object will be used with spread operator or for-of loop you won’t be able to pass any arguments.

  2. It should return an object with at least one of the two properties.

    • value: Any javascript value which we want to return from our iterator.
    • done: A boolean flag to indicate whether we reached the end of the sequence or not.

Here’s a quick range iterator example borrowed from MDN.

class RangeIterator {
  constructor({ start = 0, end = 1000, step = 1 }) {
    this.start = start;
    this.end = end;
    this.step = step;
  }

  [Symbol.iterator]() {
    let start = this.start;
    const iterable = {
      // Next fn complying with Iterator protocol.
      next: () => {
        if (start <= this.end) {
          const result = {
            value: start,
            done: false
          };
          start += this.step;
          return result;
        }

        return {
          done: true
        };
      }
    };
    return iterable;
  }
}

const range = new RangeIterator({
  start: 0,
  end: 20,
  step: 5
});
console.log(...range); // 0 5 10 15 20

Generators

Sometimes explicitly maintaining the internal state of iterators and returning an iterable object is too much of work. Generators reduce that amount of work and provide an alternate approach to make an object iterable with the help of yield keyword. Generators functions have special syntax. They are written as function *. You can read more on generators here.

Here’s our previous example re-written with the help of generators.

class RangeGenerator {
  constructor({ start = 0, end = 1000, step = 1 }) {
    this.start = start;
    this.end = end;
    this.step = step;
  }

  *[Symbol.iterator]() {
    let start = this.start;
    while (start <= this.end) {
      yield start;
      start += this.step;
    }
  }
}

const range = new RangeGenerator({
  start: 0,
  end: 20,
  step: 5
});
console.log(...range); // 0 5 10 15 20

Alright, enough about Iterators and Generators. Let’s use them with common data structures like LinkedList, Stack, BinaryTree.

LinkedList

LinkedList is a linear data structures where each node/element holds the data and pointer to the next node. The start and end of the list are called `head` and `tail`. Here’s an implementation of Linked List.
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  get isEmpty() {
    return this.head === null;
  }

  add(value) {
    const node = new Node(value);
    if (this.head === null) {
      this.head = this.tail = node;
      return this;
    }
    this.tail.next = node;
    this.tail = node;
    return this;
  }

  addHead(value) {
    const node = new Node(value);
    node.next = this.head;
    this.head = node;
  }

  removeHead() {
    if (this.isEmpty) {
      return null;
    }
    const head = this.head;
    this.head = this.head.next;
    return head.value;
  }

  removeTail() {
    if (this.isEmpty) {
      return null;
    }

    const { value } = this.tail;
    if (this.head === this.tail) {
      // List with single node.
      this.tail = this.head = null;
      return value;
    }

    let prev = null;
    let current = this.head;
    while (current.next !== null) {
      prev = current;
      current = current.next;
    }

    // Adjust tail pointer.
    prev.next = null;
    this.tail = prev;

    return value;
  }

  remove(x) {
    let prev = null;
    let current = this.head;
    while (current !== null) {
      const { value, next } = current;
      if (value !== x) {
        prev = current;
        current = next;
        continue;
      }
      // If value is at head.
      if (prev === null) {
        this.head = next;
      } else {
        prev.next = next;
      }
      return x;
    }
    return null;
  }
}

const list = [2, 1, 3, 4, 5].reduce(
  (list, value) => list.add(value),
  new LinkedList()
);

We need to add an iterator to make the linked list iterable. Our iterator function will have an internal state variable called current (which initially refers to head) representing the current node we are at. Every next call, will return the data of the current node and move the current node to the next node. Once the next method is done traversing all nodes, it returns done as true to stop the iteration.

 /**
   * Iterator function.
   *
   * @returns
   * @memberof LinkedList
   */
  [Symbol.iterator]() {
    let current = this.head;
    const iterable = {
      next: () => {
        if (current === null) {
          return {
            done: true
          };
        }
        const {
          value,
          next
        } = current;
        current = next;
        return {
          value,
          done: false
        };
      }
    };
    return iterable;
  }

Generator version of the above.

 // Generator function.
  *[Symbol.iterator]() {
    let current = this.head;
    while (current !== null) {
      const { value } = current;
      current = current.next;
      yield value;
    }
  }

You can find the full code here.

Stack

A Stack is a linear data structure which follows Last In First Out(LIFO) pattern which means items inserted into the stack last will come off first. To keep things DRY, we’ll use our earlier Linked List data structure to implement Stack. We’ll also leverage its iterator method to make our stack iterable.

class Stack {
  constructor() {
    this.list = new LinkedList();
  }

  get isEmpty() {
    return this.list.isEmpty;
  }

  /**
   * Iterator function.
   *
   * @returns
   * @memberof Stack
   */
  [Symbol.iterator]() {
    return this.list[Symbol.iterator]();
  }

  push(value) {
    this.list.addHead(value);
    return this;
  }

  pop() {
    if (this.isEmpty) {
      throw new Error('STACK_UNDERFLOW');
    }
    return this.list.removeHead();
  }
}

const stack = [1, 2, 3, 4, 5, 6].reduce(
  (stack, value) => stack.push(value),
  new Stack()
);
console.log(...stack); // 6 5 4 3 2 1

Binary Tree

Binary Tree is a subclass of Tree data structure. In Binary Tree, each node can have maximum 2 children called left and right. You can read more about Binary Trees in my post A Bit About Binary Tree. Since trees are non-linear data structure so they can be traversed in many ways. We’ll implement their Level Order or Breadth First Order traversal in our iterator method. Here’s the class which represents BinaryTreeNode for our BinaryTree.

export class BinaryTreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }

  /**
   * Inserts node in level order.
   *
   * @param {*} x
   * @returns
   * @memberof BinaryTreeNode
   */
  add(x) {
    const queue = [this];
    const newNode = new BinaryTreeNode(x);

    while (true) {
      const node = queue.shift();
      if (node.left === null) {
        node.left = newNode;
        return this;
      }

      if (node.right === null) {
        node.right = newNode;
        return this;
      }
      queue.push(node.left);
      queue.push(node.right);
    }
    return this;
  }
}

And finally, BinaryTree with iterator method.

import { BinaryTreeNode } from './BinaryTreeNode';
export class BinaryTree {
  constructor() {
    this.root = null;
  }

  get isEmpty() {
    return this.root === null;
  }

  add(x) {
    if (this.isEmpty) {
      this.root = new BinaryTreeNode(x);
    } else {
      this.root.add(x);
    }
    return this;
  }

  /**
   * Iterator. Traverses in level order.
   *
   * @memberof BinaryTree
   */
  *[Symbol.iterator]() {
    const queue = this.isEmpty ? [] : [this.root];
    while (queue.length) {
      const { value, left, right } = queue.shift();
      if (left !== null) {
        queue.push(left);
      }

      if (right !== null) {
        queue.push(right);
      }
      yield value;
    }
  }
}

Well, that’s all about Data Structures with Iterable Protocol. I have created a git-repository of examples used in this post. I hope you find them useful. Thanks for reading 🙏🏻.

Hi, I am Hitesh.

|