DEV Community: Anish Kumar

150 lines or less - implementing virtual scroll for web from scratch

Anish Kumar — Thu, 17 Apr 2025 17:20:01 +0000

NOTE: this article was originally published at StackFull.dev.

What is virtual scroll ?

Virtual scroll (also called virtualization or windowing) is a technique used to efficiently render large lists in web applications --- without loading everything into the DOM at once. Instead of rendering 1,000+ items, you only render what's visible in the viewport, plus a small buffer above and below for smooth scrolling.

As you scroll, items outside the viewport are removed from the DOM, and new ones are added on-demand. Let's see how we would implement it from scratch. We'll would use ReactJS to create a reusable component in this post, but these principles can be applied to any framework or even vanilla JS.

Step 1: prepare data for scroll

First off, let's get the preparatory step out of the way. It's not directly related to the idea of virtual scroll, but we'll need it done to test our implementation later. Here's a simple snippet that we can use to generate a huge list with random data:

const ARR_SIZE = 500_000;

const arr = new Array(ARR_SIZE).fill(null).map((_, i) => ({
  index: i + 1,
  id: Math.random(),
  value: Math.floor(Math.random() * 2 * ARR_SIZE),
}));

We'll create an array with 500,000 fake rows. Each one having:

an index (like 1, 2, 3...)
a random ID
a random value (just to show data)

Step 2: the core idea

The core idea can be understood by the diagram above.

We provide a fixed size container to the user, to scroll things within it. Let's call that windowHeight. Each row/item is also given a fixed size, say rowHeight. This means we can have atmost windowHeight/rowHight items shown in the container, let's call that WINDOW_SIZE.

As the user starts scrolling the container, we keep track of the height that has scrolled up (container.scrollTop value). We can use this value along with rowHeight to calculate the index at which container should start showing the items. Similarly, we can use windowHeight to calculate the index at which container should stop showing the items.

As the user keeps scrolling, we keep recalculating the start and end index for the items to be shown and re-render those in the UI.

An interesting thing to note here is the scroll position. Simply rendering the items from start to end index would reset the scroll position, thus not allowing the user to scroll anymore, so we need some way for maintaining desired scroll position. A simple way to achieve this would be to slap two divs, one at top of the container and another at bottom, each having height equal to expected scroll offsets at top and bottom. We'll see how to implement this shortly.

This pretty much is the crux of the solution. Let's get our hands dirty with some code now.

Step 3 - basic implementation

Lets create a component VirtualTable:

// windowSize is the number of rows to be shown in the window.
// rowHeight is the fixed height of each row.
// arr contains the huge data to be shown in virtualTable.
function VirtualTable({ arr, windowSize, rowHeight }) {
    ...
}

Let's track the scroll position as we talked earlier:

const [scrollTop, setScrollTop] = useState(0);

const handleScroll = (e) => {
  e.preventDefault();
  setScrollTop(e.target.scrollTop);
};

...
return (
      <div onScroll={handleScroll} ...> ... </div>
);

Now let's calculate the start and index for items to be shown within the virtual table:

const startIndex = Math.floor(scrollTop / rowHeight);

// Better, let's clamp it to 0, to ensure it never becomes negative.
const startIndex = Math.max(0, Math.floor(scrollTop / rowHeight));

// Similar calculation for endIndex:
const endIndex = Math.min(arr.length - 1, startIndex + windowSize - 1);

Maintain list of items to be rendered:

const shownRowsIndex = [];

for (let i = startIndex; i <= endIndex; i++) {
  shownRowsIndex.push(i);
}

We want the scroll bar to feel like it scrolls through the whole list, even though we're only rendering a few items. So we fake the total height using invisible divs.

Padding above:

const topPad = startIndex * rowHeight;

This means: if you've scrolled past 20 items, we add 20 × row height = 600px of empty space at the top.

Padding below:

const bottomPad = totalHeight - (renderedHeight + topPad);

This calculates how much space is left after the visible rows.

So if total height is 15,000px, and you've shown 30 rows and scrolled past 600px, we add just enough padding to fill in the rest.

Rendered output looks like this:

<div
  onScroll={handleScroll}
    style={{
    height: rowHeight * windowSize,
    overflowY: 'auto',
  }}
>
  <div style={{ height: topPad }}></div>

  {shownRowsIndex.map((itemIndex) => (
    <div
      className="t-row"
      style={{ height: rowHeight }}
      key={arr[itemIndex].id}
    >
      row#{arr[itemIndex].index} : {arr[itemIndex].value}
    </div>
  ))}

  <div style={{ height: bottomPad }}></div>
</div>

You can see it all in action here:

Step 4 - Optimizations

So far, we've covered the basics of virtual scroll: Only render what's visible.\
But once that works, you start to notice two issues:

Scrolling can feel a little "jumpy".
Updating on every pixel of scroll becomes expensive.

Let's fix both --- starting with buffering.

Buffer Rows --- Why They Matter

Without buffer, when you scroll down, new rows only appear when they come exactly into view. This causes a harsh snapping effect --- rows are constantly entering and exiting the DOM too quickly.

With buffer, we render a few extra rows above and below the viewport. So even if a row is just offscreen, it's already in the DOM and ready to slide in. This makes scrolling feel buttery smooth.

const SCROLL_BUFFER_SIZE = Math.floor(WINDOW_SIZE / 2);
...
const startIndex = Math.floor(
  (scrollTop - bufferSize * rowHeight) / rowHeight
);

const endIndex = startIndex + 2 * bufferSize + windowSize - 1;

This adds half the container size worth of rows above and below.

So if you're supposed to show rows 50--65, you might actually render 43--72, and visually clip the rest.

Throttling --- Why We Need It

React re-renders every time scrollTop changes. And when you scroll rapidly, onScroll can fire dozens of times per second. That's... too much.

Without control, this leads to:

Too many state updates
Laggy performance
Unnecessary DOM churn

Solution: Throttle scroll updates- We write a small helper:

function throttle(fn, t) {
  let blocked;
  return (...args) => {
    if (blocked) return;
    blocked = true;
    setTimeout(() => (blocked = false), t);
    return fn.apply(this, args);
  };
}

