Estoy implementando varias estructuras de datos y una primitiva que quiero usar es la siguiente: Tengo un fragmento de memoria A [N] (tiene una longitud variable, pero tomo 100 para mis ejemplos) y dentro de este fragmento, hay una parte más pequeña C de longitud K (digamos 30) que quiero mover sin usar memoria adicional.

La dificultad adicional es que A "envuelve", es decir, C puede comenzar en A [80] y luego los primeros 20 elementos de C son los elementos A [80..100] y los últimos 10 elementos son los elementos A [ 0..10]. Además, el rango objetivo también puede "ajustarse" y superponerse con C de cualquier forma posible. Además, no quiero usar más que una cantidad constante de memoria adicional, todo debería suceder en su lugar. Además, la parte de A que no está en el rango objetivo ni en el rango de origen puede contener algo importante, por lo que tampoco se puede usar. Así que un caso sería el siguiente:

A se ve así:

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

Y debe ser transformado a esto:

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

Simplemente delegarlo en una biblioteca o usar otra estructura de datos de una biblioteca no es una opción aquí, quiero entender el problema por mí mismo. A primera vista, pensé que podría no ser trivial, pero tan pronto como distingue algunos casos, queda claro, pero ahora estoy teniendo serios problemas. Por supuesto, hay casos triviales si no se superponen o no se ajustan, pero al menos si ambos suceden al mismo tiempo, se complica. Podría comenzar con un lugar libre y mover la parte que pertenece a ese lugar, pero luego crea otra parte libre en otro lugar y es difícil hacer un seguimiento de las partes que aún puede usar.

Tal vez me esté perdiendo algo por completo, pero incluso mi caso especial si el rango de destino no se ajusta tiene casi 100 líneas (aunque la mitad son afirmaciones y comentarios) y podría actualizarlo para que también maneje el caso general con algunos detalles adicionales. Cálculos de índice, pero si alguien tiene una solución elegante y corta, agradecería alguna ayuda. Intuitivamente, creo que esto debería ser algo trivial, pero aún no veo la mejor solución.

Nota: El caso interesante es, por supuesto, si C es casi tan grande como A. Si | C | <N / 2, es trivial.

edición: el uso de más de una cantidad constante de marcas / índices adicionales cuenta como memoria adicional y quiero evitar eso si es posible.

Edición: Algunas personas querían ver mi código. Mi pregunta es bastante abstracta, así que no quise publicarla, pero tal vez alguien vea cómo mejorarla. Es terrible, solo funciona en el caso de que el objetivo comience desde el principio (sin embargo, se puede cambiar fácilmente) y es terriblemente largo, pero hace el trabajo sin memoria adicional en 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;
}