Created attachment 203756 [details] [review]
Array: add capability to insert while keeping a specific order

Adds two new functions, Array.prototype.lower_bound and
Array.prototype.insert_sorted, that take a value and a comparator,
and find the first position at which the value can be inserted
without violating the order, in optimal time.

Created attachment 203757 [details] [review]
NetworkMenu: actually add new access point to the network list

Previously the code in _accessPointAdded was iterating over the
the network list to find a good place, and at that time, added both
the network to the list and the item to the menu. When refactored
to call queueCreateSection, I forgot to add code to insert the
network in the list.
Add it now, using the new Array.insert_sorted (and thus finally
going for O(log N) JS side + O(N) C side)

Review of attachment 203756 [details] [review]:

Is there any reason this can't be a utility function inside of network.js, or in util.js? Python supplies a separate bisect module for this, it doesn't build it into the list class.

::: js/ui/environment.js
@@ +74,3 @@
+
+    /** Array.prototype.lower_bound:
+        Returns the position of the first element that is not

Put '*'s at the start of every line here. That's how we do it elsewhere.

@@ +83,3 @@
+        that it doesn't stop at first element comparing equal.
+    */
+    Array.prototype.lower_bound = function(val, cmp) {

lowerBound... and it probably makes sense to supply a default cmp of a-b if none was provided.

@@ +86,3 @@
+        let a, b, c, v;
+
+        a = 0; b = this.length;

min and max, not a and b.

@@ +88,3 @@
+        a = 0; b = this.length;
+        while (a < (b-1)) {
+            c = Math.floor((a + b)/2);

mid, not c

@@ +100,3 @@
+    }
+
+    Array.prototype.insert_sorted = function(val, cmp) {

insertSorted

::: tests/unit/insertSorted.js
@@ +28,3 @@
+arrayInt.insert_sorted(3, cmp);
+
+assertArrayEquals('second test', [1,2,3,3,4,5,6], arrayInt);

You should test with two objects that compare the same, but are different, to make sure you're placing them in the correct spot. If I've read your code right, you want to be placed on the left of all the equivalent objects.

(In reply to comment #3)
> Review of attachment 203756 [details] [review]:
> 
> Is there any reason this can't be a utility function inside of network.js, or
> in util.js? Python supplies a separate bisect module for this, it doesn't build
> it into the list class.

No particular reason, except that I would consider this generally useful even outside network.js. I'll go for util.js if monkey patching array is not appropriate.

> ::: tests/unit/insertSorted.js
> @@ +28,3 @@
> +arrayInt.insert_sorted(3, cmp);
> +
> +assertArrayEquals('second test', [1,2,3,3,4,5,6], arrayInt);
> 
> You should test with two objects that compare the same, but are different, to
> make sure you're placing them in the correct spot. If I've read your code
> right, you want to be placed on the left of all the equivalent objects.

Not easy to build the reference test case, but ok.

Created attachment 203762 [details] [review]
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.

Created attachment 203763 [details] [review]
NetworkMenu: actually add new access point to the network list

Previously the code in _accessPointAdded was iterating over the
the network list to find a good place, and at that time, added both
the network to the list and the item to the menu. When refactored
to call queueCreateSection, I forgot to add code to insert the
network in the list.
Add it now, using the new Util.insertSorted

Created attachment 203764 [details] [review]
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.

Already found a bug (called the comparator on undefined, if the
array was empty)

Review of attachment 203764 [details] [review]:

::: js/misc/util.js
@@ +250,3 @@
+function lowerBound(array, val, cmp) {
+    let min, max, mid, v;
+    cmp = cmp || function(a, b) { return a-b; }

Missing semicolon.

@@ +256,3 @@
+
+    min = 0; max = array.length;
+    while (min < (max-1)) {

Whitespace (spaces between binary operators)

@@ +257,3 @@
+    min = 0; max = array.length;
+    while (min < (max-1)) {
+        mid = Math.floor((min + max)/2);

Whitespace (spaces between binary operators)

@@ +264,3 @@
+        else
+            max = mid;
+        }

Funky indentation.

(In reply to comment #7)
> Already found a bug (called the comparator on undefined, if the
> array was empty)

Can you add a test case for that?

Review of attachment 203763 [details] [review]:

"When refactored" => "When I refactored"

"using the new Util.insertSorted method"

Created attachment 203794 [details] [review]
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.

Created attachment 203795 [details] [review]
NetworkMenu: actually add new access point to the network list

Previously the code in _accessPointAdded was iterating over the
the network list to find a good place, and at that time, added both
the network to the list and the item to the menu. When I refactored
to call queueCreateSection, I forgot to add code to insert the
network in the list.
Add it now, using the new Util.insertSorted function.

Review of attachment 203795 [details] [review]:

Sure.

Review of attachment 203794 [details] [review]:

Sure.

Attachment 203794 [details] pushed as 09ab13c - Array: add capability to insert while keeping a specific order
Attachment 203795 [details] pushed as 77afd67 - NetworkMenu: actually add new access point to the network list