|
51
|
1 import { InputEvent, useCallback, useEffect, useRef, useState } from "react";
|
|
|
2 import ReactDOM from "react-dom/client";
|
|
|
3
|
|
|
4 // 1. input and listen to its key stroke fire findSuggestions
|
|
|
5 // 2. debounce findSuggestions
|
|
|
6 // 3. create structure for its to search
|
|
|
7
|
|
|
8 const DEBOUNCER_WAIT_TIME = 500;
|
|
|
9
|
|
|
10 const WORDS = [
|
|
|
11 "cat",
|
|
|
12 "call",
|
|
|
13 "cell",
|
|
|
14 "car",
|
|
|
15 "carpet",
|
|
|
16 "celcius"
|
|
|
17 ]
|
|
|
18
|
|
|
19 interface Tries {
|
|
|
20 children: Record<string, Tries>;
|
|
|
21 words: Set<string>;
|
|
|
22 }
|
|
|
23
|
|
|
24 function TypeAhead() {
|
|
|
25 const inputRef = useRef<HTMLInputElement | null>(null);
|
|
|
26 const debounceTimerId = useRef<NodeJS.Timeout>(null);
|
|
|
27 const tries = useRef<Tries>({ children: {}, words: new Set(WORDS) })
|
|
|
28 const [suggestions, setSuggestions] = useState<string[]>([]);
|
|
|
29
|
|
|
30 const performSearch = useCallback((value: string) => {
|
|
|
31 let curr = tries.current
|
|
|
32 const res: string[] = []
|
|
|
33 function dfs(node: Tries, pos: number, off: number = 0, matching: number = 0) {
|
|
|
34 if (off > 2) {
|
|
|
35 if (matching > Math.ceil(value.length/2)) {
|
|
|
36 node.words.forEach(word => res.push(word));
|
|
|
37 }
|
|
|
38 return;
|
|
|
39 }
|
|
|
40
|
|
|
41 if (pos == value.length) {
|
|
|
42 node.words.forEach(word => res.push(word));
|
|
|
43 return;
|
|
|
44 }
|
|
|
45
|
|
|
46 const letter = value[pos];
|
|
|
47 if (!node.children[letter]) {
|
|
|
48 Object.keys(node.children).forEach((key) => {
|
|
|
49 dfs(node.children[key], pos+1, off+1, matching)
|
|
|
50 });
|
|
|
51 } else {
|
|
|
52 dfs(node.children[letter], pos+1, off, matching + 1)
|
|
|
53 }
|
|
|
54
|
|
|
55 }
|
|
|
56 dfs(curr, 0);
|
|
|
57 setSuggestions([...res]);
|
|
|
58 }, [])
|
|
|
59
|
|
|
60 const findSuggestions = useCallback(() => {
|
|
|
61 if (debounceTimerId.current) {
|
|
|
62 clearTimeout(debounceTimerId.current);
|
|
|
63 }
|
|
|
64 debounceTimerId.current = setTimeout(() => performSearch(inputRef.current?.value || ""), DEBOUNCER_WAIT_TIME)
|
|
|
65 }, [])
|
|
|
66
|
|
|
67 useEffect(() => {
|
|
|
68 WORDS.forEach(word => {
|
|
|
69 let curr = tries.current;
|
|
|
70 for (let letter of word) {
|
|
|
71 letter = letter.toLowerCase();
|
|
|
72 if (!curr.children[letter]) {
|
|
|
73 curr.children[letter] = { children: {}, words: new Set([word]) };
|
|
|
74 } else {
|
|
|
75 curr.children[letter].words.add(word) ;
|
|
|
76 }
|
|
|
77 curr = curr.children[letter];
|
|
|
78 }
|
|
|
79 })
|
|
|
80 return () => {
|
|
|
81 if (debounceTimerId.current)
|
|
|
82 clearTimeout(debounceTimerId.current)
|
|
|
83 }
|
|
|
84 }, [])
|
|
|
85
|
|
|
86 return (
|
|
|
87 <>
|
|
|
88 <h1> Type ahead </h1>
|
|
|
89 <input ref={inputRef} onChange={findSuggestions}/>
|
|
|
90 {suggestions && (
|
|
|
91 <div style={{display: "flex", flexDirection: "column", gap: 8, border: "1px black solid"}}>
|
|
|
92 {suggestions.map(suggestion => {
|
|
|
93 return (
|
|
|
94 <div>{suggestion}</div>
|
|
|
95 )
|
|
|
96 })}
|
|
|
97 </div>
|
|
|
98 )}
|
|
|
99 </>
|
|
|
100 );
|
|
|
101 }
|
|
|
102
|
|
|
103 // Render
|
|
|
104 const root = ReactDOM.createRoot(document.getElementById("root")!);
|
|
|
105 root.render(<TypeAhead />);
|
