diff options
Diffstat (limited to 'third_party/webkit/PerformanceTests/ARES-6/Air/insertion_set.js')
-rw-r--r-- | third_party/webkit/PerformanceTests/ARES-6/Air/insertion_set.js | 89 |
1 files changed, 89 insertions, 0 deletions
diff --git a/third_party/webkit/PerformanceTests/ARES-6/Air/insertion_set.js b/third_party/webkit/PerformanceTests/ARES-6/Air/insertion_set.js new file mode 100644 index 0000000000..b070a15dd1 --- /dev/null +++ b/third_party/webkit/PerformanceTests/ARES-6/Air/insertion_set.js @@ -0,0 +1,89 @@ +/* + * Copyright (C) 2016 Apple Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY + * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +"use strict"; + +class Insertion { + constructor(index, element) + { + this._index = index; + this._element = element; + } + + get index() { return this._index; } + get element() { return this._element; } + + lessThan(other) + { + return this._index < other._index; + } +} + +class InsertionSet { + constructor() + { + this._insertions = [] + } + + appendInsertion(insertion) + { + this._insertions.push(insertion); + } + + append(index, element) + { + this.appendInsertion(new Insertion(index, element)); + } + + execute(target) + { + // We bubble-sort because that's what the C++ code, and for the same reason as we do it: + // the stdlib doesn't have a stable sort and mergesort is slower in the common case of the + // array usually being sorted. This array is usually sorted. + bubbleSort(this._insertions, (a, b) => (a.lessThan(b))); + + let numInsertions = this._insertions.length; + if (!numInsertions) + return 0; + let originalTargetSize = target.length; + target.length += numInsertions; + let lastIndex = target.length; + for (let indexInInsertions = numInsertions; indexInInsertions--;) { + let insertion = this._insertions[indexInInsertions]; + if (indexInInsertions && insertion.index < this._insertions[indexInInsertions - 1].index) + throw new Error("Insertions out of order"); + if (insertion.index > originalTargetSize) + throw new Error("Out-of-bounds insertion"); + let firstIndex = insertion.index + indexInInsertions; + let indexOffset = indexInInsertions + 1; + for (let i = lastIndex; --i > firstIndex;) + target[i] = target[i - indexOffset]; + target[firstIndex] = insertion.element; + lastIndex = firstIndex; + } + this._insertions = []; + return numInsertions; + } +} + |