パトリシア

patricia.rb

#!/usr/bin/ruby

# -*- encoding: utf-8 -*-

#
# アルゴリズム辞典
# 島内剛一 野下浩平 伏見正則 有沢誠 浜田穂積
# 
# パトリシア pp. 624-625 


require 'pp'

class Node
  attr_accessor :key, :chckbit, :left, :right

  def initialize(key = 0, chckbit = 0, left = nil, right = nil)
    @key = key
    @chckbit = chckbit
    @left = left
    @right = right
  end
end


class Patricia
  def initialize()
    @head = Node.new()
    @head.key = 0
    @head.chckbit = 0
    @head.left = @head
    @head.right = @head
    @mask = [0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80]
  end


  # 探索
  def search(key)
    x = @head
    p = nil
    
    begin
      p = x
      x = (key[0] & @mask[x.chckbit] != 0) ? x.right : x.left
    end while (p.chckbit < x.chckbit)
    
    return x
  end

  # 挿入
  def insert(key)
    x = @head
    t = nil
    p = nil
    i = 0
    
    # キーの探索
    t = self.search(key)
    if key == t.key
      puts "#{key} exists"
      return
    end
    
    # 挿入するキーと衝突するキーとの間で最初に
    # 異なるビットの位置を求める
    i = 1
    while (key[0] & @mask[i]) == (t.key[0] & @mask[i])
      i += 1
    end
    
    # キーを置く位置( x )を求める
    begin
      p = x
      x = (key[0] & @mask[x.chckbit] != 0) ? x.right : x.left
    end while ((x.chckbit < i) && (p.chckbit < x.chckbit))
    
    # 挿入する節点を生成し
    # キーと検査ビットの位置を設定する
    t = Node.new()
    t.key = key
    t.chckbit = i
    
    # 子節と親節を設定する
    if key[0] & @mask[t.chckbit] != 0
      t.right = t
      t.left =x
    else
      t.left = t
      t.right = x
    end
    
    if key[0] & @mask[p.chckbit] != 0
      p.right = t
    else
      p.left = t
    end
    
  end

end  # end of Patricia

def main(argv)
  pat = Patricia.new()
  pat.insert('a')
  pat.insert('b')
  pat.insert('c')
  
  np = pat.search('a')
  if np != nil
    puts "key: #{np.key}"
  end

  np = pat.search('b')
  if np != nil
    puts "key: #{np.key}"
  end

  np = pat.search('c')
  if np != nil
    puts "key: #{np.key}"
  end

end

main(ARGV)