Popular data structures implemented in immutable React hooks.
- useArray
- useHeap
- useList
- useQueue
- useStack
- 2024-04-10: Initial implementation
- Implementing tests
- Moving to a real repository
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 |
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 |
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 |
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 |
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 |