This allows us to call setScrollTop() at most once every 100ms. In the component:

const throttledScroll = throttle(handleScroll, 100);

...
<div onScroll={throttleScroll}> ... </div>

This way, even during fast scrolling, React doesn't panic trying to keep up.

Step 5: Putting it all together to test

You can find the final result and play around with the implementation yourself in jsPad:

This isn't all though. We can still make this more generic and performant, there's still ample scope for tweaks and improvements. For example, how do we account for rows with different heights?

I'll leave this question open for now, and maybe address it in a future post!

Cheers until then!

HTTP Refresher: Things You Should Know About HTTP

Anish Kumar — Sat, 18 Sep 2021 14:35:34 +0000

HTTP(Hyper Text Transfer Protocol) is one of many protocols used for transferring data (think of html pages, text, images, videos and much more) across machines. There are other application layer protocols like FTP, SMTP, DHCP etc.

HTTP was invented alongside HTML to create the first interactive, text-based web browser: the original World Wide Web. In this article, we'll be covering the key concepts related to HTTP, which all developers should be aware of.

Understanding the basics

Let's start with basics i.e. understanding how data transfer takes place and overall anatomy of HTTP messages.

OSI Model

The OSI (Open Systems Interconnection) is a conceptual framework used to describe the functions of a networking system. It thus helps to see how information is transferred across a network. Here's a diagram depicting various networking layers:

Application Layer: It's the layer that user interacts with. This layer uses protocols like HTTP and FTP.
Presentation Layer : This layer prepares and translates data from the network format to the application format or vice versa.
Session Layer: It's the layer responsible for establishing, maintaining, and ending connections between different applications. Typically you’ll see protocols such as NetBios, NFS, RPC, and SQL operating on this layer.
Transport Layer: It is the layer responsible for transferring data between end systems and hosts. It dictates what gets sent where, and how much of it gets sent. At this level, you see protocols like TCP, UDP, and SPX.
Network Layer: It has the job of dealing with most of the routing within a network. In simple terms, the Network Layer determines how a packet travels to its destination. Protocols like TCP/IP, AppleTalk, and IPX operate at this layer.
Data Link Layer: The data link provides for the transfer of data frames between hosts connected to the physical link.
Physical Layer: It is the hardware layer of the OSI model which includes network elements such as hubs, cables, ethernet, and repeaters. For example, this layer is responsible for executing electrical signal changes like making lights light up.

HTTP messages

As mentioned above, HTTP operates in application layer i.e. the layer user directly interacts with. Some key points regarding this protocol:

HTTP follows the classical client-server model. A client opens a connection to issue a request and then waits for the server to respond.
HTTP is a stateless protocol i.e. each request has isolated and independent lifecycle. HTTP is not session-less though. For example, HTTP cookies allow the use of stateful sessions.
HTTP, which is an application layer protocol, rides on top of TCP (Transmission Control Protocol): a transport layer protocol.
HTTP is text based protocol i.e data transmission takes place using text format.

HTTP request/response anatomy

An HTTP request can consist of four parts:

Request method
URL
Request headers
Request body

These are the possible HTTP request methods:

GET requests a specific resource in its entirety
HEAD requests a specific resource without the body content
POST adds content, messages, or data to a new page under an existing web resource
PUT directly modifies an existing web resource or creates a new URI if need be
DELETE gets rid of a specified resource
TRACE shows users any changes or additions made to a web resource
OPTIONS shows users which HTTP methods are available for a specific URL
CONNECT converts the request connection to a transparent TCP/IP tunnel
PATCH partially modifies a web resource

An HTTP request is just a series of lines of text that follow the HTTP protocol. A GET request might look like this:

GET /hello.txt HTTP/1.1
User-Agent: curl/7.63.0 libcurl/7.63.0 OpenSSL/1.1.l zlib/1.2.11
Host: www.example.com
Accept-Language: en

Once the server receives the request, It may respond with some data. A sample HTTP response would like this:

HTTP/1.1 200 OK
Date: Wed, 30 Jan 2019 12:14:39 GMT
Server: Apache
Last-Modified: Mon, 28 Jan 2019 11:17:01 GMT
Accept-Ranges: bytes
Content-Length: 12
Vary: Accept-Encoding
Content-Type: text/plain

Hello World!

HTTP and security concern

As stated earlier, HTTP uses text format for data transmission. The problem is this data is not encrypted, so it can be intercepted by third parties to gather data being passed between the two systems. This issue can be addressed using HTTPS.

What is HTTPS?

The S in HTTPS stands for "secure." HTTPS uses TLS (or SSL) to encrypt HTTP requests and responses, so in the example above, instead of the text, an attacker would see a bunch of seemingly random characters.

Instead of:

GET /hello.txt HTTP/1.1
User-Agent: curl/7.63.0 libcurl/7.63.0 OpenSSL/1.1.l zlib/1.2.11
Host: www.example.com
Accept-Language: en

The attacker would see something like:

t8Fw6T8UV81pQfyhDkhebbz7+oiwldr1j2gHBB3L3RFTRsQCpaSnSBZ78Vme+DpDVJPvZdZUZHpzbbcqmSW1+dkughdkhkuyi2u3gsJGSJHF/FNUjgH0BmVRWII6+T4MnDwmCMZUI/orxP3HGwYCSIvyzS3MpmmSe4iaWKCOHQ==

How TLS encrypts HTTP messages

TLS uses a technology called public key encryption. In a nutshell:

There are two keys, a public key and a private key.
The public key is shared with client devices via the server's SSL certificate.
When a client opens a connection with a server, the two devices use the public and private key to agree on new keys, called session keys, to encrypt further communications between them.
All HTTP requests and responses are then encrypted with these session keys, so that anyone who intercepts communications can only see a random string of characters, not the plaintext.

You can find a great article on encryption here if that interests you.

Evolution of HTTP

The protocol was developed by Tim Berners-Lee and his team between 1989-1991. The first version: HTTP/0.9 is also referred to as one line protocol. Only GET request type was supported back then. HTTP/0.9 was very limited and both browsers and servers quickly extended it to be more versatile, resulting in HTTP/1.0.

