Здравствуйте, pva, Вы писали:
pva>Задача: максимально оперативно выдавать упорядоченные по индексу непрерывные куски заданной длительности. Кусок должен содержать все "типы".
Куски могут(должны) перекрываться?
Ну, то есть если у нас ровно один тип, то что должно выдаваться при таком входе для длительности 2?

0-0-A
1-0-B -> AB
2-0-C -> BC или ""?
3-0-D -> CD

В целом, задача выглядит достаточно прямолинейно.
Берём любую отсортированную структуру queue, например B-дерево. Ключ сортировки — (индекс, тип).
Параллельно с ней заводим структуру message фиксированным размером L*N, где L — длительность, N — количество типов.
Заводим lsn — текущий номер индекса, и readyCount — количество готовых к отправке отсчётов. Оба инициализируются нулём.
При поступлении каждого сэмпла
1. Если индекс — в диапазоне [lsn, lsn+L), и в message пришедшего отсчёта ещё нет, то
1.1. Кладём отсчёт в message
2.2. Увеличиваем readyCount. Если он равен L*N, то
1.2.3. "выдаём" содержимое message
1.2.3. Сдвигаем lsn: в зависимости от ответа на мой вопрос вначале, либо на L, либо на 1.
1.2.4. Правим message: в зависимости от ответа на мой вопрос вначале, либо очищаем, либо "сдвигаем" на N, освобождая новую строку.
1.2.5. Правим readyCount: в зависимости от ответа на мой вопрос вначале, либо обнуляем, либо уменьшаем на N.
1.2.5. Заполняем освободившееся место в message из queue
1.2.6. Выбрасываем из queue все данные с ключом меньше lsn
2. Иначе (индекс >= lsn+L) — кладём отсчёт в queue.