私はいくつかのデータ構造を実装しており、使用したい 1 つのプリミティブは次のとおりです。メモリ チャンク A[N] があり (可変長ですが、例では 100 を使用します)、このチャンク内には小さな部分があります。追加のメモリを使用せずに移動したい長さ K (30 としましょう) の C。
追加の問題は、A が「ラップ」することです。つまり、C は A[80] で開始でき、C の最初の 20 要素は要素 A[80..100] であり、最後の 10 要素は要素 A[ です。 0..10]。さらに、ターゲット範囲は、「ラップ」して、可能な方法で C とオーバーラップすることもできます。さらに、一定量以上の追加メモリを使用したくありません。すべてが適切に行われる必要があります。また、ターゲット範囲にもソース範囲にもない A の部分には、何か重要なものが含まれている可能性があるため、これも使用できません。したがって、1つのケースは次のようになります。
A は次のようになります。
|456789ABCDEF0123456789AB|-----|0123|
そして、これに変換する必要があります：
|89AB|-----|0123456789ABCDEF01234567|
ライブラリに委任するか、ライブラリから別のデータ構造を使用するだけでは、ここではオプションではありません。問題を自分で理解したいと思います。一見、些細なことではないかと思いましたが、いくつかのケースを区別するとすぐに明らかになりますが、今は深刻な問題を抱えています。もちろん、重ならない、ラップしないという些細なケースもありますが、少なくとも両方が同時に発生すると、厄介になります。1 つの空いている場所から始めて、そこに属するパーツを移動することもできますが、別の場所に別の空きパーツを作成すると、まだ使用できるパーツを追跡するのが難しくなります。
多分私は何かを完全に見逃しているかもしれませんが、ターゲット範囲がラップされない場合の私の特別なケースでさえ、ほぼ100行あり（半分はアサーションとコメントですが）、いくつかの追加で一般的なケースも処理できるように更新できましたインデックスの計算ですが、誰かがエレガントで短い解決策を持っている場合は、助けていただければ幸いです。直感的には、これは些細なことだと思いますが、まだ最善の解決策がわかりません。
注: もちろん興味深いケースは、C が A とほぼ同じ大きさの場合です。< N/2、それは些細なことです。
編集:追加のフラグ/インデックスを一定量以上使用すると、追加のメモリとしてカウントされ、可能であればそれを避けたいです。
編集: 一部の人々は私のコードを見たいと思っていました。私の質問はかなり抽象的なので、投稿したくありませんでしたが、誰かがそれを改善する方法を見ているかもしれません. ひどいです。ターゲットが最初から開始され（ただし、簡単に変更できます）、非常に長い場合にのみ機能しますが、O（n）で追加のメモリなしでジョブを実行します。
#include <stddef.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
void move_part(int* A, size_t N, size_t target, size_t source, size_t size, int show_steps)
{
assert(source + size <= N);
assert(target + size <= N);
if (show_steps) {
printf("Moving size %d from %d to %d.\n", size, source, target);
}
memmove(A + target, A + source, size * sizeof(int));
}
void swap_parts(int* A, size_t N, size_t first_begin, size_t second_begin, size_t size, int show_steps)
{
if (show_steps) {
printf("Swapping size %d at %d and %d.\n", size, first_begin, second_begin);
}
assert(first_begin + size <= N);
assert(second_begin + size <= N);
size_t i;
for (i = 0; i < size; ++i) {
int x = A[first_begin + i];
A[first_begin + i] = A[second_begin + i];
A[second_begin + i] = x;
}
}
void move_to_beginning(int* A, size_t N, size_t begin, size_t size, int show_steps)
{
assert(begin <= N);
assert(size <= N);
// Denotes the start of our "working range". Increases during
// the algorithm and becomes N
size_t part_start = 0;
// Note: Keeping the size is crucial since begin == end could
// mean that the range is empty or full.
size_t end = (begin + size) % N;
while (part_start != N) {
size_t i;
if (show_steps) {
for (i = 0; i < N; ++i) {
printf("%d ", A[i]);
}
printf("\n");
printf("part_start %d begin %d end %d size %d\n", part_start, begin, end, size);
}
// loop invariants
assert(part_start < N);
// The two pointers are in our range
assert(part_start <= begin && begin <= N);
assert(part_start <= end && end <= N);
// size is valid (wrapped case, non-empty, non-full case)
assert(begin <= end || (N - begin) + (end - part_start) == size);
// size is valid (non wrapped case, non-empty, non-full case)
assert(begin >= end || end - begin == size);
// size is valid (working range is full or empty case)
assert(begin != end || size == 0 || part_start + size == N);
if (size == 0 || begin == N || begin == part_start) {
// ##|1234|# -> 1234### ||
if (show_steps) {
printf("Case 1:\nTerminating\n");
}
// #||# -> ## ||
// 12|##| -> 12## ||
// |12|## -> 12## ||
break;
/* Not necessary any more, but would be the correct transformation:
part_start = N;
begin = N;
end = N;
size = 0;*/
} else if (end == part_start) {
// |##|123 -> ##|123|
if (show_steps) {
printf("Case 2:\n");
printf("Setting end to %d.\n", N);
}
end = N;
} else if (begin < end) {
// ##|1234|# -> 1234### ||
if (show_steps) {
printf("Case 3:\n");
}
move_part(A, N, part_start, begin, size, show_steps);
break;
/* Not necessary any more, but would be the correct transformation:
part_start = N;
begin = N;
end = N;
size = 0;*/
} else {
size_t end_size = end - part_start;
size_t begin_size = N - begin;
assert(begin_size + end_size == size);
if (end_size >= begin_size) {
// 345|#|12 -> 12 5|#|34
if (show_steps) {
printf("Case 4:\n");
}
swap_parts(A, N, part_start, begin, begin_size, show_steps);
assert(begin_size > 0); // Necessary for progress
part_start += begin_size;
size = end_size;
// begin, end remain unchanged
} else if (begin - part_start <= begin_size) {
// 56|#|1234 -> 123 56|#|4
size_t size_moved = begin - part_start;
assert(size_moved >= end_size); // else the next step would be more efficient
if (show_steps) {
printf("Case 5\n");
}
swap_parts(A, N, part_start, begin, end_size, show_steps);
move_part(A, N, end, begin + end_size, begin - end, show_steps);
assert(end_size + (begin - end) == size_moved);
size -= size_moved;
part_start = begin;
begin += size_moved;
end += size_moved;
} else if (end_size <= begin_size) {
// 45|##|123 -> 123 #|45|#
if (show_steps) {
printf("Case 6\n");
}
swap_parts(A, N, part_start, begin, end_size, show_steps);
move_part(A, N, end, begin + end_size, begin_size - end_size, show_steps);
part_start += begin_size;
size = end_size;
end = begin + end_size;
// begin remains unchanged
} else {
// No case applies, this should never happen
assert(0);
}
}
}
}
int main()
{
int N = 20;
int A[20];
size_t size = 17;
size_t begin = 15;
size_t i;
for (i = 0; i < size; ++i) {
A[(begin + i) % N] = i;
}
move_to_beginning(A, N, begin, size, 0);
for (i = 0; i < size; ++i) {
printf("%d ", A[i]);
}
printf("\n");
return 0;
}