| OLD | NEW |
| 1 // Copyright 2006-2008 the V8 project authors. All rights reserved. | 1 // Copyright 2006-2008 the V8 project authors. All rights reserved. |
| 2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
| 3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
| 4 // met: | 4 // met: |
| 5 // | 5 // |
| 6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
| 7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
| 8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
| 9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
| 10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
| (...skipping 654 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 665 x = ToString(x); | 665 x = ToString(x); |
| 666 y = ToString(y); | 666 y = ToString(y); |
| 667 if (x == y) return 0; | 667 if (x == y) return 0; |
| 668 else return x < y ? -1 : 1; | 668 else return x < y ? -1 : 1; |
| 669 }; | 669 }; |
| 670 | 670 |
| 671 function QuickSort(a, from, to) { | 671 function QuickSort(a, from, to) { |
| 672 if (from >= to - 1) return; | 672 if (from >= to - 1) return; |
| 673 var pivot_index = $floor($random() * (to - from)) + from; | 673 var pivot_index = $floor($random() * (to - from)) + from; |
| 674 var pivot = a[pivot_index]; | 674 var pivot = a[pivot_index]; |
| 675 // Issue 95: Keep the pivot element out of the comparisons to avoid |
| 676 // infinite recursion if comparefn(pivot, pivot) != 0. |
| 675 a[pivot_index] = a[to - 1]; | 677 a[pivot_index] = a[to - 1]; |
| 676 a[to - 1] = pivot; | 678 a[to - 1] = pivot; |
| 677 var low_end = from; // Upper bound of the elements lower than pivot. | 679 var low_end = from; // Upper bound of the elements lower than pivot. |
| 678 var high_start = to - 1; // Lower bound of the elements greater than pivot. | 680 var high_start = to - 1; // Lower bound of the elements greater than pivot. |
| 679 for (var i = from; i < high_start; ) { | 681 for (var i = from; i < high_start; ) { |
| 680 var element = a[i]; | 682 var element = a[i]; |
| 681 var order = Compare(element, pivot); | 683 var order = Compare(element, pivot); |
| 682 if (order < 0) { | 684 if (order < 0) { |
| 683 a[i] = a[low_end]; | 685 a[i] = a[low_end]; |
| 684 a[low_end] = element; | 686 a[low_end] = element; |
| 685 low_end++; | 687 low_end++; |
| 686 i++; | 688 i++; |
| 687 } else if (order > 0) { | 689 } else if (order > 0) { |
| 688 high_start--; | 690 high_start--; |
| 689 a[i] = a[high_start]; | 691 a[i] = a[high_start]; |
| 690 a[high_start] = element; | 692 a[high_start] = element; |
| 691 } else { // order == 0 | 693 } else { // order == 0 |
| 692 i++; | 694 i++; |
| 693 } | 695 } |
| 694 } | 696 } |
| 697 // Restore the pivot element to its rightful place. |
| 695 a[to - 1] = a[high_start]; | 698 a[to - 1] = a[high_start]; |
| 696 a[high_start] = pivot; | 699 a[high_start] = pivot; |
| 697 high_start++; | 700 high_start++; |
| 698 QuickSort(a, from, low_end); | 701 QuickSort(a, from, low_end); |
| 699 QuickSort(a, high_start, to); | 702 QuickSort(a, high_start, to); |
| 700 } | 703 } |
| 701 | 704 |
| 702 var old_length = ToUint32(this.length); | 705 var old_length = ToUint32(this.length); |
| 703 | 706 |
| 704 %RemoveArrayHoles(this); | 707 %RemoveArrayHoles(this); |
| (...skipping 203 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 908 ArrayEvery: 1, | 911 ArrayEvery: 1, |
| 909 ArrayMap: 1, | 912 ArrayMap: 1, |
| 910 ArrayIndexOf: 1, | 913 ArrayIndexOf: 1, |
| 911 ArrayLastIndexOf: 1, | 914 ArrayLastIndexOf: 1, |
| 912 ArrayPush: 1 | 915 ArrayPush: 1 |
| 913 }); | 916 }); |
| 914 }; | 917 }; |
| 915 | 918 |
| 916 | 919 |
| 917 SetupArray(); | 920 SetupArray(); |
| OLD | NEW |