class Object

# File lib/sqreen/trie.rb, line 198
def bit_set?(addr, i)
  addr[max_num_bits - i - 1] == 1
end

# File lib/sqreen/trie.rb, line 191
def node_to_ip_addr(node)
  ret = IPAddr.new(node.prefix.address, node.prefix.family)
  ret.send(:mask!, node.prefix.bitlen)
  ret.singleton_class.send(:define_method, :data) { node.prefix.data }
  ret
end

# File lib/sqreen/trie.rb, line 172
def search_best(addr, family)
  nodes = search_common(addr, family)
  for i in (nodes.size - 1).downto(0)
    xcur = nodes[i]
    return node_to_ip_addr(xcur) if xcur.prefix.matches?(addr, family)
  end

  nil
end

# File lib/sqreen/trie.rb, line 202
def search_common(addr, family)
  raise 'family mismatch' unless family == self.family

  xstack = []

  xcur = head
  while !xcur.nil?
    unless xcur.empty?
      xstack << xcur
    end

    xcur = bit_set?(addr, xcur.bit) ? xcur.r : xcur.l
  end

  xstack
end

# File lib/sqreen/trie.rb, line 182
def search_matching(addr, family)
  nodes = search_common(addr, family)
  nodes.select { |xcur| xcur.prefix.matches?(addr, family) }
       .map { |xcur| node_to_ip_addr(xcur) }
       .reverse
end

# File lib/sqreen/trie.rb, line 144
def to_dot(header = true)
  res = ''
  res = "graph trie {\n" if header

  next_name = 'a'
  obj_label_map = Hash.new do |h, k|
    h[k] = next_name
    next_name = next_name.next
    h[k]
  end

  head.walk(max_num_bits, true) do |node|
    node_name = obj_label_map[node.object_id]

    if node.empty?
      label = "<glue at bit #{node.bit}>"
    else
      ip_addr = IPAddr.new(node.prefix.address, node.prefix.family)
      label = ip_addr.to_s + '/' + node.prefix.bitlen.to_s
    end
    res += "#{node_name} [label=\"#{label}\"]\n"
    res += "#{node_name} -- #{obj_label_map[node.l.object_id]} [label=\"l\"]\n" if node.l
    res += "#{node_name} -- #{obj_label_map[node.r.object_id]} [label=\"r\"]\n" if node.r
  end
  res += "}\n" if header
  res
end