Shifting Values in an Array/Accessing Random values

I'm working on a project that will be storing several audio messages in a few different "groups", to identify each as unique sets of objects from the other sets. Currently, I'm thinking of using arrays to store the data. Once the data is stored, I want to be able to delete values and then shift the other values in the array to the "front" so that I will be able to write to the first "empty" (value of 0) block in the array. I also want to be able to access a random (assuming pseudo-random) filled sector in the array. For now, I'm starting with ints just to get the theory down. As far as shifting the values goes, I've come up with the following code, but I want to see if there is some more efficient way to go about it.

const int capacity = 5;
int testArray[capacity] = {1,2,0,3,4};

void arrayShift()
{
  for(int i=0; i<4; i++)
  {
   if (testArray[i] == 0)
  {
    testArray[i] = testArray[i+1];
    testArray[i+1] = 0;
  } 
  }
}

void setup()
{
  Serial.begin(115200);
  
}

void loop()
{
  Serial.print(testArray[0]);
  Serial.print(" ");
  Serial.print(testArray[1]);
  Serial.print(" ");
  Serial.print(testArray[2]);
  Serial.print(" ");
  Serial.print(testArray[3]);
  Serial.print(" ");
  Serial.print(testArray[4]);
  Serial.print("\n");
  arrayShift();
  Serial.print(testArray[0]);
  Serial.print(" ");
  Serial.print(testArray[1]);
  Serial.print(" ");
  Serial.print(testArray[2]);
  Serial.print(" ");
  Serial.print(testArray[3]);
  Serial.print(" ");
  Serial.print(testArray[4]);
  Serial.print("\n");
  Serial.end();
}

After that, I want to be able to access a random "filled" section of the array, but I'm really not at all sure how to do that. I've read about using time to create a psuedo-random value using mathematical formulae, such as using modulo to divide millis in order to generate a value, and things along those lines, but I'd like to get some of your opinions, too. Thanks so much for the help guys! These forums never fail to impress!

EDIT: I didn't look up random number Arduino. Found the random() operator, so now I just need to write a couple if statements and loops to make sure it doesn't pick a number greater than the capacity of the array, or an empty element of the array. My idea is currently to limit the max number using a numberOfElements variable to count the number of filled elements in the array to kill both birds with one stone, but we'll see how it works. For now, I just want to see if you guys have any better ideas about shifting array values. Thanks again!

What are you planning to run this on? Audio takes up a lot of space. To have an "array" of sound clips sitting in memory is unrealistic for the limited capacity of an arduino.

A better approach would be to keep the sound files on an sd memory card. In this setup, you wouldn't have the sound clips in memory, you'd just have their file names.

I plan on getting the mp3 shield from adafruit, which has an SD card slot, and which encodes/decodes audio, so that part is pretty straight forward (so I think).

the FOR loop is a powerful way to type less...

  Serial.print(testArray[0]);
  Serial.print(" ");
  Serial.print(testArray[1]);
  Serial.print(" ");
  Serial.print(testArray[2]);
  Serial.print(" ");
  Serial.print(testArray[3]);
  Serial.print(" ");
  Serial.print(testArray[4]);
  Serial.print("\n");

check this...

  for (int i = 0; i < capacity; i++)
  {
    Serial.print(testArray[i]);
    Serial.print(" ");
  }
  Serial.print("\n");

There's a couple of other changes that will make your code a little more flexible:

#define ARRAYSIZE(x) (sizeof(x) / sizeof(x[0]))

int testArray[] = {1, 2, 0, 3, 4, 5, 6, 7, 8};

int capacity = ARRAYSIZE(testArray);

void arrayShift()
{
  for (int i = 0; i < capacity - 1; i++)
  {
    if (testArray[i] == 0)
    {
      memmove(&testArray[i], &testArray[i + 1], sizeof(testArray[0]) * (capacity - i) );   // Usually pretty fast...
      testArray[capacity - 1] = 0;
      break;       // We're done, get outta for loop
    }
  }
}


