klenwell information services : Pastebin20120829

Test Script for Sorting Problem

see also http://stackoverflow.com/q/12184015/1093087

Updated version of this script available at code.google.com

from random import shuffle
import re

#
# Test Cases
#
test_cases = [
    # (unsorted list, sorted list)
    (list('bca'), ['a', 'b', 'c']),
    (list('CbA'), ['A', 'b', 'C']),
    (list('r0B9a'), ['a', 'B', 'r', '0', '9']),
    (['a2', '1a', '10a', 'a1', 'a100'], ['a1', 'a2', 'a100', '1a', '10a']),
    (['GAM', 'alp2', 'ALP11', '1', 'alp100', 'alp10', '100', 'alp1', '2'],
        ['alp1', 'alp2', 'alp10', 'ALP11', 'alp100', 'GAM', '1', '2', '100']),
    (list('ra0b9A'), ['A', 'a', 'b', 'r', '0', '9']),
    (['Abc', 'abc', 'ABc'], ['ABc', 'Abc', 'abc']),
]

#
# Sort Functions
#
def sorted_insensitive(unsorted_list):
    return sorted(unsorted_list, key=lambda s: s.lower())
   
def sorted_natural(unsorted_list):
    """see http://stackoverflow.com/a/4836734/1093087"""
    convert = lambda text: int(text) if text.isdigit() else text.lower()
    alphanum_key = lambda key: [convert(c) for c in re.split('([0-9]+)', key)]
    return sorted(unsorted_list, key=alphanum_key)

def alpha_before_numeric(unsorted_list):
    ord_shift = lambda c: c.isdigit() and chr(ord('z') + int(c.lower()) + 1) or c.lower()
    adjust_word = lambda word: "".join([ord_shift(c) for c in list(word)])
   
    def cmp_(a, b):
        return cmp(adjust_word(a), adjust_word(b))

    return sorted(unsorted_list, cmp_)

def alpha_before_numeric_natural(unsorted_list):
    """splice each string into tuple like so:
    'abc100def' -> ('a', 'b', 'c', 100, 'd', 'e', 'f') ->
    (ord('a'), ord('b'), ord('c'), ord('z') + 1 + 100, ...) then compare
    each tuple"
""
    re_p = "([0-9]+|[A-za-z])"
    ordify = lambda s: ord('z') + 1 + int(s) if s.isdigit() else ord(s.lower())
    str_to_ord_tuple = lambda key: [ordify(c) for c in re.split(re_p, key) if c]
    return sorted(unsorted_list, key=str_to_ord_tuple)

def alpha_before_numeric_natural_sensitive(unsorted_list):
    """presorting the list should work because python sorted stable sorts;
    see http://wiki.python.org/moin/HowTo/Sorting/#Sort_Stability_and_Complex_Sorts"
""
    presorted_list = sorted(unsorted_list)
    return alpha_before_numeric_natural(presorted_list)


#
# Test Apparatus
#
sort_funcs = [
    sorted,
    sorted_insensitive,
    sorted_natural,
    alpha_before_numeric,
    alpha_before_numeric_natural,
    alpha_before_numeric_natural_sensitive,
]

def test_sort():
    for sort_func in sort_funcs:
        print "\n\nSORT FUNC: %s" % (sort_func)
        failed = False
       
        for unsorted_list, expect in test_cases:            
            try:
                sorted_list = sort_func(unsorted_list)
                assert sorted_list == expect
                print '[pass] sorted list as expected: %s -> %s == %s' % (
                    unsorted_list, sorted_list, expect)
            except AssertionError:
                failed = True
                print '[fail] failed to sort list as expected: %s -> %s != %s' % (
                    unsorted_list, sorted_list, expect)
                break
       
        if not failed:  
            print "SUCCESS: func %s succeeded" % (sort_func)
        else:
            print "FAIL: func %s failed" % (sort_func)
       
def test_performance():
    pass
       
if __name__ == "__main__":
    test_sort()