A scrollspy in JavaScript—Vanilla flavoured
Tags: javascript, dev, coding
Published: 2019-08-10 02:51:11

Many developers think a functionality embedded in a third party code must definitely be one hell of a thing to write for just any common developer. I tell you it's a big “NO!”.

One thing still holds true though; a third party code has probably been written with collaborations from different developers, and as such, would have been well structured.

Nonetheless, functional widgets for UI/UX **are not really difficult** to create. A secret you should know; **“building a functional widget is a problem”**. _You will say I contradict myself—yeah, I think so too._

Think of it as a problem, and like every computer problem a solution is needed. This is where algorithms play in UI/UX designs.

> **Note:** _By *functional widgets*, I mean, a UI widget with scripted reactions to user interactions._

## Understanding the problem.

We have a index of sections which can be navigated to in our TOC (table of contents).
Our problem is; we want to update which section in the TOC the user has scrolled onto.
Looking at it from an elevated angle this is a big problem.
Until we create a model!

## Creating a model

Creating a model moves us from such elevated view, from a depressed position, to the same plane with the problem. Now we can leverage!
When creating a model we need to know what we have and pick what is useful. We have JavaScript. What is going to be useful?
  * a scroll event.
  * a scroll position (`scrollTop`).
  * the distance of each section from the offset of the page (`offsetTop`).
  * the element that makes the section; (`HTMLHeadingElement`). I'd be using `h2-h4`.

Now we need to know when the `scrollTop` is greater than or equal to the `offsetTop` of one of the headings at a particular instant.

## Speak in codes

We are selecting `h2-h4` because we consider `h1` the big brother heading or a superior one, and `h5-h6` the inferior ones, or better to say, not as significant as making up a section.

> **Note:** I'll try as much as possible to go with es5 (way of doing things), wherever I consider necessary. Just because it's more conventional yet or so I think&mdash;ECMAScript(5X6)

```js
(function() {
  const h2 = document.querySelectorAll("h2")
  const h3 = document.querySelectorAll("h3")
  const h4 = document.querySelectorAll("h4")
}());
```

We ain't done here yet and I noticed a problem already. **How do we merge all three headings together**. Remember each one of them is a `NodeList`, hence is iterable (not necessarily [Iteration Protocols](https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/iteration_protocols), but even with every regular `for...` loop). It's more like having an array.

Since we need to have them together, there is no other place to have them better than an array! This means they'll be like a sub-array in our collection&mdash;you can call it a multidimensional array.

```js
(function() {
  const h2 = document.querySelectorAll("h2")
  const h3 = document.querySelectorAll("h3")
  const h4 = document.querySelectorAll("h4")
  let h = [h2, h3, h4]
}());
```

Yet, some other problems, we need to spread each of the `NodeList` into the array so we can have a linear array, and also we have lost ordering. The heading elements cannot be in the same order as they appeared in the HTML document that defined them as they don't have a common selector. We could possibly have had:

```html
<h2>Heading 2</h2>
<p>This is a paragraph in a section...</p>

<h3>Heading 3</h3>
<p>This is a paragraph in another section...</p>

<h2>Heading 2</h2>
<p>This is a paragraph in, even, another section...</p>
```

If they were all `h2` they would be selected in the right order also with respect to their `offsetTop`. But since there is an `h3` amidst the `h2` we would have the elements not ordered with respect to their `offsetTop`. 

A solution we can think of is:
  1. to loop through all the elements and give them a common class name, then re-select using that class name,
  2. or get the `offsetTop` and sort. I prefer this for some reasons I don't know

To spread the `NodeList` returned from each of the selected element, we will flatten the array. `Array.prototype.flat` or the es6 Object spread `...` would suffice, but let's code it raw.

```js
const flatten = function flatten(arr) {
  const reduce = Array.prototype.reduce
  return reduce.call(arr, function(acc, val) {
    return Array.isArray(val) || typeof val[Symbol.iterator] === "function" ? acc.concat(flatten(val)) : acc.concat(val);
  }, [])
}
```

The `arr` parameter may not be an array, yet iterable, and as such will not have a `reduce` method. So we don't directly use `arr.reduce`, we rather call the method and give it a `thisArg` as the value for its `this` it will need to reference
 