void ShowArray(int array[])
{
  for (int i = 0; i < capacity; i++)
  {
    Serial.print(array[i]);
    Serial.print(" ");
  }
  Serial.print("\n");
}

void setup()
{
  Serial.begin(115200);

  ShowArray(testArray);
  arrayShift();
  ShowArray(testArray);

}

void loop()
{
}

Thanks to everyone.

Rob: I don't know why I didn't use a for loop there. Kind of a silly mistake on my part. Thanks for pointing that out!

Econ: I'm quite confused by what the code you've laid out is meant to do. I'm also worried about the break you have there, which would, as I understand it, exit the for loop, even though the intention is to continue the loop, or would it just exit that iteration of the loop? There are several other parts of the code that confuse me. I guess I need to look up the memmove command, as I'm not familiar with how it operates, though the idea of the function is clear. That line of the code is what has me confused the most, but if it works like I think it does, it would definitely make the code more efficient, so thank you for that! And the ShowArray routine is something I definitely should have had to begin with, so thanks for that too.

The memmove() function simply moves a block of memory from one place to another place in memory. If you study the code, you will see that the block move does away with the need for the rest of the for loop in your code. That's the reason the break statement is needed. Take a piece of paper and draw out the array, using two bytes of memory for each value in the array. Once the zero is found, you want to "slide" the array down one position to "overwrite" the zero with the remaining bytes of the array. After that's done, you need to set the last element to 0. If you take a little time, add a few Serial.println() statements, you'll see how it works.

Why shift and delete at all. You could just have a status bit for every entry marking it as occupied or vacant.

