Add natural sorting (sorting case insensitively as well as numerically)

3 files changed, 79 insertions, 7 deletions

diff --git a/cmd2/cmd2.py b/cmd2/cmd2.py
index 68e0aef2..49ac91a5 100644
--- a/cmd2/cmd2.py
+++ b/cmd2/cmd2.py
@@ -1093,8 +1093,8 @@ class Cmd(cmd.Cmd):
             self.allow_appended_space = False
             self.allow_closing_quote = False
 
-        # Sort the matches before any trailing slashes are added
-        matches = utils.alphabetical_sort(matches)
+        # Sort the matches alphabetically before any trailing slashes are added
+        matches.sort(key=utils.norm_fold)
         self.matches_sorted = True
 
         # Build display_matches and add a slash to directories
@@ -1534,8 +1534,8 @@ class Cmd(cmd.Cmd):
 
             # Sort matches alphabetically if they haven't already been sorted
             if not self.matches_sorted:
-                self.completion_matches = utils.alphabetical_sort(self.completion_matches)
-                self.display_matches = utils.alphabetical_sort(self.display_matches)
+                self.completion_matches.sort(key=utils.norm_fold)
+                self.display_matches.sort(key=utils.norm_fold)
                 self.matches_sorted = True
 
         try:
diff --git a/cmd2/utils.py b/cmd2/utils.py
index 02956f6b..64401895 100644
--- a/cmd2/utils.py
+++ b/cmd2/utils.py
@@ -4,8 +4,9 @@
 
 import collections
 import os
-from typing import Any, List, Optional, Union
+import re
 import unicodedata
+from typing import Any, List, Optional, Union
 
 from . import constants
 
@@ -172,7 +173,52 @@ def norm_fold(astr: str) -> str:
 def alphabetical_sort(list_to_sort: List[str]) -> List[str]:
     """Sorts a list of strings alphabetically.
 
+    For example: ['a1', 'A11', 'A2', 'a22', 'a3']
+
+    To sort a list in place, don't call this method, which makes a copy. Instead, do this:
+
+    my_list.sort(key=norm_fold)
+
     :param list_to_sort: the list being sorted
     :return: the sorted list
     """
     return sorted(list_to_sort, key=norm_fold)
+
+
+def try_int_or_force_to_lower_case(input_str: str) -> Union[int, str]:
+    """
+    Tries to convert the passed-in string to an integer. If that fails, it converts it to lower case using norm_fold.
+    :param input_str: string to convert
+    :return: the string as an integer or a lower case version of the string
+    """
+    try:
+        return int(input_str)
+    except ValueError:
+        return norm_fold(input_str)
+
+
+def natural_keys(input_str: str) -> List[Union[int, str]]:
+    """
+    Converts a string into a list of integers and strings to support natural sorting (see natural_sort).
+
+    For example: natural_keys('abc123def') -> ['abc', '123', 'def']
+    :param input_str: string to convert
+    :return: list of strings and integers
+    """
+    return [try_int_or_force_to_lower_case(substr) for substr in re.split('(\d+)', input_str)]
+
+
+def natural_sort(list_to_sort: List[str]) -> List[str]:
+    """
+    Sorts a list of strings case insensitively as well as numerically.
+
+    For example: ['a1', 'A2', 'a3', 'A11', 'a22']
+
+    To sort a list in place, don't call this method, which makes a copy. Instead, do this:
+
+    my_list.sort(key=natural_keys)
+
+    :param list_to_sort: the list being sorted
+    :return: the list sorted naturally
+    """
+    return sorted(list_to_sort, key=natural_keys)
diff --git a/tests/test_utils.py b/tests/test_utils.py
index 61fd8373..691abdf8 100644
--- a/tests/test_utils.py
+++ b/tests/test_utils.py
@@ -13,7 +13,7 @@ HELLO_WORLD = 'Hello, world!'
 
 def test_strip_ansi():
     base_str = HELLO_WORLD
-    ansi_str =  Fore.GREEN + base_str + Fore.RESET
+    ansi_str = Fore.GREEN + base_str + Fore.RESET
     assert base_str != ansi_str
     assert base_str == cu.strip_ansi(ansi_str)
 
@@ -48,5 +48,31 @@ def test_unicode_casefold():
     assert cu.norm_fold(micro) == cu.norm_fold(micro_cf)
 
 def test_alphabetical_sort():
-    my_list = ['café', 'µ', 'A' , 'micro', 'unity', 'cafeteria']
+    my_list = ['café', 'µ', 'A', 'micro', 'unity', 'cafeteria']
     assert cu.alphabetical_sort(my_list) == ['A', 'cafeteria', 'café', 'micro', 'unity', 'µ']
+    my_list = ['a3', 'a22', 'A2', 'A11', 'a1']
+    assert cu.alphabetical_sort(my_list) == ['a1', 'A11', 'A2', 'a22', 'a3']
+
+def test_try_int_or_force_to_lower_case():
+    str1 = '17'
+    assert cu.try_int_or_force_to_lower_case(str1) == 17
+    str1 = 'ABC'
+    assert cu.try_int_or_force_to_lower_case(str1) == 'abc'
+    str1 = 'X19'
+    assert cu.try_int_or_force_to_lower_case(str1) == 'x19'
+    str1 = ''
+    assert cu.try_int_or_force_to_lower_case(str1) == ''
+
+def test_natural_keys():
+    my_list = ['café', 'µ', 'A', 'micro', 'unity', 'x1', 'X2', 'X11', 'X0', 'x22']
+    my_list.sort(key=cu.natural_keys)
+    assert my_list == ['A', 'café', 'micro', 'unity', 'X0', 'x1', 'X2', 'X11', 'x22', 'µ']
+    my_list = ['a3', 'a22', 'A2', 'A11', 'a1']
+    my_list.sort(key=cu.natural_keys)
+    assert my_list == ['a1', 'A2', 'a3', 'A11', 'a22']
+
+def test_natural_sort():
+    my_list = ['café', 'µ', 'A', 'micro', 'unity', 'x1', 'X2', 'X11', 'X0', 'x22']
+    assert cu.natural_sort(my_list) == ['A', 'café', 'micro', 'unity', 'X0', 'x1', 'X2', 'X11', 'x22', 'µ']
+    my_list = ['a3', 'a22', 'A2', 'A11', 'a1']
+    assert cu.natural_sort(my_list) == ['a1', 'A2', 'a3', 'A11', 'a22']