Recently, I have been thinking about a particular data structure that I’ve never seen before. For those who do not know, I am an avid C/C++ programmer and have recently discovered Ruby and Rails. Thus, I am familiar with the STL that is so closely related to C++. One of my favorite containers is the set. Sets operate just like you’d expect of a mathematical set (thus the name). It contains a set of values.

For example (an assume I have a magical print function to inspect the sets on the terminal):

set my_set;

my_set.insert( 7 );

my_set.insert( 5 );

magic_set_printer( my_set );

{5,7}

As you can see, they’re good for keeping small sets of things.

So What is a Theoretical Set?

The problem with sets as they appear in C++: they require storage space for every item stored in them. This isn’t a big problem if you have only a few elements in a set, but what’s the fun in that? Suppose you have the same set above in Figure 1 but decide to add the value 6. Under a normal set, your set will contain the values 5, 6, and 7. Extending the argument, if your set contains a contiguous, uinterrupted set from, say, 5 to 1,000, your set will contain, yes, you guessed it: 995 elements. Clearly, there’s room for some improvement if you expect contiguous values.

Enter the theoretical set.

It is just like a normal STL set, however, it will take shortcuts on memory by combining values into ranges. For example, the set: {5,6,7} becomes: {5..7}. The original set will use 3 values, the theoretical set will use 2. As you can see, if you have a large set from 5..1000, it is better to use the theoretical set as search times and memory will be saved. While I’m not sure, exactly, at what point it becomes more economical to use theoretical sets (and again, it depends on use), if you expect to have contiguous ranges in your sets, I suspect much improved performance.

Unfortunately, operating on ranges is harder than operating on single values. Thus, there is a relatively significant performance penalty when calculating intersections, differences, etc. Though, in the long-run, the penalty is not noticeable.

A Ruby Theoretical Set

I had originally envisioned such a construct to be written for the benefit of C++ coders. However, due to the number constraints, I was dissuaded. Ideally, one should be able to use a theoretical set on any type of number. While templates offer some solution, I also wanted more: complex types.

Should one not be able to arrange a set of contiguous dates? Maybe not contiguous to the second, but perhaps weekends? A set over a range of objects. Makes you tingle a bit, doesn’t it?

The nice thing about loosely typed languages, is that you can pass just about anything into them without worrying much about some of the details. So that solves the typing problems with C++ and makes for a good set!

I have not actually implemented a straight-up Ruby Theoretical Set. I have created on that uses ActiveRecord, but that’s a post for another time.

I hurriedly wrote an article this morning about my adaptation of fixtures I call sub-fixtures. While it seemed like a good idea in theory, it it beastly to implement in practice. It requires writing new fixtures for every unique test (if used correctly). When used incorrectly, the test names don’t describe the data configuration being tested against.

I sat down and thought about it a little longer. What I really need is a scenario. A database state poised for a particular test. Needless to say: such a scenario is not limited to a single table. That way, the scenario is describing the database state being tested against and can therefore be used logically in other tests as well.

Only one minor change is required. In the test directory, add the following code to the body of the Test::Unit::TestCase class in test_helper.rb:

	def load_scenario( scenario )
		directory = File.dirname(__FILE__)+'/fixtures/scenarios/'+scenario+'/'
		files = Dir.entries( directory )
		files.delete( '.' ); files.delete( '..' )
		exp = /[^\.].*\.(yml|csv)$/
		models = files.select{|f| f[exp] }
		models = models.collect{|m| m.slice(0,m.length-4).to_sym}
		Fixtures.create_fixtures( directory, models )
	end

Again, it requires a special directory structure (maybe I’ll write a scenario generator later). in the test/fixtures I added a new directory: scenarios. Within that directory are other directories containing the scenarios fixture setups. For example, if I want to create a scenario where my list of weekly cookie recipes is missing a cookie and I want to test my code to see if it finds the correct missing cookie, I simply create the following directory:

test/fixtures/scenarios/missing_cookie

And in that directory, I create the following fixture files:

• cookies.yml
• users.yml
• user_cookies.yml

Note: it works for .csv files as well. Simply create the fixtures like you normally would do.

Now, in your unit test code, add the following line to the beginning of your test case method:

load_scenario( 'missing_cookie' )

Now, when your test runs, it will create the scenario in the database that you specify. It will automatically load all the fixture files in the directory.

Problems

Again, if you use normal fixtures, they will be loaded and unloaded (will make testing a little slower).

I’ve found that when testing model classes, it’s important to have a database that is setup with records such that something fails or is configured to produces results in a particular way. With the current rails Fixture framework, this is impossible. Let me explain what I’ve been trying to do to give you a better idea of what is lacking in Rails:

Example Problem Description Finding Something That’s “Missing”

Suppose you have a database with a table called “cookies” and another table “users” and another table called “user_cookies.” As you can see, you have a set of users and types of cookies. Maybe the cookies are chocolate or mint, etc. However, these are cookies of the month. Each month, a new cookie is released. To keep track of which month the cookie is for, we include a year and month field in the cookie table. Now, if we have users that want to track which cookies they’ve tried over the course of the years, we need to either keep a list of all the cookies they’ve eaten, or search for holes in the cookie order.

