Entry

A sorted list

How can I create a list which is maintained in sorted order?

Jun 16th, 2004 02:36
Thomas Samson, thanos vassilakis, Nathan Wallace, unknown unknown, Michael Chermside, Hans Nowak, Snippet 165, Python Snippet Support Team

""" 
Packages: basic_datatypes.lists 
""" 
# ordered_mappings.py 
from UserList import UserList 
class SortedList(UserList): 
    def __init__(self, list=None): 
        self.data = [] 
        if list is not None: 
            for item in list: 
                self.append(item) 
    def sort(self, *args): 
        """ Sort according to *our* rules. """ 
        self.data.sort(self.cmp) 
        # Is this OK?? 
    def cmp(self, a, b): 
        """ Define your own sorting routine here. """ 
        return cmp(a,b) 
    def append(self, item): 
        # Traverse the list, looking for the right element... 
        index = 0 
        try: 
            while self.cmp(self.data[index], item) <= -1: 
                index = index + 1 
            # A-ha! 
            self.data.insert(index, item) 
        except IndexError: 
            # debug 
            # print 'Append for %s and %s' % (self.data, item) 
            # /debug 
            self.data.append(item) 
if __name__ == "__main__": 
    sl = SortedList() 
    for name in ('Fred', 'Anjo', 'Marsha', 'Ellen', 'Nadia'): 
        sl.append(name) 
    print sl 
    sl = sl + ['Horia'] 
    print sl 
    """ It's easy to create a list which sorts on length: Just 
override  
the 
    cmp function. """ 
    class LenList(SortedList): 
        def cmp(self, a, b): 
            if len(a) < len(b): return len(a)-len(b)    # negative 
            elif len(a) > len(b): return len(a)-len(b)  # positive 
            else: return 0 
    ll = LenList(sl) 
    print ll 
# Maybe the below is easier [tv]. 
import bisect 
class SortedList(UserList): 
    def append(self, item): 
        bisect.insort(self.data, item)