Forem: Lalit Yadav

React TypeScript: Outside Click Detector

Lalit Yadav — Fri, 02 Dec 2022 23:57:28 +0000

We want to write a type safe outside click detector component that can be wrapped around any component to listen for an outside click. Additionally, we will also listen for keypress for the scenarios when the user presses Escape to close a modal, or dropdown.

Requirements

Our Higher Order Component(HOC) should support two basic functionality for compositive usage

We can use forward Ref; React way or,
We can use document.getElementById to listen for the click

Let's define our Interface for the props for our HOC

export interface IClickOutsideProps {
  children: React.ReactNode
  wrapperId: string? // Id of our outside wrapper where we will listen for click
  listen: boolean // Toggle to listen for click
  onClickOutside: () => void // 
}

Besides, our functional requirements we should also define our non-functional requirements

We should be able to use Mouse events to interact
We should be able to use the keyboard to interact
We should be able to support touch events as well

Implementation
Now, let's write our basic component around the prop definition. But, we are missing ref But, we cannot simply pass it as a prop, we will need to use React's forwardRefAPI and before continuing, let's do a quick refresher on React's documentation on Ref forwarding

Ref forwarding is an opt-in feature that lets some components take ref they receive and pass it further down (in other words, "forward" it) to a child.
Example from React's documentation

const FancyButton = React.forwardRef((props, ref) => (
  <button ref={ref} className="FancyButton">
    {props.children}
  </button>
));

// You can now get a ref directly to the DOM button:
const ref = React.createRef();
<FancyButton ref={ref}>Click me!</FancyButton>;

We need to typeSafe our component so let's write a fundamental component that satisfies our requirements.

// Defining our imports
import React, { useEffect, useRef, forwardRef, ForwardedRef, MutableRefObject } from 'react'

If we recall the function definition for forwardRef from React's definition is React.forwardRef((props, ref) => React.ReactNode) We already have the type of our props defined earlier as IClickOutsideDetectorProps , for ref, we have already imported ForwardRef from React. So, ref: ForwardRef should work right? Not quite yet, we still need to define the inner generic type for our ForwardRef. Our component should look like this

const ClickOutsideDetector = forwardRef((props: IClickOutsideDetectorProps, ref: ForwardedRef<HTMLDivElement>) => {

})

Let's take a moment and think about our functional requirements. We should be able to use HOC with the ref or with HTML Node id to select our Node.

When we have our wrapper element we use the neat trick to check if the wrapper contains the element where the click happened if yes we return otherwise we run the callback

const ClickOutsideDetector = forwardRef((props: IClickOutsideDetectorProps, ref: ForwardedRef<HTMLDivElement>) => {
  const { children, listen, wrapperId, onClickOutside } = props
  const container = ref || useRef<HTMLDivElement>(null)

  const handleEvent = (e: MouseEvent) => {
    if ((container as MutableRefObject<HTMLDivElement>).current.contains(e.target as Node)) return
    const wrapperElm = document.getElementById(wrapperId)

    if (wrapperElm && wrapperElm.contains(e.target as Node)) return

    onClickOutside()
  }

  return <div ref={container}>{children}</div>
})

Okay, HOC has our logic in place we still need to handle MouseEvent, KeyboardEvent, and Touch events.

const ClickOutsideDetector = forwardRef((props: IClickOutsideDetectorProps, ref: ForwardedRef<HTMLDivElement>) => {
  const { children, listen, wrapperId, onClickOutside } = props
  const container = ref || useRef<HTMLDivElement>(null)
  const onKeyUp = (e: KeyboardEvent) => {
    if (e.code === 'Escape') onClickOutside()
  }

  const handleEvent = (e: KeyboardEvent | MouseEvent | TouchEvent) => {
    if ((container as MutableRefObject<HTMLDivElement>).current.contains(e.target as Node)) return
    const wrapperElm = document.getElementById(wrapperId)

    if (wrapperElm && wrapperElm.contains(e.target as Node)) return

    onClickOutside()
  }

  useEffect(() => {
    if (listen) {
      document.addEventListener('mousedown', handleEvent, false)
      document.addEventListener('touchend', handleEvent, false)
      document.addEventListener('keyup', onKeyUp, false)
    }

    return () => {
      document.removeEventListener('mousedown', handleEvent, false)
      document.removeEventListener('touchend', handleEvent, false)
      document.removeEventListener('keyup', onKeyUp, false)
    }
  })

  return <div ref={container}>{children}</div>
})

