## digitalmars.D - Algorithm question: in-place multi-bringToFront?

• H. S. Teoh (13/13) May 28 Just pickin' yall's smart brains:
• mw (9/21) May 28 If you don’t care the remaining elements’ order, just swap the
• mw (2/5) May 28 Note: If index[i] < index.length, don’t swap that element.
• tsbockman (55/68) May 28 Here's a version that preserves the order of the rest of the
• tsbockman (91/94) May 28 void cutToFront(T)(scope T[] queue, scope const(size_t[])
• Andrei Alexandrescu (4/18) May 29 Is that the complement of
• wjoe (9/22) May 29 I would just sort index[], to have more cache-friendly access to
"H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
```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

--
Customer support: the art of getting your clients to pay for your own
incompetence.
```
May 28
mw <mingwu gmail.com> writes:
```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.

If you don’t care the remaining elements’ order, just swap the
head N elements with the index array’s pointing to. (unstable
swap, linear to N=index.length)

If you need to keep them still in the original order, first grab
those indexed elements and mark their place as holes, then scan
from arr[max(index)] backwards to arr[0] move the un-indexed
elements to fill those holes, finally set the head elements with
the indexed elements. (stable move, linear to max(index))
```
May 28
mw <mingwu gmail.com> writes:
```On Friday, 29 May 2020 at 00:32:13 UTC, mw wrote:

If you don’t care the remaining elements’ order, just swap the
head N elements with the index array’s pointing to. (unstable
swap, linear to N=index.length)

Note: If index[i] < index.length, don’t swap that element.
```
May 28
tsbockman <thomas.bockman gmail.com> writes:
```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.
```
May 28
tsbockman <thomas.bockman gmail.com> writes:
```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.
}
}
}
```
May 28
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 5/28/20 7:47 PM, 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.

Is that the complement of
https://dlang.org/library/std/algorithm/mutation/remove.html? In that
case it should be adaptable from it with ease.
```
May 29
wjoe <invalid example.com> writes:
```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