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.dup 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)) : ''
123 [md.host, md.user, md.nick].map { |c| cook_component(c) }
126 def add(user, *masks)
128 debug "adding user #{user} with mask #{m.fullform}"
129 @tree.add([user, m], *mask2keys(m))
133 def remove(user, mask)
134 debug "trying to remove user #{user} with mask #{mask}"
135 @tree.remove(*mask2keys(mask)) do |val|
136 val[0] == user and val[1].fullform == mask.fullform
140 def metric(iu, bu, mask)
143 ret = iu.fullform.length - mask.fullform.length
144 ret += 10 if bu.transient?
150 debug "find(#{iu.fullform})"
152 matches = @tree.find(iud.host, iud.user, iud.nick).uniq.map do |val|
154 m ? [val[0], m] : nil
155 end.compact.sort { |a, b| a[1] <=> a[1] }
156 debug "matches: " + (matches.map do |m|
157 "#{m[0].username}: [#{m[1]}]"
159 return matches.empty? ? nil : matches[0][0]