Problem: missing burst beats

The task

Write find_missing(beats, len). The queue beats holds the beat numbers that arrived, in arrival order, and len is the number of beats in the burst. Return the beat numbers from 0 to len - 1 that never arrived, in ascending order.

Three rules settle the corner cases. A beat that arrives twice still counts once. A beat number below 0 or at or above len is ignored here, because a separate check reports invalid beats. When len is 0, the answer is empty.

Writing these rules down matters more than the code. Each rule decides an output for some input, and without the rules two reasonable-looking functions can give different answers for the same burst.

Why counting and sorting fall short

Comparing beats.size() with len fails as soon as one beat is duplicated and another dropped, which is exactly the hook. Counting distinct beats is closer, but it still says nothing about which beat is missing.

Sorting the arrivals and walking them alongside 0 to len - 1 can work. It needs care with duplicates and with out-of-range numbers, though, and it rearranges data that a later check might still need.

A count still has a use as a quick first check. If it is below len, a beat is certainly missing; if it equals len, you still need the presence map to be sure.

A presence map

1. Allocate

   Create bit seen [] = new[len];. Every element starts at 0, meaning not yet seen.

2. Mark

   For each arrival b, check that 0 <= b < len, then set seen[b] = 1. A second arrival of the same beat sets the same bit again, so duplicates cost nothing.

   beats	0 1 2 2 3 4 6 7
   seen	1 1 1 1 1 0 1 1

3. Collect

   Walk b from 0 to len - 1 and push every b whose bit is still 0. Because the walk goes upward, the result comes out sorted.

   missing	{5}

The map is sized from len, so it always holds exactly one flag per beat that the burst promised. The range check must come before the index. An out-of-range index is not always a harmless no-op: Verilator 5.052, for example, keeps only the low bits of a fixed-array index and writes the wrong element.

What it costs

The presence map visits each of the n arrivals once and each of the len beat numbers once, so the work grows as n + len. For a 256-beat burst, that is about 512 steps.

The obvious alternative searches all arrivals once for every beat number, with find_first_index or a loop. That is n × len steps, about 65,536 for the same burst, and every burst pays it.

The memory cost is one bit per beat, 256 bits for the largest burst, which is small next to the data the burst carries.

Tests that matter

Test every rule on its own, so a failure points at one cause. Cover an empty burst, nothing arriving, every beat arriving, duplicates, numbers just outside the range on both sides, and a full 256-beat burst with a beat missing at each end.

Write each expected result from the specification before running the code. A result copied from the function itself only proves the function agrees with itself.

A useful extra test runs the function on random inputs and compares it with the slow search version. The two are written differently, so they rarely share a bug.

Where the check runs

Call find_missing when the burst should be complete, which is the beat with rlast set. A burst whose rlast never arrives needs a timeout as well, or the check never runs at all.

When bursts with different IDs interleave, keep one queue of arrivals per ID in an associative array of queues. Run the check for an ID when that ID's last beat arrives, and delete its key once the check is done.

Try it

Each line is one row of the specification table, and each matches the result written there before the code ran.

Remove the beats[i] >= 0 part of the range check and run it again. The output may not change on this simulator, which is why the spec, rather than one passing run, decides whether a check is needed.

Check yourself

module tb;
  typedef int int_q [$];
  function automatic int_q find_missing(int_q beats, int len);
    int_q missing;
    bit   seen [];
    seen = new[len];
    foreach (beats[i])
      if (beats[i] >= 0 && beats[i] < len) seen[beats[i]] = 1;
    for (int b = 0; b < len; b++)
      if (!seen[b]) missing.push_back(b);
    return missing;
  endfunction
  int_q r;
  initial begin
    r = find_missing('{3, 3, 1, 7}, 5);
    $display("%0d: %0d %0d %0d", r.size(), r[0], r[1], r[2]);
  end
endmodule

int_q missing;
bit seen [int];
foreach (beats[i]) seen[beats[i]] = 1;
for (int b = 0; b < len; b++) if (!seen.exists(b)) missing.push_back(b);
return missing;

int_q missing;
bit seen [];
seen = new[len];
foreach (beats[i]) if (beats[i] >= 0 && beats[i] < len) seen[beats[i]] = 1;
for (int b = 0; b < beats.size(); b++) if (b < len && !seen[b]) missing.push_back(b);
return missing;

int_q missing, hit;
for (int b = 0; b < len; b++) begin
  hit = beats.find_first_index with (item == b);
  if (hit.size() == 0) missing.push_back(b);
end
return missing;

int_q missing;
bit seen [];
seen = new[len];
foreach (beats[i]) if (beats[i] >= 0 && beats[i] < len) seen[beats[i]] = 1;
for (int b = 0; b < len; b++) if (!seen[b]) missing.push_back(b);
return missing;

Practice

• Missing beat indices Implement · Easy