class Irc::NetmaskDb::Tree
helper backend class: generic nested radix tree
Attributes
chi[R]
pre[R]
Public Class Methods
new(pre = '', chi = Hash.new)
click to toggle source
# File lib/rbot/maskdb.rb, line 7 def initialize(pre = '', chi = Hash.new) @pre = pre @chi = chi end
Public Instance Methods
add(val, *prefs)
click to toggle source
# File lib/rbot/maskdb.rb, line 12 def add(val, *prefs) str = prefs.shift or raise 'empty prefs' @pre = str.dup if @chi.empty? n = 0 @pre.size.times do break if @pre[n] != str[n] n += 1 end rest = str.slice(n .. -1) if n != @pre.size prest = @pre.slice!(n .. -1) pc = prest.slice! 0 @chi = {pc => Tree.new(prest, @chi)} end c = rest.slice!(0) if c (@chi[c] ||= Tree.new).add(val, rest, *prefs) else if prefs.empty? (@chi[''] ||= Array.new).push val else (@chi[''] ||= Tree.new).add(val, *prefs) end end end
empty?()
click to toggle source
# File lib/rbot/maskdb.rb, line 43 def empty? @chi.empty? end
find(*prefs)
click to toggle source
# File lib/rbot/maskdb.rb, line 71 def find(*prefs) str = prefs.shift or raise 'empty prefs?' self.find_helper(str, *prefs) + self.find_helper(str.reverse, *prefs) end
remove(*prefs, &block)
click to toggle source
# File lib/rbot/maskdb.rb, line 47 def remove(*prefs, &block) str = prefs.shift or raise 'empty prefs?' return nil unless @pre.empty? or str.index(@pre) == 0 c = str.slice(@pre.size) || '' return nil unless @chi.include? c if c == '' if prefs.empty? @chi[c].reject!(&block) else @chi[c].remove(*prefs, &block) end else @chi[c].remove(str.slice((@pre.size + 1) .. -1), *prefs, &block) end @chi.delete(c) if @chi[c].empty? if @chi.size == 1 k = @chi.keys.shift return nil if k == '' @pre << k << @chi[k].pre @chi = @chi[k].chi end end
Protected Instance Methods
find_helper(*prefs)
click to toggle source
# File lib/rbot/maskdb.rb, line 77 def find_helper(*prefs) str = prefs.shift or raise 'empty prefs?' return [] unless @pre.empty? or str.index(@pre) == 0 # puts "#{self.inspect}: #{str} == #{@pre} pfx matched" if !@chi.include? '' matches = [] elsif Array === @chi[''] matches = @chi[''] else matches = @chi[''].find(*prefs) end c = str.slice(@pre.size) more = [] if c and @chi.include?(c) more = @chi[c].find_helper(str.slice((@pre.size + 1) .. -1), *prefs) end return more + matches end