ager@chromium.org | 9258b6b | 2008-09-11 09:11:10 +0000 | [diff] [blame] | 1 | // Copyright 2008 the V8 project authors. All rights reserved. |
mads.s.ager@gmail.com | 9a4089a | 2008-09-01 08:55:01 +0000 | [diff] [blame] | 2 | // Redistribution and use in source and binary forms, with or without |
| 3 | // modification, are permitted provided that the following conditions are |
| 4 | // met: |
| 5 | // |
| 6 | // * Redistributions of source code must retain the above copyright |
| 7 | // notice, this list of conditions and the following disclaimer. |
| 8 | // * Redistributions in binary form must reproduce the above |
| 9 | // copyright notice, this list of conditions and the following |
| 10 | // disclaimer in the documentation and/or other materials provided |
| 11 | // with the distribution. |
| 12 | // * Neither the name of Google Inc. nor the names of its |
| 13 | // contributors may be used to endorse or promote products derived |
| 14 | // from this software without specific prior written permission. |
| 15 | // |
| 16 | // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 17 | // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 18 | // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 19 | // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 20 | // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 21 | // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| 22 | // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| 23 | // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| 24 | // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| 25 | // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| 26 | // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 27 | |
kasperl@chromium.org | b912362 | 2008-09-17 14:05:56 +0000 | [diff] [blame] | 28 | // Flags: --allow-natives-syntax |
| 29 | |
mads.s.ager@gmail.com | 9a4089a | 2008-09-01 08:55:01 +0000 | [diff] [blame] | 30 | // Test array sort. |
| 31 | |
| 32 | // Test counter-intuitive default number sorting. |
| 33 | function TestNumberSort() { |
| 34 | var a = [ 200, 45, 7 ]; |
ager@chromium.org | 9258b6b | 2008-09-11 09:11:10 +0000 | [diff] [blame] | 35 | |
| 36 | // Default sort converts each element to string and orders |
mads.s.ager@gmail.com | 9a4089a | 2008-09-01 08:55:01 +0000 | [diff] [blame] | 37 | // lexicographically. |
| 38 | a.sort(); |
| 39 | assertArrayEquals([ 200, 45, 7 ], a); |
| 40 | // Sort numbers by value using a compare functions. |
| 41 | a.sort(function(x, y) { return x - y; }); |
| 42 | assertArrayEquals([ 7, 45, 200 ], a); |
ager@chromium.org | 9258b6b | 2008-09-11 09:11:10 +0000 | [diff] [blame] | 43 | |
| 44 | // Default sort on negative numbers. |
| 45 | a = [-12345,-123,-1234,-123456]; |
| 46 | a.sort(); |
| 47 | assertArrayEquals([-123,-1234,-12345,-123456], a); |
| 48 | |
| 49 | // Default sort on negative and non-negative numbers. |
| 50 | a = [123456,0,-12345,-123,123,1234,-1234,0,12345,-123456]; |
| 51 | a.sort(); |
| 52 | assertArrayEquals([-123,-1234,-12345,-123456,0,0,123,1234,12345,123456], a); |
| 53 | |
kasperl@chromium.org | b912362 | 2008-09-17 14:05:56 +0000 | [diff] [blame] | 54 | // Tricky case avoiding integer overflow in Runtime_SmiLexicographicCompare. |
| 55 | a = [9, 1000000000].sort(); |
| 56 | assertArrayEquals([1000000000, 9], a); |
| 57 | a = [1000000000, 1].sort(); |
| 58 | assertArrayEquals([1, 1000000000], a); |
| 59 | a = [1000000000, 0].sort(); |
| 60 | assertArrayEquals([0, 1000000000], a); |
| 61 | |
| 62 | // One string is a prefix of the other. |
| 63 | a = [1230, 123].sort(); |
| 64 | assertArrayEquals([123, 1230], a); |
| 65 | a = [1231, 123].sort(); |
| 66 | assertArrayEquals([123, 1231], a); |
| 67 | |
ager@chromium.org | 9258b6b | 2008-09-11 09:11:10 +0000 | [diff] [blame] | 68 | // Default sort on Smis and non-Smis. |
| 69 | a = [1000000000, 10000000000, 1000000001, -1000000000, -10000000000, -1000000001]; |
| 70 | a.sort(); |
| 71 | assertArrayEquals([-1000000000, -10000000000, -1000000001, 1000000000, 10000000000, 1000000001], a); |
kasperl@chromium.org | b912362 | 2008-09-17 14:05:56 +0000 | [diff] [blame] | 72 | |
| 73 | |
| 74 | for (var xb = 1; xb <= 1000 * 1000 * 1000; xb *= 10) { |
| 75 | for (var xf = 0; xf <= 9; xf++) { |
| 76 | for (var xo = -1; xo <= 1; xo++) { |
| 77 | for (var yb = 1; yb <= 1000 * 1000 * 1000; yb *= 10) { |
| 78 | for (var yf = 0; yf <= 9; yf++) { |
| 79 | for (var yo = -1; yo <= 1; yo++) { |
| 80 | var x = xb * xf + xo; |
| 81 | var y = yb * yf + yo; |
| 82 | if (!%_IsSmi(x)) continue; |
| 83 | if (!%_IsSmi(y)) continue; |
| 84 | var lex = %SmiLexicographicCompare(x, y); |
| 85 | if (lex < 0) lex = -1; |
| 86 | if (lex > 0) lex = 1; |
| 87 | assertEquals(lex, (x == y) ? 0 : ((x + "") < (y + "") ? -1 : 1), x + " < " + y); |
| 88 | } |
| 89 | } |
| 90 | } |
| 91 | } |
| 92 | } |
| 93 | } |
mads.s.ager@gmail.com | 9a4089a | 2008-09-01 08:55:01 +0000 | [diff] [blame] | 94 | } |
| 95 | |
| 96 | TestNumberSort(); |
| 97 | |
| 98 | |
| 99 | // Test lexicographical string sorting. |
| 100 | function TestStringSort() { |
| 101 | var a = [ "cc", "c", "aa", "a", "bb", "b", "ab", "ac" ]; |
| 102 | a.sort(); |
| 103 | assertArrayEquals([ "a", "aa", "ab", "ac", "b", "bb", "c", "cc" ], a); |
| 104 | } |
| 105 | |
| 106 | TestStringSort(); |
| 107 | |
| 108 | |
| 109 | // Test object sorting. Calls toString on each element and sorts |
| 110 | // lexicographically. |
| 111 | function TestObjectSort() { |
| 112 | var obj0 = { toString: function() { return "a"; } }; |
| 113 | var obj1 = { toString: function() { return "b"; } }; |
| 114 | var obj2 = { toString: function() { return "c"; } }; |
| 115 | var a = [ obj2, obj0, obj1 ]; |
| 116 | a.sort(); |
| 117 | assertArrayEquals([ obj0, obj1, obj2 ], a); |
| 118 | } |
| 119 | |
| 120 | TestObjectSort(); |
kasperl@chromium.org | 41044eb | 2008-10-06 08:24:46 +0000 | [diff] [blame] | 121 | |
| 122 | // Test array sorting with holes in the array. |
| 123 | function TestArraySortingWithHoles() { |
| 124 | var a = []; |
| 125 | a[4] = "18"; |
| 126 | a[10] = "12"; |
| 127 | a.sort(); |
| 128 | assertEquals(11, a.length); |
| 129 | assertEquals("12", a[0]); |
| 130 | assertEquals("18", a[1]); |
| 131 | } |
| 132 | |
| 133 | TestArraySortingWithHoles(); |
| 134 | |
| 135 | // Test array sorting with undefined elemeents in the array. |
| 136 | function TestArraySortingWithUndefined() { |
ager@chromium.org | 7c537e2 | 2008-10-16 08:43:32 +0000 | [diff] [blame] | 137 | var a = [ 3, void 0, 2 ]; |
kasperl@chromium.org | 41044eb | 2008-10-06 08:24:46 +0000 | [diff] [blame] | 138 | a.sort(); |
ager@chromium.org | 7c537e2 | 2008-10-16 08:43:32 +0000 | [diff] [blame] | 139 | assertArrayEquals([ 2, 3, void 0 ], a); |
kasperl@chromium.org | 41044eb | 2008-10-06 08:24:46 +0000 | [diff] [blame] | 140 | } |
| 141 | |
| 142 | TestArraySortingWithUndefined(); |
ager@chromium.org | 7c537e2 | 2008-10-16 08:43:32 +0000 | [diff] [blame] | 143 | |
| 144 | // Test that sorting using an unsound comparison function still gives a |
| 145 | // sane result, i.e. it terminates without error and retains the elements |
| 146 | // in the array. |
| 147 | function TestArraySortingWithUnsoundComparisonFunction() { |
| 148 | var a = [ 3, void 0, 2 ]; |
| 149 | a.sort(function(x, y) { return 1; }); |
| 150 | a.sort(); |
| 151 | assertArrayEquals([ 2, 3, void 0 ], a); |
| 152 | } |
| 153 | |
| 154 | TestArraySortingWithUnsoundComparisonFunction(); |