Here’s my attempt at Variations on a Binary Search Theme.

Unit Tests

Dave provided a set of unit tests for the binary search function. The tests below assume that the functions name is chop, and that it takes the target value and the array to search as arguments. Chop should return the index position in the array where the target value was found.

We put the tests into a separate module that will be included in the real test classes below. This is a useful technique when you write tests you wish to reuse in several test classes.

  require 'test/unit'

  module ChopTests
    def test_chop
      assert_equal(-1, chop(3, []))
      assert_equal(-1, chop(3, [1]))
      assert_equal(0,  chop(1, [1]))

      assert_equal(0,  chop(1, [1, 3, 5]))
      assert_equal(1,  chop(3, [1, 3, 5]))
      assert_equal(2,  chop(5, [1, 3, 5]))
      assert_equal(-1, chop(0, [1, 3, 5]))
      assert_equal(-1, chop(2, [1, 3, 5]))
      assert_equal(-1, chop(4, [1, 3, 5]))
      assert_equal(-1, chop(6, [1, 3, 5]))
      assert_equal(0,  chop(1, [1, 3, 5, 7]))
      assert_equal(1,  chop(3, [1, 3, 5, 7]))
      assert_equal(2,  chop(5, [1, 3, 5, 7]))
      assert_equal(3,  chop(7, [1, 3, 5, 7]))
      assert_equal(-1, chop(0, [1, 3, 5, 7]))
      assert_equal(-1, chop(2, [1, 3, 5, 7]))
      assert_equal(-1, chop(4, [1, 3, 5, 7]))
      assert_equal(-1, chop(6, [1, 3, 5, 7]))
      assert_equal(-1, chop(8, [1, 3, 5, 7]))
    end
  end

Variation #1: Iterative with Loop Invariants

I first read about using loop invariants on a binary search algorithm, so I thought it would be a good variation to start with.

If you have not used loop invariants in the past, they are a useful technique for understanding loops. You specify an condition that is true for every single iteration of the loop. This condition is called the loop invariant.

For the binary search, I used the following invariant.

Where lo and hi are indices into the array and result is the location in the array where our target value lies (i.e. the result of the binary search function). All this invariant states is that the final result index will be between position lo and hi. (Note that I’m assuming that the target value is in the array. We will deal with that assumption later).

The invariant must be true when we start the loop, but that is easy to handle. Just set lo to zero (the result index must be greater than or equal to zero), and set hi to one more than the largest index value (list.size works for this).

The second piece you need is a loop termination condition. Each time through the loop we will adjust hi and lo so that they move closer together (without violating the loop invariant). When the difference between the hi and lo values is 1, we can exit the loop.

Here is the termination condition.

When the loop exits, the condition TERM will be true. And the invariant INV will also be true (because it is true for every iteration). If TERM and INV are both true, then that implies that result must be equal to lo! Or in other words, when the loop exits, our search target value must be in the array indexed by lo (if it is in the array at all).

Using the above invariant and termination conditions, we can be certain that our loop will be correct (as long as they are faithfully implemented, which is not a minor problem).

Code

Here’s the code. Notice that INV will be true the first time we enter the loop. Inside the loop, we calculate the midpoint of the lo/hi indices, and compare the value at the midpoint to our target value.

If the value at the midpoint is larger than our target, then the range (lo..mid) still satisfies the invariant and we can adjust hi down to mid. Otherwise we can be sure that the range (mid..hi) satisfies the invariant, and we adjust lo up to the value of mid.

The "list[lo] == target" test at the end checks our assumption that the target value was in the array. If we found the value, we return the lo value. Otherwise we return -1.

  def chop_iterate(target, list)
    lo = 0
    hi = list.size
    while (hi-lo) > 1
      mid = (hi+lo) / 2
      if list[mid] > target
        hi = mid
      else
        lo = mid
      end
    end
    list[lo] == target ? lo : -1
  end

  class TestChopIterative < Test::Unit::TestCase
    alias chop chop_iterate
    include ChopTests
  end

Problems Encountered

So, did all that work figuring out a loop invariant help us? Perhaps. I did have one bug where a typo slipped into the calculation of the midpoint. I typed "(hi-lo)/2" by accident and had to scratch my head for a few minutes.

