#
# 234木のノード
#
class TTFTreeNode                              # TwoThreeFour

  def initialize(key, value, child1=NilNode, child2=NilNode)
    warn "Inconsistent initialization" unless child1.nil_node? == child2.nil_node?
    @keys = [key]
    @values = [value]
    @children = [child1, child2]
  end

 protected                                     # 同クラスのオブジェクトに限定
  attr_reader :keys, :values, :children
 public
  
  def nil_node? ()  false  end

  def preorder (&block)
    @keys.each_index { |i| block.call @keys[i], @values[i] }
    @children.each { |ch| ch.preorder &block }
  end
  
  def inorder (&block)
    @keys.each_index do |i|
      @children[i].inorder &block
      block.call @keys[i], @values[i]
    end
    @children[-1].inorder &block
  end

  def postorder (&block)
    @keys.each_index { |i| block.call @keys[i], @values[i] }
    @children.each { |ch| ch.preorder &block }
  end

  def find (key)                               # 同一キーの場合、一つだけ探索
    @keys.each_with_index do |k, i|
      return @children[i].find(key) if key < k
      return @values[i] if k == key
    end
    @children[-1].find(key)                    ## [-1] は最後の意味
  end




  def split
    left = TTFTreeNode.new(@keys[0], @values[0], @children[0], @children[1])
    right= TTFTreeNode.new(@keys[2], @values[2], @children[2], @children[3])
    @keys = @keys[1,1]
    @values = @values[1,1]
    @children = [left, right]
    self
  end

  def insert (key, value) # 戻り値: split が必要なとき、その木、必要ないとき nil
    if @keys.find { |k| key == k }
      warn "Duplicate key (#{key}), not inserted."
      return nil
    end
    up = @keys.length==3 ? split : nil         # top-down 2-3-4-木の場合、前もって split
    where = @keys.length unless where = @keys.find_index { |k| key < k }
    if insert_node = @children[where].insert(key, value)
      @keys[where,0] = insert_node.keys[0]     ## array[a, b]= は a から b 個の要素を
      @values[where,0] = insert_node.values[0] ## 入れ替えて挿入
      @children[where,1] = insert_node.children[0,2]
    end
    up
  end
  
  def find_replacement (key)
    if @children[0].nil_node?
        @keys[0], key = key, @keys[0]
        [key, @values[0]]
    else
      @children[0].find_replacement(key)
    end
  end

  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  def delete (key)
    where = @keys.length unless where = @keys.find_index { |k| key <= k }
    if key==@keys[where]                       # key found
      if @children[0].nil?                     # leaf node
        @keys.delete_at(where)
        @values.delete_at(where)
        return @keys.length==0                 # signal underflow if no keys anymore
      else
        @keys[where], @values[where] = @children[where+1].find_replacement(key)
        where += 1
      end
    end

    if @children[where].delete(key)            # underflow signaled from child
      if where>0 and @children[where-1].keys.length>1  # transfer from left
        @children[where].children.shift @children[where-1].children.pop
        @children[where].keys = [keys[where-1]]
        @keys[where-1] = @children[where-1].keys.pop
        @children[where].values = [values[where-1]]
        @values[where-1] = @children[where-1].values.pop
      elsif where<=@keys.length and @children[where+1].keys.length>1  # transfer from right
        @children[where].children.push @children[where+1].children.unshift
        @children[where].keys = [keys[where]]
        @keys[where] = @children[where+1].keys.unshift
        @children[where].values = [values[where]]
        @values[where] = @children[where+1].values.unshift
      elsif where>0                            # fuse left
        @children[where-1].push @children[where].children[0]
        @children.delete_at where
        @keys[where-1].push(@keys.delete_at(where))
        @values[where-1].push(@values.delete_at(where))
        return true if @keys.length==0         # signal underflow
      else                                     # fuse right
        @children[where-1].push @children[where].children[0]
        @children.delete_at where
        @keys[where+1].unshift(@keys.delete_at(where))
        @values[where+1].unshift(@values.delete_at(where))
        return true if @keys.length==0         # signal underflow
      end
    end
    false
  end
  
  def inspect(ind=0)
    result = ''
    @children.each_with_index do |ch, i|
      child_inspect = ch.inspect ind+2
      result << child_inspect
      if @keys[i]
        result << (' '*ind + "key: #{@keys[i]}, value: #{@values[i]}\n")
      end
    end
    result
  end
end

class NilNodeClass                             # 子が無い印に使用
  def nil_node? ()  true  end
  def preorder(&block)  end                    # 何もしない
  def postorder(&block)  end
  def find ()  nil  end
  def insert (key, value)  TTFTreeNode.new(key, value)  end
  def delete (key)
    warn "Key #{key} not found"
    false                                      # no underflow
  end
  def inspect (ind=0)  ''  end                   # 表示のため: ' '*ind + "N\n"
end

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

#
# 234木
#
class TTFTree
  def initialize ()
    @top = NilNode
  end

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

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

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

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

  def inspect ()  @top.inspect  end
end