001: // Copyright 2002 Finn Bock
002:
003: package org.python.core;
004:
005: /**
006: * The MergeState class is a java implementation of the sort created
007: * Tim Peters and added to CPython2.3.
008: *
009: * The algorithm is described in details in the file
010: * python/dist/src/Objects/listsort.txt in the CPython development CVS.
011: */
012: class MergeState {
013: /**
014: * The maximum number of entries in a MergeState's pending-runs stack.
015: * This is enough to sort arrays of size up to about
016: * 32 * phi ** MAX_MERGE_PENDING
017: * where phi ~= 1.618. 85 is ridiculously large enough, good for an
018: * array with 2**64 elements.
019: */
020: static final int MAX_MERGE_PENDING = 85;
021:
022: /**
023: * If a run wins MIN_GALLOP times in a row, we switch to galloping mode,
024: * and stay there until both runs win less often than MIN_GALLOP
025: * consecutive times. See listsort.txt for more info.
026: */
027: static final int MIN_GALLOP = 8;
028:
029: /**
030: * Initial temp array size
031: */
032: static final int MERGESTATE_TEMP_SIZE = 256;
033:
034: private PyObject[] a = new PyObject[MERGESTATE_TEMP_SIZE];
035:
036: private int[] base = new int[MAX_MERGE_PENDING];
037: private int[] len = new int[MAX_MERGE_PENDING];
038:
039: private PyObject compare;
040: private PyObject[] data;
041: private int size;
042: private int n;
043:
044: MergeState(PyObject[] data, int size, PyObject compare) {
045: this .data = data;
046: this .compare = compare;
047: this .size = size;
048: this .n = 0;
049: }
050:
051: public void sort() {
052: int nremaining = this .size;
053: if (nremaining < 2) {
054: return;
055: }
056:
057: int lo = 0;
058: int hi = nremaining;
059: int minrun = merge_compute_minrun(nremaining);
060:
061: boolean[] descending = new boolean[1];
062: do {
063: /* Identify next run. */
064: int localN = count_run(lo, hi, descending);
065: if (descending[0])
066: reverse_slice(lo, lo + localN);
067: /* If short, extend to min(minrun, nremaining). */
068: if (localN < minrun) {
069: int force = nremaining < minrun ? nremaining : minrun;
070: binarysort(lo, lo + force, lo + localN);
071: localN = force;
072: }
073: /* Push run onto pending-runs stack, and maybe merge. */
074: //ms.assert_(ms.n < ms.MAX_MERGE_PENDING);
075: this .base[this .n] = lo;
076: this .len[this .n] = localN;
077: ++this .n;
078: merge_collapse();
079: /* Advance to find next run */
080: lo += localN;
081: nremaining -= localN;
082: } while (nremaining != 0);
083: //assert_(lo == hi);
084:
085: merge_force_collapse();
086: //assert_(ms.n == 1);
087: //assert_(ms.base[0] == 0);
088: //assert_(ms.len[0] == size);
089: }
090:
091: public void getmem(int need) {
092: if (need <= this .a.length)
093: return;
094: this .a = new PyObject[need];
095: }
096:
097: int count_run(int lo, int hi, boolean[] descending) {
098: //assert_(lo < hi);
099: descending[0] = false;
100: ++lo;
101: if (lo == hi)
102: return 1;
103: int localN = 2;
104: if (iflt(this .data[lo], this .data[lo - 1])) {
105: descending[0] = true;
106: for (lo = lo + 1; lo < hi; ++lo, ++localN) {
107: if (!iflt(this .data[lo], this .data[lo - 1]))
108: break;
109: }
110: } else {
111: for (lo = lo + 1; lo < hi; ++lo, ++localN) {
112: if (iflt(this .data[lo], this .data[lo - 1]))
113: break;
114: }
115: }
116: return localN;
117: }
118:
119: void merge_lo(int pa, int na, int pb, int nb) {
120: //debug("merge_lo pa:" + pa + " na:" + na + " pb:" + pb + " nb:" + nb);
121: //dump_data("padata", pa, na);
122: //dump_data("pbdata", pb, nb);
123:
124: //assert_(na > 0 && nb > 0 && pa + na == pb);
125: getmem(na);
126: System.arraycopy(this .data, pa, this .a, 0, na);
127: int dest = pa;
128: pa = 0;
129:
130: this .data[dest++] = this .data[pb++];
131: --nb;
132: if (nb == 0)
133: return;
134: if (na == 1) {
135: // CopyB;
136: System.arraycopy(this .data, pb, this .data, dest, nb);
137: this .data[dest + nb] = this .a[pa];
138: return;
139: }
140:
141: try {
142: for (;;) {
143: int acount = 0; /* # of time A won in a row */
144: int bcount = 0; /* # of time B won in a row */
145:
146: /* Do the straightforward thing until (if ever) one run
147: * appears to win consistently.
148: */
149: for (;;) {
150: boolean k = iflt(this .data[pb], this .a[pa]);
151: if (k) {
152: this .data[dest++] = this .data[pb++];
153: ++bcount;
154: acount = 0;
155: --nb;
156: if (nb == 0)
157: return;
158: if (bcount >= MIN_GALLOP)
159: break;
160: } else {
161: this .data[dest++] = this .a[pa++];
162: ++acount;
163: bcount = 0;
164: --na;
165: if (na == 1) {
166: // CopyB;
167: System.arraycopy(this .data, pb, this .data,
168: dest, nb);
169: this .data[dest + nb] = this .a[pa];
170: na = 0;
171: return;
172: }
173: if (acount >= MIN_GALLOP)
174: break;
175: }
176: }
177:
178: /* One run is winning so consistently that galloping may
179: * be a huge win. So try that, and continue galloping until
180: * (if ever) neither run appears to be winning consistently
181: * anymore.
182: */
183: do {
184: int k = gallop_right(this .data[pb], this .a, pa, na,
185: 0);
186: acount = k;
187: if (k != 0) {
188: System
189: .arraycopy(this .a, pa, this .data, dest,
190: k);
191: dest += k;
192: pa += k;
193: na -= k;
194: if (na == 1) {
195: // CopyB
196: System.arraycopy(this .data, pb, this .data,
197: dest, nb);
198: this .data[dest + nb] = this .a[pa];
199: na = 0;
200: return;
201: }
202: /* na==0 is impossible now if the comparison
203: * function is consistent, but we can't assume
204: * that it is.
205: */
206: if (na == 0)
207: return;
208: }
209:
210: this .data[dest++] = this .data[pb++];
211: --nb;
212: if (nb == 0)
213: return;
214:
215: k = gallop_left(this .a[pa], this .data, pb, nb, 0);
216: bcount = k;
217: if (k != 0) {
218: System.arraycopy(this .data, pb, this .data,
219: dest, k);
220: dest += k;
221: pb += k;
222: nb -= k;
223: if (nb == 0)
224: return;
225: }
226: this .data[dest++] = this .a[pa++];
227: --na;
228: if (na == 1) {
229: // CopyB;
230: System.arraycopy(this .data, pb, this .data,
231: dest, nb);
232: this .data[dest + nb] = this .a[pa];
233: na = 0;
234: return;
235: }
236: } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
237: }
238: } finally {
239: if (na != 0)
240: System.arraycopy(this .a, pa, this .data, dest, na);
241:
242: //dump_data("result", origpa, cnt);
243: }
244: }
245:
246: void merge_hi(int pa, int na, int pb, int nb) {
247: //debug("merge_hi pa:" + pa + " na:" + na + " pb:" + pb + " nb:" + nb);
248: //dump_data("padata", pa, na);
249: //dump_data("pbdata", pb, nb);
250:
251: //assert_(na > 0 && nb > 0 && pa + na == pb);
252: getmem(nb);
253: int dest = pb + nb - 1;
254: int basea = pa;
255: System.arraycopy(this .data, pb, this .a, 0, nb);
256:
257: pb = nb - 1;
258: pa += na - 1;
259:
260: this .data[dest--] = this .data[pa--];
261: --na;
262: if (na == 0)
263: return;
264: if (nb == 1) {
265: // CopyA;
266: dest -= na;
267: pa -= na;
268: System
269: .arraycopy(this .data, pa + 1, this .data, dest + 1,
270: na);
271: this .data[dest] = this .a[pb];
272: nb = 0;
273: return;
274: }
275:
276: try {
277: for (;;) {
278: int acount = 0; /* # of time A won in a row */
279: int bcount = 0; /* # of time B won in a row */
280:
281: /* Do the straightforward thing until (if ever) one run
282: * appears to win consistently.
283: */
284: for (;;) {
285: boolean k = iflt(this .a[pb], this .data[pa]);
286: if (k) {
287: this .data[dest--] = this .data[pa--];
288: ++acount;
289: bcount = 0;
290: --na;
291: if (na == 0)
292: return;
293: if (acount >= MIN_GALLOP)
294: break;
295: } else {
296: this .data[dest--] = this .a[pb--];
297: ++bcount;
298: acount = 0;
299: --nb;
300: if (nb == 1) {
301: // CopyA
302: dest -= na;
303: pa -= na;
304: System.arraycopy(this .data, pa + 1,
305: this .data, dest + 1, na);
306: this .data[dest] = this .a[pb];
307: nb = 0;
308: return;
309: }
310: if (bcount >= MIN_GALLOP)
311: break;
312: }
313: }
314:
315: /* One run is winning so consistently that galloping may
316: * be a huge win. So try that, and continue galloping until
317: * (if ever) neither run appears to be winning consistently
318: * anymore.
319: */
320: do {
321: int k = gallop_right(this .a[pb], this .data, basea,
322: na, na - 1);
323: acount = k = na - k;
324: if (k != 0) {
325: dest -= k;
326: pa -= k;
327: System.arraycopy(this .data, pa + 1, this .data,
328: dest + 1, k);
329: na -= k;
330: if (na == 0)
331: return;
332: }
333:
334: this .data[dest--] = this .a[pb--];
335: --nb;
336: if (nb == 1) {
337: // CopyA
338: dest -= na;
339: pa -= na;
340: System.arraycopy(this .data, pa + 1, this .data,
341: dest + 1, na);
342: this .data[dest] = this .a[pb];
343: nb = 0;
344: return;
345: }
346:
347: k = gallop_left(this .data[pa], this .a, 0, nb,
348: nb - 1);
349: bcount = k = nb - k;
350: if (k != 0) {
351: dest -= k;
352: pb -= k;
353: System.arraycopy(this .a, pb + 1, this .data,
354: dest + 1, k);
355: nb -= k;
356: if (nb == 1) {
357: // CopyA
358: dest -= na;
359: pa -= na;
360: System.arraycopy(this .data, pa + 1,
361: this .data, dest + 1, na);
362: this .data[dest] = this .a[pb];
363: nb = 0;
364: return;
365: }
366: /* nb==0 is impossible now if the comparison
367: * function is consistent, but we can't assume
368: * that it is.
369: */
370: if (nb == 0)
371: return;
372: }
373: this .data[dest--] = this .data[pa--];
374: --na;
375: if (na == 0)
376: return;
377: } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
378: }
379: } finally {
380: if (nb != 0)
381: System.arraycopy(this .a, 0, this .data, dest - (nb - 1),
382: nb);
383:
384: //dump_data("result", origpa, cnt);
385: }
386: }
387:
388: /*
389: Locate the proper position of key in a sorted vector; if the vector contains
390: an element equal to key, return the position immediately to the left of
391: the leftmost equal element. [gallop_right() does the same except returns
392: the position to the right of the rightmost equal element (if any).]
393:
394: "a" is a sorted vector with n elements, starting at a[0]. n must be > 0.
395:
396: "hint" is an index at which to begin the search, 0 <= hint < n. The closer
397: hint is to the final result, the faster this runs.
398:
399: The return value is the int k in 0..n such that
400:
401: a[k-1] < key <= a[k]
402:
403: pretending that *(a-1) is minus infinity and a[n] is plus infinity. IOW,
404: key belongs at index k; or, IOW, the first k elements of a should precede
405: key, and the last n-k should follow key.
406:
407: Returns -1 on error. See listsort.txt for info on the method.
408: */
409:
410: private int gallop_left(PyObject key, PyObject[] localData,
411: int localA, int localN, int hint) {
412: //assert_(n > 0 && hint >= 0 && hint < n);
413: localA += hint;
414: int ofs = 1;
415: int lastofs = 0;
416:
417: if (iflt(localData[localA], key)) {
418: /* a[hint] < key -- gallop right, until
419: * a[hint + lastofs] < key <= a[hint + ofs]
420: */
421: int maxofs = localN - hint; // data[a + n - 1] is highest
422: while (ofs < maxofs) {
423: if (iflt(localData[localA + ofs], key)) {
424: lastofs = ofs;
425: ofs = (ofs << 1) + 1;
426: if (ofs <= 0) // int overflow
427: ofs = maxofs;
428: } else {
429: // key < data[a + hint + ofs]
430: break;
431: }
432: }
433: if (ofs > maxofs)
434: ofs = maxofs;
435: // Translate back to offsets relative to a.
436: lastofs += hint;
437: ofs += hint;
438: } else {
439: /* key <= a[hint] -- gallop left, until
440: * a[hint - ofs] < key <= a[hint - lastofs]
441: */
442: int maxofs = hint + 1; // data[a] is lowest
443: while (ofs < maxofs) {
444: if (iflt(localData[localA - ofs], key))
445: break;
446: // key <= data[a + hint - ofs]
447: lastofs = ofs;
448: ofs = (ofs << 1) + 1;
449: if (ofs <= 0) // int overflow
450: ofs = maxofs;
451: }
452: if (ofs > maxofs)
453: ofs = maxofs;
454: // Translate back to offsets relative to a.
455: int k = lastofs;
456: lastofs = hint - ofs;
457: ofs = hint - k;
458: }
459: localA -= hint;
460: //assert_(-1 <= lastofs && lastofs < ofs && ofs <= n);
461: /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the
462: * right of lastofs but no farther right than ofs. Do a binary
463: * search, with invariant a[lastofs-1] < key <= a[ofs].
464: */
465: ++lastofs;
466: while (lastofs < ofs) {
467: int m = lastofs + ((ofs - lastofs) >> 1);
468: if (iflt(localData[localA + m], key))
469: lastofs = m + 1; // data[a + m] < key
470: else
471: ofs = m; // key <= data[a + m]
472: }
473: //assert_(lastofs == ofs); // so data[a + ofs -1] < key <= data[a+ofs]
474: return ofs;
475: }
476:
477: /*
478: * Exactly like gallop_left(), except that if key already exists in a[0:n],
479: * finds the position immediately to the right of the rightmost equal value.
480: *
481: * The return value is the int k in 0..n such that
482: * a[k-1] <= key < a[k]
483: * or -1 if error.
484: *
485: * The code duplication is massive, but this is enough different given that
486: * we're sticking to "<" comparisons that it's much harder to follow if
487: * written as one routine with yet another "left or right?" flag.
488: */
489:
490: private int gallop_right(PyObject key, PyObject[] aData,
491: int localA, int localN, int hint) {
492: //assert_(n > 0 && hint >= 0 && hint < n);
493: localA += hint;
494: int lastofs = 0;
495: int ofs = 1;
496:
497: if (iflt(key, aData[localA])) {
498: /* key < a[hint] -- gallop left, until
499: * a[hint - ofs] <= key < a[hint - lastofs]
500: */
501: int maxofs = hint + 1; /* data[a] is lowest */
502: while (ofs < maxofs) {
503: if (iflt(key, aData[localA - ofs])) {
504: lastofs = ofs;
505: ofs = (ofs << 1) + 1;
506: if (ofs <= 0) // int overflow
507: ofs = maxofs;
508: } else {
509: /* a[hint - ofs] <= key */
510: break;
511: }
512: }
513: if (ofs > maxofs)
514: ofs = maxofs;
515: /* Translate back to positive offsets relative to &a[0]. */
516: int k = lastofs;
517: lastofs = hint - ofs;
518: ofs = hint - k;
519: } else {
520: /* a[hint] <= key -- gallop right, until
521: * a[hint + lastofs] <= key < a[hint + ofs]
522: */
523: int maxofs = localN - hint; /* data[a + n - 1] is highest */
524: while (ofs < maxofs) {
525: if (iflt(key, aData[localA + ofs]))
526: break;
527: /* a[hint + ofs] <= key */
528: lastofs = ofs;
529: ofs = (ofs << 1) + 1;
530: if (ofs <= 0) /* int overflow */
531: ofs = maxofs;
532: }
533: if (ofs > maxofs)
534: ofs = maxofs;
535: /* Translate back to offsets relative to &a[0]. */
536: lastofs += hint;
537: ofs += hint;
538: }
539: localA -= hint;
540:
541: //assert_(-1 <= lastofs && lastofs < ofs && ofs <= n);
542:
543: /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the
544: * right of lastofs but no farther right than ofs. Do a binary
545: * search, with invariant a[lastofs-1] <= key < a[ofs].
546: */
547: ++lastofs;
548: while (lastofs < ofs) {
549: int m = lastofs + ((ofs - lastofs) >> 1);
550: if (iflt(key, aData[localA + m]))
551: ofs = m; // key < data[a + m]
552: else
553: lastofs = m + 1; // data[a + m] <= key
554: }
555: //assert_(lastofs == ofs); // so data[a + ofs -1] <= key < data[a+ofs]
556: return ofs;
557: }
558:
559: void merge_at(int i) {
560: //assert_(n >= 2);
561: //assert_(i >= 0);
562: //assert_(i == n - 2 || i == n - 3);
563:
564: int pa = this .base[i];
565: int pb = this .base[i + 1];
566: int na = this .len[i];
567: int nb = this .len[i + 1];
568:
569: //assert_(na > 0 && nb > 0);
570: //assert_(pa + na == pb);
571:
572: // Record the length of the combined runs; if i is the 3rd-last
573: // run now, also slide over the last run (which isn't involved
574: // in this merge). The current run i+1 goes away in any case.
575: if (i == this .n - 3) {
576: this .len[i + 1] = this .len[i + 2];
577: this .base[i + 1] = this .base[i + 2];
578: }
579: this .len[i] = na + nb;
580: --this .n;
581:
582: // Where does b start in a? Elements in a before that can be
583: // ignored (already in place).
584: int k = gallop_right(this .data[pb], this .data, pa, na, 0);
585: pa += k;
586: na -= k;
587: if (na == 0)
588: return;
589:
590: // Where does a end in b? Elements in b after that can be
591: // ignored (already in place).
592: nb = gallop_left(this .data[pa + na - 1], this .data, pb, nb,
593: nb - 1);
594: if (nb == 0)
595: return;
596:
597: // Merge what remains of the runs, using a temp array with
598: // min(na, nb) elements.
599: if (na <= nb)
600: merge_lo(pa, na, pb, nb);
601: else
602: merge_hi(pa, na, pb, nb);
603: }
604:
605: /* Examine the stack of runs waiting to be merged, merging adjacent runs
606: * until the stack invariants are re-established:
607: *
608: * 1. len[-3] > len[-2] + len[-1]
609: * 2. len[-2] > len[-1]
610: *
611: * See listsort.txt for more info.
612: */
613: void merge_collapse() {
614: while (this .n > 1) {
615: int localN = this .n - 2;
616: if (localN > 0
617: && this .len[localN - 1] <= this .len[localN]
618: + this .len[localN + 1]) {
619: if (this .len[localN - 1] < this .len[localN + 1])
620: --localN;
621: merge_at(localN);
622: } else if (this .len[localN] <= this .len[localN + 1]) {
623: merge_at(localN);
624: } else {
625: break;
626: }
627: }
628: }
629:
630: /* Regardless of invariants, merge all runs on the stack until only one
631: * remains. This is used at the end of the mergesort.
632: *
633: * Returns 0 on success, -1 on error.
634: */
635: void merge_force_collapse() {
636: while (this .n > 1) {
637: int localN = this .n - 2;
638: if (localN > 0
639: && this .len[localN - 1] < this .len[localN + 1])
640: --localN;
641: merge_at(localN);
642: }
643: }
644:
645: /* Compute a good value for the minimum run length; natural runs shorter
646: * than this are boosted artificially via binary insertion.
647: *
648: * If n < 64, return n (it's too small to bother with fancy stuff).
649: * Else if n is an exact power of 2, return 32.
650: * Else return an int k, 32 <= k <= 64, such that n/k is close to, but
651: * strictly less than, an exact power of 2.
652: *
653: * See listsort.txt for more info.
654: */
655: int merge_compute_minrun(int localN) {
656: int r = 0; // becomes 1 if any 1 bits are shifted off
657:
658: //assert_(n >= 0);
659: while (localN >= 64) {
660: r |= localN & 1;
661: localN >>= 1;
662: }
663: return localN + r;
664: }
665:
666: void assert_(boolean expr) {
667: if (!expr)
668: throw new RuntimeException("assert");
669: }
670:
671: private boolean iflt(PyObject x, PyObject y) {
672: //assert_(x != null);
673: //assert_(y != null);
674:
675: if (this .compare == null) {
676: /* NOTE: we rely on the fact here that the sorting algorithm
677: only ever checks whether k<0, i.e., whether x<y. So we
678: invoke the rich comparison function with _lt ('<'), and
679: return -1 when it returns true and 0 when it returns
680: false. */
681: return x._lt(y).__nonzero__();
682: }
683:
684: PyObject ret = this .compare.__call__(x, y);
685:
686: if (ret instanceof PyInteger) {
687: int v = ((PyInteger) ret).getValue();
688: return v < 0;
689: }
690: throw Py.TypeError("comparision function must return int");
691: }
692:
693: void reverse_slice(int lo, int hi) {
694: --hi;
695: while (lo < hi) {
696: PyObject t = this .data[lo];
697: this .data[lo] = this .data[hi];
698: this .data[hi] = t;
699: ++lo;
700: --hi;
701: }
702: }
703:
704: /*
705: * binarysort is the best method for sorting small arrays: it does
706: * few compares, but can do data movement quadratic in the number of
707: * elements.
708: * [lo, hi) is a contiguous slice of a list, and is sorted via
709: * binary insertion. This sort is stable.
710: * On entry, must have lo <= start <= hi, and that [lo, start) is already
711: * sorted (pass start == lo if you don't know!).
712: * If islt() complains return -1, else 0.
713: * Even in case of error, the output slice will be some permutation of
714: * the input (nothing is lost or duplicated).
715: */
716: void binarysort(int lo, int hi, int start) {
717: //debug("binarysort: lo:" + lo + " hi:" + hi + " start:" + start);
718: int p;
719:
720: //assert_(lo <= start && start <= hi);
721: /* assert [lo, start) is sorted */
722: if (lo == start)
723: ++start;
724: for (; start < hi; ++start) {
725: /* set l to where *start belongs */
726: int l = lo;
727: int r = start;
728: PyObject pivot = this .data[r];
729: // Invariants:
730: // pivot >= all in [lo, l).
731: // pivot < all in [r, start).
732: // The second is vacuously true at the start.
733: //assert_(l < r);
734: do {
735: p = l + ((r - l) >> 1);
736: if (iflt(pivot, this .data[p]))
737: r = p;
738: else
739: l = p + 1;
740: } while (l < r);
741: //assert_(l == r);
742: // The invariants still hold, so pivot >= all in [lo, l) and
743: // pivot < all in [l, start), so pivot belongs at l. Note
744: // that if there are elements equal to pivot, l points to the
745: // first slot after them -- that's why this sort is stable.
746: // Slide over to make room.
747: for (p = start; p > l; --p)
748: this .data[p] = this .data[p - 1];
749: this .data[l] = pivot;
750: }
751: //dump_data("binsort", lo, hi - lo);
752: }
753:
754: /* //debugging methods.
755: private void dump_data(String txt, int lo, int n) {
756: System.out.print(txt + ":");
757: for (int i = 0; i < n; i++)
758: System.out.print(data[lo + i] + " ");
759: System.out.println();
760: }
761: private void debug(String str) {
762: //System.out.println(str);
763: }
764: */
765: }
|