Skip to content

Commit ec1e7f1

Browse files
Bishop92Bishop92
committed
Added initial trie data structure
1 parent 2f6f509 commit ec1e7f1

2 files changed

Lines changed: 209 additions & 0 deletions

File tree

‎lib/Trie/Trie.js‎

Lines changed: 142 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,142 @@
1+
/**
2+
* Created by Stefano on 02/02/2015.
3+
*/
4+
5+
/**
6+
* The single node of the tree.
7+
* @param [string = null] The string of the node.
8+
* @param [item = null] The item to store in the node.
9+
* @constructor
10+
*/
11+
function TNode(string, item) {
12+
/**
13+
* The item stored.
14+
* @type {*|null}
15+
*/
16+
this.item = item || null;
17+
/**
18+
* The key of the node.
19+
* @type {string|null}
20+
*/
21+
this.string = string || null;
22+
/**
23+
* The parent node. It's null if there's no a parent node.
24+
* @type {TNode|null}
25+
*/
26+
this.parent = null;
27+
/**
28+
* The children of the node.
29+
* @type {Array<TNode>}
30+
*/
31+
this.childs = [];
32+
}
33+
34+
Trie.prototype = new Aggregate();
35+
Trie.prototype.constructor = Trie;
36+
37+
/**
38+
* Class for managing a trie
39+
* @constructor
40+
*/
41+
function Trie() {
42+
/**
43+
* The root of the tree.
44+
* @type {TNode}
45+
*/
46+
this.root = new TNode('');
47+
}
48+
49+
/**
50+
* @inheritDoc
51+
*/
52+
Trie.prototype.getIterator = function () {
53+
return new TrieIterator(this);
54+
};
55+
56+
/**
57+
* Insert the string in the tree creating the relative path to it.
58+
* If the string already exists then the values are updated
59+
* @param string {string} The string to store.
60+
* @param [item = null] The item to store.
61+
* @return {void}
62+
*/
63+
Trie.prototype.insert = function (string, item) {
64+
var node = this.root;
65+
66+
var i = 0;
67+
while (i < string.length && node.childs[string.charCodeAt(i)]) {
68+
node = node.childs[string.charCodeAt(i)];
69+
++i;
70+
}
71+
72+
while (i < string.length) {
73+
node.childs[string.charCodeAt(i)] = new TNode();
74+
node = node.childs[string.charCodeAt(i)];
75+
++i;
76+
}
77+
78+
node.string = string;
79+
node.item = item;
80+
};
81+
82+
/**
83+
* Suggest the possible conclusion for the string.
84+
* @param string {string} The start of the string.
85+
* @return {Array<string>} The array of possible string conclusion to fill.
86+
*/
87+
Trie.prototype.suggest = function (string) {
88+
var node = this.root;
89+
90+
for (var i = 0; i < string.length && node; ++i) {
91+
node = node.childs[string.charCodeAt(i)];
92+
}
93+
94+
var results = [];
95+
if (node) {
96+
this.stringsToArray(results, node);
97+
}
98+
return results;
99+
};
100+
101+
/**
102+
* Return all the string saved under the node in the array.
103+
* @param result {Array<string>} The array to fill.
104+
* @param [node {TNode|null} = null] The node from which start searching the strings.
105+
* @return {void}
106+
*/
107+
Trie.prototype.stringsToArray = function (result, node) {
108+
node = node || this.root;
109+
110+
111+
if (node.string) {
112+
result.push(node.string);
113+
}
114+
115+
for (var key in node.childs) {
116+
if (key !== 'length' && node.childs.hasOwnProperty(key)) {
117+
this.stringsToArray(result, node.childs[key]);
118+
}
119+
}
120+
};
121+
122+
/**
123+
* Get the minimum string stored in the tree.
124+
* @param [node = root] {Node} The node from which start the search.
125+
* @return {string} The string found.
126+
*/
127+
Trie.prototype.minimum = function (node) {
128+
node = node || this.root;
129+
return node.string;
130+
};
131+
132+
/**
133+
* Get the maximum string stored in the tree.
134+
* @param [node = root] {Node} The node from which start the search.
135+
* @return {string} The string found.
136+
*/
137+
Trie.prototype.maximum = function (node) {
138+
node = node || this.root;
139+
while (node && node.childs[node.childs.length - 1])
140+
node = node.childs[node.childs.length - 1];
141+
return node.string;
142+
};

‎lib/Trie/TrieIterator.js‎

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
/**
2+
* Created by Stefano on 06/04/2014.
3+
*/
4+
5+
TrieIterator.prototype = new Iterator();
6+
TrieIterator.prototype.constructor = TrieIterator;
7+
8+
/**
9+
* Class that implements the iterator for a trie.
10+
* @param aggregate {Trie} The aggregate to scan.
11+
* @constructor
12+
*/
13+
function TrieIterator(aggregate) {
14+
/**
15+
* The aggregate relates to this iterator.
16+
* @type {Trie}
17+
*/
18+
this.aggregate = aggregate;
19+
20+
/**
21+
* The pointer to the position.
22+
* @type {TNode|null}
23+
*/
24+
this.pointer = null;
25+
}
26+
27+
/**
28+
* @inheritDoc
29+
*/
30+
TrieIterator.prototype.first = function () {
31+
this.pointer = this.aggregate.minimum();
32+
};
33+
34+
/**
35+
* @inheritDoc
36+
*/
37+
TrieIterator.prototype.next = function () {
38+
this.pointer = this.aggregate.successor(this.pointer);
39+
};
40+
41+
/**
42+
* @inheritDoc
43+
*/
44+
TrieIterator.prototype.last = function () {
45+
this.pointer = this.aggregate.maximum();
46+
};
47+
48+
/**
49+
* @inheritDoc
50+
*/
51+
TrieIterator.prototype.previous = function () {
52+
this.pointer = this.aggregate.predecessor(this.pointer);
53+
};
54+
55+
/**
56+
* @inheritDoc
57+
*/
58+
TrieIterator.prototype.isDone = function () {
59+
return !this.pointer;
60+
};
61+
62+
/**
63+
* @inheritDoc
64+
*/
65+
TrieIterator.prototype.getItem = function () {
66+
return this.pointer.item;
67+
};

0 commit comments

Comments
 (0)