How to do z-order insertion with a functional style

Question

I'd like to do an insertion into an array based either on insertion order (pushing to the end), or in increasing order based on an object property called z. (e.g. drawing order in 2d graphics, either the order things were added or overridden by a z-order).

The code below goes to a lot of trouble to do this, looping backwards, finding the index one too far, jumping through a hoop to insert without mutation. (borrowed from here).

It seems like there ought to be something more concise and functional than what I have. Am I missing some part of the language that can simplify and improve this?

edit I've been thinking about findIndex as the approach, but I think I need something like reverseFindIndex, to get the insertion order at the end when z's are equal, and I'd still like to improve non-mutating insertion after I know the index.

let children = [
  { z: 10 }, { z: 10 }, { z: 0 }, { z: 0 }, { z: -1 }, { z: -1 }
]

function insertZ(object, children) {
  for (var index = children.length - 1; index >= 0; index--) { // yuck, not functional
    if (object.z <= children[index].z) break;  // yuck, break
  }
  index++;  // yuck, went too far
  return [  // yuck, ugly non-mutating insert
  ...children.slice(0, index),
  object,
  ...children.slice(index)
  ]
}

let object = { z: 7, name: 'new guy' }   // after the 10s, before the 0s
// other test cases...
// let object = { z: 10, name: 'new guy' }  // after the 10s, before the 0s 
// let object = { z: -1, name: 'new guy' }  // after the -1s
// let object = { z: 90, name: 'new guy' }  // before everything

console.log(insertZ(object, children))

That's interesting @MORÈ, can I depend on the insert order as a secondary sort? — goodson, Jun 22 '22 at 15:53
@MORÈ, If I insert using z order and sort, I want last inserted object to end up *after* all the other z's that are equal to it. I worry that sort() might not care about that. I think I'll end up depending on implementation details of sort() that might be undependable — goodson, Jun 22 '22 at 15:57

T.J. Crowder · Accepted Answer · 2022-06-22T16:09:40.593

You could use recursion to find the insertion point, passing the index around:

function insertZ(object, children, index = 0) {
    if (index >= children.length || children[index].z < object.z) {
        return [
            ...children.slice(0, index),
            object,
            ...children.slice(index),
        ];
    }
    return insertZ(object, children, index + 1);
}

Live Example:

let children = [{ z: 10 }, { z: 10 }, { z: 0 }, { z: 0 }, { z: -1 }, { z: -1 }];

function insertZ(object, children, index = 0) {
    if (index >= children.length || children[index].z < object.z) {
        return [
            ...children.slice(0, index),
            object,
            ...children.slice(index),
        ];
    }
    return insertZ(object, children, index + 1);
}

let object1 = { z: 7, name: "new guy" };    // after the 10s, before the 0s
console.log(insertZ(object1, children));
let object2 = { z: 10, name: "new guy" };   // after the 10s, before the 0s
console.log(insertZ(object2, children));
let object3 = { z: -1, name: "new guy" };   // after the -1s
console.log(insertZ(object3, children));
let object4 = { z: 90, name: "new guy" };   // before everything
console.log(insertZ(object4, children));
// Testing adding to an empty array
console.log(insertZ(object4, []));

.as-console-wrapper {
    max-height: 100% !important;
}

If desired, to avoid callers passing duff indexes, the work could be done by a private inner function:

let children = [{ z: 10 }, { z: 10 }, { z: 0 }, { z: 0 }, { z: -1 }, { z: -1 }];

function insertZ(object, children) {
    const worker = (object, dhildren, index = 0) => {
        if (index >= children.length || children[index].z < object.z) {
            return [
                ...children.slice(0, index),
                object,
                ...children.slice(index),
            ];
        }
        return worker(object, children, index + 1);
    };
    return worker(object, children);
}

let object1 = { z: 7, name: "new guy" };    // after the 10s, before the 0s
console.log(insertZ(object1, children));
let object2 = { z: 10, name: "new guy" };   // after the 10s, before the 0s
console.log(insertZ(object2, children));
let object3 = { z: -1, name: "new guy" };   // after the -1s
console.log(insertZ(object3, children));
let object4 = { z: 90, name: "new guy" };   // before everything
console.log(insertZ(object4, children));
// Testing adding to an empty array
console.log(insertZ(object4, []));

.as-console-wrapper {
    max-height: 100% !important;
}

Alternatively, you could use recursion with a bunch of temporary arrays:

function insertZ(object, children) {
    if (children.length === 0) {
        return [object];
    }
    const [first] = children;
    if (first.z < object.z) {
        return [object, ...children];
    }
    return [first, ...insertZ(object, children.slice(1))];
}