HTTP/1.0 brought in quite a few novelties. It introduced concepts of status code, multiple request methods(GET , HEAD, POST), request/response headers etc.

Lack of Persistence

HTTP/1.0 required to open up a new TCP connection for each request (and close it immediately after the response was sent).
TCP connection in turn uses a three-way handshake to establish a reliable connection. The connection is full duplex(two way connection), and both sides synchronize (SYN) and acknowledge (ACK) each other. The exchange of these four flags is performed in three steps—SYN, SYN-ACK, and ACK—as shown in Figure:

For better performance, it was crucial to reduce these round-trips between client and server. HTTP/1.1 solved this with persistent connections. What's a persistent connection? It's a (network communication) channel that remains open for further HTTP requests and responses rather than closing after a single exchange.

Keep-Alive header

keep-alive header was added to HTTP 1.0 to facilitate persistent connection. If the client supports keep-alive, it adds an additional header to the request:

Connection: keep-alive

Then, when the server receives this request and generates a response, it also adds a header to the response:

Connection: keep-alive

Following this, the connection is not dropped, but is instead kept open. When the client sends another request, it uses the same connection. This will continue until either the client or the server decides that the conversation is over, and one of them drops the connection.

HTTP/1.1

HTTP/1.1 Introduced critical performance optimizations and feature enhancements. Major offerings are listed below:

Persistent and pipelined connections

Persistence: In HTTP 1.1, all connections are considered persistent unless declared otherwise. The HTTP persistent connections do not use separate keep-alive messages, they just allow multiple requests to use a single connection by default.
Pipelining: is the process of sending successive requests, over the same persistent connection, without waiting for the answer. This avoids latency of the connection.

The image below illustrates difference between short lived, persistent and pipelined connections.

** Head of line blocking*: Even though pipelining reduces number of requests and re-uses same connection, it still requires the responses to arrive in order. Which means if the first request takes too long to be responded, subsequent requests remain blocked. This is called "Head of line blocking". HTTP/2.0 sloves this using **binary framing* without sacrificing parallelism. More on this is discussed ahead in this article.

Chunked transfers encoding

keep-alive makes it difficult for the client to determine where one response ends and the next response begins, particularly during pipelined HTTP operation. This is a serious problem when Content-Length cannot be used due to streaming. To solve this problem, HTTP 1.1 introduced a chunked transfer coding that defines a last-chunk bit. The last-chunk bit is set at the end of each response so that the client knows where the next response begins.

Compression and Decompression

HTTP/1.1 introduced headers that allow transfer of compressed data over the network. It can be done with the help of Accept-Encoding and Content-Encoding headers. Here's summary of how it works:

Client issues request with Accept-Encoding header to let server understand the compression schemes it supports:

GET /encrypted-area HTTP/1.1
Host: www.example.com
Accept-Encoding: gzip, deflate

If server supports any these compression schemes, it can choose to compress the content and respond with it along with Content-Encoding header:

HTTP/1.1 200 OK
Date: mon, 26 June 2016 22:38:34 GMT
Server: Apache/1.3.3.7 (Unix)  (Red-Hat/Linux)
Last-Modified: Wed, 08 Jan 2003 23:11:55 GMT
Accept-Ranges: bytes
Content-Length: 438
Connection: close
Content-Type: text/html; charset=UTF-8
Content-Encoding: gzip

HTTP/1.1 Also introduced following concepts:

Virtual hosting: a server with a single IP Address hosting multiple domains
Cache support: faster response and great bandwidth savings by adding cache support.

HTTP/2.0

HTTP/2 is a major revision of the HTTP protocol. It was derived from the earlier experimental SPDY protocol, originally developed by Google.

HTTP2 is binary, instead of textual

At the core of all performance enhancements of HTTP/2 is the new binary framing layer, which dictates how the HTTP messages are encapsulated and transferred between the client and server. Following are the critical terms associated with framing layer:

Frame: The smallest unit of communication in HTTP/2, each containing a frame header, which at a minimum identifies the stream to which the frame belongs.
Message: A complete sequence of frames that map to a logical request or response message.
Stream: A bidirectional flow of bytes within an established connection, which may carry one or more messages in it.

The image below illustrates how an HTTP/1.x message compares to HTTP/2.0 message (Source):

Multiplexing

In HTTP/2.0, client and server can break down an HTTP message into independent frames, interleave them, and then reassemble them on the other end. This is called multiplexing. It can be understood better by the diagram below:

Parallelism: One connection per origin

With the new binary framing mechanism in place, HTTP/2 no longer needs multiple TCP connections to multiplex streams in parallel; each stream is split into many frames, which can be interleaved and prioritized. As a result, all HTTP/2 connections are persistent, and only one connection per origin is required, which offers numerous performance benefits.

Server push

Another powerful new feature of HTTP/2 is the ability of the server to send multiple responses for a single client request. That is, in addition to the response to the original request, the server can push additional resources to the client without the client having to request each one explicitly.

Future of HTTP: HTTP/3.0

HTTP/3.0 is the upcoming major version of HTTP. So far the underlying transport layer mechanism behind HTTP has been TCP. HTTP/3.0 changes that, even though the core semantics remain unchanged.

The fundamental difference between HTTP/2 and HTTP/3 is that HTTP/3 runs over QUIC, and QUIC runs over connectionless UDP instead of the connection-oriented TCP.

Another significant different is HTTP/3.0 mandates secure transfer of data. HTTP/3 includes encryption that borrows heavily from TLS but isn’t using it directly. This change is because HTTP/3 differs from HTTPS/TLS in terms of what it encrypts:

With the older HTTPS/TLS protocol, only the data itself is protected by TLS, leaving a lot of the transport metadata visible.
In HTTP/3 both the data and the transport protocol are protected.

Note: Most browsers do not support h2c (HTTP/2 without TLS), which means opting for HTTP/2.0 pretty much needs you to opt for TLS if you're hosting a website. Here's a relevant stackoverlow thread on why browsers act this way.

The diagram below illustrates fundamental difference between HTTP/3.0 and it's predecessor(source):

References:

This article has been originally published at StackFull.dev. If you enjoyed reading this, you may want to opt for my newsletter. It would let me reach out to you whenever I publish a new thought!

Design patterns in Javascript: Publish-Subscribe or PubSub

Anish Kumar — Tue, 14 Sep 2021 02:40:42 +0000

What's a design pattern in software engineering? It's a general repeatable solution to a commonly occurring problem in software design. In this article, we'll be looking at one of such common design patterns and see how it can be put to use in real world applications.

This pattern is referred to as Publish-Subscribe or PubSub. Let's start with the overall notion behind this pattern before writing some code.

Overview

The image above describes the general idea behind this pattern:

We have a PubSub 'container' that maintains a list of subscribers (a subscriber is just a function)
A new subscription can be created by using the subscribe(subscriber) method, which essentially adds the subscriber into our PubSub container
We can use publish(payload) to call all the existing subscribers in the PubSub container with payload
Any specific subscriber can be removed from the container, at any point in time, using the unsubscribe(subscriber) method.

Implementation

Looking at the points above it's pretty straightforward to come up with a simple implementation:



// pubsub.js

export default class PubSub {
  constructor(){
    // this is where we maintain list of subscribers for our PubSub
    this.subscribers = []
  }

  subscribe(subscriber){
    // add the subscriber to existing list
    this.subscribers = [...this.subscribers, subscriber]
  }

  unsubscribe(subscriber){
   // remove the subscriber from existing list
    this.subscribers = this.subscribers.filter(sub => sub!== subscriber)
  }

  publish(payload){
   // publish payload to existing subscribers by invoking them
    this.subscribers.forEach(subscriber => subscriber(payload))
  }
}

Let's add a bit of error handling to this implementation:



// pubsub.js

export default class PubSub {
  constructor(){
    this.subscribers = []
  }

  subscribe(subscriber){
    if(typeof subscriber !== 'function'){
      throw new Error(`${typeof subscriber} is not a valid argument for subscribe method, expected a function instead`)
    }
    this.subscribers = [...this.subscribers, subscriber]
  }

  unsubscribe(subscriber){
    if(typeof subscriber !== 'function'){
      throw new Error(`${typeof subscriber} is not a valid argument for unsubscribe method, expected a function instead`)
    }
    this.subscribers = this.subscribers.filter(sub => sub!== subscriber)
  }

  publish(payload){
    this.subscribers.forEach(subscriber => subscriber(payload))
  }
}

Usage

We can use this implementation as follows:



// main.js
import PubSub from './PubSub';

const pubSubInstance = new PubSub();

export default pubSubInstance

Now, elsewhere in the application, we can publish and subscribe using this instance:



//app.js

import pubSubInstance from './main.js';

pubSubInstance.subscribe(payload => {

  // do something here

  showMessage(payload.message)

})



// home.js

import pubSubInstance from './main.js';

pubSubInstance.publish({ message: 'Hola!' });

Is it useful in real applications?

Yes. In fact, there are many libraries that use it under the hood and you may not have realized it so far. Let's take the example of the popular state management library for ReactJS - Redux. Of course, its implementation is not as simple as ours, since it's been implemented to handle many other nuances and use-cases. Nevertheless, the underlying concept remains the same.

Looking at the methods offered by Redux, You would see dispatch() and subscribe() methods which are equivalent to publish() and subscribe() methods we implemented above. You usually won't see subscribe() method getting used directly, this part is abstracted away behind connect() method offered by react-redux library. You can follow the implementation details here if that interests you.

In summary, all react components using connect() method act as subscribers. Any component using dispatch() acts as the publisher. And that explains why dispatching an action from any component causes all connected components to rerender.

What's next

We'll see how the idea behind PubSub can be extended further to build a state management library like redux from scratch.
We'll also see how an Event Emitter can be built from scratch, using similar notion as PubSub

This article has been originally published at StackFull.dev. If you enjoyed reading this, you may want to opt for my newsletter. It would let me reach out to you whenever I publish a new thought!

Applying tree traversal algorithms to DOM

Anish Kumar — Tue, 31 Aug 2021 05:35:04 +0000

We've looked through few binary tree traversal techniques so far:

1- Traversing through binary tree using recursive and iterative algorithms

2- Traversing through binary tree using parent pointers

In this article we'll put those learnings to use for an n-ary tree i.e. DOM. We'll see how we can locate DOM elements using various CSS selectors without using inbuilt APIs like getElementById, getElementsByClassname or querySelector/querySelectorAll. The article would thus also throw light on how these APIs might be working under the hood.

DOM traversal overview

Borrowing the idea from first article, let's come up with the preOrder traversal algorithm for DOM:

function walkPreOrder(node){
  if(!node) return

  // do something here
  console.log(node)

  for(let child of node.children){
     walkPreOrder(child)
  }
}

We can modify this algorithm to return an iterator instead:

function* walkPreOrder(node){
  if(!node) return

  // do something here
  yield node
  for(let child of node.children){
    yield* walkPreOrder(child)
  }
}

// USAGE
for(let node of walkPreOrder(root)){
  console.log(node)
}

We can use any of breadth first or depth first algorithms (discussed in previous articles) to traverse the DOM. For the sake of this article, we'll stick with the above approach though.

Let's also assume we're working on a document having following HTML:

<html>
  <head>
    <title>DOM selection algorithm</title>
  </head>
<body>

  <div class="container">
    <div class="body">
      <div class="row">
        <img id="profile" src="xyz.jpg" alt="">
      </div>
      <div class="row"></div>
      <div class="row"></div>
    </div>
  </div>

</body>
</html>

Locating a node by ID

Browsers offer document.getElementById() API to achieve this result. Using the walkPreOrder() helper it becomes really simple to achieve this. Let's see:

function locateById(nodeId){
  // iterate through all nodes in depth first (preOrder) fashion
  // return the node as soon as it's found
  for(let node of walkPreOrder(document.body)){
     if(node.id === nodeId){
        return node
     }
  }
   return null
}

We can use the locateById() function as follows:

const img = locateById('profile')
// returns the image node

Locating nodes by className

