React Immutable Data Structures Hooks

react-immutable-data-structures-hooks.md

React Immutable Data Structures Hooks

Popular data structures implemented in immutable React hooks.

Hooks:

• useArray
• useHeap
• useList
• useQueue
• useStack

Changelog:

• 2024-04-10: Initial implementation

TODO:

• Implementing tests
• Moving to a real repository

use-array.ts

import { useCallback, useState } from "react"

/**
 * Immutable Array
 * @param initialState
 * @returns
 */
function useArray<T>(initialState: T[] = []) {
  const [state, setState] = useState<T[]>(initialState)

  const checkOverflow = useCallback(
    function (index: number) {
      if (index < 0 || index >= state.length) {
        throw new RangeError("Index must be between 0 and maximum array size")
      }
    },
    [state.length],
  )

  const prepend = useCallback(function (value: T) {
    setState((state) => [value, ...state])
  }, [])

  const append = useCallback(function (value: T) {
    setState((state) => [...state, value])
  }, [])

  const remove = useCallback(
    function (index: number) {
      console.log("remove", index, [
        ...state.slice(0, index),
        ...state.slice(index + 1),
      ])
      setState((state) => [...state.slice(0, index), ...state.slice(index + 1)])
    },
    [state],
  )

  const entries = useCallback(
    function () {
      return state.entries()
    },
    [state],
  )

  const swap = useCallback(function (a: number, b: number) {
    setState((state) => {
      const v = [...state]
      const t = v[a]
      v[a] = v[b]
      v[b] = t
      return v
    })
  }, [])

  const insert = useCallback(function (index: number, value: T) {
    setState((state) => [
      ...state.slice(0, index),
      value,
      ...state.slice(index),
    ])
  }, [])

  const set = useCallback(function (index: number, value: T) {
    setState((state) => [
      ...state.slice(0, index),
      value,
      ...state.slice(index + 1),
    ])
  }, [])

  const has = useCallback(
    function (index: number) {
      return index > 0 && index < state.length
    },
    [state],
  )

  const get = useCallback(
    function (index: number) {
      checkOverflow(index)
      return state.at(index)
    },
    [checkOverflow, state],
  )

  const sort = useCallback(function (compareFn?: (a: T, b: T) => number) {
    setState((state) => {
      const v = [...state]
      return v.sort(compareFn)
    })
  }, [])

  const clear = useCallback(function () {
    setState([])
  }, [])

  const every = useCallback(
    function (predicate: (value: T, index: number) => value is T) {
      return state.every(predicate)
    },
    [state],
  )

  const some = useCallback(
    function (predicate: (value: T, index: number) => value is T) {
      return state.some(predicate)
    },
    [state],
  )

  const find = useCallback(
    function (predicate: (value: T, index: number) => value is T) {
      return state.find(predicate)
    },
    [state],
  )

  const filter = useCallback(function (
    predicate: (value: T, index: number) => boolean,
  ) {
    setState((state) => {
      const v = [...state]
      return v.filter(predicate)
    })
  }, [])

  const includes = useCallback(
    function (searchElement: T, fromIndex?: number) {
      return state.includes(searchElement, fromIndex)
    },
    [state],
  )

  const reduce = useCallback(
    function (
      callbackfn: (
        previousValue: T,
        currentValue: T,
        currentIndex: number,
        array: T[],
      ) => T,
    ) {
      return state.reduce(callbackfn)
    },
    [state],
  )

  const reverse = useCallback(
    function () {
      return [...state].reverse()
    },
    [state],
  )

  const map = useCallback(
    function <U>(callbackfn: (value: T, index: number) => U) {
      return state.map(callbackfn)
    },
    [state],
  )

  return {
    size: state.length,
    includes,
    reverse,
    entries,
    prepend,
    append,
    insert,
    filter,
    remove,
    reduce,
    every,
    clear,
    some,
    swap,
    find,
    sort,
    set,
    has,
    get,
    map,
  }
}

export default useArray

use-heap.ts

import { useCallback, useEffect, useMemo, useState } from "react"

export class Node<T> {
  constructor(
    public priority: number,
    public item: T,
  ) {}
}

function parentIdx(index: number) {
  return (index - 1) / 2
}

function lchildIdx(index: number) {
  return 2 * index + 1
}

function rchildIdx(index: number) {
  return 2 * index + 2
}

function idxLevel(index: number) {
  return Math.floor(Math.log2(index + 1))
}

function swap<T>(state: Node<T>[], a: number, b: number) {
  const t = state[a]
  state[a] = state[b]
  state[b] = t
  return state
}

function moveUp<T>(state: Node<T>[], index: number) {
  while (index > 0 && state[parentIdx(index)] > state[index]) {
    swap(state, parentIdx(index), index)
    index = parentIdx(index)
  }
}

function moveDown<T>(state: Node<T>[], index: number) {
  let childIdx = lchildIdx(index)

  while (childIdx < state.length) {
    if (childIdx < state.length - 1 && state[childIdx] > state[childIdx + 1]) {
      childIdx++
    }

    if (state[index] > state[childIdx]) {
      swap(state, index, childIdx)
      index = childIdx
      childIdx = lchildIdx(index)
    } else {
      childIdx = state.length
    }
  }
}

function moveDownSequence<T>(state: Node<T>[], start: number, end: number) {
  for (let i = start; i >= end; i--) {
    moveDown(state, i)
  }
}

