1 files changed, 81 insertions, 10 deletions

diff --git a/src/engine/SCons/Util.py b/src/engine/SCons/Util.py
index 49e52ff..e2399a8 100644
--- a/src/engine/SCons/Util.py
+++ b/src/engine/SCons/Util.py
@@ -638,7 +638,7 @@ def scons_subst_list(strSubst, env, mode=SUBST_RAW, target=None, source=None, di
     class ListSubber(UserList.UserList):
         """A class to construct the results of a scons_subst_list() call.
 
-        Like StringSubber, this class binds a specific construction 
+        Like StringSubber, this class binds a specific construction
         environment, mode, target and source with two methods
         (substitute() and expand()) that handle the expansion.
 
@@ -774,7 +774,7 @@ def scons_subst_list(strSubst, env, mode=SUBST_RAW, target=None, source=None, di
             """Append the string x to the end of the current last word
             in the result.  If that is not possible, then just add
             it as a new word.  Make sure the entire concatenated string
-            inherits the object attributes of x (in particular, the 
+            inherits the object attributes of x (in particular, the
             escape function) by wrapping it as CmdStringHolder."""
 
             if not self.in_strip or self.mode != SUBST_SIG:
@@ -934,17 +934,17 @@ class Proxy:
     subject.  So, for the benefit of the python newbie, what does
     this really mean?  Well, it means that you can take an object, let's
     call it 'objA', and wrap it in this Proxy class, with a statement
-    like this 
+    like this
 
-                 proxyObj = Proxy(objA),   
+                 proxyObj = Proxy(objA),
 
-    Then, if in the future, you do something like this  
+    Then, if in the future, you do something like this
 
-                 x = proxyObj.var1, 
+                 x = proxyObj.var1,
+
+    since Proxy does not have a 'var1' attribute (but presumably objA does),
+    the request actually is equivalent to saying
 
-    since Proxy does not have a 'var1' attribute (but presumably objA does), 
-    the request actually is equivalent to saying 
-                
                  x = objA.var1
 
     Inherit from this class to create a Proxy."""
@@ -1141,7 +1141,7 @@ def PrependPath(oldpath, newpath, sep = os.pathsep):
 
     normpaths = []
     paths = []
-    # now we add them only of they are unique
+    # now we add them only if they are unique
     for path in newpaths:
         normpath = os.path.normpath(os.path.normcase(path))
         if path and not normpath in normpaths:
@@ -1317,3 +1317,74 @@ def adjustixes(fname, pre, suf):
     if suf and not splitext(fname)[1] and fname[-len(suf):] != suf:
             fname = fname + suf
     return fname
+
+
+def unique(s):
+    """Return a list of the elements in s, but without duplicates.
+
+    For example, unique([1,2,3,1,2,3]) is some permutation of [1,2,3],
+    unique("abcabc") some permutation of ["a", "b", "c"], and
+    unique(([1, 2], [2, 3], [1, 2])) some permutation of
+    [[2, 3], [1, 2]].
+
+    For best speed, all sequence elements should be hashable.  Then
+    unique() will usually work in linear time.
+
+    If not possible, the sequence elements should enjoy a total
+    ordering, and if list(s).sort() doesn't raise TypeError it's
+    assumed that they do enjoy a total ordering.  Then unique() will
+    usually work in O(N*log2(N)) time.
+
+    If that's not possible either, the sequence elements must support
+    equality-testing.  Then unique() will usually work in quadratic
+    time.
+    """
+
+    n = len(s)
+    if n == 0:
+        return []
+
+    # Try using a dict first, as that's the fastest and will usually
+    # work.  If it doesn't work, it will usually fail quickly, so it
+    # usually doesn't cost much to *try* it.  It requires that all the
+    # sequence elements be hashable, and support equality comparison.
+    u = {}
+    try:
+        for x in s:
+            u[x] = 1
+    except TypeError:
+        del u  # move on to the next method
+    else:
+        return u.keys()
+
+    # We can't hash all the elements.  Second fastest is to sort,
+    # which brings the equal elements together; then duplicates are
+    # easy to weed out in a single pass.
+    # NOTE:  Python's list.sort() was designed to be efficient in the
+    # presence of many duplicate elements.  This isn't true of all
+    # sort functions in all languages or libraries, so this approach
+    # is more effective in Python than it may be elsewhere.
+    try:
+        t = list(s)
+        t.sort()
+    except TypeError:
+        del t  # move on to the next method
+    else:
+        assert n > 0
+        last = t[0]
+        lasti = i = 1
+        while i < n:
+            if t[i] != last:
+                t[lasti] = last = t[i]
+                lasti = lasti + 1
+            i = i + 1
+        return t[:lasti]
+
+    # Brute force is all that's left.
+    u = []
+    for x in s:
+        if x not in u:
+            u.append(x)
+    return u
+
+