// For debugging
ClickOutsideDetector.displayName = 'ClickOutsideDetector'

Testing
We can test our component simply by using ReactTestingLibrary underneath. There is not much to explain here, the code is self-explanatory

import React, { createRef, useState } from 'react'
import { render, screen } from '@testing-library/react'
import userEvent from '@testing-library/user-event'
import '@testing-library/jest-dom'

import { ClickOutsideDetector } from './index'

const TestComponent = () => {
  const [isOpen, setIsOpen] = useState(true)
  const containerRef = createRef<HTMLDivElement>()
  const handleClickOutSide = () => setIsOpen(false)

  return (
    <div>
      <div data-testid='clickableArea'>
        <button>Click happens here</button>
      </div>
      <div id='wrapperId'>
        <ClickOutsideDetector
          ref={containerRef}
          wrapperId='wrapperId'
          listen={true}
          onClickOutside={handleClickOutSide}
        >
          <p data-testid='renderedItem'>{isOpen ? 'open' : 'closed'}</p>
        </ClickOutsideDetector>
      </div>
    </div>
  )
}

describe('Running functional test for ClickOutsideDetector', () => {
  test('Check if ClickOutside is working on Click', async () => {
    render(<TestComponent />)

    expect(screen.getByTestId('renderedItem')).toHaveTextContent('open')
    await userEvent.click(screen.getByTestId('clickableArea'))
    expect(screen.getByTestId('renderedItem')).toHaveTextContent('closed')
  })

  test('Check if ClickOutside is working on Keyboard', async () => {
    render(<TestComponent />)

    expect(screen.getByTestId('renderedItem')).toHaveTextContent('open')
    await userEvent.keyboard('{Escape}')
    expect(screen.getByTestId('renderedItem')).toHaveTextContent('closed')
  })
})

If you enjoy the article or have any comments please feel free to comment. Happy coding!

JS Array method polyfills

Lalit Yadav — Thu, 17 Jun 2021 16:46:56 +0000

Array.prototype.map()

The map() method creates a new array populated with the results of calling a provided function on every element in the calling array.

  Array.prototype.myMap = function(callback) {
    if (typeof callback !== 'function') {
      throw new TypeError(callback + ' is not a function');
    }

    const obj = Object(this);
    let newArr = new Array(this.length);
    let i = 0;

    while (i < obj.length) {
      if (i in obj) {
        newArr[i] = callback.call(this, obj[i], i, obj);
      }
      i++;
    }

    return newArr;
  }

Array.prototype.filter()

The filter() method creates a new array with all elements that pass the test implemented by the provided function.

  Array.prototype.myFilter = function(callback) {
    if (typeof callback !== 'function') {
      throw new TypeError(callback + ' is not a function');
    }

    const obj = Object(this);
    let newArr = new Array(obj.length);
    let i = 0, actualLen = 0;

    while (i < obj.length) {
      if (i in obj) {
        if (callback.call(this, obj[i], i, obj)) {
          newArr[actualLen++] = obj[i];
        }
      }
      i++;
    }

    newArr.length = actualLen;

    return newArr;
  }

Array.prototype.reduce()

