Re: [QUIZ] Programmer Ping-Pong (#150)

On 12/18/07, James Koppel <[e-mail]> wrote:
> I just realized that it might be a good idea to change my test to make each accept an options hash rather than ordered arguments, since my change and my new test will cause each to accept two keyword arguments. That is, rather than having calls like
>
> @tree.each(:postorder,:node){...}
>
> having something along the lines of
>
> @ree.each(:traversal=>:postorder,:val=>:node)
>
> ----- Original Message ----
> From: James Koppel <[e-mail]>
> To: ruby-talk ML <[e-mail]>
> Sent: Tuesday, December 18, 2007 8:23:35 PM
> Subject: Re: [QUIZ] Programmer Ping-Pong (#150)
>
>
> On 12/18/07, Adam Shelly wrote:
> >I added test_remove_multiple_nodes - there are definitely a few
> >mistakes in the current remove :)
>
> Seems the only mistake was that remove was expecting AVLTree#each to
>  return the node traversed, but it was instead returning the node's data.
>  I modified each to accept the name of a function to be passed to
>  itself, which defaults to data. I made an "identity" method called node, and
>  the passed it in when each is called within remove.
>
> For my test, each and to_a must now accept symbols denoting the type of
>  traversal to be performed, including inorder (the current traversal),
>  preorder, postorder, and level-by-level.
>

Ok, I did the each and the to_a.   I did not add the hash as suggested
- I don't think it's a good idea to provide tree users with nodes
directly.  And I refactored remove so that it didn't need each(:node)
anyway.  I expanded my previous test_remove_multiple_nodes test to
help ensure the refactoring was robust.
It was also bugging me that we were creating so many ExternalNodes
where we didn't care about the data, only the methods, so I moved all
the methods to the class, and removed all the calls to new (I just
realized I should have made new private)

My new test lets you add and subtract trees.

-Adam

==> avl_tree.rb <==
class AVLTree

  include Enumerable

  # Need something smarter than nil for external nodes
  # but we dont need all these separate instances - they are all identical
   class ExternalNode
     def self::include?(_)     false      end
     def self::height;         0          end
     def self::each(*args,&iter)          end
     def self::each_level(sequence,&iter)
       sequence.shift.each_level(sequence,&iter) unless sequence.empty?
     end
     def self::each_node(&iter)  end
     def self::to_a(_); []       end
     def self::pop;  nil         end
     def self::shift; nil        end
     def self::parent=(p); nil   end
     def self::to_s; '';         end
  end

  class Node
    attr_accessor :data, :parent
    attr_reader :left, :right

    def initialize obj, sortblock
      @parent = nil
      @data  = obj
      @left  = ExternalNode
      @right  = ExternalNode
      @height = 1
      @compare = sortblock
    end

    def left=(node)
      @height = nil
      @left = node
      node.parent = self
    end

    def right=(node)
      @height = nil
      @right = node
      node.parent = self
    end

    def each(traversal, &iter)
      case traversal
        when :inorder
          @left.each(traversal,&iter)
           iter[@data]
          @right.each(traversal,&iter)
        when :preorder
           iter[@data]
          @left.each(traversal,&iter)
          @right.each(traversal,&iter)
        when :postorder
          @left.each(traversal,&iter)
          @right.each(traversal,&iter)
           iter[@data]
      end
    end

    def each_level sequence,&iter
      iter[@data]
      sequence.push @left
      sequence.push @right
      sequence.shift.each_level(sequence,&iter) unless sequence.empty?
    end

    def each_node &iter
      @left.each_node(&iter)
      iter[self]
      @right.each_node(&iter)
    end

    def height
      @height || ( [ @left.height, @right.height ].max + 1)
    end

    def << node
      case @compare[node.data,@data]
      when -1
        if Node === @left
          @left << node
        else
          self.left = node
        end
      when 0
        return self            # no dups
      when +1
        if Node === @right
          @right << node
        else
          self.right = node
        end
      end
      rebalance if balance_factor.abs > 1
      @height = nil
    end

    def remove obj
      case @compare[obj,@data]
      when -1
        @left.remove(obj)
      when 0
        path = @left.pop || @right.shift || drop_self
        self.data = path.data
        while Node === (path = path.parent)
          break if path.balance_factor.abs == 1
          path.rebalance
        end
        self
      when +1
        @right.remove(obj)
      end
    end

    def drop_self
      parent.send :replace_child, self, ExternalNode#.new(parent)
      self
    end

    def pop
      @right.pop  || drop_self
    end

    def shift
      @left.shift || drop_self
    end

    def include? obj
      case obj <=> @data
      when -1 : @left.include?(obj)
      when  0 : true
      when +1 : @right.include?(obj)
      end
    end

    def to_a traversal
      left,root,right = @left.to_a(traversal), [@data], @right.to_a(traversal)
      case traversal
        when :inorder
          left+root+right
        when :preorder
         root+left+right
        when :postorder
         left+right+root
        when :by_level
         # pad out the left array so zip gets all the right elements too
         while (left.size < right.size) do left<<nil end
         [root]+left.zip(right).map{|set| set.flatten}
      end
    end

    def [](idx)
        if idx < (leftheight = @left.height)
          @left[idx]
        elsif (idx== leftheight)
          @data
        elsif (idx-=(leftheight+1)) < @right.height
          @right[idx]
        end
    end

    def to_s
      bf = case balance_factor <=> 0
            when -1 : '-' * -balance_factor
            when  0 : '.'
            when  1 : '+' * balance_factor
            end
      "[#{left} "+
        "(#{@data}{#{height}#{bf}}^#{parent.data})"+
        " #{right}]"
    end

    protected

    def balance_factor
      @right.height - @left.height
    end

    def rotate_left
      my_parent, from, to = @parent, self, @right
      temp = @right.left
      @right.left = self
      self.right = temp
      my_parent.send :replace_child, from, to
      to.parent = my_parent
    end

    def rotate_right
      my_parent, from, to = @parent, self, @left
      temp = @left.right
      @left.right = self
      self.left = temp
      my_parent.send :replace_child, from, to
      to.parent = my_parent
    end

    def rebalance
      if (bf = balance_factor) > 1 # right is too high
        if @right.balance_factor < 0
          # double rotate right-left
          # - first the right subtree
          @right.rotate_right
        end
        rotate_left            # single rotate left
      elsif bf < -1            # left must be too high
        if @left.balance_factor > 0
          # double rotate left-right
          # - first force left subtree
          @left.rotate_left
        end
        rotate_right            # single rotate right
      end
    end

    def replace_child(from, to)
      if from.eql? @left
        @left = to
      elsif from.eql? @right
        @right = to
      else
        raise(ArgumentError,
              "#{from} is not a branch of #{self}")
      end
    end

  end

  def initialize(root = ExternalNode, &block)
    @root = root
    if block
      raise(ArgumentError,
        "Block argument for #{self.class.name} must" +
        " take 2 arguments and act as sort function"
        ) unless block.arity == 2
    else
      block = proc{|a,b| a<=>b}
    end
    @compare = block
  end

  def empty?
    @root == ExternalNode
  end

  def include?(obj)
    @root.include?(obj)
  end

  def <<(obj)
    raise(ArgumentError,
          "Objects added to #{self.class.name} must" +
          " respond to <=> (#{obj.inspect})"
          ) unless obj.respond_to?(:<=>)

    if empty?
      @root = Node.new(obj, @compare)
      @root.parent = self
    else
      @root << Node.new(obj, @compare)
    end
    self
  end

   def remove(obj)
    @root.remove(obj).data
   end

  def height
    @root.height
  end

  def [](idx)
    @root[idx]
  end

  def to_a( traversal=:inorder )
    @root.to_a(traversal).flatten.compact
  end

  def each(traversal=:inorder,&iter)
    if traversal==:by_level
      @root.each_level([],&iter)
    else
      @root.each(traversal,&iter)
    end
  end

  def to_s
    empty? ? "[]" : @root.to_s
  end

  # Indicates that parent is root in to_s
  def data; '*'; end

  protected

  def replace_child(from, to)
    if @root.eql? from
      @root = to
    else
      raise(ArgumentError,
            "#{from} is not a branch of #{self}")
    end
  end

end
__END__


==> test_avl_tree.rb <==
#!/usr/bin/env ruby -wKU
require "test/unit"
require "avl_tree"

class TestAVLTree < Test::Unit::TestCase
  def setup
    @tree = AVLTree.new
  end

  ##################################################
  # Membership tests
  def test_tree_membership
    assert_equal(true,  @tree.empty?)
    assert_equal(false, @tree.include?(3))

    @tree << 3

    assert_equal(false, @tree.empty?)
    assert_equal(true,  @tree.include?(3))
  end

  def test_tree_should_allow_more_than_one_element
    @tree << 3
    @tree << 4

    assert(@tree.include?(4), "4 not in #{@tree}")
    assert(@tree.include?(3), "3 not in #{@tree}")
  end

  def test_tree_include_many
    0.upto(10) do |i|
      assert_equal(false, @tree.include?(i),
                    "Tree should not include #{i} yet.")
      @tree << i
      0.upto(i) do |j|
        assert_equal(true, @tree.include?(j),
                      "Tree should have 0..#{i},"+
                      " where's #{j}? ")
      end
    end
  end

  # This sits at the intersection of membership
  # and height tests.  We know one node has height 1,
  # and two nodes has height 2, so if we insert one
  # object twice and the height is 1, there must
  # only be one node in the tree.
  def test_tree_does_not_keep_duplicates
    @tree << 'a'
    @tree << 'a'
    assert_equal 1, @tree.height, "one node: #{@tree}"
  end

  ##################################################
  # Height tests
  def test_tree_height_of_one_or_two_nodes_is_N
    @tree << 5
    assert_equal 1, @tree.height, "one node: #{@tree}"
    @tree << 6
    assert_equal 2, @tree.height, "two nodes: #{@tree}"
  end

  def test_tree_height_of_three_nodes_is_two
    @tree << 5
    @tree << 6
    @tree << 7
    assert_equal 2, @tree.height, @tree.to_s
  end

  # RobB: The more precise limit given in [Knuth] is
  # used rather than that from [Wikipedia]
  def test_tree_growth_limit_is_1pt44_log_N
    (1..10).each do |i|
      @tree << i
      limit = ((1.4405 *
                Math::log(i+2.0)/Math::log(2.0)
                ) - 0.3277).ceil
      assert(@tree.height <= limit,
              "Tree of #{i} nodes is too tall by" +
              " #{@tree.height - limit}" +
              " #{@tree}")
    end
  end

  def test_balances_left
    4.downto(1) { |i| @tree << i }
    assert(@tree.height < 4,
            "expected tree height #{@tree.height} < 4")
  end

  def test_balances_right
    1.upto(4) { |i| @tree << i }
    assert(@tree.height < 4,
            "expected tree height #{@tree.height} < 4")
  end

  def test_non_sequential_insertion__part_1
    items = [ 1, 3, 2 ]
    items.each do |i|
      @tree << i
    end
    items.each do |i|
      assert_equal(true, @tree.include?(i),
                    "where is #{i}? ")
    end
  end

  def test_non_sequential_insertion__part_2
    items = [ 3, 1, 2 ]
    items.each do |i|
      @tree << i
    end
    items.each do |i|
      assert_equal(true, @tree.include?(i),
                    "where is #{i}? ")
    end
  end

  ##################################################
  # Access tests (getting data back out)

  # RobB: this tests too much at one time; I sorted ary.
  def test_tree_traverse
    ary = [ 3, 5, 17, 30, 42, 54, 1, 2 ].sort

    ary.each { |n| @tree << n }
    traversal = []
    @tree.each { |n| traversal << n }

    assert_equal(ary.size, traversal.size)

    ary.each do |n|
      assert_equal(true, traversal.include?(n),
                    "#{n} was not visited in tree.")
    end
  end

  def test_alternate_traversals
    items = [3,2,4,1,5]
    items.each {|el| @tree << el}

    preorder_result = [3,2,1,4,5]
    assert_equal(preorder_result,@tree.to_a(:preorder))
    @tree.each(:preorder) {|el| assert_equal(preorder_result.shift,el)}

    inorder_result = [1,2,3,4,5]
    assert_equal(inorder_result,@tree.to_a(:inorder))
    @tree.each(:inorder) {|el| assert_equal(inorder_result.shift,el)}

    postorder_result = [1,2,5,4,3]
    assert_equal(postorder_result,@tree.to_a(:postorder))
    @tree.each(:postorder) {|el|
    assert_equal(postorder_result.shift,el)}

    bylevel_result = [3,2,4,1,5]
    assert_equal(bylevel_result,@tree.to_a(:by_level))
    @tree.each(:by_level) {|el| assert_equal(bylevel_result.shift,el)}
  end


  def test_tree_find
    [1,2,3,4].each{|n| @tree<<n}
    assert_equal(1, @tree.find{|v|v>0} )
    assert_equal(2, @tree.find{|v|v%2==0} )
    assert_equal([2,4], @tree.find_all{|v|v%2==0} )
  end

  def test_sequential_access
    items = [ 50, 17, 72 ]
    items.each { |n| @tree << n }
    items.sort.each_with_index do |e,i|
      assert_equal(e, @tree[i],
                    "@tree[#{i}] should be like " +
                    "#{items.inspect}.sort[#{i}]")
    end
  end

  # [Knuth] p.473: "The problem of deletion can be solved
  # in O(log N) steps if we approach it correctly."
  def test_remove_node
    @tree << 314
    @tree.remove(314)
    assert_equal(false, @tree.include?(314),
                  '314 still in the tree')
    end


    def test_remove_multiple_nodes
      #expanded to test rebalancing better
      items=[35, 79, 68, 49, 5, 50, 24, 71,
                66, 81, 41, 1, 37, 20, 95, 62]
      items.each { |n| @tree << n }
      items.size.times do
        togo = items.shift
        @tree.remove(togo)
        assert_equal(false, @tree.include?(togo),
                  '#{togo} still in the tree')
        items.each{|i| assert_equal(true, @tree.include?(i),
                  "tree should still include #{i}")
        }
      end
      assert_equal true, @tree.empty?
      @tree<<2
      assert_equal true, @tree.include?(2)
    end

    def test_tree_merge
      [1,2,3,4].each{|v| @tree << v}
      tree2 = AVLTree.new
      [2,4,6,8].each{|v| tree2<<v}
      mergedTree = @tree+tree2
      assert_equal([1,2,3,4,6,8], mergedTree.to_a)
      assert_equal([1,3], (mergedTree-tree2).to_a)
    end




  ##################################################
  # Interface tests

  def test_custom_comparison_code
    rev_tree = AVLTree.new { |a, b| b <=> a }
    values  = [3, 2, 1]
    values.each { |v| rev_tree << v }
    rev_tree.each { |v| assert_equal(values.shift, v) }

    len_tree = AVLTree.new { |a, b| a.length <=> b.length }
    values  = %w[3 22 111]
    values.each { |v| len_tree << v }
    len_tree.each { |v| assert_equal(values.shift, v) }
  end

end
=begin
[Knuth] Knuth, Donald Ervin,
     The Art of Computer Programming, 2nd ed.
     Volume 3, Sorting and Searching,
     section 6.2.3 "Balanced Trees", pp. 458-478
[Wikipedia]
     AVL Tree, http://en.wikipedia.org/wiki/AVL_tree
=end
__END__