3 # helper backend class: generic nested radix tree
7 def initialize(pre = '', chi = Hash.new)
13 str = prefs.shift or raise 'empty prefs'
14 @pre = str if @chi.empty?
18 break if @pre[n] != str[n]
22 rest = str.slice(n .. -1)
25 prest = @pre.slice!(n .. -1)
27 @chi = {pc => Tree.new(prest, @chi)}
33 (@chi[c] ||= Tree.new).add(val, rest, *prefs)
36 (@chi[''] ||= Array.new).push val
38 (@chi[''] ||= Tree.new).add(val, *prefs)
47 def remove(*prefs, &block)
48 str = prefs.shift or raise 'empty prefs?'
49 return nil unless @pre.empty? or str.index(@pre) == 0
50 c = str.slice(@pre.size) || ''
51 return nil unless @chi.include? c
54 @chi[c].reject!(&block)
56 @chi[c].remove(*prefs, &block)
59 @chi[c].remove(str.slice((@pre.size + 1) .. -1), *prefs, &block)
61 @chi.delete(c) if @chi[c].empty?
66 @pre << k << @chi[k].pre
72 str = prefs.shift or raise 'empty prefs?'
73 self.find_helper(str, *prefs) + self.find_helper(str.reverse, *prefs)
77 def find_helper(*prefs)
78 str = prefs.shift or raise 'empty prefs?'
79 return [] unless @pre.empty? or str.index(@pre) == 0
80 # puts "#{self.inspect}: #{str} == #{@pre} pfx matched"
83 elsif Array === @chi['']
86 matches = @chi[''].find(*prefs)
89 c = str.slice(@pre.size)
92 if c and @chi.include?(c)
93 more = @chi[c].find_helper(str.slice((@pre.size + 1) .. -1), *prefs)
99 # api wrapper for netmasks
105 def cook_component(str)
106 s = (str && !str.empty?) ? str : '*'
107 l = s.index(/[\?\*]/)
109 l2 = s.size - s.rindex(/[\?\*]/) - 1
115 return (l > 0) ? s.slice(0 .. (l - 1)) : ''
122 [m.host, m.user, m.nick].map { |c| cook_component(c) }
125 def add(user, *masks)
127 debug "adding user #{user} with mask #{m}"
128 @tree.add([user, m], *mask2keys(m))
132 def remove(user, mask)
133 debug "trying to remove user #{user} with mask #{mask}"
134 @tree.remove(*mask2keys(mask)) do |val|
135 val[0] == user and val[1].fullform == mask.fullform
139 def metric(iu, bu, mask)
142 ret = iu.fullform.length - mask.fullform.length
143 ret += 10 if bu.transient?
149 debug "find(#{iu.fullform})"
150 matches = @tree.find(iu.host, iu.user, iu.nick).uniq.map do |val|
152 m ? [val[0], m] : nil
153 end.compact.sort { |a, b| a[1] <=> a[1] }
154 debug "matches: " + (matches.map do |m|
155 "#{m[0].username}: [#{m[1]}]"
157 return matches.empty? ? nil : matches[0][0]