Browsers offer document.getElementsByClassName() API to achieve this result. Let's see how we can implement something similar:

function locateAllByClassName(className){
   const result = []
   for(let node of walkPreOrder(document.body)){
      if(node.classList.contains(className)){
        result.push(node)
      }
   }
   return result
}

// USAGE
const elements = locateAllByClassName('row')

How browser optimizes the selection queries

Selecting DOM node is a fairly common operation for web applications. Traversing through the tree multiple times for the same selector doesn't seem optimal. Browser optimizes the selection by using memoization.

Looking at mozilla parser's source, namely an excerpt from the function startTag:

 // ID uniqueness
 @IdType String id = attributes.getId();
 if (id != null) {
      LocatorImpl oldLoc = idLocations.get(id);
      if (oldLoc != null) {
            err("Duplicate ID \u201C" + id + "\u201D.");
            errorHandler.warning(new SAXParseException(
                  "The first occurrence of ID \u201C" + id
                  + "\u201D was here.", oldLoc));
       } else {
            idLocations.put(id, new LocatorImpl(tokenizer));
       }
 }

We can see that node IDs are kept in a simple hash map. It's done to ensure repeated queries for the same ID do not require full traversal, instead we can just look it up from hashMap and return it.

Here's how our solution would look like post memoization:

function getSelectors(){
  const idLocations = {}
  const classLocations = {}

  // updated selector functions  
  function locateById(nodeId){
    if(idLocations.hasOwnProperty(nodeId)) 
       return idLocations[nodeId]

    for(let node of walkPreOrder(document.body)){
       if(node.id === nodeId){
          idLocations[nodeId]= node //memoize
          return node
       }
     }
    idLocations[nodeId]= null // memoize
    return null
  }

  function locateAllByClassName(className){
    if(classLocations.hasOwnProperty(className)) 
         return classLocations[className]

    const result = []
    for(let node of walkPreOrder(document.body)){
       if(node.classList.contains(className)){
          result.push(node)
        }
     }
     classLocations[nodeId]= result
     return result
  }

  return {
       locateById,
       locateAllByClassName
    }

} 

  // USAGE
  const {locateById, locateAllByClassName} = getSelectors();
  const result = locateAllByClassName('row') // returns array of elements
  const img = locateById('profile') // returns an element, if found

Dealing with more complex selectors

Let's try to implement something like element.querySelector. Here's how MDN describes it:

The querySelector() method of the Element interface returns the first element that is a descendant of the element on which it is invoked that matches the specified group of selectors.

Example:

const firstRow = document.querySelector('.container .row:first-child')

In this case we can pass any CSS selector to the function and it should be able to traverse the DOM to find that element for us. Let's see it we how it can be implemented:

function myQuerySelector(selector){
  const path = selector.split(' ').map(str => str.trim())

  let currentNode = document.body
  while(path.length && currentNode){

    const currentSelector = path.shift()
    let found = false

    for(let node of walkPreOrder(currentNode)){
      if(node.matches(currentSelector)){
        currentNode = node
        found = true
        break
      }
    }

    if(!found) currentNode = null
  }
  return currentNode
}

// USAGE:
const firstRow = myQuerySelector('.container .row:first-child')

Implementation of myQuerySelectorAll (similar to element.querySelectorAll) also follows the same approach with slight modification:

function myQuerySelectorAll(selector){
  const path = selector.split(' ').map(str => str.trim())
  const result = []

  let currentNode = document.body
  while(path.length && currentNode){

    const currentSelector = path.shift()

    for(let node of walkPreOrder(currentNode)){
      if(node.matches(currentSelector)){
        currentNode = node
        result.push(currentNode)
      }
    }
  }
  return result
}

Bonus

We can use the recursive preOrder traversal approach, describe at the start of this article, to clone any tree. Let's see how we can use it to clone any DOM tree, similar to what element.cloneNode(true) does:

Create a clone of source node, by create a new node with same tagName and then copying over the attributes.
Recursively call cloneTree method on all children of the source node, and append the returned nodes as children to cloned node.

function cloneTree(node){
  if(!node) return

  const clonedNode = document.createElement(node.tagName.toLowerCase())
  const attributes = node.getAttributeNames()

  attributes.forEach(attribute => {
     clonedNode.setAttribute(attribute, node.getAttribute(attribute))
  })

  for(const child of node.children){
      clonedNode.append(cloneTree(child))
  }

  return clonedNode
}

This article has been originally published at StackFull.dev. If you enjoyed reading this, you may want to opt for my newsletter. It would let me reach out to you whenever I publish a new thought!

Memoization in Javascript

Anish Kumar — Sun, 29 Aug 2021 04:06:22 +0000

NOTE: this article was originally published at StackFull.dev.

Memoization is a useful concept. It helps avoid time taking or expensive calculations, after it's been done once. Applying memoization to a synchronous function is relatively straightforward. This article aims to introduce the overall concept behind memoization and then dive into the problems and their solutions while trying to memoize async functions.

Memoization

Let's start with memoizing a pure function. Let's say we have a function called getSquare, which returns square of the given:

  function getSquare(x){
     return x * x
  }

To memoize this we can do something like this:


const memo = {}

function getSquare(x){
    if(memo.hasOwnProperty(x)) {
      return memo[x]
    }
    memo[x] = x * x
    return memo[x]
}

So, with few lines of code we've memoized our getSquare function.

Let's create a memoize helper. It would accept a pure function as the first argument and agetKey function (which returns a unique key given argument of the function) as the second argument, to return a memoized version of the function:

function memoize(fn, getKey){
  const memo = {}
  return function memoized(...args){
     const key = getKey(...args)
     if(memo.hasOwnProperty(key)) return memo[key]

     memo[key] = fn.apply(this, args)
     return memo[key]
  }
}

We can apply this function to getSquare as follows:

const memoGetSquare = memoize(getSquare, num => num)

Memoizing a function accepting multiple arguments:

const getDivision = (a, b) => a/b

// memoizing using the helper
const memoGetDivision= memoize(getDivision, (a, b) => `${a}_${b}`)

Memoizing async functions

