Я реализую несколько структур данных, и один примитив, который я хочу использовать, следующий: у меня есть блок памяти A [N] (он имеет переменную длину, но я беру 100 для моих примеров), и внутри этого блока есть меньшая часть C длиной K (скажем, 30), которую я хочу переместить без использования дополнительной памяти.

Дополнительная трудность заключается в том, что "обертывания»то есть, C может начинаться с A [80], и тогда первые 20 элементов C являются элементами A [80..100], а последние 10 элементов являются элементами A [0..10]. Кроме того, целевой диапазон также может "заворачивать" и перекрываются с C любым возможным способом. Кроме того, я неЕсли вы хотите использовать больше, чем постоянный объем дополнительной памяти, все должно происходить на месте. Кроме того, часть A, которая не находится ни в целевом диапазоне, ни в исходном диапазоне, может содержать что-то важное, поэтому ее также нельзя использовать. Таким образом, один случай будет следующим:

А выглядит так:

| 456789ABCDEF0123456789AB | ----- | 0123 |

И должно быть преобразовано в это:

| 89AB | ----- | 0123456789ABCDEF01234567 |

Просто делегировать его в библиотеку или использовать другую структуру данных из библиотеки здесь не вариант, я хочу сам разобраться в проблеме. С первого взгляда я подумал, что это может быть не тривиально, но как только вы различаете несколько случаев, становится понятно, но сейчас у меня серьезные проблемы. Конечно, есть тривиальные случаи, если они нене перекрываются или неОберните, но, по крайней мере, если оба произойдут одновременно, это станет грязным. Вы можете начать с одного свободного места и переместить принадлежащую ему деталь, но затем вы создадите еще одну свободную часть где-нибудь еще, и вам будет сложно отследить, какие части вы можете использовать.

Может быть, я что-то упустил полностью, но даже мой особый случай, если целевой диапазон не переносится, имеет почти 100 строк (хотя половина из них - утверждения и комментарии), и я мог бы обновить его, чтобы он также обрабатывал общий случай с некоторыми дополнительными Индекс вычисления, но если у кого-то есть элегантное и краткое решение, я был бы признателен за помощь. Интуитивно я думаю, что это должно быть тривиально, но я просто непока не вижу лучшего решения.

Примечание: интересный случай, конечно, если C почти такой же большой, как A. Если | C | < N / 2, это тривиально.

редактирование: использование более чем постоянного количества дополнительных флагов / индексов считается дополнительной памятью, и я хочу избежать этого, если это возможно.

редактировать: некоторые люди хотели увидеть мой код. Мой вопрос довольно абстрактный, поэтому я неНе хочу публиковать, но, возможно, кто-то видит, как его улучшить. Это ужасно, это работает только в том случае, если цель начинается с начала (однако это легко можно изменить) и ужасно долго, но она выполняет работу без дополнительной памяти в O (n).

#include 
#include 
#include 
#include 

void move_part(int* A, size_t N, size_t target, size_t source, size_t size, int show_steps)
{
  assert(source + size