| 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 |
""" |
| 17 |
Sorts using alphanum algorithm which can be explained as: |
| 18 |
|
| 19 |
Normal sort: ['a', 'a1', 'a10', 'a2'] |
| 20 |
Alphanum sort: ['a', 'a1', 'a2', 'a10'] |
| 21 |
|
| 22 |
It can sortof many kinds of objects, using name attribe if possible, |
| 23 |
otherwise it will try to use str(). |
| 24 |
|
| 25 |
How to use: |
| 26 |
|
| 27 |
from alphanum import AlphanumSort |
| 28 |
|
| 29 |
sorted( foo, key=AlphanumSort) |
| 30 |
|
| 31 |
""" |
| 32 |
import re |
| 33 |
|
| 34 |
|
| 35 |
re_chunk = re.compile(r"([\D]+|[\d]+)") |
| 36 |
re_letters = re.compile(r"\D+") |
| 37 |
re_numbers = re.compile(r"\d+") |
| 38 |
|
| 39 |
|
| 40 |
def 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 |
|
| 52 |
def cmp(a, b): |
| 53 |
return (a > b) - (a < b) |
| 54 |
|
| 55 |
|
| 56 |
def 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 |
|
| 83 |
class 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 |
|
| 106 |
if __name__ == "__main__": |
| 107 |
|
| 108 |
mylist = ["a2", "a1", "a10", "a"] |
| 109 |
assert sorted(mylist, key=AlphanumSort) == ["a", "a1", "a2", "a10"] |