#
# The Alphanum Algorithm is an improved sorting algorithm for strings
# containing numbers.  Instead of sorting numbers in ASCII order like
# a standard sort, this algorithm sorts numbers in numeric order.
#
# The Alphanum Algorithm is discussed at http://www.DaveKoelle.com
#
# To use this in Perl, you need to say
#
# @sorted_list = sort alphanum @unsorted_list;
#
# TODO: Make decimal points be considered in the same class as digits
#

import re

def alphanum(a, b):
  # a and b are automagically passed to alphanum.
  # A copy of them has to be made, or else we will edit the global $a and $b
  a_copy=a;
  b_copy=b;
  n=0;

  achunkdef = re.compile('[\D]+|[\d]+')
  bchunkdef = re.compile('[\D]+|[\d]+')
  chunknumbers = re.compile('\d+')
  chunkletters = re.compile('\D+')  
  
  while n==0:
	# Get next "chunk"
	# (A chunk is either a group of letters or a group of numbers)
	
	a_match = achunkdef.match(a_copy)
	if a_match:
		a_chunk = a_match.group()
	else:
		a_chunk = ''
	a_copy = a_copy[len(a_chunk):]

	b_match = bchunkdef.match(b_copy)
	if b_match:
		b_chunk = b_match.group()
	else:
		b_chunk = ''
	b_copy = b_copy[len(b_chunk):]

	# Compare the chunks

	# Case 1: They both contain letters

	if ( chunkletters.match(a_chunk) and chunkletters.match(b_chunk) ):
	  n = cmp(a_chunk,b_chunk)
	

	# Case 2: They both contain numbers
	else:
		
		if ( chunknumbers.match(a_chunk) and chunknumbers.match(b_chunk) ):
			n = cmp(int(a_chunk), int(b_chunk))
	

	      # Case 3: One has letters, one has numbers; or one is empty
		else:
			n = cmp(a_chunk,b_chunk)
			# If these are equal, make one (which one is arbitrary) come before
			# the other   (or else we'll be stuck in this "while $n==0" loop)
			if n==0: n=1;
	
  return n;



a = "z1.doc z2.doc z3.doc z10.doc z4.doc z5.doc".split()
b = "z1.doc z2.doc z3.doc z10.doc z4.doc z5.doc".split()
c = ["1000X Radonius Maximus",\
"10X Radonius",\
"200X Radonius",\
"20X Radonius",\
"20X Radonius Prime",\
"30X Radonius",\
"40X Radonius",\
"Allegia 50 Clasteron",\
"Allegia 500 Clasteron",\
"Allegia 51 Clasteron",\
"Allegia 51B Clasteron",\
"Allegia 52 Clasteron",\
"Allegia 60 Clasteron"]

print "Normal Sort"
print a
a.sort()
print a

print "AlphaNum sort"
print b
b.sort(alphanum)
print b

print "AlphaNum sort"
print c
c.sort(alphanum)
print c