The reduce() method executes a reducer function (that you provide) on each element of the array, resulting in a single output value.

  Array.prototype.myReduce = function(...args) {
    if (typeof args[0] !== 'function') {
      throw new TypeError(args[0] + ' is not a function');
    }

    const obj = Object(this);
    let i = 0;
    let result;

    if (args.length > 1) {
      result = args[1];
    } else {
      result = obj[i++];
    }

    while (i < obj.length) {
      if (i in obj) {
        result = args[0].call(this, result, obj[i], i, this);
      }
      i++;
    }

    return result;
  }

The above polyfills are only meant for implementation purpose, the one provided on MDN are definitely better and one should not use their own polyfills over the API's methods. Thanks for reading :)

AVL Tree C++

Lalit Yadav — Fri, 11 Jun 2021 08:28:31 +0000

AVL Tree is a balanced binary search tree in which any two subtree height only differ by at most 1 i.e height of |Left child - Right child| <= 1. Along with key and value at each node we also store the computed Height property.

We do Rebalancing if the difference is more than 1.
AVL supports following operations:-

Find in O(logN)
Insert in O(logN)
Delete in O(logN)

Analysis of operations

 AVLInsert(k, R)
  Insert(k, R)
  N <- Find(k, R)
  Rebalance(N)

 Rebalancing
 if |N.Left.Height - N.Right.Height| <= 1

 Rebalance(N)
  p <- N.Parent
  if N.Left.Height > N.Right.Height + 1:
    RebalanceRight(N)
  if N.Right.Height > N.Left.Height + 1:
    RebalanceLeft(N)
  AdjustHeight(N)
  if P != null:
    Rebalance(N)

 AdjustHeight(N)
  N.Height <- 1 + max(N.Left.Height + N.Right.Height)

Code

The code is pretty straightforward, we will just implement the operations. It is self explanatory and pretty verbose


//
//  AVLTree.h
//  Data structures
//
//  Created by Lalit Yadav on 06/09/20.
//  Copyright © 2020 Lalit Yadav. All rights reserved.
//

#ifndef AVLTree_h
#define AVLTree_h

#include <iostream>

using namespace std;

struct Node {
  int data;
  int height;
  Node * parent;
  Node * left;
  Node * right;
};

typedef Node * Nodeptr;

class AVLTree {
  Nodeptr root;
  Nodeptr Maximum(Nodeptr node);
  int GetHeight(Nodeptr node);
  void AdjustHeight(Nodeptr node);
  void ReplaceChild(Nodeptr parent, Nodeptr child, Nodeptr new_child);

  void RotateLeft(Nodeptr node);
  void RotateRight(Nodeptr node);

  void Rebalance(Nodeptr node);
  void RebalanceLeft(Nodeptr node);
  void RebalanceRight(Nodeptr node);
  public:
    AVLTree(): root(nullptr) {}
  AVLTree(int key);
  bool IsEmpty();
  Nodeptr Root();
  Nodeptr Find(int key);
  void Insert(int key);
  void Delete(int key);
  void PrintInOrder(Nodeptr node);
  void PrintPreOrder(Nodeptr node);
};

bool AVLTree::IsEmpty() {
  return root == nullptr;
}

Nodeptr AVLTree::Root() {
  return root;
}

Nodeptr AVLTree::Maximum(Nodeptr node) {
  if (node -> right != NULL) {
    return Maximum(node -> right);
  } else {
    return node;
  }
}

int AVLTree::GetHeight(Nodeptr node) {
  if (node == nullptr)
    return 0;

  return node -> height;
}

Nodeptr AVLTree::Find(int key) {
  if (IsEmpty()) {
    return nullptr;
  }

  auto parent = root;

  while (parent != nullptr) {
    if (key > parent -> data && parent -> right != nullptr)
      parent = parent -> right;
    else if (key < parent -> data && parent -> left != nullptr)
      parent = parent -> left;
    else
      return parent;
  }

  return parent;
}

void AVLTree::AdjustHeight(Nodeptr node) {
  node -> height = 1 + max(GetHeight(node -> left), GetHeight(node -> right));
}