/**
 * Immutable Heap implementation
 * @param initialState
 * @returns
 */
function useHeap<T>(initialState: (T | Node<T>)[] = []) {
  const [state, setState] = useState<Node<T>[]>([])
  const first = state[0]

  const checkEmptiness = useCallback(
    function () {
      if (state.length === 0) {
        throw new RangeError("Heap is empty")
      }
    },
    [state.length],
  )

  const firstNonLeafIdx = useCallback(
    function () {
      return state.length / 2 - 1
    },
    [state.length],
  )

  const rebalance = useCallback(
    function (start: number = firstNonLeafIdx(), end: number = 0) {
      setState(function (state) {
        const v = [...state]
        moveDownSequence(v, start, end)
        return v
      })
    },
    [firstNonLeafIdx],
  )

  const push = useCallback(function (value: T | Node<T>, priority?: number) {
    setState((state) => {
      const v = [
        ...state,
        value instanceof Node
          ? value
          : new Node(priority || state.length, value),
      ]
      moveUp(v, v.length - 1)
      return v
    })
  }, [])

  const clear = useCallback(function () {
    setState([])
  }, [])

  const filter = useCallback(
    function (predicate: (node: Node<T>, index: number) => boolean) {
      setState((state) => {
        const v = [...state.filter(predicate)]
        moveDownSequence(v, firstNonLeafIdx(), 0)
        return v
      })
    },
    [firstNonLeafIdx],
  )

  const peek = useCallback(
    function () {
      return first
    },
    [first],
  )

  const pop = useCallback(
    function () {
      checkEmptiness()

      setState((state) => {
        const v = [state[-1], ...state.slice(1, -1)]
        moveDown(v, 0)
        return v
      })

      return first
    },
    [checkEmptiness, first],
  )

  const iterator = useCallback(
    function () {
      let current: number = -1

      function next() {
        current = current++

        return {
          value: {
            ...state[current],
            level: idxLevel(current),
            parent: state[parentIdx(current)],
            children:
              current <= firstNonLeafIdx()
                ? {
                    left: state[lchildIdx(current)],
                    right: state[rchildIdx(current)],
                  }
                : undefined,
          },
          done: current + 1 === state.length,
        }
      }

      return {
        next,
      }
    },
    [firstNonLeafIdx, state],
  )

  const find = useCallback(
    function (predicate: (node: Node<T>, index: number) => boolean) {
      return state.find(predicate)
    },
    [state],
  )

  const map = useCallback(
    function <U>(callbackfn: (value: Node<T>, index: number) => U) {
      return state.map(callbackfn)
    },
    [state],
  )

  useEffect(
    function () {
      if (initialState) {
        clear()
        for (const item of initialState) {
          push(item)
        }
      }
    },
    [clear, initialState, push],
  )

  return {
    size: state.length,
    rebalance,
    filter,
    clear,
    push,
    peek,
    find,
    pop,
    map,
    [Symbol.iterator]: iterator,
  }
}

export default useHeap

use-list.ts

import { useCallback, useState } from "react"

function useList<T>(items?: T[]) {
  const [list, setList] = useState<T[]>(items || [])

  const prepend = useCallback(function (item: T) {
    setList((list) => [item, ...list])
  }, [])

  const append = useCallback(function (item: T) {
    setList((list) => [...list, item])
  }, [])

  const remove = useCallback(function (item: T) {
    setList((list) => list.filter((i) => i !== item))
  }, [])

  const removeIndex = useCallback(function (index: number) {
    setList((list) => {
      if (index == 0) {
        return list.slice(1)
      }

      if (index == list.length - 1) {
        return list.slice(0, -1)
      }

      if (index > 0 && index < list.length) {
        return [...list.slice(0, index), ...list.slice(index + 1)]
      }

      return [...list]
    })
  }, [])

  return {
    prepend,
    append,
    removeIndex,
    remove,
    list,
  }
}

export default useList

use-queue.ts

import { useCallback, useState } from "react"

/**
 * Immutable Queue implementation
 * @param initialState
 * @returns
 */
function useQueue<T>(initialState: T[] = []) {
  const [state, setState] = useState<T[]>(initialState)

  const enqueue = useCallback(function (value: T) {
    setState((state) => [...state, value])
  }, [])

  const dequeue = useCallback(
    function () {
      setState((state) => state.slice(1))
      return state[0]
    },
    [state],
  )

  const clear = useCallback(function () {
    setState([])
  }, [])

  const peek = useCallback(
    function () {
      return state[0]
    },
    [state],
  )

  return {
    size: state.length,
    enqueue,
    dequeue,
    clear,
    peek,
  }
}

export default useQueue

use-stack.ts

import { useCallback, useState } from "react"

/**
 * Immutable Stack implementation
 * @param initialState
 * @returns
 */
function useStack<T>(initialState: T[] = []) {
  const [state, setState] = useState<T[]>(initialState)

  const push = useCallback(function (value: T) {
    setState((state) => [value, ...state])
  }, [])

  const clear = useCallback(function () {
    setState([])
  }, [])

  const pop = useCallback(
    function () {
      setState((state) => state.slice(1))
      return state[0]
    },
    [state],
  )

  const peek = useCallback(
    function () {
      return state[0]
    },
    [state],
  )

  return {
    size: state.length,
    clear,
    push,
    peek,
    pop,
  }
}

export default useStack