Let's say there' a function called expensiveOperation(key) which accepts a key as an argument and performs some async operation before returning the final result via a callback:

// does some async operation and invokes the callback with final result

expensiveOperation(key, ( data) => {
   // Do something
})

Let's use similar notion as above to memoize this function:

const memo = {}

function memoExpensiveOperation(key, callback){
  if(memo.hasOwnProperty(key)){
    callback(memo[key])
    return
  } 

  expensiveOperation(key, data => {
   memo[key] = data
   callback(data)
  })
}

So that was pretty easy. But wait! It doesn't solve the whole problem yet. Consider the following scenario:

1- Invoked expensiveOperation with key 'a'

2- While #1 is still in progress, invoked it again with same key

The function would run twice for the same operation, because #1 is yet to save the final data in memo. That's not something we wanted. We would instead want concurrent calls to be resolved at once, after the earliest call is complete. Let's see how we can accomplish this:

const memo = {}, progressQueues = {}

function memoExpensiveOperation(key, callback){
     if(memo.hasOwnProperty(key)){
       callback(memo[key])
       return
      }

     if(!progressQueues.hasOwnProperty(key)){
        // processing new key, create an entry for it in progressQueues
        progressQueues[key] = [callback]

      } else {
       // processing a key that's already being processed, enqueue it's callback and exit. 
        progressQueues[key].push(callback);
        return
      }

      expensiveOperation(key, (data) => {
           // memoize result
           memo[key] = data 
           // process all the enqueued items after it's done
           for(let callback of progressQueues[key]) {
                callback(data)
           }
           // clean up progressQueues
           delete progressQueue[key]
       })

}

We can go a step further, just like the last section, and create a re-usable helper say memoizeAsync:

function memoizeAsync(fn, getKey){
   const memo = {}, progressQueues = {}

   return function memoized(...allArgs){
       const callback = allArgs[allArgs.length-1]
       const args = allArgs.slice(0, -1)
       const key = getKey(...args)

        if(memo.hasOwnProperty(key)){
            callback(key)
            return
        }


        if( !progressQueues.hasOwnProperty(key) ){
           // processing new key, create an entry for it in progressQueues
           progressQueues[key] = [callback]
        } else {
           // processing a key that's already being processed, enqueue it's callback and exit. 
           progressQueues[key].push(callback);
           return
        }

        fn.call(this, ...args , (data) => {
           // memoize result
           memo[key] = data 
           // process all the enqueued items after it's done
           for(let callback of progressQueues[key]) {
                callback(data)
           }
           // clean up progressQueues
           delete progressQueue[key]
       })
   }
}

// USAGE

const memoExpensiveOperation = memoizeAsync(expensiveOperation, key => key)

Promises

Let's say we have a function processData(key) which accepts a key as argument and returns a Promise. Let's see how it can be memoized.

Memoizing the underlying promise:

Simplest way would be to memoize the promise issued against the key. Here's how it would look like:

const memo = {}
function memoProcessData(key){
  if(memo.hasOwnProperty(key)) {
    return memo[key]
  }

  memo[key] = processData(key) // memoize the promise for key
  return memo[key]
}

The code is fairly simple and self explanatory here. In fact, we can use the memoize helper we created a while ago:

 const memoProcessData = memoize(processData, key => key)

Can we memoize the value returned by Promise?

Yes. We can apply the same approach as the callback here. Though it might be an overkill for the sake of memoizing such a function:

  const memo = {},  progressQueues = {}

  function memoProcessData(key){

    return new Promise((resolve, reject) => {
      // if the operation has already been done before, simply resolve with that data and exit
      if(memo.hasOwnProperty(key)){
        resolve(memo[key])
        return;
      }

      if( !progressQueues.hasOwnProperty(key) ){
        // called for a new key, create an entry for it in progressQueues
        progressQueues[key] = [[resolve, reject]]

      } else {
       // called for a key that's still being processed, enqueue it's handlers and exit.         
        progressQueues[key].push([resolve, reject]);
        return;
      }


      processData(key)
        .then(data => {
            memo[key] = data; // memoize the returned data
            // process all the enqueued entries after successful operation
            for(let [resolver, ] of progressQueues[key])
              resolver(data)
        })
        .catch(error => {
           // process all the enqueued entries after failed operation
           for(let [, rejector] of progressQueues[key])
              rejector(error);
         })
        .finally(() => {
          // clean up progressQueues
           delete progressQueues[key]
         })
    })
  }

Further improvement

Since we're using an memo object to keep track of memoized operations, with too many calls to expensiveOperation with various keys(and each operation returning a sizeable chunk of data post processing) the size of this object may grow beyond what's ideal. To handle this scenario we can use a cache eviction policy such as LRU (Least Recently Used). It would ensure we're memoizing without crossing memory limits!

This article has been originally published at StackFull.dev. If you enjoyed reading this, you may want to opt for my newsletter. It would let me reach out to you whenever I publish a new thought!

Tree traversal techniques in JavaScript

Anish Kumar — Fri, 27 Aug 2021 15:21:57 +0000

Tree is an interesting data structure. It has wide variety of applications in all sorts of fields.
For example:

DOM is a tree data structure
Directory and files in our OS can be represented as trees
A family hierarchy can be represented as a tree.

There are bunch of variations of tree (such as heaps, BST etc.) which can be used in solving problems related to scheduling, image processing, databases etc. Many of complex problems may not seem related to tree on a quick look, but can actually be represented as one. We'll walk through such problems as well (in later parts of this series) to see how trees can make seemingly complex problems much easier to comprehend and solve.

Introduction

Implementing a Node for a binary tree is pretty straightforward.



function Node(value){
  this.value = value
  this.left = null
  this.right = null
}
// usage
const root = new Node(2)
root.left = new Node(1)
root.right = new Node(3)

So these few lines of code would create a binary tree for us which looks like this:



        2  
      /  \
     1    3
   /        \
null       null

Cool! So that was easy. Now, how do we put this to use?

Traversal

Let's start with trying to walk through these connected tree nodes (or a tree). Just as we can iterate through an array, it would be cool if we can 'iterate' through tree nodes as well. However, trees are not linear data structures like arrays, so there isn't just one way of traversing these. We can broadly classify the traversal approaches into following:

Breadth first traversal
Depth first traversal

Breadth First Search/Traversal (BFS)

In this approach, we traverse the tree level by level. We would start at the root, then cover all of it's children, and we cover all of 2nd level children, so on and so forth.
For example for the tree above, traversal would result in something like this:



2, 1, 3

Here's an illustration with slightly complex tree to make this even simpler to understand:

To achieve this form of traversal we can use a queue (First In First Out) data structure. Here's how the overall algorithm would look like:

Initiate a queue with root in it
Remove the first item out of queue
Push the left and right children of popped item into the queue
Repeat steps 2 and 3 until the queue is empty

Here's how this algorithm would look like post implementation:



function walkBFS(root){
  if(root === null) return

  const queue = [root]
  while(queue.length){
      const item = queue.shift()
      // do something
      console.log(item)

      if(item.left) queue.push(item.left)
      if(item.right) queue.push(item.right)
   }
}

We can modify above algorithm slightly to return an array of arrays, where each inner array represents a level with elements within in:



function walkBFS(root){
  if(root === null) return

  const queue = [root], ans = []

  while(queue.length){
      const len = queue.length, level = []
      for(let i = 0; i < len; i++){
          const item = queue.shift()
          level.push(item)
          if(item.left) queue.push(item.left)
          if(item.right) queue.push(item.right)
       }
       ans.push(level)
   }
  return ans
}

Depth First Search/Traversal (DFS)

In DFS, we take one node and keep exploring it's children until the depth the fully exhausted. It can be done in one of following ways:



 root node -> left node -> right node // pre-order traversal
 left node -> root node -> right node // in-order traversal
 left node -> right node -> root node // post-order traversal

All of these traversal techniques can be implemented recursively as well as iteratively. Let's jump into the implementation details:

Pre-Order traversal

Here's how PreOrder traversal looks like for a tree:



 root node -> left node -> right node

Trick:

We can use this simple trick to find out the PreOrder traversal of any tree manually: traverse the entire tree starting from the root node keeping yourself to the left.

Implementation:

Let's dive into actual implementation for such a traversal.
Recursive approach is fairly intuitive.



function walkPreOrder(root){
  if(root === null) return

  // do something here
  console.log(root.val)

  // recurse through child nodes
  if(root.left) walkPreOrder(root.left)
  if(root.right) walkPreOrder(root.left)
}

Iterative approach for PreOrder traversal is very similar to BFS, except we use a stack instead of a queue and we push the right child first into the queue:



function walkPreOrder(root){
  if(root === null) return

  const stack = [root]
  while(stack.length){
      const item = stack.pop()

      // do something
      console.log(item)

      if(item.right) stack.push(item.right)
      if(item.left) stack.push(item.left)
   }
}

In-Order traversal

Here's how InOrder traversal looks like for a tree:



left node -> root node -> right node

Trick:

We can use this simple trick to find out InOrder traversal of any tree manually: keep a plane mirror horizontally at the bottom of the tree and take the projection of all the nodes.

Implementation:

Recursive:



function walkInOrder(root){
  if(root === null) return

  if(root.left) walkInOrder(root.left)

 // do something here
  console.log(root.val)

  if(root.right) walkInOrder(root.right)
}

Iterative:



function walkInOrder(root){
  if(root === null) return

  const stack = []
  let current = root

  while(stack.length || current){
      while(current){
         stack.push(current)
         current = current.left
      }
      const last = stack.pop()

      // do something
      console.log(last)

      current = last.right
   }
}

Post-Order traversal

Here's how postOrder traversal looks like for a tree:



 left node -> right node -> root node

Trick:

For quick manual PostOrder traversal of any tree: pluck all the leftmost leaf nodes one by one.

Implementation:

Let's dive into actual implementation for such a traversal.

Recursive:



function walkPostOrder(root){
  if(root === null) return

  if(root.left) walkPostOrder(root.left)
  if(root.right) walkPostOrder(root.right)

  // do something here
  console.log(root.val)

}

Iterative:



function walkPostOrder(root){
  if(root === null) return []

  const tempStack = [root], mainStack = []

  while(tempStack.length){
      const last = tempStack.pop()

      mainStack.push(last)

      if(last.left) tempStack.push(last.left)
      if(last.right) tempStack.push(last.right)
    }

    return mainStack.reverse()
}

Bonus: JavaScript tip

How nice it would be if we could traverse the tree in one of following ways:



 for(let node of walkPreOrder(tree) ){
   console.log(node)
 }

Looks really nice and pretty simple to read, isn't it? All we've got to do is use a walk function, which would return an iterator.

Here's how we can modify our walkPreOrder function above to behave as per the example shared above:




function* walkPreOrder(root){
   if(root === null) return

  const stack = [root]
  while(stack.length){
      const item = stack.pop()
      yield item
      if(item.right) stack.push(item.right)
      if(item.left) stack.push(item.left)
   }
}

This article has been originally published at StackFull.dev. If you'd like to be notified when I drop more such articles, consider subscribing to the newsletter.

Quick Start with Redux and Redux-Saga using Redux-Box

Anish Kumar — Tue, 20 Feb 2018 21:09:26 +0000

It's a quick tutorial for all the visual learners, showing how you can use redux and redux-saga in your react / react-native applications to manage the store in a modular and expressive fashion.

What's Redux-Box:

Setting up and organizing a redux store in your react/react-native projects can be a tedious and daunting task. Redux-Box aims at extracting the complexity in setting up redux with redux-saga, without losing the flexibility or without introducing new bizarre terms.

For more info, here's the Github repo:
https://github.com/anish000kumar/redux-box

Redux is easier than you think

Anish Kumar — Mon, 29 Jan 2018 19:24:54 +0000

"The number one complaint I see about Redux is that there's "too much boilerplate". I also frequently see complaints that there's too much to learn, too many other addons that are needed to do anything useful, and too many aspects where Redux doesn't have any opinion and therefore doesn't offer any kind of built-in guidance..."

