Algorithm question: in-place multi-bringToFront?

[tsbockman]

On Thursday, 28 May 2020 at 23:47:50 UTC, H. S. Teoh wrote:
> Just pickin' yall's smart brains:
>
> Given an array A and a set of indices into the array, is there 
> a fast algorithm for rearranging A in-place so that the 
> elements at the given indices are moved to the front?
>
> E.g.: A = [ 0, 1, 2, 3, 4, 5 ], index = [ 1, 3, 5 ]
>
> The result should have 1, 3, and 5 at the front of the array 
> (the exact
> order is unimportant).
>
> For efficiency considerations, assume the size of the index is 
> relatively small, but the array itself may be quite large, so 
> scanning the entire array or copying large chunks of it is 
> undesirable.
>
>
> T

Here's a version that preserves the order of the rest of the 
array:

void cutToFront(T)(scope T[] queue, scope size_t[] cutterXs ...) {
     // Sort cutterXs:
     import std.algorithm : move, sort;
     sort(cutterXs);

     // Convert cutterXs into a set:
     size_t cutterCount = 0, lastCutterX = 0;
     for(size_t cutterXX = 0; cutterXX < cutterXs.length; 
++cutterXX) {
         const cutterX = cutterXs[cutterXX];
         if(cutterX != lastCutterX) {
             lastCutterX = cutterX;
             cutterXs[cutterCount] = cutterX;
             ++cutterCount;
         }
     }
     cutterXs = cutterXs[0 .. cutterCount];

     if(cutterCount > 0) {
         // Validate the indices:
         if(lastCutterX >= queue.length)
             assert(0);

         // Pull the cutters out of the queue temporarily, sliding 
other items back as needed:
         const(size_t) lastCutterXX = cutterCount - 1;
         size_t gap = 0, oldX = lastCutterX, oldCutterX = 
cutterXs[lastCutterXX];
         T[] cutters = new T[cutterXs.length];
         while(true) {
             T* dest;
             if(oldX == oldCutterX) {
                 dest = &(cutters[lastCutterXX - gap]);
                 ++gap;
                 if(gap <= lastCutterXX)
                     oldCutterX = cutterXs[lastCutterXX - gap];
             } else {
                 const newX = oldX + gap;
                 dest = &(queue[newX]);
             }
             move(queue[oldX], *dest);

             if(oldX <= 0)
                 break;
             --oldX;
         }

         // Finally, place the cutters at the front of the line:
         for(size_t x = 0; x < cutterCount; ++x)
             move(cutters[x], queue[x]);
     }
}

Performance is O(maxElement(cutterXs) + cutterXs.length * 
log(cutterXs.length)). It could be made pure @safe nothrow @nogc 
fairly easily, except that maintaining proper attribute inference 
based on the attributes of implicitly called methods of T is a 
pain.