Lars Wassermann avatar Lars Wassermann committed d02d002

(tfel, lwassermann) replaced inplace quicksort by rpython timsort in fieldtypes

Comments (0)

Files changed (1)

spyvm/fieldtypes.py

 from spyvm import model, shadow
 
 from rpython.rlib import objectmodel, jit, signature
+from rpython.rlib.listsort import TimSort
 
 class TypeTag():
     pass
 flt = TypeTag()
 obj = TypeTag()
 
+class FieldSort(TimSort):
+    def lt(self, a, b):
+        return a[0] < b[0]
+
 maps = {}
 
 class VarSizedFieldTypes():
     def ascent(self, changes):
         parent = self.parent
         if parent is None:
-            sort(changes)
+            FieldSort(changes).sort()
             return self.descent(changes)
         else:
             change = self.diff
             return typer
     except AttributeError:
         return nilTyper
-
-def sort(an_array):
-    end = len(an_array) - 1
-    sort_quick_inplace(an_array, 0, end)
-
-
-def sort_quick_inplace(an_array, start, end):
-    assert start >= 0 and end < len(an_array)
-
-    def partition(an_array, start, end):
-        key = an_array[start][0]
-        i = start - 1
-        j = end + 1
-        while True:
-            i += 1
-            j -= 1
-            while not an_array[j][0] <= key:
-                j -= 1
-            while not an_array[i][0] >= key:
-                i += 1
-            if j <= i:
-                return j
-            else:
-                an_array[i], an_array[j] = an_array[j], an_array[i]
-
-    if start < end:
-        mid = partition(an_array, start, end)
-        sort_quick_inplace(an_array, start, mid)
-        sort_quick_inplace(an_array, mid + 1, end)
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.