After fixing the typo, the rest of the algorithm worked without a hitch.

Where’s the Invariant?

An interesting thing happened to our invariant and termination conditions. The termination condition was inverted to "(hi-lo) > 1" instead of the "(hi-lo) <= 1" we originally used. That’s because the while statement expects a "stay-in-the-loop" test instead of a "get-out-of-the-loop-test".

But more importantly, our loop invariant has disappeared! It has no representation in the source code at all, except as an implicit constraint on the loop values. This is unfortunate because some important information is lost that should have been communicated to the reader.

The loop construct in the Eiffel language allows you to directly specify the loop invariants. The same loop in Eiffel would look something like this …

           from
               lo := list.lower
               hi := list.upper + 1
           invariant
               lower_limit: -- lo <= Result
               upper_limit: -- hi <  Result
           variant
               hi - lo
           until
               (hi-lo) <= 1
           loop
               mid := (hi+lo) // 2
               if list.at(mid) > target then
                   hi := mid
               else
                   lo := target
               end
           end

Although rather verbose, notice how every part of the loop has its proper place. The termination condition is expressed as an "until" condition, therefore it isn’t inverted.

The invariants are expressed directly. It turns out that our invariants cannot be checked at runtime (since we don’t know the actual value of Result until after the loop terminates), so we expressed them as comments. However, if they were executable, Eiffel would check them at runtime for us.

The "variant" section is interesting. The variant is an non-negative integer expression that must be smaller each time through the loop. Providing a valid variant proves that your loop eventually terminates.

Even the initialization of the loop variables (hi and lo) have their own section.

Next Time …

I was going to write up all 9 variations at once, but this is long enough now for a posting. I’ll hit the two recursive variations in the next installment.

For example, the other night I was testing some CGI code. To display a page of HTML, my object under test calls a print_template method on an object in the CGI framework I am using. It needs to pass in the template name and a hash table of template values to be substituted in the template. The test code might look something like this …

    def test_error_page
      web = CGI::Template.new        # Object from the CGI framework
      page = ErrorPage.new(web)
      page.error_message = "Oops!"
      page.render
      # test that "Oops!" was properly passed to the template object.
    end

The last line of the test wants to validate that the error message was properly passed to the web template. We could check this by parsing the HTML output from the CGI::Template, but that is a lot of work (not to mention error prone as well).

A much better way is to directly test that the parameters are passed to the CGI framework object correctly. We do that by replacing the CGI framework object with out own mock object.

Something like this (lines numbered for reference)…

  01:  def test_error_page
  02:    FlexMock.use { |web|
  03:      web.mock_handle(:print_template, 1) { |template_name, hash|
  04:        assert_equal 'Oops!', hash['error_message']
  05:      }
  06:      page = ErrorPage.new(web)
  07:      page.error_message = "Oops!"
  08:      page.render
  09:    }
  10:  end

In line 2, the FlexMock.use method creates a mock object and passes it to the given block. At the end of the block (line 9), FlexMock.use will verify that all expected calls were actually made to the mock object.

In line 3, we inform the mock web object what methods calls it should expect by passing the name of the expected method to mock_handle. Since we are only interested in the print_template call, that is all we define. The number 1 in the calling sequence tells our mock object to expect exactly one call.

The mock_handle method also gets a block (still on line 3). This block is executed whenever print_template is called in our test. The block object parameters (template_name and hash in this case) should match the parameters of the print_template method.

It is the hash argument to print_template that hold our interest. We need to make sure that the hash table passed to the template engine correctly defines our error message as "Oops!". We verify this in line 4.

The rest of the test method just creates an ErrorPage and feeds it the mock object primed for testing. In line 8 we invoke the render method that should eventually format our page and call the print_template method of the mock object.

By using the mock object, we avoid a lot of setup details that would be required for a real CGI framework object (which in turn might require more objects with more setup). Using a mock object allows us to concentrate on the details of what is being tested without constructing an elaborate framework of live objects merely to support a quick test.

