Parent

Class/Module Index [+]

Quicksearch

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

[Validate]

Generated with the Darkfish Rdoc Generator 2.