```js
(function() {
  const h2 = document.querySelectorAll("h2")
  const h3 = document.querySelectorAll("h3")
  const h4 = document.querySelectorAll("h4")
  let h = flatten([h2, h3, h4])
}());
```

## Solution 1
Add a common class name and re-select. There could be an initial offset, probably due to the space your sticky navbar eats up
```js
(function(offset) {
  const elOffsetIndex = {}
  const h2 = document.querySelectorAll("h2")
  const h3 = document.querySelectorAll("h3")
  const h4 = document.querySelectorAll("h4")
  let h = flatten([h2, h3, h4])

  // Time Complexity: O(n) => O(h.length)
  h.forEach(function(el) {
    el.className = "some-section"
  })

  h = document.querySelectorAll(".some-section")
  // now order is being kept

  window.addEventListener("DOMContentLoaded", function() {
    // without this event, the `offsetTop` value may not be right
    // as document may not have finished rendering
    const offsets = []

    // Time Complexity: O(n) => O(h.length)
    for (var i = 0; i < h.length; i++) {
      let hOffset = h[i].offsetTop + offset;
      offsets.push(hOffset);
      elOffsetIndex[hOffset] = h[i];
    }

    document.addEventListener("scroll", function() {
      const scrollTop = this.documentElement.scrollTop

      // Time Complexity: worst-case O(n) => O(offsets.length)
      for (var i in offsets) {
        if (scrollTop >= offsets[i]) {
          elOffsetIndex[offsets[i]].classList.add("active")
          break
        }
      }
    })
}(0));
```

The total time complexity for the above, using the Big O, in the worst-case is `O(3n)`


## Solution 2

Sorting the `offsetTop` of the heading. We would be using a [QuickSort](https://en.wikipedia.org/wiki/QuickSort) algorithm to sort our array of offsets. The Quicksort has a best-case/average performance of `O(n log n)` and worst-case performance of <code>O(n<sup>2</sup>)</code>.
With some optimizations, our sort should never get to the worst-case , as we should not encounter any repeating numbers which would mean no section is placed over the other.

### Quicksort
```js
const quickSort = function quickSort(data) { // no optimizations
  const partition = function partition(data, lo, hi) {
  const pivot = data[hi]
  let i = lo
  for (let j = lo; j < hi; j++) {
    if (data[j] < pivot) {
      data[i] = data[j] - data[i] + (data[j] = data[i]);
      i++
    }
  }
  // swap
  data[i] = data[hi] - data[i] + (data[hi] = data[i]);
    return i
  };
  const sort = function sort(data, lo, hi) {
    if (lo < hi) {
      let p = partition(data, lo, hi)
      sort(data, lo, p - 1)
      sort(data, p + 1, hi)
    }
  };
  sort(data, 0, data.length - 1)
}
```


```js
(function(offset) {
  const elOffsetIndex = {}
  const h2 = document.querySelectorAll("h2")
  const h3 = document.querySelectorAll("h3")
  const h4 = document.querySelectorAll("h4")
  let h = flatten([h2, h3, h4])

  window.addEventListener("DOMContentLoaded", function() {
    // without this event, the `offsetTop` value may not be right
    // as document may not have finished rendering
    const offsets = []

    // Time Complexity: O(n) => O(h.length)
    for (var i = 0; i < h.length; i++) {
      let hOffset = h[i].offsetTop + offset;
      offsets.push(hOffset);
      elOffsetIndex[hOffset] = h[i];
    }

    // Time Complexity: O(n log(n)) => O(h.length log(h.length))
    quickSort(offsets)

    document.addEventListener("scroll", function() {
      const scrollTop = this.documentElement.scrollTop

      // Time Complexity: worst case O(n) => O(offsets.length)
      for (var i in offsets) {
        if (scrollTop >= offsets[i]) {
          elOffsetIndex[offsets[i]].classList.add("active")
          break
        }
      }
    })
}(0));
```

> **Note:** all <code>log</code> is taken in <code>log<sub>2</sub></code>

The total time complexity for the above, using the Big O, in the worst-case is `O(2n + n log(n))` and rarely <code>O(2n + n<sup>2</sup>)</code>. If rarely remains rarely, probably with some optimizations or not having an already ordered(sorted) offsets, then it is more efficient this way, otherwise...Thank you!