src/third_party/WebKit/LayoutTests/inspector/utilities.html

   1 <html>
   2 <head>
   3 <script src="../http/tests/inspector/inspector-test.js"></script>
   4 <script>
   5
   6 function test()
   7 {
   8     InspectorTest.runTestSuite([
   9         function orderedMergeIntersect(next)
  10         {
  11             function comparator(a, b)
  12             {
  13                 return a - b;
  14             }
  15             function count(a, x)
  16             {
  17                 return a.upperBound(x) - a.lowerBound(x);
  18             }
  19             function testAll(a, b)
  20             {
  21                 testOperation(a, b, a.mergeOrdered(b, comparator), Math.max, "U");
  22                 testOperation(a, b, a.intersectOrdered(b, comparator), Math.min, "x");
  23             }
  24             function testOperation(a, b, actual, checkOperation, opName)
  25             {
  26                 var allValues = a.concat(b).concat(actual);
  27                 for (var i = 0; i < allValues.length; ++i) {
  28                     var value = allValues[i];
  29                     expectedCount = checkOperation(count(a, value), count(b, value));
  30                     actualCount = count(actual, value);
  31                     InspectorTest.assertEquals(expectedCount, actualCount,
  32                         "Incorrect result for value: " + value + " at [" + a + "] " + opName + " [" + b + "] -> [" + actual + "]");
  33                 }
  34                 InspectorTest.assertEquals(JSON.stringify(actual.sort()), JSON.stringify(actual), "result array is ordered");
  35             }
  36             var testArrays = [
  37                 [], [],
  38                 [1], [],
  39                 [1, 2, 2, 2, 3], [],
  40                 [4, 5, 5, 8, 8], [1, 1, 1, 2, 6],
  41                 [1, 2, 2, 2, 2, 3, 3, 4], [2, 2, 2, 3, 3, 3, 3],
  42                 [1, 2, 3, 4, 5], [1, 2, 3]
  43             ];
  44             for (var i = 0; i < testArrays.length; i += 2) {
  45                 testAll(testArrays[i], testArrays[i + 1]);
  46                 testAll(testArrays[i + 1], testArrays[i]);
  47             }
  48             next();
  49         },
  50
  51         function binaryIndexOfTest(next)
  52         {
  53             var testArrays = [
  54                 [],
  55                 [1],
  56                 [1, 10],
  57                 [1, 10, 11, 12, 13, 14, 100],
  58                 [-100, -50, 0, 50, 100],
  59                 [-100, -14, -13, -12, -11, -10, -1]
  60             ];
  61
  62             function testArray(array)
  63             {
  64                 function comparator(a, b)
  65                 {
  66                     return a < b ? -1 : (a > b ? 1 : 0);
  67                 }
  68
  69                 for (var i = -100; i <= 100; ++i) {
  70                     var reference = array.indexOf(i);
  71                     var actual = array.binaryIndexOf(i, comparator);
  72                     InspectorTest.assertEquals(reference, actual, "binaryIndexOf");
  73                 }
  74                 return true;
  75             }
  76
  77             for (var i = 0, l = testArrays.length; i < l; ++i)
  78                 testArray(testArrays[i]);
  79             next();
  80         },
  81
  82         function lowerBoundTest(next)
  83         {
  84             var testArrays = [
  85                 [],
  86                 [1],
  87                 [-1, -1, 0, 0, 0, 0, 2, 3, 4, 4, 4, 7, 9, 9, 9]
  88             ];
  89
  90             function testArray(array, useComparator)
  91             {
  92                 function comparator(a, b)
  93                 {
  94                     return a < b ? -1 : (a > b ? 1 : 0);
  95                 }
  96
  97                 for (var value = -2; value <= 12; ++value) {
  98                     var index = useComparator ? array.lowerBound(value, comparator) : array.lowerBound(value);
  99                     InspectorTest.assertTrue(0 <= index && index <= array.length, "index is within bounds");
 100                     InspectorTest.assertTrue(index === 0 || array[index - 1] < value, "array[index - 1] < value");
 101                     InspectorTest.assertTrue(index === array.length || array[index] >= value, "array[index] >= value");
 102                 }
 103             }
 104
 105             for (var i = 0, l = testArrays.length; i < l; ++i) {
 106                 testArray(testArrays[i], false);
 107                 testArray(testArrays[i], true);
 108             }
 109             next();
 110         },
 111
 112         function upperBoundTest(next)
 113         {
 114             var testArrays = [
 115                 [],
 116                 [1],
 117                 [-1, -1, 0, 0, 0, 0, 2, 3, 4, 4, 4, 7, 9, 9, 9]
 118             ];
 119
 120             function testArray(array, useComparator)
 121             {
 122                 function comparator(a, b)
 123                 {
 124                     return a < b ? -1 : (a > b ? 1 : 0);
 125                 }
 126
 127                 for (var value = -2; value <= 12; ++value) {
 128                     var index = useComparator ? array.upperBound(value, comparator) : array.upperBound(value);
 129                     InspectorTest.assertTrue(0 <= index && index <= array.length, "index is within bounds");
 130                     InspectorTest.assertTrue(index === 0 || array[index - 1] <= value, "array[index - 1] <= value");
 131                     InspectorTest.assertTrue(index === array.length || array[index] > value, "array[index] > value");
 132                 }
 133             }
 134
 135             for (var i = 0, l = testArrays.length; i < l; ++i) {
 136                 testArray(testArrays[i], false);
 137                 testArray(testArrays[i], true);
 138             }
 139             next();
 140         },
 141
 142         function qselectTest(next)
 143         {
 144             var testArrays = [
 145                 [],
 146                 [0],
 147                 [0, 0, 0, 0, 0, 0, 0, 0],
 148                 [4, 3, 2, 1],
 149                 [1, 2, 3, 4, 5],
 150                 [-1, 3, 2, 7, 7, 7, 10, 12, 3, 4, -1, 2]
 151             ];
 152
 153             function testArray(array)
 154             {
 155                 function compare(a, b)
 156                 {
 157                     return a - b;
 158                 }
 159                 var sorted = array.slice(0).sort(compare);
 160
 161                 var reference = {
 162                     min: sorted[0],
 163                     median: sorted[Math.floor(sorted.length / 2)],
 164                     max: sorted[sorted.length - 1]
 165                 }
 166
 167                 var actual = {
 168                     min: array.slice(0).qselect(0),
 169                     median: array.slice(0).qselect(Math.floor(array.length / 2)),
 170                     max: array.slice(0).qselect(array.length - 1)
 171                 }
 172                 InspectorTest.addResult("Array: " + JSON.stringify(array));
 173                 InspectorTest.addResult("Reference: " + JSON.stringify(reference));
 174                 InspectorTest.addResult("Actual:    " + JSON.stringify(actual));
 175             }
 176             for (var i = 0, l = testArrays.length; i < l; ++i)
 177                 testArray(testArrays[i]);
 178             next();
 179         },
 180
 181         function sortRangeTest(next)
 182         {
 183             var testArrays = [
 184                 [],
 185                 [1],
 186                 [2, 1],
 187                 [6, 4, 2, 7, 10, 15, 1],
 188                 [10, 44, 3, 6, 56, 66, 10, 55, 32, 56, 2, 5]
 189             ];
 190
 191             function testArray(array)
 192             {
 193                 function comparator(a, b)
 194                 {
 195                     return a < b ? -1 : (a > b ? 1 : 0);
 196                 }
 197
 198                 function compareArrays(a, b, message)
 199                 {
 200                     InspectorTest.assertEquals(JSON.stringify(a), JSON.stringify(b), message);
 201                 }
 202
 203                 for (var left = 0, l = array.length - 1; left < l; ++left) {
 204                     for (var right = left, r = array.length; right < r; ++right) {
 205                         for (var first = left; first <= right; ++first) {
 206                             for (var count = 1, k = right - first + 1; count <= k; ++count) {
 207                                 var actual = array.slice(0);
 208                                 actual.sortRange(comparator, left, right, first, first + count - 1);
 209                                 compareArrays(array.slice(0, left), actual.slice(0, left), "left " + left + " " + right + " " + count);
 210                                 compareArrays(array.slice(right + 1), actual.slice(right + 1), "right " + left + " " + right + " " + count);
 211                                 var middle = array.slice(left, right + 1);
 212                                 middle.sort(comparator);
 213                                 compareArrays(middle.slice(first - left, first - left + count), actual.slice(first, first + count), "sorted " + left + " " + right + " " + first + " " + count);
 214                                 actualRest = actual.slice(first + count, right + 1);
 215                                 actualRest.sort(comparator);
 216                                 compareArrays(middle.slice(first - left + count), actualRest, "unsorted " + left + " " + right + " " + first + " " + count);
 217                             }
 218                         }
 219                     }
 220                 }
 221             }
 222
 223             for (var i = 0, len = testArrays.length; i < len; ++i)
 224                 testArray(testArrays[i]);
 225             next();
 226         },
 227
 228         function naturalOrderComparatorTest(next)
 229         {
 230             var testArray = [
 231                 "dup",
 232                 "a1",
 233                 "a4222",
 234                 "a91",
 235                 "a07",
 236                 "dup",
 237                 "a7",
 238                 "a007",
 239                 "abc00",
 240                 "abc0",
 241                 "abc",
 242                 "abcd",
 243                 "abc000",
 244                 "x10y20z30",
 245                 "x9y19z29",
 246                 "dup",
 247                 "x09y19z29",
 248                 "x10y22z23",
 249                 "x10y19z43",
 250                 "1",
 251                 "10",
 252                 "11",
 253                 "dup",
 254                 "2", "2", "2",
 255                 "555555",
 256                 "5",
 257                 "5555",
 258                 "dup",
 259             ];
 260
 261             for (var i = 0, n = testArray.length; i < n; ++i)
 262                 InspectorTest.assertEquals(0, String.naturalOrderComparator(testArray[i], testArray[i]), "comparing equal strings");
 263
 264             testArray.sort(String.naturalOrderComparator);
 265             InspectorTest.addResult("Sorted in natural order: [" + testArray.join(", ") + "]");
 266
 267             // Check comparator's transitivity.
 268             for (var i = 0, n = testArray.length; i < n; ++i) {
 269                 for (var j = 0; j < n; ++j) {
 270                     var a = testArray[i];
 271                     var b = testArray[j];
 272                     var diff = String.naturalOrderComparator(a, b);
 273                     if (diff === 0)
 274                         InspectorTest.assertEquals(a, b, "zero diff");
 275                     else if (diff < 0)
 276                         InspectorTest.assertTrue(i < j);
 277                     else
 278                         InspectorTest.assertTrue(i > j);
 279                 }
 280             }
 281             next();
 282         },
 283
 284         function stableSortPrimitiveTest(next)
 285         {
 286             InspectorTest.assertEquals("", [].stableSort().join(","));
 287             InspectorTest.assertEquals("1", [1].stableSort().join(","));
 288             InspectorTest.assertEquals("1,2", [2,1].stableSort().join(","));
 289             InspectorTest.assertEquals("1,1,1", [1,1,1].stableSort().join(","));
 290             InspectorTest.assertEquals("1,2,3,4", [1,2,3,4].stableSort().join(","));
 291
 292             function defaultComparator(a, b)
 293             {
 294                 return a < b ? -1 : (a > b ? 1 : 0);
 295             }
 296
 297             function strictNumberCmp(a, b)
 298             {
 299                 if (a !== b)
 300                     return false;
 301                 if (a)
 302                     return true;
 303                 return 1/a === 1/b; // Neg zero comparison.
 304             }
 305
 306             // The following fails with standard Array.sort()
 307             var original = [0,-0,0,-0,-0,-0,0,0,0,-0,0,-0,-0,-0,0,0];
 308             var sorted = original.slice(0).stableSort(defaultComparator);
 309             for (var i = 0; i < original.length; ++i)
 310                 InspectorTest.assertTrue(strictNumberCmp(original[i], sorted[i]), "Sorting negative zeros");
 311
 312             // Test sorted and backward-sorted arrays.
 313             var identity = [];
 314             var reverse = [];
 315             for (var i = 0; i < 100; ++i) {
 316                 identity[i] = i;
 317                 reverse[i] = -i;
 318             }
 319             identity.stableSort(defaultComparator);
 320             reverse.stableSort(defaultComparator);
 321             for (var i = 1; i < identity.length; ++i) {
 322                 InspectorTest.assertTrue(identity[i - 1] < identity[i], "identity");
 323                 InspectorTest.assertTrue(reverse[i - 1] < reverse[i], "reverse");
 324             }
 325
 326             next();
 327         },
 328
 329         function stableSortTest(next)
 330         {
 331             function Pair(key1, key2)
 332             {
 333                 this.key1 = key1;
 334                 this.key2 = key2;
 335             }
 336             Pair.prototype.toString = function() {
 337                 return "Pair(" + this.key1 + ", " + this.key2 + ")";
 338             }
 339
 340             var testArray = [
 341                 new Pair(1, 1),
 342                 new Pair(3, 31),
 343                 new Pair(3, 30),
 344                 new Pair(5, 55),
 345                 new Pair(5, 54),
 346                 new Pair(5, 57),
 347                 new Pair(4, 47),
 348                 new Pair(4, 46),
 349                 new Pair(4, 45),
 350                 new Pair(5, 52),
 351                 new Pair(5, 59),
 352                 new Pair(3, 37),
 353                 new Pair(3, 38),
 354                 new Pair(5, -58),
 355                 new Pair(5, 58),
 356                 new Pair(4, 41),
 357                 new Pair(4, 42),
 358                 new Pair(4, 43),
 359                 new Pair(3, 33),
 360                 new Pair(3, 32),
 361                 new Pair(9, 9),
 362             ];
 363
 364             var testArrayKey2Values = [];
 365             for (var i = 0, n = testArray.length; i < n; ++i) {
 366                 var value = testArray[i].key2;
 367                 InspectorTest.assertTrue(testArrayKey2Values.indexOf(value) === -1, "FAIL: key2 values should be unique");
 368                 testArrayKey2Values.push(value);
 369             }
 370
 371             function comparator(a, b)
 372             {
 373                 return a.key1 - b.key1;
 374             }
 375             testArray.stableSort(comparator);
 376             InspectorTest.addResult("Stable sort result:\n" + testArray.join("\n"));
 377
 378             function assertHelper(condition, message, i, a, b)
 379             {
 380                 InspectorTest.assertTrue(condition, "FAIL: " + message + " at index " + i + ": " + a + " < " + b);
 381             }
 382
 383             for (var i = 1, n = testArray.length; i < n; ++i) {
 384                 var a = testArray[i - 1];
 385                 var b = testArray[i];
 386                 assertHelper(a.key1 <= b.key1, "primary key order", i, a, b);
 387                 if (a.key1 !== b.key1)
 388                     continue;
 389                 var key2IndexA = testArrayKey2Values.indexOf(a.key2);
 390                 InspectorTest.assertTrue(key2IndexA !== -1);
 391                 var key2IndexB = testArrayKey2Values.indexOf(b.key2);
 392                 InspectorTest.assertTrue(key2IndexB !== -1);
 393                 assertHelper(key2IndexA < key2IndexB, "stable order", i, a, b);
 394             }
 395             next();
 396         }
 397
 398     ]);
 399 }
 400
 401 </script>
 402 </head>
 403
 404 <body onload="runTest()">
 405 <p>
 406 This test checks Web Inspector utilities.
 407 </p>
 408
 409 </body>
 410 </html>