Ruby Gem Sarah version 2.0.1 has just been released.

What Is It?

Sarah is a combination sequential array, sparse array, and (“random access”) hash.

Ruby’s own array literal and method calling syntaxes allow you to specify a list of sequential values followed by an either implicit or explicit hash of name/value pairs stored at end of the array. Sarah takes this concept a few steps further.

Values with sequential indexes beginning at 0 are typically stored in the sequential array for efficiency. You can also assign values with non-sequential indexes, and these values are stored in the sparse array (which is actually implemented as a hash). The sequential and sparse arrays work together like a traditional Ruby array, except that there can really be empty holes with no values (as opposed to having nil values as place-holders where no other value has been set in the case of a traditional Ruby array). You can perform most of the typical array operations, including pushing, popping, shifting, unshifting, and deleting. These result in the re-indexing of sparse values in addition to sequential values after the point of insertion or deletion, just as if they had all been stored in a traditional Ruby array.

Values stored with non-integer keys are stored in a separate “random access” (i.e. unordered) hash. Re-indexing of the sequential and sparse arrays does not affect these key/value pairs.

Instead of accessing sparse and random-access values through a hash at the end of the array first, these values all appear at the same level. Compare:

# Traditional Ruby array with implicit hash
a = ['first', 5 => 'second', :greeting => 'hello']
# a[0] = 'first'
# a[1] is a hash
# a[1][5] = 'second'
# a[1][:greeting] = 'hello'

# Using a Sarah
s = Sarah['first', 5 => 'second', :greeting => 'hello']
# s[0] = 'first'
# s[5] = 'second'
# s[:greeting] = 'hello'

Why Should I Use It?

Sarah provides a pure-Ruby sparse array implementation, and can easily be the basis for a pure-Ruby sparse matrix implementation. It also provides efficient linear storage and manipulation in case you don’t know in advance if your data will be sequential or sparse in nature (i.e. it can vary significantly based on user input).

By default, negative indexes are interpreted relative to the end of the array. However, if it’s appropriate to your problem domain, Sarah also has a mode that supports negative indexes as actual indexes. In this mode, insertions and deletions do not result in value re-indexing.

Ruby Gem XKeys version 2.0.0 has just been released.

What Is It?

XKeys is a module that can be included in Ruby classes or used to extend Ruby objects to provide convenient handling of nested arrays or hashes, including Perl-like auto-vivification, PHP-like auto-indexing, and per-access default values.

Perl-Like Auto-Vivification For Ruby

A fairly common Ruby programming question, especially for current and former Perl programmers, is how to automatically generate intermediate nodes in nested array and hash structures.

Say, for example, that you want to keep some sort of running tally grouped by year, month, and day. In Perl, this is easily accomplished as follows:

my %tally; # top-level hash of tallies
# and later...
++$tally{$year}{$month}{$day}; # increment tally by year/month/day

Perl will automatically create nested arrays or hashes as you attempt to write to them. They just “spring to life” when you need them; the process is called auto-vivification.

In straight Ruby, implementing the example is more cumbersome…

tally = {} # top-level hash of tallies
# and later...
tally[year] ||= {} # make sure year hash exists
tally[year][month] ||= {} # make sure month hash exists
tally[year][month][day] ||= 0 # make sure day value exists
tally[year][month][day] += 1 # increment tally by year/month/day

Alternatively, you can provide a block of code to the top-level hash to create new hashes whenever a non-existent node is referenced, but they are created when reading (getting) the nested structure instead of when writing (setting) the nested structure, so you get new nodes even when you’re “just looking”.

Using the XKeys gem, the code becomes easier again:

require 'xkeys'
tally = {}.extend XKeys::Hash
# and later...
tally[year, month, day, :else => 0] += 1

The “:else” value is used when the value doesn’t exist yet (this avoids generating an error trying to add 1 to nil on the first tally of each day). Missing nodes are automatically added, but only on write, not on read.

PHP-Like Auto-Indexing For Ruby

PHP allows you to auto-index items being added to the end of an array by leaving the array subscript empty. For example:

$languages = array();
$languages[] = 'Perl'; # assigned to $languages[0]
$languages[] = 'PHP'; # assigned to $languages[1]
$languages[] = 'Ruby'; assigned to $languages[2]

XKeys allows you to do something similar using the symbol :[] with arrays or other types of containers supporting the #push method. This is called “push mode”. In Ruby using XKeys, it looks like this:

require 'xkeys'
languages = [].extend XKeys::Auto
languages[:[]] = 'Perl' # languages.push 'Perl' ==> languages[0]
languages[:[]] = 'PHP' # languages.push 'PHP' ==> languages[1]
languages[:[]] = 'Ruby' # languages.push 'Ruby' ==> languages[2]