# Based on Dave Koelle's Alphanum algorithm
# Rik Hemsley, 2007
# See also http://rikkus.info/arch/sensible_sort.rb

#
# This library is free software; you can redistribute it and/or
# modify it under the terms of the GNU Lesser General Public
# License as published by the Free Software Foundation; either
# version 2.1 of the License, or any later version.
# 
# This library is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
# Lesser General Public License for more details.
# 
# You should have received a copy of the GNU Lesser General Public
# License along with this library; if not, write to the Free Software
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
#

require 'test/unit'

module Enumerable

	def sensible_sort
		sort { |a, b| grouped_compare(a, b) }
	end

	def sensible_sort!
		sort! { |a, b| grouped_compare(a, b) }
	end
	
	private

	def grouped_compare(a, b)

		loop {

			a_chunk, a = extract_alpha_or_number_group(a)
			b_chunk, b = extract_alpha_or_number_group(b)

			ret = a_chunk <=> b_chunk

			return -1 if a_chunk == ''
			return ret if ret != 0

		}

	end

	def extract_alpha_or_number_group(item)

		matchdata = /([A-Za-z]+|[\d]+)/.match(item)

		if matchdata.nil?
			["", ""]
		else
			[matchdata[0], item = item[matchdata.offset(0)[1] .. -1]]
		end

	end


end

if __FILE__ == $0

	class AlphanumericSortTestCase < Test::Unit::TestCase

		def test_empty
			assert_equal(['', ''], ['', ''].sensible_sort)
		end

		def test_identical_simple
			assert_equal(['x', 'x'], ['x', 'x'].sensible_sort)
		end

		def test_identical_two_groups
			assert_equal(['x1', 'x1'], ['x1', 'x1'].sensible_sort)
		end

		def test_ordered_simple
			assert_equal(['x', 'y'], ['x', 'y'].sensible_sort)
		end

		def test_ordered_simple_start_backwards
			assert_equal(['x', 'y'], ['y', 'x'].sensible_sort)
		end

		def test_ordered_two_groups
			assert_equal(['x1', 'x2'], ['x1', 'x2'].sensible_sort)
		end

		def test_ordered_two_groups_start_backwards
			assert_equal(['x1', 'x2'], ['x2', 'x1'].sensible_sort)
		end

		def test_ordered_two_groups_separated
			assert_equal(['x_1', 'x_2'], ['x_2', 'x_1'].sensible_sort)
		end

		def test_ordered_two_groups_separated_different_distances
			assert_equal(['x_1', 'x__2'], ['x__2', 'x_1'].sensible_sort)
		end

		def test_ordered_two_groups_separated_different_distances_swapped
			assert_equal(['x__1', 'x_2'], ['x_2', 'x__1'].sensible_sort)
		end

		def test_three_groups
			assert_equal(
				['hello 2 world', 'hello world', 'hello world 2'],
				['hello world', 'hello world 2', 'hello 2 world'].sensible_sort
			)
		end

		def test!
			x = ['hello world', 'hello world 2', 'hello 2 world']
			x.sensible_sort!
			assert_equal(['hello 2 world', 'hello world', 'hello world 2'], x)
		end


	end

end