This comment precisely describes how overwhelming it can be for a beginner to get started with the core concepts of redux. The above text has been borrowed from an active issue on official redux repo (source : https://github.com/reactjs/redux/issues/2295). The kind of response this issue has received from the community clearly shows that the issue is real. And it's not something that only beginners face, in fact, any efficient developer wouldn't be a fan of repeating the same piece of code over and again, specially when it can be abstracted away.

Abstraction of repetitive boilerplate/functionality offers some great perks, such as:

It Saves time!
It Reduces the moving parts of your program, thus leaving lesser chances of committing mistake
It makes your code cleaner and thus easier to maintain

More options = more moving parts = higher chances of mistake

Let's use (redux - the noise)

I will be using the classic todo-list example to illustrate how simple redux can be. But before that, here's a diagram, illustrating the core philosophy of redux in simplest terms:

source:blog.apptension.com

Here are the key points :

There's a plain javascript object, which contains the state for the whole application. (state)
The state is immutable, meaning, it cannot be directly changed. For example, you can't do state.name="john"
To make any changes in the state, you must dispatch an action (which is also a plain object).
The reducer (a function) listens for any dispatched actions and accordingly mutates the state.
Finally, the state gets updated and the view is rendered again to show the updated state.

Don't worry if that's confusing, the fun part begins now :

We have 3 simple objectives for our todo app:

User should be able to add todos
User should be able to mark incomplete todos as complete and vice-versa
User should be able to delete todos

Let's start with a fresh react-application:

create-react-app  todo-redux

Also let's pull in redux-box to set up redux, redux-saga, dev tools and much more in a trice:

npm install --save redux-box

Great, we've got the essentials. Let's set up our redux-store quickly by creating src/store folder. This is where we would be programming anything related to the store. Redux box emphasizes on modular store, i.e split your store into multiple modules to manage stuffs easily.

For our todo-app we will have just one module, for simplicity. Let's call it todo.js. The module would specify it's initial state, actions and mutations, like so:

const state = {
    items: [],  
}

const actions = {

}

const mutations ={

}

export const module = {
    name : 'todos',
    state, 
    actions, 
    mutations
}

That's the bare-bones of our module. Let's register it with the global store :

src/store/index.js

import {createStore} from 'redux-box';
import {module as todoModule} from './todo'

export default createStore([
    todoModule
])

There we go! We have set up our redux store with all the needed bells and whistles in just a few lines of code. (You could have set up redux-saga as well, but since our todo app won't require that, I'm skipping the snippet showing how sagas can be used in a module. You may want to refer to the repo if you are curious enough. )

Final step in the setup is to wrap our root component around Provider, so that the app can recognise our store:
src/App.js

import {Provider} from 'react-redux';
import store from './store'
import TodoMain from './components/TodoMain'

class App extends Component {
  render() {
    return (
      <Provider store={store} >
        <div className="App">
           <TodoMain></TodoMain>
        </div>
      </Provider>
    );
  }
}

export default App;

Here components/TodoMain.js is our main component where we will be putting our UI and integrating it with our todo module.

In TodoMain.js, we would have:

An input, to let us add new todos
A list showing all the todos
A delete-icon alongside each list item, allowing us to delete the todo

Here's how our final TodoMain.js looks like:

import React, { Component } from 'react'


export default class TodoMain extends Component {
 constructor(){
     super();
 }

 render() {

    return (
      <div className="main">
        <h1>Todos Manager</h1>
        <input type="text"/>

        <ol className="todos">
            // list items go here
        </ol>
      </div>
    )
  }
}

Writing the logic to add, delete and toggle todos

We would need three mutations, for adding, deleting and toggling todos. And for each mutation, we will be creating an action, so that our components can call those mutations (a component can directly access state and actions of any module, but nothing else). Thus our todo module looks like this:

const state = {
    items: [],  
    active_todo :
}

const actions = {
    addTodo : (todo) => ({
         type: 'ADD_TODO' , 
         todo }) ,
    toggleTodoStatus : (todo) => ({
        type : 'TOGGLE_TODO', 
        todo}),
    deleteTodo : (todo) => ({
        type : 'DELETE_TODO',
        todo
    })
}

const mutations ={
    ADD_TODO : (state, action) => state.items.push(action.todo),

    TOGGLE_TODO : (state, {todo}) => {
       state.items = state.items.map(item => {
           if(item.id== todo.id)
               item.completed = !item.completed
           return item
       });
    },
    DELETE_TODO : (state, {todo}) => {
       let index = state.items.findIndex(item => item.id==todo.id);
       state.items.splice(index, 1);
    }

}

export const module = {
    name : 'todos',
    state, 
    actions, 
    mutations
}

Finally, let the component interact with module logic

To connect our store with component, we use connectStore decorator from redux-box. The decorator then attaches the module to the prop of the component:

import React, { Component } from 'react'
import {module as todoModule} from '../store/todos';
import {connectStore} from 'redux-box';
import cn from 'classnames';

@connectStore({
    todos : todoModule
})
class TodoMain extends Component {
 constructor(){
     super();
     this.state ={
         todo :  ''
     }
 }

 addTodo = (item) => {
    if(e.keyCode==13)
        todos.addTodo({
           id : Math.random(),
           text: this.state.todo,
           completed: false
        })          
  }

  render() {
    const {todos} = this.props
    return (
      <div className="main">
        <h1>Todos Manager</h1>
        <input type="text" value={this.state.todo}

        onChange={(e)=>{
            this.setState({ todo : e.target.value})
        }} 

        onKeyUp = {(e)=> this.addTodo(e.target.value)}
        />
        <ol className="todos">
            {  
                todos.items.map((item,i) => {
                    return <li 
                    className={cn({'completed': item.completed})} 
                    onClick={()=> todos.toggleTodoStatus(item) }
                    key={i}>
                        {item.text}
                       <i class="fa fa-trash"
                        onClick= { (item) => todos.deleteTodo(item) }
                        ></i>
                    </li>
                })
            }
        </ol>
      </div>
    )
  }
}

export default TodoMain

That's it...

You see! Redux is easy. It's purpose is to make your life easier, so keep it simple :)

And yes, Feel free to star redux-box at GitHub, if you think it truly helps!