?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
codegen: Fix floating reference regression with Variants
[vala-gnome.git] / gee / timsort.vala
blob2db14fd3edeaeb73e6bdd2e7dafb8252c258b29f
1 /* timsort.vala
2 *
3 * Copyright (C) 2009 Didier Villevalois
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
9
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
14
15 * You should have received a copy of the GNU Lesser General Public
16 * License along with this library; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
18 *
19 * Author:
20 * Didier 'Ptitjes Villevalois <ptitjes@free.fr>
21 */
22
23 /**
24 * A stable, adaptive, iterative mergesort that requires far fewer than n*lg(n)
25 * comparisons when running on partially sorted arrays, while offering
26 * performance comparable to a traditional mergesort when run on random arrays.
27 * Like all proper mergesorts, this sort is stable and runs O(n*log(n)) time
28 * (worst case). In the worst case, this sort requires temporary storage space
29 * for n/2 object references; in the best case, it requires only a small
30 * constant amount of space.
31 *
32 * This implementation was adapted from Tim Peters's list sort for Python,
33 * which is described in detail here:
34 * [[http://svn.python.org/projects/python/trunk/Objects/listsort.txt]]
35 *
36 * Tim's C code may be found here:
37 * [[http://svn.python.org/projects/python/trunk/Objects/listobject.c]]
38 *
39 * The underlying techniques are described in this paper (and may have even
40 * earlier origins):
41 *
42 * "Optimistic Sorting and Information Theoretic Complexity"
43 * Peter McIlroy
44 * SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms), pp
45 * 467-474, Austin, Texas, 25-27 January 1993.
46 */
47 internal class Vala.TimSort<G> {
48
49 public static void sort<G> (List<G> list, CompareDataFunc<G> compare) {
50 if (list is ArrayList) {
51 TimSort.sort_arraylist<G> ((ArrayList<G>) list, compare);
52 } else {
53 TimSort.sort_list<G> (list, compare);
54 }
55 }
56
57 private static void sort_list<G> (List<G> list, CompareDataFunc<G> compare) {
58 TimSort<G> helper = new TimSort<G> ();
59
60 helper.list_collection = list;
61 helper.array = list.to_array ();
62 helper.list = helper.array;
63 helper.index = 0;
64 helper.size = list.size;
65 helper.compare = compare;
66
67 helper.do_sort ();
68
69 // TODO Use a list iterator and use iter.set (item)
70 list.clear ();
71 foreach (G item in helper.array) {
72 list.add (item);
73 }
74 }
75
76 private static void sort_arraylist<G> (ArrayList<G> list, CompareDataFunc<G> compare) {
77 TimSort<G> helper = new TimSort<G> ();
78
79 helper.list_collection = list;
80 helper.list = list._items;
81 helper.index = 0;
82 helper.size = list._size;
83 helper.compare = compare;
84
85 helper.do_sort ();
86 }
87
88 private const int MINIMUM_GALLOP = 7;
89
90 private List<G> list_collection;
91 private G[] array;
92 private void** list;
93 private int index;
94 private int size;
95 private Slice<G>[] pending;
96 private int minimum_gallop;
97 private unowned CompareDataFunc<G> compare;
98
99 private void do_sort () {
100 if (size < 2) {
101 return;
102 }
103
104 pending = new Slice<G>[0];
105 minimum_gallop = MINIMUM_GALLOP;
106
107 Slice<G> remaining = new Slice<G> (list, index, size);
108 int minimum_length = compute_minimum_run_length (remaining.length);
109
110 while (remaining.length > 0) {
111 // Get the next run
112 bool descending;
113 Slice<G> run = compute_longest_run (remaining, out descending);
114 #if DEBUG
115 message ("New run (%d, %d) %s", run.index, run.length,
116 descending ? "descending" : "ascending");
117 #endif
118 if (descending) {
119 run.reverse ();
120 }
121
122 // Extend it to minimum_length, if needed
123 if (run.length < minimum_length) {
124 int sorted_count = run.length;
125 run.length = int.min (minimum_length, remaining.length);
126 insertion_sort (run, sorted_count);
127 #if DEBUG
128 message ("Extended to (%d, %d) and sorted from index %d",
129 run.index, run.length, sorted_count);
130 #endif
131 }
132
133 // Move remaining after run
134 remaining.shorten_start (run.length);
135
136 // Add run to pending runs and try to merge
137 pending += (owned) run;
138 merge_collapse ();
139 }
140
141 assert (remaining.index == size);
142
143 merge_force_collapse ();
144
145 assert (pending.length == 1);
146 assert (pending[0].index == 0);
147 assert (pending[0].length == size);
148 }
149
150 private delegate bool LowerFunc (G left, G right);
151
152 private inline bool lower_than (G left, G right) {
153 return compare (left, right) < 0;
154 }
155
156 private inline bool lower_than_or_equal_to (G left, G right) {
157 return compare (left, right) <= 0;
158 }
159
160 private int compute_minimum_run_length (int length) {
161 int run_length = 0;
162 while (length >= 64) {
163 run_length |= length & 1;
164 length >>= 1;
165 }
166 return length + run_length;
167 }
168
169 private Slice<G> compute_longest_run (Slice<G> a, out bool descending) {
170 int run_length;
171 if (a.length <= 1) {
172 run_length = a.length;
173 descending = false;
174 } else {
175 run_length = 2;
176 if (lower_than (a.list[a.index + 1], a.list[a.index])) {
177 descending = true;
178 for (int i = a.index + 2; i < a.index + a.length; i++) {
179 if (lower_than (a.list[i], a.list[i-1])) {
180 run_length++;
181 } else {
182 break;
183 }
184 }
185 } else {
186 descending = false;
187 for (int i = a.index + 2; i < a.index + a.length; i++) {
188 if (lower_than (a.list[i], a.list[i-1])) {
189 break;
190 } else {
191 run_length++;
192 }
193 }
194 }
195 }
196 return new Slice<G> (a.list, a.index, run_length);
197 }
198
199 private void insertion_sort (Slice<G> a, int offset) {
200 #if DEBUG
201 message ("Sorting (%d, %d) at %d", a.index, a.length, offset);
202 #endif
203 for (int start = a.index + offset; start < a.index + a.length; start++) {
204 int left = a.index;
205 int right = start;
206 void* pivot = a.list[right];
207
208 while (left < right) {
209 int p = left + ((right - left) >> 1);
210 if (lower_than (pivot, a.list[p])) {
211 right = p;
212 } else {
213 left = p + 1;
214 }
215 }
216 assert (left == right);
217
218 Memory.move (&a.list[left + 1], &a.list[left], sizeof (G) * (start - left));
219 a.list[left] = pivot;
220 }
221 }
222
223 private void merge_collapse () {
224 #if DEBUG
225 message ("Merge Collapse");
226 #endif
227 int count = pending.length;
228 while (count > 1) {
229 #if DEBUG
230 message ("Pending count: %d", count);
231 if (count >= 3) {
232 message ("pending[count-3]=%p; pending[count-2]=%p; pending[count-1]=%p",
233 pending[count-3], pending[count-2], pending[count-1]);
234 }
235 #endif
236 if (count >= 3 && pending[count-3].length <= pending[count-2].length + pending[count-1].length) {
237 if (pending[count-3].length < pending[count-1].length) {
238 merge_at (count-3);
239 } else {
240 merge_at (count-2);
241 }
242 } else if (pending[count-2].length <= pending[count-1].length) {
243 merge_at (count-2);
244 } else {
245 break;
246 }
247 count = pending.length;
248 #if DEBUG
249 message ("New pending count: %d", count);
250 #endif
251 }
252 }
253
254 private void merge_force_collapse () {
255 #if DEBUG
256 message ("Merge Force Collapse");
257 #endif
258 int count = pending.length;
259 #if DEBUG
260 message ("Pending count: %d", count);
261 #endif
262 while (count > 1) {
263 if (count >= 3 && pending[count-3].length < pending[count-1].length) {
264 merge_at (count-3);
265 } else {
266 merge_at (count-2);
267 }
268 count = pending.length;
269 #if DEBUG
270 message ("New pending count: %d", count);
271 #endif
272 }
273 }
274
275 private void merge_at (int index) {
276 #if DEBUG
277 message ("Merge at %d", index);
278 #endif
279 Slice<G> a = (owned) pending[index];
280 Slice<G> b = (owned) pending[index + 1];
281
282 assert (a.length > 0);
283 assert (b.length > 0);
284 assert (a.index + a.length == b.index);
285
286 pending[index] = new Slice<G> (list, a.index, a.length + b.length);
287 pending.move (index + 2, index + 1, pending.length - index - 2);
288 pending.length -= 1;
289
290 int sorted_count = gallop_rightmost (b.peek_first (), a, 0);
291 a.shorten_start (sorted_count);
292 if (a.length == 0) {
293 return;
294 }
295
296 b.length = gallop_leftmost (a.peek_last (), b, b.length - 1);
297 if (b.length == 0) {
298 return;
299 }
300
301 if (a.length <= b.length) {
302 merge_low ((owned) a, (owned) b);
303 } else {
304 merge_high ((owned) a, (owned) b);
305 }
306 }
307
308 private int gallop_leftmost (G key, Slice<G> a, int hint) {
309 #if DEBUG
310 message ("Galop leftmost in (%d, %d), hint=%d", a.index, a.length, hint);
311 #endif
312 assert (0 <= hint);
313 assert (hint < a.length);
314
315 int p = a.index + hint;
316 int last_offset = 0;
317 int offset = 1;
318 if (lower_than (a.list[p], key)) {
319 int max_offset = a.length - hint;
320 while (offset < max_offset) {
321 if (lower_than (a.list[p + offset], key)) {
322 last_offset = offset;
323 offset <<= 1;
324 offset++;
325 } else {
326 break;
327 }
328 }
329
330 if (offset > max_offset) {
331 offset = max_offset;
332 }
333
334 last_offset = hint + last_offset;
335 offset = hint + offset;
336 } else {
337 int max_offset = hint + 1;
338 while (offset < max_offset) {
339 if (lower_than (a.list[p - offset], key)) {
340 break;
341 } else {
342 last_offset = offset;
343 offset <<= 1;
344 offset++;
345 }
346 }
347
348 if (offset > max_offset) {
349 offset = max_offset;
350 }
351
352 int temp_last_offset = last_offset;
353 int temp_offset = offset;
354 last_offset = hint - temp_offset;
355 offset = hint - temp_last_offset;
356 }
357
358 assert (-1 <= last_offset);
359 assert (last_offset < offset);
360 assert (offset <= a.length);
361
362 last_offset += 1;
363 while (last_offset < offset) {
364 int m = last_offset + ((offset - last_offset) >> 1);
365 if (lower_than (a.list[a.index + m], key)) {
366 last_offset = m + 1;
367 } else {
368 offset = m;
369 }
370 }
371
372 assert (last_offset == offset);
373 return offset;
374 }
375
376 private int gallop_rightmost (G key, Slice<G> a, int hint) {
377 #if DEBUG
378 message ("Galop rightmost in (%d, %d), hint=%d", a.index, a.length, hint);
379 #endif
380 assert (0 <= hint);
381 assert (hint < a.length);
382
383 int p = a.index + hint;
384 int last_offset = 0;
385 int offset = 1;
386 if (lower_than_or_equal_to (a.list[p], key)) {
387 int max_offset = a.length - hint;
388 while (offset < max_offset) {
389 if (lower_than_or_equal_to (a.list[p + offset], key)) {
390 last_offset = offset;
391 offset <<= 1;
392 offset++;
393 } else {
394 break;
395 }
396 }
397
398 if (offset > max_offset) {
399 offset = max_offset;
400 }
401
402 last_offset = hint + last_offset;
403 offset = hint + offset;
404 } else {
405 int max_offset = hint + 1;
406 while (offset < max_offset) {
407 if (lower_than_or_equal_to (a.list[p - offset], key)) {
408 break;
409 } else {
410 last_offset = offset;
411 offset <<= 1;
412 offset++;
413 }
414 }
415
416 if (offset > max_offset) {
417 offset = max_offset;
418 }
419
420 int temp_last_offset = last_offset;
421 int temp_offset = offset;
422 last_offset = hint - temp_offset;
423 offset = hint - temp_last_offset;
424 }
425
426 assert (-1 <= last_offset);
427 assert (last_offset < offset);
428 assert (offset <= a.length);
429
430 last_offset += 1;
431 while (last_offset < offset) {
432 int m = last_offset + ((offset - last_offset) >> 1);
433 if (lower_than_or_equal_to (a.list[a.index + m], key)) {
434 last_offset = m + 1;
435 } else {
436 offset = m;
437 }
438 }
439
440 assert (last_offset == offset);
441 return offset;
442 }
443
444 private void merge_low (owned Slice<G> a, owned Slice<G> b) {
445 #if DEBUG
446 message ("Merge low (%d, %d) (%d, %d)", a.index, a.length, b.index, b.length);
447 #endif
448 assert (a.length > 0);
449 assert (b.length > 0);
450 assert (a.index + a.length == b.index);
451
452 int minimum_gallop = this.minimum_gallop;
453 int dest = a.index;
454 a.copy ();
455
456 try {
457 list[dest++] = b.pop_first ();
458 if (a.length == 1 || b.length == 0) {
459 return;
460 }
461
462 while (true) {
463 int a_count = 0;
464 int b_count = 0;
465
466 while (true) {
467 if (lower_than (b.peek_first (), a.peek_first ())) {
468 list[dest++] = b.pop_first ();
469 if (b.length == 0) {
470 return;
471 }
472
473 b_count++;
474 a_count = 0;
475 if (b_count >= minimum_gallop) {
476 break;
477 }
478 } else {
479 list[dest++] = a.pop_first ();
480 if (a.length == 1) {
481 return;
482 }
483
484 a_count++;
485 b_count = 0;
486 if (a_count >= minimum_gallop) {
487 break;
488 }
489 }
490 }
491
492 minimum_gallop++;
493
494 while (true) {
495 minimum_gallop -= (minimum_gallop > 1 ? 1 : 0);
496 this.minimum_gallop = minimum_gallop;
497
498 a_count = gallop_rightmost (b.peek_first (), a, 0);
499 a.merge_in (list, a.index, dest, a_count);
500 dest += a_count;
501 a.shorten_start (a_count);
502 if (a.length <= 1) {
503 return;
504 }
505
506 list[dest++] = b.pop_first ();
507 if (b.length == 0) {
508 return;
509 }
510
511 b_count = gallop_leftmost (a.peek_first (), b, 0);
512 b.merge_in (list, b.index, dest, b_count);
513 dest += b_count;
514 b.shorten_start (b_count);
515 if (b.length == 0) {
516 return;
517 }
518
519 list[dest++] = a.pop_first ();
520 if (a.length == 1) {
521 return;
522 }
523
524 if (a_count < MINIMUM_GALLOP && b_count < MINIMUM_GALLOP) {
525 break;
526 }
527 }
528
529 minimum_gallop++;
530 this.minimum_gallop = minimum_gallop;
531 }
532 } finally {
533 assert (a.length >= 0);
534 assert (b.length >= 0);
535 b.merge_in (list, b.index, dest, b.length);
536 a.merge_in (list, a.index, dest + b.length, a.length);
537 }
538 }
539
540 private void merge_high (owned Slice<G> a, owned Slice<G> b) {
541 #if DEBUG
542 message ("Merge high (%d, %d) (%d, %d)", a.index, a.length, b.index, b.length);
543 #endif
544 assert (a.length > 0);
545 assert (b.length > 0);
546 assert (a.index + a.length == b.index);
547
548 int minimum_gallop = this.minimum_gallop;
549 int dest = b.index + b.length;
550 b.copy ();
551
552 try {
553 list[--dest] = a.pop_last ();
554 if (a.length == 0 || b.length == 1) {
555 return;
556 }
557
558 while (true) {
559 int a_count = 0;
560 int b_count = 0;
561
562 while (true) {
563 if (lower_than (b.peek_last (), a.peek_last ())) {
564 list[--dest] = a.pop_last ();
565 if (a.length == 0) {
566 return;
567 }
568
569 a_count++;
570 b_count = 0;
571 if (a_count >= minimum_gallop) {
572 break;
573 }
574 } else {
575 list[--dest] = b.pop_last ();
576 if (b.length == 1) {
577 return;
578 }
579
580 b_count++;
581 a_count = 0;
582 if (b_count >= minimum_gallop) {
583 break;
584 }
585 }
586 }
587
588 minimum_gallop++;
589
590 while (true) {
591 minimum_gallop -= (minimum_gallop > 1 ? 1 : 0);
592 this.minimum_gallop = minimum_gallop;
593
594 int k = gallop_rightmost (b.peek_last (), a, a.length - 1);
595 a_count = a.length - k;
596 a.merge_in_reversed (list, a.index + k, dest - a_count, a_count);
597 dest -= a_count;
598 a.shorten_end (a_count);
599 if (a.length == 0) {
600 return;
601 }
602
603 list[--dest] = b.pop_last ();
604 if (b.length == 1) {
605 return;
606 }
607
608 k = gallop_leftmost (a.peek_last (), b, b.length - 1);
609 b_count = b.length - k;
610 b.merge_in_reversed (list, b.index + k, dest - b_count, b_count);
611 dest -= b_count;
612 b.shorten_end (b_count);
613 if (b.length <= 1) {
614 return;
615 }
616
617 list[--dest] = a.pop_last ();
618 if (a.length == 0) {
619 return;
620 }
621
622 if (a_count < MINIMUM_GALLOP && b_count < MINIMUM_GALLOP) {
623 break;
624 }
625 }
626
627 minimum_gallop++;
628 this.minimum_gallop = minimum_gallop;
629 }
630 } finally {
631 assert (a.length >= 0);
632 assert (b.length >= 0);
633 a.merge_in_reversed (list, a.index, dest - a.length, a.length);
634 b.merge_in_reversed (list, b.index, dest - a.length - b.length, b.length);
635 }
636 }
637
638 [Compact]
639 private class Slice<G> {
640
641 public void** list;
642 public void** new_list;
643 public int index;
644 public int length;
645
646 public Slice (void** list, int index, int length) {
647 this.list = list;
648 this.index = index;
649 this.length = length;
650 }
651
652 ~Slice () {
653 if (new_list != null)
654 free (new_list);
655 }
656
657 public void copy () {
658 new_list = Memory.dup (&list[index], (uint) sizeof (G) * length);
659 list = new_list;
660 index = 0;
661 }
662
663 public inline void merge_in (void** dest_array, int index, int dest_index, int count) {
664 Memory.move (&dest_array[dest_index], &list[index], sizeof (G) * count);
665 }
666
667 public inline void merge_in_reversed (void** dest_array, int index, int dest_index, int count) {
668 Memory.move (&dest_array[dest_index], &list[index], sizeof (G) * count);
669 }
670
671 public inline void shorten_start (int n) {
672 index += n;
673 length -= n;
674 }
675
676 public inline void shorten_end (int n) {
677 length -= n;
678 }
679
680 public inline void* pop_first () {
681 length--;
682 return list[index++];
683 }
684
685 public inline void* pop_last () {
686 length--;
687 return list[index + length];
688 }
689
690 public inline unowned void* peek_first () {
691 return list[index];
692 }
693
694 public inline unowned void* peek_last () {
695 return list[index + length - 1];
696 }
697
698 public void reverse () {
699 int low = index;
700 int high = index + length - 1;
701 while (low < high) {
702 swap (low++, high--);
703 }
704 }
705
706 private inline void swap (int i, int j) {
707 void* temp = list[i];
708 list[i] = list[j];
709 list[j] = temp;
710 }
711 }
712 }
713
Gnome vala