debian/tmp/usr/share/ewebkit-0/webinspector/PartialQuickSort.js

   1 /*
   2  * Copyright (C) 2011 Google Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are
   6  * met:
   7  *
   8  *     * Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *     * Redistributions in binary form must reproduce the above
  11  * copyright notice, this list of conditions and the following disclaimer
  12  * in the documentation and/or other materials provided with the
  13  * distribution.
  14  *     * Neither the name of Google Inc. nor the names of its
  15  * contributors may be used to endorse or promote products derived from
  16  * this software without specific prior written permission.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  */
  30
  31 Object.defineProperty(Array.prototype, "sortRange", { value:
  32 /** @this {Array} */
  33 function(comparator, leftBound, rightBound, k)
  34 {
  35     function swap(array, i1, i2)
  36     {
  37         var temp = array[i1];
  38         array[i1] = array[i2];
  39         array[i2] = temp;
  40     }
  41
  42     function partition(array, comparator, left, right, pivotIndex)
  43     {
  44         var pivotValue = array[pivotIndex];
  45         swap(array, right, pivotIndex);
  46         var storeIndex = left;
  47         for (var i = left; i < right; ++i) {
  48             if (comparator(array[i], pivotValue) < 0) {
  49                 swap(array, storeIndex, i);
  50                 ++storeIndex;
  51             }
  52         }
  53         swap(array, right, storeIndex);
  54         return storeIndex;
  55     }
  56
  57     function quickSortFirstK(array, comparator, left, right, k)
  58     {
  59         if (right <= left)
  60             return;
  61         var pivotIndex = Math.floor(Math.random() * (right - left)) + left;
  62         var pivotNewIndex = partition(array, comparator, left, right, pivotIndex);
  63         quickSortFirstK(array, comparator, left, pivotNewIndex - 1, k);
  64         if (pivotNewIndex < left + k - 1)
  65             quickSortFirstK(array, comparator, pivotNewIndex + 1, right, k);
  66     }
  67
  68     if (leftBound === 0 && rightBound === (this.length - 1) && k === this.length)
  69         this.sort(comparator);
  70     else
  71         quickSortFirstK(this, comparator, leftBound, rightBound, k);
  72     return this;
  73 }});