# encoding: UTF-8
#
# 二分木のノード
#
class BinaryTreeNode
  attr_reader :key, :value

  def initialize(key, value)
    @key = key
    @value = value
    @left = NilNode
    @right = NilNode
  end

  protected                                    ## 使用は同クラスのオブジェクトに限定
  attr_accessor :left, :right

  def find_replacement
    if @left.left.nil_node?                    # ノードを一個先読み
      keep = @left
      @left = @left.right
      keep
    else
      @left.find_replacement
    end
  end

  public

  def nil_node? ()  false  end

  def preorder (&block)
    block.call self
    @left.preorder &block
    @right.preorder &block
  end

  def inorder (&block)
    @left.inorder &block
    block.call self
    @right.inorder &block
  end

  def postorder (&block)
    @left.postorder &block
    @right.postorder &block
    block.call self
  end

  
  
  
  
  
  
  
  def find (key)                               # 同一キーの場合、一つだけ探索
    if key == @key                             ## if-else 文も値がある
      self                                     ## このような値も戻り値に使われる
    elsif key < @key
      @left.find(key)
    else
      @right.find(key)
    end
  end

  def insert (new_node)
    if new_node.key < @key
      @left = @left.insert(new_node)           # 親ノードをメソッドに渡す変わりに代入
    elsif new_node.key >= @key                 # 重複 key のノードは右部分木に追加
      @right = @right.insert(new_node)         # それによって、sort は安定
    end
    self
  end

  def delete (key)
    if key < @key
      @left  = @left.delete(key);   self       ## 改行したくない場合に ; を使用
    elsif key > @key
      @right = @right.delete(key);  self
    elsif @left.nil_node?                      # 葉または右の部分木だけ存在
      @right
    elsif @right.nil_node?                     # 左の部分木だけ存在
      @left
    elsif @right.left.nil_node?                # ノードを一個先読み
      @right.left = @left;  @right
    else
      replacement = @right.find_replacement    # 右部分木で置き換えに使えるノードを探す
      replacement.left = @left
      replacement.right = @right
      replacement
    end
  end

  def inspect(ind=0)
    "#{@right.inspect(ind+2)}" + ' '*ind + "#{key}\n#{@left.inspect(ind+2)}"
  end
  
  def check_local_consistency
    (@left.nil_node?  or
        (@key > @left.key   and @left.check_local_consistency)) and
    (@right.nil_node? or
        (@key <= @right.key and @right.check_local_consistency))
  end

  def size ()  @left.size + @right.size + 1  end
  def max_depth ()  [@left.max_depth, @right.max_depth].max + 1  end
  def total_depth ()  @left.total_depth + @right.total_depth + size  end
end



class NilNodeClass                             # 子が無い印に使用
  def nil_node? ()  true  end
  def insert (other_node)  other_node  end
  def delete (key)
    warn "Key #{key} not found"
    self
  end
  def preorder(&block)  end                    # 何もしない
  def inorder(&block)  end
  def postorder(&block)  end
  def find ()  nil  end
  def inspect (ind=0)  end                     # 表示のため: ' '*ind + "N\n"
  def check_local_consistency ()  true  end
  def size ()  0  end
  def max_depth ()  0  end
  def total_depth ()  0  end
end

NilNode = NilNodeClass.new                     # NilNode は一つで十分


#
# 二分木
#
class BinaryTree
  def initialize ()
    @top = NilNode
  end

  def preorder(&block)   @top.preorder(&block)   end
  def inorder(&block)    @top.inorder(&block)    end
  def postorder(&block)  @top.postorder(&block)  end

  def insert(key, value)
    new = BinaryTreeNode.new(key, value)
    @top = @top.insert(new)
  end

  def delete(key)
    @top = @top.delete(key)
  end

  def find(key)  @top.find(key).value  end

  def sort ()
    result = []
    @top.inorder { |node| result << node.key } # result に通りかけ順に key を追加
    result
  end

  def inspect ()  @top.inspect  end

  
  
  
  
  def check_loops ()                           # バグ防止のための無限ループ検出
    nodes = []
    @top.inorder do |node|
      if nodes.include? node
        raise
        return                                 # 無限ループを打ち切る
      else
        nodes << node
      end
    end
  end
  
  def check_consistency ()
    problem = ""
    check_loops rescue problem = "Infinite loop in tree structure"
    unless @top.check_local_consistency        ## unless の意味は "if not"
      problem = "Tree structure not locally consistent"
    end
    warn problem unless problem != ""
    return problem != ""
  end
  
  # 統計用
  def size ()  @top.size  end
  def max_depth ()  @top.max_depth  end
  def average_depth ()  @top.total_depth.to_f / @top.size  end 
end


# テスト用
# RANGE_TOP = 100

class BinaryTree
  def test (n=1)
    n.times do
	  r = rand RANGE_TOP
      if rand(2) == 1
        puts "\ninserting #{r}"
        insert r, r
      else
        puts "\ndeleting #{r}"
        delete r
      end                                          ## rescue: 例外発生の場合の救済
      check_loops rescue warn "Infinite loop in tree structure"
      check_consistency
    end
    puts inspect
	puts "Size: #{size}"
	puts "Max depth: #{max_depth}"
	puts "Average depth: #{average_depth}"
  end
end