alphanum.rb

# Originally posted on http://pastie.org/131174 (21 December 2007)
# Alphanum implementation -- http://www.davekoelle.com/alphanum.html
#  (C) 2007 Marcello Barnaba <vjt@openssl.it>
#
# Released under the terms of the Ruby License:
#  http://www.ruby-lang.org/en/LICENSE.txt
#
class String
  # The algorithm breaks strings into chunks, where a chunk contains either all alphabetic characters,
  # or all numeric characters. These chunks are then compared against each other. If both chunks contain
  # numbers, a numerical comparison is used. If either chunk contains characters, the ASCII comparison is used.
  #
  def alphanum(other)
    # Break strings into chunks...
    t1 = self.to_alphanum_tokens
    t2 = other.to_alphanum_tokens

    if t1.size < t2.size
      t1 += [nil] * (t2.size - t1.size)
    end

    t1.zip(t2).map do |x|

      # If either chunks contains characters (are instances of different classes)...
      if x.map { |i| i.class }.uniq.size > 1 
        # .. ASCII comparison is used
        x = x.map { |i| i.to_s }
      end

      # Compare the chunks..
      x[0] <=> x[1]

      # and get the first difference.. if first returns nil
      # the string were equal, so return 0.
    end.reject { |r| r == 0 }.first || 0

    # The builtin implementation doesn't work in this corner case:
    # "test_420".alphanum("420_test")
    #self.to_alphanum_tokens <=> other.to_alphanum_tokens
  end
  #protected
  def to_alphanum_tokens
    self.scan(/(\d+\.?\d*|\D+)/).flatten.map { |i| i =~ /^\d+(\.\d*)?$/ ? i.to_f : i }
  end
end

if $0 == __FILE__
  require 'test/unit'

  module Enumerable
    def alphanum_sort
      sort { |a,b| a.alphanum(b) }
    end
  end

  class TestAlphaNum < Test::Unit::TestCase
    def test_alphanum_strings
      unsorted = %w( test1 test4 test100 test4.3 test )
      sorted   = %w( test test1 test4 test4.3 test100 )
      assert_equal sorted, unsorted.alphanum_sort
    end

    def test_alpha_strings
      unsorted = %w( tablinda supercazzola tapioca antani )
      sorted   = %w( antani supercazzola tablinda tapioca )
      assert_equal sorted, unsorted.alphanum_sort
    end

    def test_numeric_strings
      unsorted = %w( 123 456 789 420 )
      sorted   = %w( 123 420 456 789 )
      assert_equal sorted, unsorted.alphanum_sort
    end

    def test_mixed_strings
      unsorted = %w( test_495 test_240 420_test test__xyz test_test_240 )
      sorted   = %w( 420_test test_240 test_495 test__xyz test_test_240 )
      assert_equal sorted, unsorted.alphanum_sort
    end

    def test_empty_strings
      assert_equal [''] * 5, ([''] * 5).alphanum_sort 
    end

    def test_filenames
      unsorted = %w( z1.doc z10.doc z100.doc z101.doc z102.doc z11.doc
        z12.doc z13.doc z14.doc z15.doc z16.doc z17.doc z18.doc z19.doc
        z2.doc z20.doc z3.doc z4.doc z5.doc z6.doc z7.doc z8.doc z9.doc )

      sorted   = %w( z1.doc z2.doc z3.doc z4.doc z5.doc z6.doc z7.doc
        z8.doc z9.doc z10.doc z11.doc z12.doc z13.doc z14.doc z15.doc
        z16.doc z17.doc z18.doc z19.doc z20.doc z100.doc z101.doc z102.doc )

      assert_equal sorted, unsorted.alphanum_sort
    end 

  end