new object $trie: $frob; var $root created_on = 800074237; var $root flags = ['methods, 'code, 'variables, 'core]; var $root help_node = $help_obj_trie; var $root inited = 1; var $root managed = [$trie]; var $root manager = $trie; public method ._add() { arg trie, key, @values; var n, word; // This still ain't working. Current problem: values get mingled if (trie[1]) { if (key == ((trie[1])[1])) return trie.replace(1, [key, @values]); word = (trie[1])[1]; if (word) { if (!(n = (word[1]) in (trie[2]))) trie = [@trie.replace(2, (trie[2]) + (word[1])), ._add([0, ""], word.subrange(2), @(trie[1]).subrange(2))]; else trie = trie.replace(n + 2, ._add(trie[n + 2], word.subrange(2), @(trie[1]).subrange(2), @values)); trie = trie.replace(1, 0); } } if (((!(trie[1])) && ((trie.length()) == 2)) || (!key)) return trie.replace(1, [key, @values]); if (!(n = (key[1]) in (trie[2]))) return [@trie.replace(2, (trie[2]) + (key[1])), ._add([0, ""], key.subrange(2), @values)]; return trie.replace(n + 2, ._add(trie[n + 2], key.subrange(2), @values)); }; public method ._del() { arg trie, key; var n, t1; if ((trie[1]) && (key == ((trie[1])[1]))) { trie = trie.replace(1, 0); if (((trie.length()) == 3) && (!((trie[3])[2]))) trie = [((trie[3])[1]).replace(1, (trie[2]) + (((trie[3])[1])[1])), ""]; return trie; } if (!key) throw(~ambig, "Trie: Can't delete more than one key."); if (!(n = (key[1]) in (trie[2]))) throw(~keynf, "Trie: No such key."); t1 = (> ._del(trie[n + 2], key.subrange(2)) <); if (t1 == [0, ""]) trie = (trie.delete(n + 2)).replace(2, ((trie[2]).subrange(1, n - 1)) + ((trie[2]).subrange(n + 1))); else trie = trie.replace(n + 2, t1); if (((trie.length()) == 3) && ((!(trie[1])) && (!((trie[3])[2])))) trie = [((trie[3])[1]).replace(1, (trie[2]) + (((trie[3])[1])[1])), ""]; return trie; }; public method .add() { arg @args; return (<$trie, (._add(@args))>); }; public method .del() { arg @args; return (<$trie, (._del(@args))>); }; public method .keys() { arg trie, @prefix; var n, i, l; [(prefix ?= "")] = prefix; l = (trie[1]) ? [prefix + ((trie[1])[1])] : []; if (trie[2]) { for i in [1 .. (trie[2]).length()] l += .keys(trie[2 + i], prefix + ((trie[2])[i])); refresh(); } return l; }; public method .match_begin() { arg trie, key; var n, t; if ((trie[1]) && ((key == ((trie[1])[1])) || (((trie.length()) == 2) && match_begin((trie[1])[1], key)))) return trie[1]; if (!key) throw(~ambig, "Trie: ambiguous match."); if (!(n = (key[1]) in (trie[2]))) throw(~keynf, "Trie: key not found."); (> (t = .match_begin(trie[n + 2], key.subrange(2))) <); t = t.replace(1, (key[1]) + (t[1])); return t; }; public method .match_exact() { arg trie, key; var n, t; if ((trie[1]) && (key == ((trie[1])[1]))) return trie[1]; if ((!key) || (!(n = (key[1]) in (trie[2])))) throw(~keynf, "Trie: key not found."); (> (t = .match_exact(trie[n + 2], key.subrange(2))) <); t = t.replace(1, (key[1]) + (t[1])); return t; }; public method .new() { arg @ignore; return (<this(), [0, ""]>); }; public method .to_dict() { arg trie, @prefix; var n, i, dict; // This function will only convert single-valued tries (such as were probably obtained from dictionaries [(prefix ?= "")] = prefix; dict = (trie[1]) ? #[[prefix + ((trie[1])[1]), (trie[1])[2]]] : #[]; if (trie[2]) { for i in [1 .. (trie[2]).length()] dict = dict.union(.to_dict(trie[2 + i], prefix + ((trie[2])[i]))); refresh(); } return dict; };