void AVLTree::RotateLeft(Nodeptr node) {
  auto pivot = node -> right;

  // Update the parent of the node
  pivot -> parent = node -> parent;
  node -> parent = pivot;

  // Update the child of of the updated parent
  if (pivot -> parent == nullptr)
    root = pivot;
  else if (pivot -> parent -> left == node)
    pivot -> parent -> left = pivot; // Update the child link of the parent
  else
    pivot -> parent -> right = pivot;

  node -> right = pivot -> left;

  if (pivot -> left != nullptr)
    pivot -> left -> parent = node;

  pivot -> left = node;

  AdjustHeight(node);
  AdjustHeight(pivot);
}

void AVLTree::RotateRight(Nodeptr node) {
  auto pivot = node -> left;

  pivot -> parent = node -> parent;
  node -> parent = pivot;

  if (pivot -> parent == nullptr)
    root = pivot;
  else if (pivot -> parent -> left == node)
    pivot -> parent -> left = pivot;
  else
    pivot -> parent -> right = pivot;

  node -> left = pivot -> right;

  if (pivot -> right != nullptr)
    pivot -> right -> parent = node;

  pivot -> right = node;

  AdjustHeight(node);
  AdjustHeight(pivot);
}

void AVLTree::RebalanceLeft(Nodeptr node) {
  auto right_child = node -> right;

  if (right_child != nullptr) {
    if (GetHeight(right_child -> left) > GetHeight(right_child -> right))
      RotateRight(right_child);
  }

  RotateLeft(node);
}

void AVLTree::RebalanceRight(Nodeptr node) {
  auto left_child = node -> left;

  if (left_child != nullptr) {
    if (GetHeight(left_child -> right) > GetHeight(left_child -> left))
      RotateLeft(left_child);
  }

  RotateRight(node);
}

void AVLTree::Rebalance(Nodeptr node) {
  auto parent = node -> parent;

  if (GetHeight(node -> left) > GetHeight(node -> right) + 1)
    RebalanceRight(node);

  if (GetHeight(node -> right) > GetHeight(node -> left) + 1)
    RebalanceLeft(node);

  AdjustHeight(node);

  if (parent != nullptr) {
    Rebalance(parent);
  }
}

void AVLTree::Insert(int key) {
  auto p = new Node;

  p -> data = key;
  p -> height = 0;
  p -> parent = nullptr;
  p -> left = nullptr;
  p -> right = nullptr;

  if (IsEmpty()) {
    root = p;
  } else {
    auto parent = Find(key);
    p -> height = 1;

    if (key < parent -> data)
      parent -> left = p;
    else
      parent -> right = p;

    p -> parent = parent;
    Rebalance(parent);
  }
}

void AVLTree::Delete(int key) {
  auto node = Find(key);

  if (node == nullptr)
    return;

  if (node -> right == nullptr && node -> left == nullptr) {
    if (node -> parent == nullptr) {
      root = nullptr;
    } else {
      ReplaceChild(node -> parent, node, nullptr);
      Rebalance(node -> parent);
    }
  } else if (node -> left == nullptr) {
    // Replace the node with it's right child
    if (node -> parent == nullptr) {
      root = node -> right;
      node -> right -> parent = nullptr;
      Rebalance(node -> right);
    } else {
      ReplaceChild(node -> parent, node, node -> right);
      node -> right -> parent = node -> parent;
      Rebalance(node -> parent);
    }
  } else {
    // Replace the node with the maximum key from it's left child
    auto new_node = Maximum(node -> left);

    if (node -> parent == nullptr) {
      root = new_node;

      new_node -> right = node -> right;
      new_node -> left = node -> left;

      Rebalance(new_node);
    } else {
      auto parent_new_node = new_node -> parent;
      ReplaceChild(node -> parent, node, new_node);
      ReplaceChild(new_node -> parent, new_node, nullptr);

      new_node -> parent = node -> parent;
      new_node -> left = node -> left;

      if (node -> right != nullptr) {
        new_node -> right = node -> right;
        new_node -> right -> parent = new_node;
      }

      if (parent_new_node -> parent == node) {
        parent_new_node -> parent = new_node;
      }

      Rebalance(parent_new_node);
    }
  }

  delete node;
}

