Replace a data sequence with another in an array

Question

I would need to replace some data sequences with others, in an array, such as in this example (whose signature I imagined for the replacement function):

seq_replace(
    int *array, size_t size0,      // The array to modify         + its size
    int *to_replace, size_t size1, // The sequence to be replaced + its size
    int *to_place, size_t size2);  // The sequence to be placed   + its size

int array[] = {0, 6, 3, 0, 6, 2};
seq_replace(
    &array, 6,
    (const int[]){0, 6}, 2,
    (const int[]){9}, 1);

And would be obtain my array with values {9, 3, 9, 2}.

I imagine that linked lists would be more suitable for this style of task, but I work throughout my project with arrays, and making conversions between types of container would cost time.

Anyway, I don't know of any algorithm to do this kind of thing, and I haven't found anything interesting on the Internet either. I therefore turn to this site for advice on how to carry out this task.

Not enough precise.. Can to_place be longer than to_replace ? If yes, what behavior is expected ? In your example, what is the result of replacing {0,6} by {7,8,9} ? Or {2} by {4,5} ? — didou
– didou, Commented Oct 26, 2019 at 15:52
Any length of to_replace and to_place should be possible. In your examples, replacing {0, 6} with {7, 8, 9} would give this: {7, 8, 9, 3, 7, 8, 9, 2}. Or replace {2} with {4, 5} would give this: {0, 6, 3, 0, 6, 4, 5}... So there is a resizing of the array, which reminds me of an implementation track, where we would not directly modify the array, but create a temporary one. I'm going to see if there's a way to do it like that. — Foxy
– Foxy, Commented Oct 26, 2019 at 16:13
if size2 > size1 and if you want to do all replacement, the resulting array is larger than the initial. Either you know there is enough space after size0 (this is not the case of your example) or you need to dynamically allocate (malloc) a new table. Or do you think you receive a dynamically allocated table (in that case we can do a realloc() on it) ? In any case, if you (re)allocate the table you need to return the new pointer and also the new size, so the current signature of seq_replace is not good. Try to tell us exactly what you want. — didou
– didou, Commented Oct 26, 2019 at 16:30
I see... I may be doing it wrong for what I want to do, but I would like to make a toy peephole optimizer for a series of instructions on a stack. For example, replace unnecessary instructions such as dup swap with dup, or swap swap by <nothing>. I don't see how else to do it, actually. — Foxy
– Foxy, Commented Oct 26, 2019 at 16:43

didou · Accepted Answer · 2019-10-26 18:26:40Z

Here is a code that works in the case array is known to be large enough for any replacement. The function returns the new logical size of array. The // p += size2; commented instruction makes it possible to recursively replace inside the result of to_place (as it is the case for a peephole optimizer). For instance in {0,6,6} replacing {0,6} by {0} gives {0}.

There is a main() to test various cases.

#include <stdio.h>
#include <string.h>

void show_array(const int *array, size_t size0)
{
 int i;
  for(i = 0; i < size0; i++)
    printf("%3d", array[i]);
  puts("");
}

int seq_replace(int *array, size_t size0,            // The array to modify         + its size
                const int *to_replace, size_t size1, // The sequence to be replaced + its size
                const int *to_place, size_t size2)   // The sequence to be placed   + its size
{
  int *p = array, *end = array + size0;

  while(p < end)
    {
      if (p + size1 <= end && memcmp(p, to_replace, size1 * sizeof(*p)) == 0)
        {
          memmove(p + size2, p + size1, (end - p - size1) * sizeof(*p));
          memcpy(p, to_place, size2 * sizeof(*p));
          // p += size2; // uncomment to avoid replacements in to_place itself
          size0 = size0 - size1 + size2;
          end = array + size0;
        }
      else
        {
          p++;
        }
    }
  return size0; // return logical new size
}

#define N_ELEM(p) (sizeof(p) / sizeof(*(p)))

// array is physically large enough
int array[1000] = {0, 6, 6, 0, 6, 2, 0, 6, 0, 6};
int size0 = 10; // its logical length
int to_replace[] = {0, 6};
int to_place[] = {0}; // try {9, 8}, {9, 8, 7}, {9} and even {}

int main()
{

  printf("initial array; length: %d\n", size0);
  show_array(array, size0);

  size0 = seq_replace(array, size0,
                      to_replace, N_ELEM(to_replace),
                      to_place, N_ELEM(to_place));

  printf("final array, new length: %d\n", size0);
  show_array(array, size0);
}

Collectives™ on Stack Overflow

Replace a data sequence with another in an array

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related