Created
November 28, 2012 09:02
-
-
Save hao-ji-xing/4160017 to your computer and use it in GitHub Desktop.
TrieTree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(function (window, document, ns, undefined) { | |
var Node = function (data, parentNode) { | |
this._childCount = 0; | |
this.data = data; | |
this.parentNode = parentNode || null; | |
this.childNodes = {}; | |
}; | |
Node.prototype = { | |
constuctor : Node, | |
appendChild : function (data) { | |
var child; | |
if(!(child = this.getChild(data))){ | |
child = new Node(data, this); | |
this.childNodes[data] = child; | |
this._childCount ++; | |
} | |
return child; | |
}, | |
getChild : function (data) { | |
if(this.childNodes.hasOwnProperty(data)){ | |
return this.childNodes[data]; | |
} | |
return null; | |
}, | |
removeChild : function (data) { | |
var child; | |
if(child = this.getChild(data)){ | |
delete this.childNodes[data]; | |
this._childCount-- ; | |
} | |
return child; | |
}, | |
clearChild : function () { | |
this.childNodes = {}; | |
this._childCount = 0; | |
return this; | |
}, | |
hasChild : function (data) { | |
if(!this._childCount){ | |
return false; | |
} | |
if(arguments.length > 0){ | |
for (var i = arguments.length; i--; ){ | |
if(!this.getChild(arguments[i])){ | |
return false; | |
} | |
} | |
return true; | |
} | |
return true; | |
} | |
}; | |
var TrieTree = function (aData) { | |
var maxLength = 0; | |
var currentStr; | |
var currentChar; | |
var root = new Node(''); | |
var currentNode; | |
var childNode; | |
for (var i = 0, l = aData.length; i < l; i++) { | |
if(!(currentStr = aData[i])){ | |
continue; | |
} | |
currentNode = root; | |
for (var j = 0, li = currentStr.length; j < li; j++ ){ | |
currentChar = currentStr.charAt(j); | |
childNode = currentNode.getChild(currentChar); | |
if(!childNode){ | |
childNode = currentNode.appendChild(currentChar); | |
} | |
currentNode = childNode; | |
} | |
}; | |
this._root = root; | |
}; | |
TrieTree.prototype = { | |
constuctor : TrieTree, | |
exactMatch : function (str) { | |
var currentNode = this._root; | |
var childNode; | |
for (var i = 0, l = str.length; i < l; i++){ | |
childNode = currentNode.getChild(str.charAt(i)); | |
if(!childNode){ | |
return false; | |
} | |
currentNode = childNode; | |
} | |
if(currentNode.hasChild()){ | |
return false; | |
} | |
return true; | |
}, | |
mmFetch : function (str) { | |
var currentNode = this._root; | |
var childNode; | |
for (var i = 0, l = str.length; i < l; i++){ | |
childNode = currentNode.getChild(str.charAt(i)); | |
if(!childNode){ | |
return false; | |
} | |
currentNode = childNode; | |
} | |
return true; | |
} | |
}; | |
ns.TrieTree = TrieTree; | |
}(window, document, window)); | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment