From: Ruby Quiz <james@...>
Date: 2007-12-14T22:13:43+09:00
Subject: [QUIZ] Programmer Ping-Pong (#150)

The three rules of Ruby Quiz:

1.  Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2.  Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3.  Enjoy!

Suggestion:  A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion.  Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

This is a non-traditional Ruby Quiz that changes the rules of the contest. 
Please read the entire message before playing along.  We will be back to normal
quizzes next time, for those that end up missing them.

	The Game

Eric Hodel described Programmer Ping-Pong in his RubyConf 2007 presentation.  I
wasn't familiar with the concept before that and it sounds like fun, so let's
all try it out together.

The rules are:

	* This quiz does not have a no-spoiler period so you may
	  submit at anytime after reading this message
	* I'll make the initial serve, starting the quiz off with
	  a single failing test
	* Anyone can return the ball at anytime by doing exactly
	  two things, in order:  make all tests pass including the
	  recently added failure and then add a new failing test
	  of your own

I want to see if we can build an entire library using just that process.

	The Task

Let's build a pure Ruby binary AVL tree.  An AVL tree is a self-balancing binary
tree data structure where insertion, deletion, and lookup all take O(log n) time
to execute.  This is handy to have for many search problems that must run
quickly.  It can also be used to build constructs like an OrderedHash.

You can read more about AVL trees on Wikipedia:

	http://en.wikipedia.org/wiki/Avl_tree

There's also a handy document describing their rotations in detail:

	http://fortheloot.com/public/AVLTreeTutorial.rtf

What features our AVL tree will support will be decided by you as you write
tests.  Here are some suggestions of things we might try though, just to get you
thinking:

	* Support for custom Ruby objects as nodes of the tree
	* The ability to customize the comparison code, perhaps with a block
	* A String output visualizer, possibly for the inspect() method
	* Any other great features you can think of to add

	The Details

We will have two files:  avl_tree.rb and test_avl_tree.rb.  Please pass both
files in each submission email you make for this quiz.  Let's not complicate
this with directory structures or zip files.

Please don't add any external dependencies, unless it's a standard library.  We
want everyone to be able to easily run this code and play along.

We are using Test::Unit instead of RSpec, or any other tool, for similar
reasons.

Please keep your tests short.  Under 10 lines is preferred, but don't go over
24.

Also try to test just one aspect of the implementation with each test.  I did
purposely say "aspect" and not "method."  I do test more than one method in the
serve and I can imagine other scenarios where it could be useful, like checking
support for a handful of the standard Enumerator methods.

You can refactor any code as needed provided you do not change its function and
all tests still pass after you do so.

Adds comments if you need to, but writing code that needs no comment would be
even better.

Let's use some simple spacing conventions to keep all of us on the same page. 
Indent two space and do not use tabs.  Break up long lines so they do not exceed
80 characters.

Finally, this quiz has the potential to be very chaotic.  Take pity on your
quizmaster who must track this process and on the rest of the community who may
be bothered by a highly active thread.  I suggest good email manners:

	* Use your client's "Reply" feature and make sure you are replying to
	  the message that contains the test you made pass
	* Trim any unneeded context from the reply, including the previous
	  version of the code since you will be including the current copy
	  of the whole thing
	* Kindness to your fellow programmers trumps any listed guidelines

	The Serve

The initial contents of avl_tree.rb are:

	#!/usr/bin/env ruby -wKU
	
	class AVLTree
	
	end

The test file, test_avl_tree.rb, begins as:

	#!/usr/bin/env ruby -wKU
	
	require "test/unit"
	
	require "avl_tree"
	
	class TestAVLTree < Test::Unit::TestCase
	  def setup
	    @tree = AVLTree.new
	  end
	  
	  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
	end