Insert value into array

I was curious what the most effective way was for inserting a value into an array. I literally mean inserting a value into an array, as in between two values, not just replacing an item at a specific index. Example,

psuedoish code,

Code:

---

example[4] = {1,2,3,4};
insert(9,2,example);
example[4] == {1,2,9,3};

---

I need to insert several large strings into an array several thousand characters long. (similar to how a text editor would do it)

Do the characters that cannot fit inside the array simply fall off the right end? At least that's what I got out of your example.

Yes.

That means you need to start at the right, replacing element n by element n-1, going back until you reach the insertion point.

For small strings you can "worm" the char's over, index by index, from right to left, and that's ok.

But that's also inefficient - much like bubblesort, actually. Because the char's may need to move many spaces over to the right, and a naive algorithm will really slow things down.

A better algorithm would be:

get the length of the string to be added, a[1], make that length1.

get the length of the string (the char array) that's to be adjusted (a2[]), and make that length2

Now choose the index that is length2 - length1. Start there, and move that char in a2[] to a2[length2-1].

Continue moving char's until the index = (length2 - length1) - length1. That is, if a1[] is 100 char's long, and a2[] = 1,000 char's in length, then you want to start at index 1,000 , and continue until you get to index 900. (Just remember to -1 from these index numbers for zero based arrays)

This is a naive implementation. If you run it step by step, you'll see that the char's are moved over and over again. The move itself is fast, but with a long string, I'd use the better algorithm described above. I don't have an example of it to show.

Code:

---

/*edit_str.c Overwrites or inserts a string into an array of char, Adak
Status: ok
*/

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

int insert(void);
int overwrite(void);

char a1[] = { "When you spit, upon a star" }; //apologies to Disney :)
char a2[] = { "you wish," };
char a3[] = {"Now is the time for all good men to come to the aid of their country."};
char a4[] = {" and wise"}; 

int main(void)  {
  overwrite();
  insert();
  return 0;
}

int insert(void) {
  int i, j, left, right, length3, length4;
  length3 = strlen(a3);
  length4 = strlen(a4);

  left = 27;  //where I want to insert the a2 string
  for(j = length4 - 1; j > -1; j--)  {
      for(i = length3 - 2; i > left; i--)  {
        a3[i+1] = a3[i];
        if(i < 0 || i > length3-1)
            return 1;
      }                  //the a4 string is fed into a3, from right to
      ++i;              //left. Each inserted char is then moved to the
      a3[i] = a4[j];    //right in a3, appropriately.
      if(j < 0 || j > length4-1)
        return 1;
  }
  printf("%s\n", a3);
 
  i = getchar();
  return 0;
}
int overwrite(void) {
  int i, j, left, right, length1;

  left = 5;
  right = strlen(a2);
  length1 = strlen(a1);

  for(i = left, j = 0; j < right; i++)  {
      a1[i] = a2[j++];
      if(i > length1-1)
        return 1;
  }
  printf("%s\n", a1);
  i = getchar();
 
  return 0;
}

---

If this is truly the best way to approach your problem, I'd think that memmove() + memcpy() would be the solution (assuming I didn't make a mistake here):

Code:

---

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

static void insert(const char *to_insert, char *string, size_t offset)
{
  size_t slen = strlen(string);
  size_t ilen = strlen(to_insert);

  assert(ilen + offset <= slen);

  memmove(&string[offset + ilen], &string[offset], slen - ilen - offset);
  memcpy(&string[offset], to_insert, ilen);
}

int main(void)
{
  char s[] = "string for replacement";

  insert("is ", s, 7);

  puts(s);

  return 0;
}

---

Before writing code what have you tried as far as designing the algorithm is concerned.