trie.js
class Trie {
constructor() {
this.d = new Map()
}
insert(k,v) {
if( k.length === 0 ) {
this.data = v
return
}
const c = k[0]
if( ! this.d.has(c) ) {
this.d.set(c,new Trie())
}
return this.d.get(c).insert(k.slice(1),v)
}
remove(k) {
// blatant memory leak but
// our intention for this structure
// is that we populate it at page load
// and then no longer modify it.
// so this function shouldn't really
// even be here
const node = this.getNode(k)
if( node.data !== undefined ) {
node.data = undefined
}
}
has(k) {
const node = this.getNode(k)
if( node.data !== undefined ) return true
return false
}
get(k) {
const node = this.getNode(k)
return node?.data
}
getNode(k) {
// inefficient recursive approach
if( k.length === 0 ) return this
const c = k[0]
if( !this.d.has(c) ) return undefined
return this.d.get(c).getNode(k.slice(1))
}
}
Test runner
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
<script src="trie.js"></script>
<script>
window.addEventListener("load", _ => {
const body = document.body
const bob = document.createElement("div")
const terry = document.createElement("div")
bob.classList.add("bob")
terry.classList.add("terry")
body.append(terry)
body.append(bob)
const trie = new Trie()
trie.insert("hello",42)
trie.insert("heman",11)
trie.insert("he","boing")
console.log(undefined,trie.get("hell"))
console.log(42,trie.get("hello"))
console.log(undefined,trie.get("hellos"))
console.log(trie.getNode("hel"))
trie.insert(["C-x","C-d"],"wibble")
console.log("wibble",trie.get(["C-x","C-d"]))
// so the idea is that we start at the root
// and proceed until we match a sequence
// we need to have an 'immediate' flag
// meaning that the action is executed
// even if the sequence is a prefix
// -- a node is terminal iff this.d.size === 0
// we set a timeout of say 0.5s and accept
// this node if no further input comes in.
// we can use sequences of strings, or
// just strings, so basically keys are strings
// of ACMSx combos.
})
</script>
<style>
terry {
background-color: #ffa;
font-size: 1.4rem;
}
bob {
white-space: pre;
font-family: monospace;
font-size: 1.4rem;
background-color: #faf;
}
</style>
</head>
<body>
</body>
</html>