Even if we had a list, say we had a weekly and monthly cookie. If we wanted to know which monthly cookies we’re missing, the list will be of no use as well, as the list cannot differentiate between monthly or weekly. We’re forced to look for holes. Luckily, such a request is rare in our system, so a brute force search will be small (there are ways of making it faster, but that’s beyond the scope of this article).

Rails Testing Framework “Deficiency”

Don’t get me wrong, the testing framework for Rails is well done, easy to use, and mostly comprehensive. However, the Fixture support is a bit lacking. If you want to have multiple types of tests that act on the database records as a whole, you need custom fixtures. For the above problem, we need a fixture to test cookie lookups, but we also need a test to detect missing cookies.

So we need multiple fixtures we can load with different tests. Well, that’s not really possible with the standard testing framework. The class method “fixtures” for Test::Unit::TestCase (the testing base class) will only load up the standard fixtures. Bummer. I want to create subdirectories in the fixtures directory that are named after the model being tested. Within those directories, there will be more directories that name the test in progress. Within THAT directory will be the .yml files for custom database setups.

So the directory structure is of this form:

|-+BASE RAILS APPLICATION
| |-+ test
| | |-+ fixtures
| | | |-+ MODEL_NAMEs
| | | | |-+ test_find_missing_cookies
| | | | | |- users.yml
| | | | | |- cookies.yml
| | | | | |- user_cookies.yml
| | | | |-+ test_find_favorite_cookie
| | | | | |- user_cookies.yml
 ...

Not only can you deploy custom fixtures for models and more than just one, you can also specify tables to populate other than the model with which you’re working. This provides as much flexibility as I can fathom that I need.

But, alas, you need a way to load these fixtures up. Admittedly, my method is a bit messy and slow if you use the traditional Fixtures. You need to modify the test_helper.rb file. Add this to the Test::Unit::TestCase class:

	@@model_name = nil
	def self.fixture_model( m )
		@@model_name = m
	end
	
	protected
	def load_subfixtures( test_method, pfixture_table_names = [], pfixture_class_names = [] )
		raise StandardError.new( 'load_subfixtures requires that you specify the model name in the class by calling the class method: fixture_model' ) if @@model_name.nil?
		fixture_path = File.dirname(__FILE__) + '/fixtures/'+@@model_name.to_s+'/'+test_method+'/'
		return super unless File.exists?( fixture_path )

		oldpath = fixture_path
		oldtables = fixture_table_names
		oldclasses = fixture_class_names
		@@fixture_path = fixture_path
		@@fixture_table_names = pfixture_table_names
		if @@fixture_table_names.empty?
			@@fixture_table_names = fixture_table_names
		else
			@@fixture_table_names.push @@model_name
		end
		@@fixture_class_names = pfixture_class_names
		@@fixture_class_names = fixture_class_names if @@fixture_class_names.empty?
		oldret = load_fixtures
		@@fixture_path = oldpath
		@@fixture_table_names = oldtables
		@@fixture_class_names = oldclasses

		return oldret
	end

As you can see, it does not override the fixture initializer for the unit tests. It merely calls it again. Here’s how you use it:

require File.dirname(__FILE__) + '/../test_helper'

class UserCookieTest < Test::Unit::TestCase
  fixture_model :user_cookies

  # Replace this with your real tests.
  def test_find_missing_cookies
		load_subfixtures( 'test_find_missing_cookies', [:users,:cookies] )
		assert_equal 2, UserCookie.count
  end
end

For the test: test_find_missing_cookies, it will load up the .yml files: user_cookies.yml, cookies.yml, and users.yml for use with that test.

You need to specify the fixture_model as this is the directory it will look in for additional sub-fixtures. If you don’t the call will fail with an exception.

Problems

Obviously, it’s not very smart. It can’t automatically detect the test name. Though, this allows you to re-use fixtures from other tests as well as mix and match the sub-fixtures loaded with the test. But it requires that you manually type in the test name for every test.

In addition, if the fixture has already been loaded using the standard class method call: fixtures, it will be loaded and overwritten by the test a second time. This will slow the testing process down.

I’m happy with it. I bet you’ve been waiting for something like this too. Enjoy!

Edit

An update to this article is posted here.

For my security class, I chose to author my extended abstract concerning secret group handshakes. Though not intended to be a research paper, it covers the basic aspects of how secret handshakes are done, why they’re useful, and some security weaknesses inherent in the common approaches.

Abstract

“Secret groups, while preserving the anonymity of the members, have a multitude of applications. Discussed here are the fundamentals of a relatively new approach to anonymity called a secret handshake and the key concepts preserving that secrecy. Following an explanation of the mechanics of two and multi-party handshakes, open problems are presented and future research directions are suggested.”

Read the paper