okay, so I am making a wordTree. just like any tree but with 28 branches " " , and "-", are included.
I have it set so the node as a prop called word, which is the string path to get to that node. and def, which is either null or a definition.
class wordNode{
constructor(wordString,def){
this.word = wordString;
this.def= def;
this.A=null;
this.B=null;
this.C=null;
this.D=null;
this.E=null;
this.F=null;
this.G=null;
this.H=null;
this.I=null;
this.J=null;
this.K=null;
this.L=null;
this.M=null;
this.N=null;
this.O=null;
this.P=null;
this.Q=null;
this.R=null;
this.S=null;
this.T=null;
this.U=null;
this.V=null;
this.W=null;
this.X=null;
this.Y=null;
this.Z=null;
this["-"]=null;
this[" "]=null;
}
}
is what the wordNode looks like... pretty simple...
the insertion however is failing in ways I don't understand. words are getting transformed.
original => unwanted change
EQUIVALUE = >ELUIVALUE
GREASINESS = >GRUASINESS
SPERMATOOEN = >SAIRMATOOEN
?
class WORDTREE{
constructor(dictionaryArray){
this.root = new wordNode("",null);
dictionaryArray.forEach(entry=>{
console.log(entry.word,"WORD");
this.insert(entry);
});
}
insert(wordObject){
const wordStringArray = wordObject.word.split("");
const targetLetter = wordStringArray[0];
this.__insert(targetLetter, wordStringArray, this.root, wordObject,"");
}
__insert(letter,array, ref, word){
const wordString =array.join("");
const nextArray = wordString.split("");
const nextLetter = array[0];
nextArray.shift();
if(ref[letter]==null){
console.log(ref.word+nextLetter, ref.word, nextLetter, "a = b+c here?");
ref[letter]=new wordNode(ref.word+nextLetter, (ref.word+nextLetter)==word.word?word.def:null);
}
const nextRef = ref[letter];
if(nextArray.length>0){
this.__insert(nextLetter,nextArray,nextRef,word);
}
else{
console.log(nextRef.word);
console.log("inserted at?");
console.log(nextRef);
}
}
}
the dictionaryArrayObject i'm generated this from is structured like
[{word:"",def:""},{...}...]
I think ref[letter] = new wordNode() is failing under a specific condition?
I wonder if you wouldn't be better off with a simpler data structure. We could have the same basic trie stucture including only the letters actually used, with a special value at leaf nodes to hold definitions. Something like this:
const dict = [
{word: 'foo', def: 'foo def'},
{word: 'fob', def: 'fob def'},
{word: 'foolish', def: 'foolish def'},
{word: 'bard', def: 'bard def'},
{word: 'barstool', def: 'barstool def'},
{word: 'bar', def: 'bar def'}
]
const tree = wordTree (dict)
//=>
// {
// b: {a: {r: {
// $: 'bar def',
// d: {$: 'bard def'},
// s: {t: {o: {o: {l: {$: 'barstool def'}}}}}
// }}},
// f: {o: {
// b: {$: 'fob def'},
// o: {
// $: 'foo def',
// l: {i: {s: {h: {$: 'foolish def'}}}
// }
// }}
// }
We could build this with fairly standard recursive techniques, using plain objects for our data, with keys of the relevant letters, and the key '$' representing the definition.
The following are pure functions to create a tree from a array of {word, def} elements (wordTree), to create a new tree by inserting a word into an existing tree (insertWord), to list all the words in the tree (listWords), or to fetch the definition for a word in the list, returning undefined if it's not included (getWord).
const wordTree = (words) =>
words .reduce (insertWord, {})
const insertWord = (tree, {def, word: [letter, ...letters]}) =>
letter
? {...tree, [letter]: insertWord (tree [letter] || {}, {def, word: letters})}
: {...tree, $: def}
const listWords = (tree, prefix = '', {$, ...children} = tree) =>
[
... ($ ? [prefix] : []),
... Object .keys (children) .sort () .flatMap (c => listWords (tree [c], prefix + c))
]
const getWord = (tree, [letter, ...letters]) =>
letter
? letter in tree && getWord (tree [letter], letters)
: '$' in tree
? tree ['$']
: undefined
const dict = [
{word: 'foo', def: 'foo def'},
{word: 'fob', def: 'fob def'},
{word: 'foolish', def: 'foolish def'},
{word: 'bard', def: 'bard def'},
{word: 'barstool', def: 'barstool def'},
{word: 'bar', def: 'bar def'}
]
const tree = wordTree (dict)
console .log (getWord (tree, 'barstool'))
console .log (listWords (tree))
console .log (tree).as-console-wrapper {max-height: 100% !important; top: 0}If we wanted a deleteWord function as well, a simple naive version might be enough, using a helper that clones an object removing a particular key:
const omitKey = (key, obj) =>
Object .fromEntries (Object .entries (obj) .filter (([k, v]) => k !== key))
const deleteWord = (tree, [letter, ...letters]) =>
letter
? letter in tree ? {...tree, [letter]: deleteWord (tree [letter], letters)} : tree
: omitKey ('$', tree)
This will leave behind some detritus. It's probably not harmful, but if for instance, we deleted 'foolish' from the list above, the resulting structure would include l: {i: {s: {h: {}}}, which is now unnecessary:
// ...
f: {o: {
b: {$: 'fob def'},
o: {
$: 'foo def',
l: {i: {s: {h: {}}}
}
}}
// ...
It's not harmful, as far as I can tell, but it feels less than clean. This, on the other hand, cleans everything up really nicely, but at a likely significant performance cost:
const deleteWord = (tree, targetWord) =>
wordTree (
listWords (tree)
.filter (word => word !== targetWord)
.map (word => ({word, def: getWord (tree, word)}))
)
I'm sure that with a little thought, we could write something more elegant.
In any case, this is just a suggested alternative. I find it quite a bit simpler than your constructor-based, pre-allocated version. But, as always, YMMV.
That delete was bothering me. I had to try to come up with something better. I like this version:
const deleteWord = (tree, [letter, ...letters], child) =>
letter
? (child = deleteWord (tree [letter], letters)) &&
Object .keys (child) .length == 0
? omitKey (letter, tree)
: {...tree, [letter]: child}
: omitKey ('$', tree)
I'm am perhaps a little to enamored of expression-only coding, and if that version is unclear because of the odd && (which could also be done with a comma expression) and rewritten child parameter, then we could choose this equivalent instead:
const deleteWord = (tree, [letter, ...letters]) => {
if (!letter) {
return omitKey ('$', tree)
}
const child = deleteWord (tree [letter], letters)
return Object .keys (child) .length == 0
? omitKey (letter, tree)
: {...tree, [letter]: child}
}
Either way, this has the right characteristics to me. It cleans up behind itself and doesn't blow away the entire tree in order to do its work.
And while I'm here, I'm happy enough with the wordTree factory function. It's elegant and reasonably performant, but I just want to note an alternative that is more in keeping with the rest of the code:
const wordTree = ([word, ...words], tree = {}) =>
word
? wordTree (words, insertWord (tree, word))
: tree
I wouldn't actually recommend this. Unless and until tail-call optimization becomes the norm, this will run quickly into recursion-depth problems. But it's nice to see it alongside the rest of the recursive code.