On the other hand, be careful. It is easy to get carried away with mocking to the point where it is more work to create a web of mock objects than it is to just create a network of live objects in the first place. When you start creating mock object that return other mock objects, you should take one step back and reassess your code base.

There are other Mock objects implementations. The original ruby-mock object is a bit rigid for my tastes. You need to know exactly what methods are called and in what order, and that over constrains the solution to your test. The test-unit-mock object is much more flexible than ruby-mock (or even FlexMock), it is just complicated enough that I forget how to use it between the times I need it. FlexMock seems to fit in that middle of the position where, for me, it does what I need without extra stuff.

You can find FlexMock at onestepback.org/software/flexmock.

New features include …

Updated Software Packages …

Rake (onestepback.org/software/rake)

A Make-like scripting language written entirely in Ruby. I have been using Rake for all my recent projects.

Source2Html (onestepback.org/software/source2html)

Convert source files to nicely formatted HTML pages. Source2html will automatically create links between files in a project. Works with Ruby, Python, Java, Eiffel and a number of other languages.

Updated Articles …

Same Fringe, Iterating Parallel Lists in Ruby (onestepback.org/articles/same_fringe)

A short article on parallel lists and iterating schemes in Ruby. We touch on generators and continuations.

I can identify with that. I’ve downloaded most of my brain into Emacs macros so that I find it difficult to survive without a fully functional Emacs available. However, when it comes to editting Java code, it is tough to beat Eclipse (or IntelliJ/IDEA, or any number of similar IDEs). Although I still like Emacs for pure code/text entry, Eclipse really shines when you need to do browsing, refactoring or even CVS integration.

This is one gotcha, however. Whenever I save a file in Emacs, I hit

• Control-A (goto the beginning of the line), then
• Control-X Control-S (save a file).

Over the years I have learned that frequent saving is a good thing, and I perform that sequence of keystrokes without even thinking.

However, that same key combination in Eclipse performs …

• Control-A (select all)
• Control-X (cut selection)
• Control-S (save file)

Oops! Thankfully, Control-Z (undo) forgives all sins.

Using the standard shapes example, I posted some code in C showing how to do runtime polymorphism using pointers to functions. I also include C++ and Java examples. Then everybody got in the act and we ended up with this (onestepback.org/articles/poly).

Some of the source files are missing, and I’ll replace them when I can. In the meantime, enjoy.

Feel free to provide feedback at jweirich@one.net.

Most content on this site is covered by a Creative Content License. Materials not covered by this license will be explicitly noted (for example, most of the code is offered under one of the Open Source/Free Software licenses).

This Creative Commons license essentially says that you have permission to use the material covered by the license for non-commericial purposes as long as you attribute it to the author (that would be me). Click on the Creative Commons graphic for all of the details.

Of course, this only applies to the material written by me (Jim Weirich). Material written by others will be covered by their own copyrights.

Check out the Creative Commons web site. They have a number of different licences available, and they do a good job of explaining them. There may be a license there that suites your needs.

I can answer that question because I just did it for the UML system you see here.

Here’s what I loaded …

• I have download most of my brain into Emacs macros, so working without emacs for any length of time is not acceptable. Fortunately, a quick ‘apt-get install emacs21’ and a working emacs system becomes available.
• After loading emacs, I grabbed the .emacs file (and all of its supporting libraries) from my desktop system.
• My overall plan for this UML system is to use it as my web host. That means that apache is required. Grabbing apache with apt-get was simple.
• I plan to base my web site around a Ruby based blogging package called Rublog. That means Ruby will be needed. Since I tend to track the latest version of Ruby a little more closely than Debian does, I normally install Ruby by hand from source. Fortunately, installing Ruby is trivial. I just downloaded the source (from www.ruby-lang.org), and did the standard configure/make/make install commands.
• Next I needed the Rublog software. I had been playing with Rublog on my laptop, so I had the configuration pretty well decided by that point. I just copied the laptop setup to the UML system.
• Finally, Rublog needs RDoc to render any RDoc postings. A quick visit to the Ruby Application Archive to grab RDoc and I was good to go.

And that completed my first phase of setups. I had to do a little reading on setting up iptables and a bit of configuration with apache. The result is what you see here.

So, what packages do you need to work with.