Removing Element From Array While Keeping Order

Question

I'm building a wireless mechanical keyboard. There is an array of 6 elements that stores the keys pressed by the user (since 6 is the max number of keys you can send at once over Bluetooth). An example would be 02-05-03-00-00-00. Notice the "00" at the end, these are just "placeholders" and don't have a meaning other than to indicate that there are no more keys pressed. When the user releases key 05 for example, the array should become this 02-03-00-00-00-00. I don't know how to do this however, since you can't just remove and item from an array and there doesn't seem to be a polished option for lists in Arduino.

Does anyone have any idea for an algorithm that finds the 0's in an array, places them at the end of the array and keeps the order of the other elements?

Answer 1

You need to compact the vector: First search for the first non-zero element and then move all non-zero elements. It could look something like below:

void setup()
{
  Serial.begin(57600);
  while (!Serial);

  char vec[] = { 2, 5, 3, 0, 0, 1 };
  print(vec, sizeof(vec));

  compact(vec, sizeof(vec));
  print(vec, sizeof(vec));

  vec[1] = 0;
  print(vec, sizeof(vec));

  compact(vec, sizeof(vec));
  print(vec, sizeof(vec));
}

void loop()
{
}

void compact(char* vec, size_t len)
{
  int i = 0;
  for (; i < len && vec[i] != 0; i++);
  if (i == len) return;
  int j = i;
  for (; i < len; i++) {
    char c = vec[i];
    if (c != 0) {
      vec[j++] = c;
      vec[i] = 0;
    }
  }
}

void print(char* vec, size_t len)
{
  for (int i = 0; i < len; i++) {
    unsigned c = vec[i];
    if (c < 16) Serial.print(0);
    Serial.print(c, HEX);
    if (i + 1 < len) Serial.print('-');
  }
  Serial.println();
}

This give the following output:

02-05-03-00-00-01
02-05-03-01-00-00
02-00-03-01-00-00
02-03-01-00-00-00

Cheers!

Answer 2

Remove Zeros

void removeZeros(uint8_t array[], size_t length) {
// Sanity check.
if(array != nullptr && length > 0) {
    for(size_t i = 0; i < length; i++) {
      if(array[i] == 0) {
        for(size_t j = i + 1; j < length; j++){
          if(array[j] != 0) {
            array[i] = array[j];
            array[j] = 0;
            break;
          }
        }
      }
    }
  }
}

Usage:

uint8_t keyBuffer[] = { 2, 0, 3, 0, 4, 0 };
removeZeros(keyBuffer, sizeof(keyBuffer)/sizeof(keyBuffer[0]);

New value of keyBuffer: { 2, 3, 4, 0, 0, 0 }

Remove a single indexed value

void removeIndex(uint8_t array[], size_t length, size_t index){
  // Sanity check.
  if(array != nullptr && length > 0) {
    for(size_t i = index; i < (length - 1); i++){
      array[i] = array[i + 1];
    }
    array[length-1] = 0;
  }
}

Usage:

uint8_t keyBuffer[] = { 2, 5, 3, 0, 0, 0 };
removeZeros(keyBuffer, sizeof(keyBuffer)/sizeof(keyBuffer[0], 1);

New value of keyBuffer: { 2, 3, 0, 0, 0, 0 }