[gnome-shell] Array: add capability to insert while keeping a specific order
- From: Giovanni Campagna <gcampagna src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gnome-shell] Array: add capability to insert while keeping a specific order
- Date: Mon, 19 Dec 2011 15:55:34 +0000 (UTC)
commit 09ab13cf04c7a5826b54cbbb66ca9aca8568a8dc
Author: Giovanni Campagna <gcampagna src gnome org>
Date: Sat Dec 17 23:52:11 2011 +0100
Array: add capability to insert while keeping a specific order
Adds two new functions, Util.lowerBound and Util.insertSorted,
that take an array, a value and a comparator, and find the
first position at which the value can be inserted without
violating the order, in optimal time.
https://bugzilla.gnome.org/show_bug.cgi?id=666429
js/misc/util.js | 50 +++++++++++++++++++++++++++++++
tests/Makefile.am | 1 +
tests/unit/insertSorted.js | 71 ++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 122 insertions(+), 0 deletions(-)
---
diff --git a/js/misc/util.js b/js/misc/util.js
index 4d9a7c4..3664058 100644
--- a/js/misc/util.js
+++ b/js/misc/util.js
@@ -232,3 +232,53 @@ function fixupPCIDescription(desc) {
return out.join(' ');
}
+
+// lowerBound:
+// @array: an array or array-like object, already sorted
+// according to @cmp
+// @val: the value to add
+// @cmp: a comparator (or undefined to compare as numbers)
+//
+// Returns the position of the first element that is not
+// lower than @val, according to @cmp.
+// That is, returns the first position at which it
+// is possible to insert @val without violating the
+// order.
+// This is quite like an ordinary binary search, except
+// that it doesn't stop at first element comparing equal.
+
+function lowerBound(array, val, cmp) {
+ let min, max, mid, v;
+ cmp = cmp || function(a, b) { return a - b; };
+
+ if (array.length == 0)
+ return 0;
+
+ min = 0; max = array.length;
+ while (min < (max - 1)) {
+ mid = Math.floor((min + max) / 2);
+ v = cmp(array[mid], val);
+
+ if (v < 0)
+ min = mid + 1;
+ else
+ max = mid;
+ }
+
+ return (cmp(array[min], val) < 0) ? max : min;
+}
+
+// insertSorted:
+// @array: an array sorted according to @cmp
+// @val: a value to insert
+// @cmp: the sorting function
+//
+// Inserts @val into @array, preserving the
+// sorting invariants.
+// Returns the position at which it was inserted
+function insertSorted(array, val, cmp) {
+ let pos = lowerBound(array, val, cmp);
+ array.splice(pos, 0, val);
+
+ return pos;
+}
diff --git a/tests/Makefile.am b/tests/Makefile.am
index caf3f52..e848b34 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -20,6 +20,7 @@ TEST_JS = \
testcommon/face-plain.png \
testcommon/ui.js \
unit/format.js \
+ unit/insertSorted.js \
unit/markup.js \
unit/jsParse.js \
unit/url.js
diff --git a/tests/unit/insertSorted.js b/tests/unit/insertSorted.js
new file mode 100644
index 0000000..e23848a
--- /dev/null
+++ b/tests/unit/insertSorted.js
@@ -0,0 +1,71 @@
+/* -*- mode: js2; js2-basic-offset: 4; indent-tabs-mode: nil -*- */
+
+// Test cases for Util.insertSorted
+
+const JsUnit = imports.jsUnit;
+
+// Needed so that Util can bring some UI stuff
+// we don't actually use
+const Environment = imports.ui.environment;
+Environment.init();
+const Util = imports.misc.util;
+
+function assertArrayEquals(errorMessage, array1, array2) {
+ JsUnit.assertEquals(errorMessage + ' length',
+ array1.length, array2.length);
+ for (let j = 0; j < array1.length; j++) {
+ JsUnit.assertEquals(errorMessage + ' item ' + j,
+ array1[j], array2[j]);
+ }
+}
+
+function cmp(one, two) {
+ return one-two;
+}
+
+let arrayInt = [1, 2, 3, 5, 6];
+Util.insertSorted(arrayInt, 4, cmp);
+
+assertArrayEquals('first test', [1,2,3,4,5,6], arrayInt);
+
+// no comparator, integer sorting is implied
+Util.insertSorted(arrayInt, 3);
+
+assertArrayEquals('second test', [1,2,3,3,4,5,6], arrayInt);
+
+let obj1 = { a: 1 };
+let obj2 = { a: 2, b: 0 };
+let obj3 = { a: 2, b: 1 };
+let obj4 = { a: 3 };
+
+function objCmp(one, two) {
+ return one.a - two.a;
+}
+
+let arrayObj = [obj1, obj3, obj4];
+
+// obj2 compares equivalent to obj3, should be
+// inserted before
+Util.insertSorted(arrayObj, obj2, objCmp);
+
+assertArrayEquals('object test', [obj1, obj2, obj3, obj4], arrayObj);
+
+function checkedCmp(one, two) {
+ if (typeof one != 'number' ||
+ typeof two != 'number')
+ throw new TypeError('Invalid type passed to checkedCmp');
+
+ return one-two;
+}
+
+let arrayEmpty = [];
+
+// check that no comparisons are made when
+// inserting in a empty array
+Util.insertSorted(arrayEmpty, 3, checkedCmp);
+
+// Some more insertions
+Util.insertSorted(arrayEmpty, 2, checkedCmp);
+Util.insertSorted(arrayEmpty, 1, checkedCmp);
+
+assertArrayEquals('checkedCmp test', [1, 2, 3], arrayEmpty);
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]