Try this. (Sorry if it looks quite long, it's mostly Serial.print statements and a klunky input function to let you see what's going on. I've kept the logic VERY simple. It could be optimised a great deal by looking at the status bits a byte at a time.

int capacity=8;
int testArray [8]={1,2,0,4,5,6,7,8};
bool statusBit[8]={1,1,0,4,5,6,7,8};

//saves newValue in first space it can find
void saveValue(int newValue)
{
  int n;
  //first find a vacant space
  for (n=0;n<capacity;n++)
    if(!statusBit[n])
    {
      testArray[n]=newValue;
      statusBit[n]=true;
      Serial.print(F("Added "));
      Serial.print(newValue,DEC);
      Serial.print(F(" in position "));
      Serial.println(n,DEC);
      return;
    }
  Serial.println(F("Sorry, Array is full"));
}

//victim is Array element index to be deleted
void deleteValue(int victim)
{
  if(victim>capacity)
  {
    Serial.print(F("Error Deleting Maximum Array index is "));
    Serial.println(capacity);
    return;
  }
  statusBit[victim]=false;
  Serial.print(F("Deleted element "));
  Serial.println(victim,DEC);
}

//patient is index of element to be revived
void undeleteValue(int patient)
{
  if(patient>capacity)
  {
    Serial.print(F("Error UNDELETING Maximum:Array index is "));
    Serial.println(capacity);
    return;
  }
  statusBit[patient]=true;
  Serial.print(F("Undeleted "));
  Serial.println(patient,DEC);
}

void showArray()
{
  Serial.println(F(""));
  Serial.print(F("Array currently holds   "));
  int n;
  for(n=0;n<capacity;n++)
  {
    if(n) 
      Serial.print(", ");
    if(statusBit[n])
      Serial.print(testArray[n]);
    else
      Serial.print(F("SPARE"));
  }
  Serial.println("");
}

void setup()
{
  Serial.begin(9600);
  Serial.println(F("Enter command as a letter followed by a number"));
  Serial.println(F("A xx = Add value XX to array"));
  Serial.println(F("D xx = Delete element xx from array"));
  Serial.println(F("U xx = UNDELETE element xx from array"));
  Serial.println(F("(Element indexes are zero based)"));
}

void loop()
{
  showArray();
  getInstruction();
}

//klunky little input function
void getInstruction()
{
  char character;  
  char buffer[10];
  int index=0;
  int value;
  Serial.print(">");
  //wait for user
  while(!Serial.available());
  while(Serial.available())
  { 
    character=Serial.read();
    buffer[index]=character;
    index+=(index<18);
    delay(20);
    buffer[index]=0;
    if((character=='\n')||(character=='\r'))
    {
      sscanf(buffer+1,"%i",&value);
      switch(buffer[0])
      {
      case 'A': 
      case 'a':
        saveValue(value);
        break;
      case 'D': 
      case 'd':
        deleteValue(value);
        break;
      case 'U': 
      case 'u':
        undeleteValue(value);
        break;
      default:
        Serial.print(F("What?"));
        break;
      }
      while(Serial.available())
        Serial.read();
      break;
    }
  }
}

Sorry for the late reply. The reason I'd like to shift the array is so that I can easily use a random number generator (i.e.: random()) to randomly select one of the audio files in the array. Currently, I'm just testing the theory using int's, but the eventual goal is to use an MP3 shield to add audio encoding/decoding so that the user can record several greetings and have one randomly played back. I thought it would be easier to choose a random point in the array, and ensure it was a "filled" point, if I shifted the values and used a numberOfElements variable to keep track of how many filled elements there were by incrementing and decrementing the numberOfElements variable when an item was added or deleted. Using that method, I can just limit my random() to the value of numberOfElements and not have to worry about running random(), then checking to see if that value is nonzero, then running again until the value points to a segment in the array that is nonzero, if that makes sense.

This is the code I've come up with after looking through everyone's posts. I really liked memmove(), but I read a few different posts saying that there is a lot of potential for memory leaks and corruption when working with objects (and since I'm working with audio files, I imagine the potential is that much greater). I'm definitely keeping memmove() in my back pocket though, as that's an extremely handy little operator, so thank you for teaching me that! As for the statusBit example, I'm not sure how well that would work when using random() to access a nonzero location in the array, but I have another project that would work in, and it's such a simple concept that I had forgotten all about, so thanks for the refresher!

Onto the code! (ignore the printArray, I was just using it to test/debug):

const int capacity = 10;
int testArray[capacity] = {
  1,2,0,3,4,5,0,0,0,0};
int numOfElements = 5;
int randNumber;

void arrayShift()
{
  for(int i=0; i<4; i++)
  {
    if (testArray[i] == 0)
    {
      testArray[i] = testArray[i+1];
      testArray[i+1] = 0;
    } 
  }
}
void printArray()
{
  for(int i = 0; i < 5; i++)
  {
    Serial.print(testArray[i]);
    Serial.print(" ");
  }
  Serial.print("\n");
}

void randNumGen()
{
  if (numOfElements != 0)
  {
    randNumber = random(numOfElements - 1);
    Serial.print(randNumber);
    Serial.print(" ");
    Serial.print(testArray[randNumber]);
    Serial.print("\n");
  }
}

void setup()
{
  Serial.begin(115200); 
}

void loop()
{
  printArray();
  arrayShift();
  printArray();
  for (int i = 0; i<100; i++)
  {
    randNumGen();
  }
  Serial.end();
}

It appears to be working as intended, and the random(numOfElements - 1) never (so far) accesses an empty array element, so woohoo! Thanks for your help everyone!

PS: If you have any more tips or ideas for this type of operation, please continue to comment. I definitely appreciate any and all input!

if that makes sense.

It does, but looping to choose a random number, and verifying that it represents an index position that contains data, is going to be much faster than shuffling data around.

I guess I didn't think about it that way.

Eventually, I want the user to be able to scroll through the array, which will be filled with audio files, and preview each of the files. The user would then be able to delete a chosen file, and/or add another recording to the list, up to CAPACITY. My thoughts on the interface were that it would be awkward as a user to scroll through the list, seeing that spots 2, 4, and 9 (just as an example) were empty, but the other spots were filled. I thought it would be easier, from the user side, to just scroll through and see how many were full.

The project I'm working on will eventually have audio playback, timekeeping, and alarms based on time for the user, while having access to audio recording through a special menu, probably accessed by holding a button or combination of buttons down for several seconds. With all of these functions it seemed that it would be easier to just get the shift out of the way and operating on a defined parameter (numOfElements), instead of trying to build several different functions for checking whether the array element contains data before executing. Knowing this, would you say that it would still be better (whether from a hardware or software standpoint) to do a check for data, rather than a shift? I'm not very far into the project yet, so I'm definitely open to suggestion, and better to fix misconceptions now rather than later.

Hassurunous:
Eventually, I want the user to be able to scroll through the array, which will be filled with audio files, and preview each of the files. The user would then be able to delete a chosen file, and/or add another recording to the list, up to CAPACITY.

If you just remove the following lines from my example, it does exactly that
else
** Serial.print(F("SPARE"));**

My thoughts on the interface were that it would be awkward as a user to scroll through the list, seeing that spots 2, 4, and 9 (just as an example) were empty, but the other spots were filled. I thought it would be easier, from the user side, to just scroll through and see how many were full.

You don't need to show the empty spots.

For what you are doing, I think I'd be using a doubly linked list. Adding stuff in the middle, at the beginning, or at the end is trivial. Deleting a node simply means making the before node link to the after node, and the after node link to the before node.

Another possibility is an array of struct pointers. Moving pointers is fast. Moving the pointed to data is not.

I'm assuming that you are not using a 328-based Arduino, so memory isn't in critically short supply.

KenF: I didn't even realize! I'll admit, your code was a bit daunting, and I didn't even realize that interaction was already there. Doh! I suppose I could use the same logic to fill in the statusBit array by checking to see if the value in the audioArray is nonzero. Something like:

int audioArray[8] = {1, 2, 3, 0, 4, 0, 5, 0};
boolean statusBit[8];

for (int i = 0; i < 8; i++)
{
  if (audioArray[i] != 0)
  {
    statusBit[i] = 1;
  }
  else if (audioArray[i] == 0)
  {
    statusBit[i] = 0;
  }
}

PaulS: I was probably going to go with an array of pointers to the save locations, since, as you pointed out, moving the actual files will be slow, though that makes me realize that I would be using the pointers to point to a non-equivalent (i.e.: pointerArray[0] may not point to musicArray[0]) so it doesn't even seem worth it to shift the pointers at that point.

I am having trouble wrapping my head around using lists (I'm still pretty new at this; I've been teaching myself on and off for the last couple months; even pointers are still fairly new for me) so I need to devote more study time to those.

I'm using a Mega2560 for the project, and I'm adding the mp3 shield from adafruit when I get one, so storage memory won't be a problem, and RAM is fairly high. Not sure which memory you were referring to, since I'm a newbie though I assume you meant RAM. Sorry!

At this point, I think I'll probably just skip shifting the arrays, since, as you guys have pointed out, at least for this project, it doesn't make much sense to waste time even bothering with it. Thanks for all your help and advice! I never regret coming to these forums!

Hassurunous:
KenF: I didn't even realize! I'll admit, your code was a bit daunting, and I didn't even realize that interaction was already there. Doh! I suppose I could use the same logic to fill in the statusBit array by checking to see if the value in the audioArray is nonzero. Something like:

int audioArray[8] = {1, 2, 3, 0, 4, 0, 5, 0};

boolean statusBit[8];

for (int i = 0; i < 8; i++)
{
  if (audioArray[i] != 0)
  {
    statusBit[i] = 1;
  }
  else if (audioArray[i] == 0)
  {
    statusBit[i] = 0;
  }
}

That's pretty similar to what the saveValue(int newValue) function does in my example.