-
Notifications
You must be signed in to change notification settings - Fork 275
Trie
Pawel Decowski edited this page Oct 9, 2016
·
5 revisions
https://en.wikipedia.org/wiki/Trie
Clarity of prefix declarations, ease of updates.
Take Discover regex:
/^(6011|622(12[6-9]|1[3-9][0-9]|[2-8][0-9]{2}|9[0-1][0-9]|92[0-5]|64[4-9])|65)/
Using a trie and a helper Range
class, it can be represented more clearly:
6011, 622126-622925, 644-649, 65
Tests have shown that the initial implementation of trie is about as fast as a regex.
class Trie
constructor: ->
@trie = {}
push: (value) ->
value = value.toString()
obj = @trie
for char, i in value.split('')
if not obj[char]?
if i == (value.length - 1)
obj[char] = null
else
obj[char] = {}
obj = obj[char]
find: (value) ->
value = value.toString()
obj = @trie
for char, i in value.split('')
if obj.hasOwnProperty char
if obj[char] == null
return true
else
return false
obj = obj[char]
class Range
constructor: (@trie) ->
if @trie.constructor != Trie
throw 'Range constructor requires a Trie parameter'
@rangeWithString: (ranges) ->
if typeof ranges != 'string'
throw 'rangeWithString requires a string parameter'
ranges = ranges.replace(/ /g, '')
ranges = ranges.split ','
trie = new Trie
for range in ranges
if r = range.match /^(\d+)-(\d+)$/
for n in [r[1]..r[2]]
trie.push +n
else if range.match /^\d+$/
trie.push +range
else
throw "Invalid range '#{r}'"
new Range trie
match: (number) ->
return @trie.find(number)