gee/timsort.vala

   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 Gee.TimSort<G> : Object {
  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 static 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 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