Live Example:

let children = [{ z: 10 }, { z: 10 }, { z: 0 }, { z: 0 }, { z: -1 }, { z: -1 }];

function insertZ(object, children) {
    if (children.length === 0) {
        return [object];
    }
    const [first] = children;
    if (first.z < object.z) {
        return [object, ...children];
    }
    return [first, ...insertZ(object, children.slice(1))];
}

let object1 = { z: 7, name: "new guy" };    // after the 10s, before the 0s
console.log(insertZ(object1, children));
let object2 = { z: 10, name: "new guy" };   // after the 10s, before the 0s
console.log(insertZ(object2, children));
let object3 = { z: -1, name: "new guy" };   // after the -1s
console.log(insertZ(object3, children));
let object4 = { z: 90, name: "new guy" };   // before everything
console.log(insertZ(object4, children));
// Testing adding to an empty array:
console.log(insertZ(object4, []));

.as-console-wrapper {
    max-height: 100% !important;
}

Wow, both ideas are mind-blowing. Thank you. Am I right that the second idea trades prettiness for creating some garbage collection work? I think, in my app, these arrays will not exceed mid-100s in length — goodson, Jun 22 '22 at 16:08
@goodson - Yes indeed. :-) That's not an uncommon trade-off in FP as I understand it, which prefers recursion over loops. I should warn you though that I'm not a big FP-head, so take anything I suggest with a grain of salt as it could be the result of FP ignorance on my part. — T.J. Crowder, Jun 22 '22 at 16:11
Thanks, I think I'll use your first approach. Curious what you think about @MORÈ's answer. I probably haven't done a good job expressing my concern with that.... I'm treating the built in sort algorithm as a black box that might only accidentally respect insertion order (and do so inconsistently across implementations) — goodson, Jun 22 '22 at 16:16

score 1 · Answer 2 · answered Jun 22 '22 at 16:01

1

Below snippet will push a new object after all z > <target_value>, even if there are already object with the same z

let children = [
  { z: 10 }, { z: 10 }, { z: 7 }, { z: 0 }, { z: 0 }, { z: -1 }, { z: -1 }
]

let object = { z: 7, name: 'new guy' }   // after the 10s, before the 0s
children.push(object);
children.sort((a, b) => a.z > b.z ? -1 : 1);
console.log(children);

If you want to insert it before you just need to change the condition to a.z >= b.z.

let children = [
  { z: 10 }, { z: 10 }, { z: 7 }, { z: 0 }, { z: 0 }, { z: -1 }, { z: -1 }
]

let object = { z: 7, name: 'new guy' }   // after the 10s, before the 0s
children.push(object);
children.sort((a, b) => a.z >= b.z ? -1 : 1);
console.log(children);

answered Jun 22 '22 at 16:01

MORÈ

2,480
3
16
23

This is great, thanks, but do you understand my worry about sort()? Is there a way I can depend on preserving insertion order across implementations? – goodson Jun 22 '22 at 16:11
1

@goodson - Good news! You can depend on it in all modern JavaScript engines -- per specification. The specification was updated sometime in the past couple of years to require that the sort function be *stable* (which is the term for what you're you're looking for -- an algorithm that will not change the relative order of "equal" elements). They were able to add that to the specification because all major implementations already used stable sort algorithms. I don't know whether IE's is, but IE is officially dead and buried (right?). :-) – T.J. Crowder Jun 22 '22 at 17:01
Here's a link to the spec saying it has to be stable: https://tc39.es/ecma262/multipage/indexed-collections.html#sec-array.prototype.sort – T.J. Crowder Jun 22 '22 at 17:03
My concern about the above if I were an FP guy would be that it mutates the existing array rather than creating a new array. My impression is that *usually*, FP prefers copies to mutations. It's an easy fix though. – T.J. Crowder Jun 22 '22 at 17:09
(I just had to check: IE's sort function is definitely not stable. [MDN's page](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort#browser_compatibility) shows "No" for stable sort, but I wasn't sure whether that was just "not guaranteed" or "known not to be stable." A quick test established it's not stable. What's worse, Edge's sort is not stable when in "IE compatibility mode." [It is otherwise.]) – T.J. Crowder Jun 22 '22 at 17:27
Okay, thank you both! I don't anticipate much non-safari/chrome usage, but think I'll go with something where I'm not forced to decide. – goodson Jun 22 '22 at 17:36

How to do z-order insertion with a functional style

2 Answers2