pypy / pypy / rlib / listsort.py

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
from pypy.rlib.rarithmetic import ovfcheck


## ------------------------------------------------------------------------
## Lots of code for an adaptive, stable, natural mergesort.  There are many
## pieces to this algorithm; read listsort.txt for overviews and details.
## ------------------------------------------------------------------------
##         Adapted from CPython, original code and algorithms by Tim Peters

def make_timsort_class():

    class TimSort:

        """TimSort(list).sort()

        Sorts the list in-place, using the overridable method lt() for comparison.
        """

        def __init__(self, list, listlength=None):
            self.list = list
            if listlength is None:
                listlength = len(list)
            self.listlength = listlength

        def lt(self, a, b):
            return a < b

        def le(self, a, b):
            return not self.lt(b, a)   # always use self.lt() as the primitive

        # binarysort is the best method for sorting small arrays: it does
        # few compares, but can do data movement quadratic in the number of
        # elements.
        # "a" is a contiguous slice of a list, and is sorted via binary insertion.
        # This sort is stable.
        # On entry, the first "sorted" elements are already sorted.
        # Even in case of error, the output slice will be some permutation of
        # the input (nothing is lost or duplicated).

        def binarysort(self, a, sorted=1):
            for start in xrange(a.base + sorted, a.base + a.len):
                # set l to where list[start] belongs
                l = a.base
                r = start
                pivot = a.list[r]
                # Invariants:
                # pivot >= all in [base, l).
                # pivot  < all in [r, start).
                # The second is vacuously true at the start.
                while l < r:
                    p = l + ((r - l) >> 1)
                    if self.lt(pivot, a.list[p]):
                        r = p
                    else:
                        l = p+1
                assert l == r
                # The invariants still hold, so pivot >= all in [base, l) and
                # pivot < all in [l, start), so pivot belongs at l.  Note
                # that if there are elements equal to pivot, l points to the
                # first slot after them -- that's why this sort is stable.
                # Slide over to make room.
                for p in xrange(start, l, -1):
                    a.list[p] = a.list[p-1]
                a.list[l] = pivot

        # Compute the length of the run in the slice "a".
        # "A run" is the longest ascending sequence, with
        #
        #     a[0] <= a[1] <= a[2] <= ...
        #
        # or the longest descending sequence, with
        #
        #     a[0] > a[1] > a[2] > ...
        #
        # Return (run, descending) where descending is False in the former case,
        # or True in the latter.
        # For its intended use in a stable mergesort, the strictness of the defn of
        # "descending" is needed so that the caller can safely reverse a descending
        # sequence without violating stability (strict > ensures there are no equal
        # elements to get out of order).

        def count_run(self, a):
            if a.len <= 1:
                n = a.len
                descending = False
            else:
                n = 2
                if self.lt(a.list[a.base + 1], a.list[a.base]):
                    descending = True
                    for p in xrange(a.base + 2, a.base + a.len):
                        if self.lt(a.list[p], a.list[p-1]):
                            n += 1
                        else:
                            break
                else:
                    descending = False
                    for p in xrange(a.base + 2, a.base + a.len):
                        if self.lt(a.list[p], a.list[p-1]):
                            break
                        else:
                            n += 1
            return ListSlice(a.list, a.base, n), descending

        # Locate the proper position of key in a sorted vector; if the vector
        # contains an element equal to key, return the position immediately to the
        # left of the leftmost equal element -- or to the right of the rightmost
        # equal element if the flag "rightmost" is set.
        #
        # "hint" is an index at which to begin the search, 0 <= hint < a.len.
        # The closer hint is to the final result, the faster this runs.
        #
        # The return value is the index 0 <= k <= a.len such that
        #
        #     a[k-1] < key <= a[k]      (if rightmost is False)
        #     a[k-1] <= key < a[k]      (if rightmost is True)
        #
        # as long as the indices are in bound.  IOW, key belongs at index k;
        # or, IOW, the first k elements of a should precede key, and the last
        # n-k should follow key.

        def gallop(self, key, a, hint, rightmost):
            assert 0 <= hint < a.len
            if rightmost:
                lower = self.le   # search for the largest k for which a[k] <= key
            else:
                lower = self.lt   # search for the largest k for which a[k] < key

            p = a.base + hint
            lastofs = 0
            ofs = 1
            if lower(a.list[p], key):
                # a[hint] < key -- gallop right, until
                #     a[hint + lastofs] < key <= a[hint + ofs]

                maxofs = a.len - hint     # a[a.len-1] is highest
                while ofs < maxofs:
                    if lower(a.list[p + ofs], key):
                        lastofs = ofs
                        try:
                            ofs = ovfcheck(ofs << 1)
                        except OverflowError:
                            ofs = maxofs
                        else:
                            ofs = ofs + 1
                    else:  # key <= a[hint + ofs]
                        break

                if ofs > maxofs:
                    ofs = maxofs
                # Translate back to offsets relative to a.
                lastofs += hint
                ofs += hint

            else:
                # key <= a[hint] -- gallop left, until
                #     a[hint - ofs] < key <= a[hint - lastofs]
                maxofs = hint + 1   # a[0] is lowest
                while ofs < maxofs:
                    if lower(a.list[p - ofs], key):
                        break
                    else:
                        # key <= a[hint - ofs]
                        lastofs = ofs
                        try:
                            ofs = ovfcheck(ofs << 1)
                        except OverflowError:
                            ofs = maxofs
                        else:
                            ofs = ofs + 1
                if ofs > maxofs:
                    ofs = maxofs
                # Translate back to positive offsets relative to a.
                lastofs, ofs = hint-ofs, hint-lastofs

            assert -1 <= lastofs < ofs <= a.len

            # Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the
            # right of lastofs but no farther right than ofs.  Do a binary
            # search, with invariant a[lastofs-1] < key <= a[ofs].

            lastofs += 1
            while lastofs < ofs:
                m = lastofs + ((ofs - lastofs) >> 1)
                if lower(a.list[a.base + m], key):
                    lastofs = m+1   # a[m] < key
                else:
                    ofs = m         # key <= a[m]

            assert lastofs == ofs         # so a[ofs-1] < key <= a[ofs]
            return ofs

        # hint for the annotator: the argument 'rightmost' is always passed in as
        # a constant (either True or False), so we can specialize the function for
        # the two cases.  (This is actually needed for technical reasons: the
        # variable 'lower' must contain a known method, which is the case in each
        # specialized version but not in the unspecialized one.)
        gallop._annspecialcase_ = "specialize:arg(4)"

        # ____________________________________________________________

        # When we get into galloping mode, we stay there until both runs win less
        # often than MIN_GALLOP consecutive times.  See listsort.txt for more info.
        MIN_GALLOP = 7

        def merge_init(self):
            # This controls when we get *into* galloping mode.  It's initialized
            # to MIN_GALLOP.  merge_lo and merge_hi tend to nudge it higher for
            # random data, and lower for highly structured data.
            self.min_gallop = self.MIN_GALLOP

            # A stack of n pending runs yet to be merged.  Run #i starts at
            # address pending[i].base and extends for pending[i].len elements.
            # It's always true (so long as the indices are in bounds) that
            #
            #     pending[i].base + pending[i].len == pending[i+1].base
            #
            # so we could cut the storage for this, but it's a minor amount,
            # and keeping all the info explicit simplifies the code.
            self.pending = []

        # Merge the slice "a" with the slice "b" in a stable way, in-place.
        # a.len and b.len must be > 0, and a.base + a.len == b.base.
        # Must also have that b.list[b.base] < a.list[a.base], that
        # a.list[a.base+a.len-1] belongs at the end of the merge, and should have
        # a.len <= b.len.  See listsort.txt for more info.

        def merge_lo(self, a, b):
            assert a.len > 0 and b.len > 0 and a.base + a.len == b.base
            min_gallop = self.min_gallop
            dest = a.base
            a = a.copyitems()

            # Invariant: elements in "a" are waiting to be reinserted into the list
            # at "dest".  They should be merged with the elements of "b".
            # b.base == dest + a.len.
            # We use a finally block to ensure that the elements remaining in
            # the copy "a" are reinserted back into self.list in all cases.
            try:
                self.list[dest] = b.popleft()
                dest += 1
                if a.len == 1 or b.len == 0:
                    return

                while True:
                    acount = 0   # number of times A won in a row
                    bcount = 0   # number of times B won in a row

                    # Do the straightforward thing until (if ever) one run
                    # appears to win consistently.
                    while True:
                        if self.lt(b.list[b.base], a.list[a.base]):
                            self.list[dest] = b.popleft()
                            dest += 1
                            if b.len == 0:
                                return
                            bcount += 1
                            acount = 0
                            if bcount >= min_gallop:
                                break
                        else:
                            self.list[dest] = a.popleft()
                            dest += 1
                            if a.len == 1:
                                return
                            acount += 1
                            bcount = 0
                            if acount >= min_gallop:
                                break

                    # One run is winning so consistently that galloping may
                    # be a huge win.  So try that, and continue galloping until
                    # (if ever) neither run appears to be winning consistently
                    # anymore.
                    min_gallop += 1

                    while True:
                        min_gallop -= min_gallop > 1
                        self.min_gallop = min_gallop

                        acount = self.gallop(b.list[b.base], a, hint=0,
                                             rightmost=True)
                        for p in xrange(a.base, a.base + acount):
                            self.list[dest] = a.list[p]
                            dest += 1
                        a.advance(acount)
                        # a.len==0 is impossible now if the comparison
                        # function is consistent, but we can't assume
                        # that it is.
                        if a.len <= 1:
                            return

                        self.list[dest] = b.popleft()
                        dest += 1
                        if b.len == 0:
                            return

                        bcount = self.gallop(a.list[a.base], b, hint=0,
                                             rightmost=False)
                        for p in xrange(b.base, b.base + bcount):
                            self.list[dest] = b.list[p]
                            dest += 1
                        b.advance(bcount)
                        if b.len == 0:
                            return

                        self.list[dest] = a.popleft()
                        dest += 1
                        if a.len == 1:
                            return

                        if acount < self.MIN_GALLOP and bcount < self.MIN_GALLOP:
                            break

                    min_gallop += 1  # penalize it for leaving galloping mode
                    self.min_gallop = min_gallop

            finally:
                # The last element of a belongs at the end of the merge, so we copy
                # the remaining elements of b before the remaining elements of a.
                assert a.len >= 0 and b.len >= 0
                for p in xrange(b.base, b.base + b.len):
                    self.list[dest] = b.list[p]
                    dest += 1
                for p in xrange(a.base, a.base + a.len):
                    self.list[dest] = a.list[p]
                    dest += 1

        # Same as merge_lo(), but should have a.len >= b.len.

        def merge_hi(self, a, b):
            assert a.len > 0 and b.len > 0 and a.base + a.len == b.base
            min_gallop = self.min_gallop
            dest = b.base + b.len
            b = b.copyitems()

            # Invariant: elements in "b" are waiting to be reinserted into the list
            # before "dest".  They should be merged with the elements of "a".
            # a.base + a.len == dest - b.len.
            # We use a finally block to ensure that the elements remaining in
            # the copy "b" are reinserted back into self.list in all cases.
            try:
                dest -= 1
                self.list[dest] = a.popright()
                if a.len == 0 or b.len == 1:
                    return

                while True:
                    acount = 0   # number of times A won in a row
                    bcount = 0   # number of times B won in a row

                    # Do the straightforward thing until (if ever) one run
                    # appears to win consistently.
                    while True:
                        nexta = a.list[a.base + a.len - 1]
                        nextb = b.list[b.base + b.len - 1]
                        if self.lt(nextb, nexta):
                            dest -= 1
                            self.list[dest] = nexta
                            a.len -= 1
                            if a.len == 0:
                                return
                            acount += 1
                            bcount = 0
                            if acount >= min_gallop:
                                break
                        else:
                            dest -= 1
                            self.list[dest] = nextb
                            b.len -= 1
                            if b.len == 1:
                                return
                            bcount += 1
                            acount = 0
                            if bcount >= min_gallop:
                                break

                    # One run is winning so consistently that galloping may
                    # be a huge win.  So try that, and continue galloping until
                    # (if ever) neither run appears to be winning consistently
                    # anymore.
                    min_gallop += 1

                    while True:
                        min_gallop -= min_gallop > 1
                        self.min_gallop = min_gallop

                        nextb = b.list[b.base + b.len - 1]
                        k = self.gallop(nextb, a, hint=a.len-1, rightmost=True)
                        acount = a.len - k
                        for p in xrange(a.base + a.len - 1, a.base + k - 1, -1):
                            dest -= 1
                            self.list[dest] = a.list[p]
                        a.len -= acount
                        if a.len == 0:
                            return

                        dest -= 1
                        self.list[dest] = b.popright()
                        if b.len == 1:
                            return

                        nexta = a.list[a.base + a.len - 1]
                        k = self.gallop(nexta, b, hint=b.len-1, rightmost=False)
                        bcount = b.len - k
                        for p in xrange(b.base + b.len - 1, b.base + k - 1, -1):
                            dest -= 1
                            self.list[dest] = b.list[p]
                        b.len -= bcount
                        # b.len==0 is impossible now if the comparison
                        # function is consistent, but we can't assume
                        # that it is.
                        if b.len <= 1:
                            return

                        dest -= 1
                        self.list[dest] = a.popright()
                        if a.len == 0:
                            return

                        if acount < self.MIN_GALLOP and bcount < self.MIN_GALLOP:
                            break

                    min_gallop += 1  # penalize it for leaving galloping mode
                    self.min_gallop = min_gallop

            finally:
                # The last element of a belongs at the end of the merge, so we copy
                # the remaining elements of a and then the remaining elements of b.
                assert a.len >= 0 and b.len >= 0
                for p in xrange(a.base + a.len - 1, a.base - 1, -1):
                    dest -= 1
                    self.list[dest] = a.list[p]
                for p in xrange(b.base + b.len - 1, b.base - 1, -1):
                    dest -= 1
                    self.list[dest] = b.list[p]

        # Merge the two runs at stack indices i and i+1.

        def merge_at(self, i):
            a = self.pending[i]
            b = self.pending[i+1]
            assert a.len > 0 and b.len > 0
            assert a.base + a.len == b.base

            # Record the length of the combined runs and remove the run b
            self.pending[i] = ListSlice(self.list, a.base, a.len + b.len)
            del self.pending[i+1]

            # Where does b start in a?  Elements in a before that can be
            # ignored (already in place).
            k = self.gallop(b.list[b.base], a, hint=0, rightmost=True)
            a.advance(k)
            if a.len == 0:
                return

            # Where does a end in b?  Elements in b after that can be
            # ignored (already in place).
            b.len = self.gallop(a.list[a.base+a.len-1], b, hint=b.len-1,
                                rightmost=False)
            if b.len == 0:
                return

            # Merge what remains of the runs.  The direction is chosen to
            # minimize the temporary storage needed.
            if a.len <= b.len:
                self.merge_lo(a, b)
            else:
                self.merge_hi(a, b)

        # Examine the stack of runs waiting to be merged, merging adjacent runs
        # until the stack invariants are re-established:
        #
        # 1. len[-3] > len[-2] + len[-1]
        # 2. len[-2] > len[-1]
        #
        # See listsort.txt for more info.

        def merge_collapse(self):
            p = self.pending
            while len(p) > 1:
                if len(p) >= 3 and p[-3].len <= p[-2].len + p[-1].len:
                    if p[-3].len < p[-1].len:
                        self.merge_at(-3)
                    else:
                        self.merge_at(-2)
                elif p[-2].len <= p[-1].len:
                    self.merge_at(-2)
                else:
                    break

        # Regardless of invariants, merge all runs on the stack until only one
        # remains.  This is used at the end of the mergesort.

        def merge_force_collapse(self):
            p = self.pending
            while len(p) > 1:
                if len(p) >= 3 and p[-3].len < p[-1].len:
                    self.merge_at(-3)
                else:
                    self.merge_at(-2)

        # Compute a good value for the minimum run length; natural runs shorter
        # than this are boosted artificially via binary insertion.
        #
        # If n < 64, return n (it's too small to bother with fancy stuff).
        # Else if n is an exact power of 2, return 32.
        # Else return an int k, 32 <= k <= 64, such that n/k is close to, but
        # strictly less than, an exact power of 2.
        #
        # See listsort.txt for more info.

        def merge_compute_minrun(self, n):
            r = 0    # becomes 1 if any 1 bits are shifted off
            while n >= 64:
                r |= n & 1
                n >>= 1
            return n + r

        # ____________________________________________________________
        # Entry point.

        def sort(self):
            remaining = ListSlice(self.list, 0, self.listlength)
            if remaining.len < 2:
                return

            # March over the array once, left to right, finding natural runs,
            # and extending short natural runs to minrun elements.
            self.merge_init()
            minrun = self.merge_compute_minrun(remaining.len)

            while remaining.len > 0:
                # Identify next run.
                run, descending = self.count_run(remaining)
                if descending:
                    run.reverse()
                # If short, extend to min(minrun, nremaining).
                if run.len < minrun:
                    sorted = run.len
                    run.len = min(minrun, remaining.len)
                    self.binarysort(run, sorted)
                # Advance remaining past this run.
                remaining.advance(run.len)
                # Push run onto pending-runs stack, and maybe merge.
                self.pending.append(run)
                self.merge_collapse()

            assert remaining.base == self.listlength

            self.merge_force_collapse()
            assert len(self.pending) == 1
            assert self.pending[0].base == 0
            assert self.pending[0].len == self.listlength

    class ListSlice:
        "A sublist of a list."

        def __init__(self, list, base, len):
            self.list = list
            self.base = base
            self.len  = len

        def copyitems(self):
            "Make a copy of the slice of the original list."
            start = self.base
            stop  = self.base + self.len
            assert 0 <= start <= stop     # annotator hint
            return ListSlice(self.list[start:stop], 0, self.len)

        def advance(self, n):
            self.base += n
            self.len -= n

        def popleft(self):
            result = self.list[self.base]
            self.base += 1
            self.len -= 1
            return result

        def popright(self):
            self.len -= 1
            return self.list[self.base + self.len]

        def reverse(self):
            "Reverse the slice in-place."
            list = self.list
            lo = self.base
            hi = lo + self.len - 1
            while lo < hi:
                list[lo], list[hi] = list[hi], list[lo]
                lo += 1
                hi -= 1
    return TimSort

TimSort = make_timsort_class() #backward compatible interface
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.