Back to index

plone3  3.1.7
unique.py
Go to the documentation of this file.
00001 ## Script (Python) "unique"
00002 ##bind container=container
00003 ##bind context=context
00004 ##bind namespace=
00005 ##bind script=script
00006 ##bind subpath=traverse_subpath
00007 ##parameters=s
00008 ##title=Tim Peters unique recipe
00009 
00010 # taken from ASPN Python Cookbook, http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52560
00011 """Return a list of the elements in s, but without duplicates.
00012 
00013 For example, unique([1,2,3,1,2,3]) is some permutation of [1,2,3],
00014 unique("abcabc") some permutation of ["a", "b", "c"], and
00015 unique(([1, 2], [2, 3], [1, 2])) some permutation of
00016 [[2, 3], [1, 2]].
00017 
00018 For best speed, all sequence elements should be hashable.  Then
00019 unique() will usually work in linear time.
00020 
00021 If not possible, the sequence elements should enjoy a total
00022 ordering, and if list(s).sort() doesn't raise TypeError it's
00023 assumed that they do enjoy a total ordering.  Then unique() will
00024 usually work in O(N*log2(N)) time.
00025 
00026 If that's not possible either, the sequence elements must support
00027 equality-testing.  Then unique() will usually work in quadratic
00028 time.
00029 """
00030 
00031 n = len(s)
00032 if n == 0:
00033     return []
00034 
00035 # Try using a dict first, as that's the fastest and will usually
00036 # work.  If it doesn't work, it will usually fail quickly, so it
00037 # usually doesn't cost much to *try* it.  It requires that all the
00038 # sequence elements be hashable, and support equality comparison.
00039 u = {}
00040 try:
00041     for x in s:
00042         u[x] = 1
00043 except TypeError:
00044     del u  # move on to the next method
00045 else:
00046     return u.keys()
00047 
00048 # We can't hash all the elements.  Second fastest is to sort,
00049 # which brings the equal elements together; then duplicates are
00050 # easy to weed out in a single pass.
00051 # NOTE:  Python's list.sort() was designed to be efficient in the
00052 # presence of many duplicate elements.  This isn't true of all
00053 # sort functions in all languages or libraries, so this approach
00054 # is more effective in Python than it may be elsewhere.
00055 try:
00056     t = list(s)
00057     t.sort()
00058 except TypeError:
00059     del t  # move on to the next method
00060 else:
00061     assert n > 0
00062     last = t[0]
00063     lasti = i = 1
00064     while i < n:
00065         if t[i] != last:
00066             t[lasti] = last = t[i]
00067             lasti += 1
00068         i += 1
00069     return t[:lasti]
00070 
00071 # Brute force is all that's left.
00072 u = []
00073 for x in s:
00074     if x not in u:
00075         u.append(x)
00076 return u