Algorithm question: in-place multi-bringToFront?

[tsbockman]

On Friday, 29 May 2020 at 03:29:05 UTC, tsbockman wrote:
> 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.

void cutToFront(T)(scope T[] queue, scope const(size_t[]) 
cutterXs ...) {
     import core.bitop : bsr;
     import core.memory : pureCalloc, pureFree;
     import std.algorithm : move, moveEmplace, sort;

     // Allocate scratch space:
     const(size_t) memSize = (cutterXs.length + 1) * 
(size_t.sizeof + T.sizeof);
     void* mem = () @trusted { return pureCalloc(memSize, 1); }();
     if(mem == null)
         assert(0, "Allocation failed - possibly out of memory?");
     scope(exit) { () @trusted {
         /* IMPORTANT: T must not throw from inside move or 
moveEmplace, below,
         because it's too hard to figure out which item's 
destructors should be called for cutters. */
         pureFree(mem);
     }(); }

     // Prepare scratch slices:
     size_t[] cutterXSet = () @trusted {
         static assert(size_t.alignof == size_t(1) << 
bsr(size_t.alignof));
         auto ptr = cast(size_t*) ((size_t.alignof - 1 + 
cast(size_t) mem) & -size_t.alignof);
         return ptr[0 .. cutterXs.length];
     }();
     T[] cutters = () @trusted {
         static assert(T.alignof == size_t(1) << bsr(T.alignof));
         auto ptr = cast(T*) ((((cutterXSet.length + 1) * 
size_t.sizeof) + T.alignof - 1 + cast(size_t) mem) & -T.alignof);
         return ptr[0 .. cutterXSet.length];
     }();
     assert((cutterXSet.length * typeof(cutterXSet[0]).sizeof + 
cast(void*) cutterXSet.ptr) < cast(void*) cutters.ptr
           && (cutters.length * typeof(cutters[0]).sizeof + 
cast(void*) cutters.ptr) < (memSize + mem));

     // Sort cutterXs:
     cutterXSet[] = cutterXs[];
     sort(cutterXSet);

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

     if(cutterCount > 0) {
         // Validate the indices:
         if(lastCutterX >= queue.length)
             assert(0, "Invalid cutter index.");

         // 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 = 
cutterXSet[lastCutterXX];
         while(true) {
             T* dest;
             if(oldX == oldCutterX) {
                 // If T makes moveEmplace!T unsafe, then the 
move!T call below should also be unsafe.
                 () @trusted nothrow { moveEmplace(queue[oldX], 
cutters[lastCutterXX - gap]); }();
                 ++gap;
                 if(gap <= lastCutterXX)
                     oldCutterX = cutterXSet[lastCutterXX - gap];
             } else {
                 const newX = oldX + gap;
                 () nothrow { move(queue[oldX], queue[newX]); }();
             }

             if(oldX <= 0)
                 break;
             --oldX; // Iterate backwards to avoid overwriting 
later entries before they have been moved elsewhere.
         }

         // Finally, place the cutters at the front of the line:
         size_t x = lastCutterXX;
         while(true) {
             () nothrow { move(cutters[x], queue[x]); }();
             if(x <= 0)
                 break;
             --x; // Iterate through queue[newX] in the same 
direction as the loop above to avoid confusing the prefetcher.
         }
     }
}