void AVLTree::ReplaceChild(Nodeptr parent, Nodeptr child, Nodeptr new_child) {
  if (parent -> left == child) {
    parent -> left = new_child;
  } else {
    parent -> right = new_child;
  }
}

void AVLTree::PrintInOrder(Nodeptr node) {
  if (node == nullptr)
    return;

  PrintInOrder(node -> left);
  cout << node -> data << ' ';
  PrintInOrder(node -> right);
}

void AVLTree::PrintPreOrder(Nodeptr node) {
  if (node == nullptr)
    return;

  cout << node -> data << ' ';
  PrintPreOrder(node -> left);
  PrintPreOrder(node -> right);
}

#endif /* AVLTree_h */

Understanding recursions and memory

Lalit Yadav — Thu, 18 Jun 2020 15:58:22 +0000

Recursion is a very well-known concept in modern high-level programming languages. In this post, we will try to analyze the recursion in C language. I am pretty sure learning in C should be sufficient to understand this topic's implementation in other languages as well. Well, that's being said recursion are language agnostics just like loops but there is one catch; language should have some support for recursion optimization via tail recursion. In present time, every language has it.

Just to give a quick refresher, recursion or recursive function is the function that returns itself with new computed parameters. The incoming parameters determine the condition for the next call; if the terminating condition is met then, it will return some value else the cycle continues.

A recursive function has one terminating condition and, two phases: winding and unwinding. Let's understand this by a simple expression

// Calculates sum of digits
int recursive_sum(int num) {
  if (num == 1) {
    return num;
  } else {
    return num + recursive_sum(num - 1);
  }
}

Which is simply doing something like this:
F(5) = 5 + F(4); winding start
        4 + F(3);
            3 + F(2);
                2 + F(1); winding end
                1; terminating condition return
            2 + 1; unwinding start
        3 + 3;
    4 + 6;
  F(5) = 5 + 10; unwinding end

or in simple terms: F(x) -> F'(F''(x''));

Recursion can be subdivided into two parts:

Basic/traditional recursion
Tail recursion

A basic recursion is a recursion that has both winding and unwinding phase and tail recursion just has a winding phase. To fully comprehend the recursion we will be looking into how memory is utilized in a C program.

Whenever we start the execution of our program, memory is allocated for computations. The program can be divided into segments like variables, loops, constants, globals, functions, instructions so on and forth. The memory semantics are different for each segment. Our compiler utilizes the different regions of memory to execute the program, the regions are:

Code area
Static data area
Stack
Heap

Code area contains the instructions which your program executes as it advances.

Static data area stores the data that is declared by the program for the duration of its life cycle. Global variables, constants (Read-only) reside here along with the variables which can be modified during runtime.

Stack region is similar to the Stack data structure; it follows the LIFO, last in fast out principle. The stack stores the information about function call for the duration of its execution. Whenever we call a function, our compiler allocates some storage in the stack in a region called activation record or simply a stack frame. In simple terms Stack is an array where each block is a stack frame that stores some information about the function. The top frame is called a Stack pointer which will be updated to refer the most recent activation call.

The stack frame can be further divided into five separate regions to store different information about an activation call.

Incoming parameters
Return value
Temporary storage
Saved state information
Outgoing parameters

Incoming parameters are the parameters provided in the activation call. Outgoing parameters are the parameters that are passed onto the next call to function(next activation call). Temporary storage stores the data used during the execution. Saved state information is the saved information for reference when the activation terminates. The return value is simply the return of a function.

Heap or dynamic memory is the memory allocated at the runtime. When we cannot pre-allocate storage for our program, we may generally request, reserve, and free the memory as per our need. Malloc, calloc, realloc for memory allocation, and free to deallocate are used in C but most other programming languages do it by default by using something called ARC (Automatic reference control if ARC is 0 for some object then the memory gets freed).

