1#!/usr/bin/env python 2# Copyright (C) 2012 OpenStack, LLC. 3# 4# Licensed under the Apache License, Version 2.0 (the "License"); 5# you may not use this file except in compliance with the License. 6# You may obtain a copy of the License at 7# 8# http://www.apache.org/licenses/LICENSE-2.0 9# 10# Unless required by applicable law or agreed to in writing, software 11# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 12# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 13# License for the specific language governing permissions and limitations 14# under the License. 15 16""" 17Sorts using alphanum algorithm which can be explained as: 18 19Normal sort: ['a', 'a1', 'a10', 'a2'] 20Alphanum sort: ['a', 'a1', 'a2', 'a10'] 21 22It can sortof many kinds of objects, using name attribe if possible, 23otherwise it will try to use str(). 24 25How to use: 26 27from alphanum import AlphanumSort 28 29sorted( foo, key=AlphanumSort) 30 31""" 32import re 33 34 35re_chunk = re.compile(r"([\D]+|[\d]+)") 36re_letters = re.compile(r"\D+") 37re_numbers = re.compile(r"\d+") 38 39 40def getchunk(item): 41 itemchunk = re_chunk.match(item) 42 43 # Subtract the matched portion from the original string 44 # if there was a match, otherwise set it to "" 45 item = item[itemchunk.end() :] if itemchunk else "" 46 # Don't return the match object, just the text 47 itemchunk = itemchunk.group() if itemchunk else "" 48 49 return (itemchunk, item) 50 51 52def cmp(a, b): 53 return (a > b) - (a < b) 54 55 56def alphanum(a, b): 57 a = a.name if hasattr(a, "name") else str(a) 58 b = b.name if hasattr(b, "name") else str(b) 59 60 n = 0 61 62 while n == 0: 63 # Get a chunk and the original string with the chunk subtracted 64 (ac, a) = getchunk(a) 65 (bc, b) = getchunk(b) 66 67 # Both items contain only letters 68 if re_letters.match(ac) and re_letters.match(bc): 69 n = cmp(ac, bc) 70 else: 71 # Both items contain only numbers 72 if re_numbers.match(ac) and re_numbers.match(bc): 73 n = cmp(int(ac), int(bc)) 74 # item has letters and one item has numbers, or one item is empty 75 else: 76 n = cmp(ac, bc) 77 # Prevent deadlocks 78 if n == 0: 79 n = 1 80 return n 81 82 83class AlphanumSort(object): 84 def __init__(self, obj, *args): 85 self.obj = obj 86 87 def __lt__(self, other): 88 return alphanum(self.obj, other.obj) < 0 89 90 def __gt__(self, other): 91 return alphanum(self.obj, other.obj) > 0 92 93 def __eq__(self, other): 94 return alphanum(self.obj, other.obj) == 0 95 96 def __le__(self, other): 97 return alphanum(self.obj, other.obj) <= 0 98 99 def __ge__(self, other): 100 return alphanum(self.obj, other.obj) >= 0 101 102 def __ne__(self, other): 103 return alphanum(self.obj, other.obj) != 0 104 105 106if __name__ == "__main__": 107 108 mylist = ["a2", "a1", "a10", "a"] 109 assert sorted(mylist, key=AlphanumSort) == ["a", "a1", "a2", "a10"] 110