In C memory leaks happen if we forget to call free and in other languages like Swift memory leak will happen if a Node is self-referencing i.e class referring to self, in that case, ARC will always be 1 even when the Class doesn't have any member. There are options of ways to solve this in the respective languages but they are beyond the scope of our main topic. There are memory leaks at stack level as well which we will be looking next, like how recursions could lead to stack overflow.

Copy by reference is generally dynamic memory while copy by value is static, or Class members(not in C) are stored in the heap and struct members in the stack. Accessing heap is costly than accessing stack so a little optimization trick is to use a struct.

Coming back to recursion, each function call in our recursive function is going to be stored in our stack frame along with the information associated with it. Now, let's look into a simple recursive code:

int recursive_sum(int num) {
  if (num == 1) {
    return num;
  } else {
    return num + recursive_sum(num - 1);
  }
}

int t_recursive_sum(int num, int sum = 0) {
  if (num == 0) {
   return sum;
  } else {
   return t_recursive_sum(num - 1, sum + num);
  }
}

int main() {
  printf("Basic: %d\n", recursive_sum(5));
  printf("Tail: %d\n", t_recursive_sum(5));
  return 0;
}

recursive_sum and t_recursive_sum both return the same value, essentially they are doing the same thing but what we abstracted is how they are doing it.

Let's say F(x) is recurive_sum(5);

F(5) -> 5 + (F(4) -> 4 + (F(3) -> 3 + (F(2) -> 2 + (F(1) -> 1))))
F(5) = 5 + F(4); // winding start
      4 + F(3);
         3 + F(2);
            2 + F(1); // winding end
               1; // terminating condition
            2 + 1; // unwinding start
         3 + 3;
      4 + 6;
F(5) = 5 + 10; // unwiding end

F'(x) is t_recursive_function(5);

F'(5, 0) -> F(4, 5) -> F(3, 9) -> F(2, 12) -> F(1, 14) -> F(0, 15)
F(5, 0) = F(4, 5);  // winding start
        F(3, 9);
           F(2, 12);
              F(1, 14);
                 F(0, 15);
                 15; // final return
no unwinding

Both F(x) and F'(x) are doing winding but F(x) is also doing unwinding. This means if there were n call till the first actual return (notice how many parentheses our F(5) has) then there will be n more returns before F(x) finally finishes the execution.

Since F(5) is doing some computations on each return so the stack frames which were used when we returned F(4)…F(1) are never freed this means if there were n calls then there are n stack frames still holding all the information about function variables and state. This means our stack will grow in size but what if it just cannot grow more? Well it will throw an error famously knows as Stack Overflow.

So our basic recursion is not only slow but dangerous as well. Tail recursion just returns the function itself and it finishes its execution (the function memory is freed as soon as it returns). To make it more clear think it like this in basic recursion the function never gets freed since it is doing something like this constant + F'(x) so in this case, the last function or stack frame gets freed first.

In our tail recursion, our stack pointer never updated to the next stack that is because as soon as the function returns, the memory used by it will be freed. It doesn't matter if it returns the next function, the point is next call will be independent of its parent as soon as it is called so we do not need to hold the memory. So we can just rewrite on the previous stack. This means more optimizations and no overflow :).

In conclusion, recursions can be avoided by using iteration but if you are using them then try to use tail recursion. You can practice on recursion if you look into greedy algorithms or divide and conquer(does binary search ring a bell?). If you want to see recursion more interactively you can check Algorithm Visualizations and how basic recursion is significantly improved by using iteration and memorization in the case of Fibonacci numbers.

Thanks for reading the post, please note this is by no means a deep dive into the memory topic but just an introduction. My goal was to understand how recursions and memory work for code optimization and how recursion is analogical with iterations, so I wrote this one to share whatever less I know. Have a good day :)