Сложный вопрос - "кольцевой буфер"

[tonline_kms65_1]

Опять и снова все здравствуйте!
Один из нерешенных моих вопросов - это вопрос о так называемом "кольцевом буфере", или проще массив без переполнения, похоже на динамический но с определенным размером. Пока не могу понятно объяснить, но как то так.
Если есть такие, кто с таким вопросом сталкивался - можно обсудить, там и мысли сформируются.

Конкретно что мне нужно - мне нужно, например, 4 (или больше) последних координаты игрока, я не хочу использовать динамические массивы т.к. если раунд бесконечный - массив может раздуться до ...... Используя "кольцевой буфер" я просто перезаписываю данные в массиве не меняя его размер, выглядит примерно так - складываю в ящик, только с низу(вообще, без разницы, сверху), верхний предмет вываливается и происходит смещение на 1 значение, это наверно самое близкое сравнение.
Соответственно мне нужны 3 (или больше) самые последние координаты. Если бы я писал в текстовый файл - я потом циклом проходил бы в обратном порядке и получал бы 3 последние, постоянно обновляемые координаты. Это несложно.
Проблема в том, что массив имеет индексы, так как я не теоретик, я не могу себе представить, что может произойти в результате работы так же, как с текстовым файлом. Предполагаю что при удалении элемента массива и добавлении нового, индексы элементов массива перезаписываются, повторюсь - я не теоретик, я в ней слаб.
Такой вопрос. Наверняка сумбурно, поэтому желательно участие тех кто имел с таким дело, ну или неплохо разбирается в массивах.

 

[komashchenko]

Хоть это и не кольцевой буфер но он должен подойти под ваши требования

Спойлер: FixedArray

#define FixedArray_SIZE 8
float g_FixedPosArray[FixedArray_SIZE][3];

FixedPosArray_Push(const float fPos[3])
{
    for (int i = FixedArray_SIZE - 1; i != 0;)
    {
        g_FixedPosArray[i] = g_FixedPosArray[--i];
    }
    
    g_FixedPosArray[0] = fPos;
}

public void OnPluginStart()
{
    FixedPosArray_Push(view_as<float>({15.0, 8.0, 9.0}));
    FixedPosArray_Push(view_as<float>({14.0, 8.0, 9.0}));
    FixedPosArray_Push(view_as<float>({13.0, 8.0, 9.0}));
    FixedPosArray_Push(view_as<float>({12.0, 8.0, 9.0}));
    FixedPosArray_Push(view_as<float>({11.0, 8.0, 9.0}));
    FixedPosArray_Push(view_as<float>({10.0, 8.0, 9.0}));
    FixedPosArray_Push(view_as<float>({9.0, 8.0, 9.0}));
    FixedPosArray_Push(view_as<float>({8.0, 8.0, 9.0}));
    FixedPosArray_Push(view_as<float>({7.0, 8.0, 9.0}));
    FixedPosArray_Push(view_as<float>({6.0, 8.0, 9.0}));
    FixedPosArray_Push(view_as<float>({5.0, 8.0, 9.0}));
    FixedPosArray_Push(view_as<float>({4.0, 8.0, 9.0}));
    
    for (int i = 0; i < sizeof g_FixedPosArray; i++)
    {
        PrintToServer("%d %f %f %f", i, g_FixedPosArray[i][0], g_FixedPosArray[i][1], g_FixedPosArray[i][2]);
    }
}

0 4.000000 8.000000 9.000000
1 5.000000 8.000000 9.000000
2 6.000000 8.000000 9.000000
3 7.000000 8.000000 9.000000
4 8.000000 8.000000 9.000000
5 9.000000 8.000000 9.000000
6 10.000000 8.000000 9.000000
7 11.000000 8.000000 9.000000

 

[Reiko1231]

Данный вопрос не является сложным. В SM такой массив можно реализовать двумя способами:

1. Через сам массив и индекс "последнего" значения. Для этого мы создаем массив нужной нам длины и ещё одну вспомогательную переменную, которая указывает на "хвост" массива. При добавлении значения в этот массив мы пишем значение в индекс хвоста, а затем увеличиваем хвост на один и если индекс хвоста становится больше длины массива, то обнуляем хвост (таким образом со след. записи мы начнём затирать первые значения и так по кругу). Реализовать это можно сделать следующим образом:
Объявим сам массив и индекс его последнего значения

#define CIRCULAR_ARRAY_MAX_LENGTH 3

float g_positions[CIRCULAR_ARRAY_MAX_LENGTH][3];
int g_last_index = 0;

Чтобы было проще им пользоваться, создадим вспомогательную функцию по добавлению значения

void AddValue(float value[3])
{
    g_positions[g_last_index] = value;
    g_last_index += 1;
    g_last_index = g_last_index % CIRCULAR_ARRAY_MAX_LENGTH;
}

Поскольку массив из функции вернуть нельзя, сделаем функцию по возврату индекса по относительному номеру конца (0 для последнего записанного значения, 1 для предпоследнего, 2 для второго с конца и т.д.)

void GetIndex(int index_from_last)
{
    int index = g_last_index - index_from_last;
    index = index % CIRCULAR_ARRAY_MAX_LENGTH;
    if (index < 0) index *= -1;
    return index;
}

Таким образом, добавляем значения с помощью функции AddValue, а получением значение как float position[3] = g_positions[GetIndex(0)].

2. Через ArrayList. Эта реализация гораздо проще:
Объявляем сам массив

ArrayList g_circular_array = new ArrayList(ByteCountToCells(3));

И при вставке нам нужно освободить место под новое значение в начале массива (т.е. сместить все значения вверх)

g_circular_array.ShiftUp(0);

Затем вставляем наше значение на освободившееся место

g_circular_array.SetArray(0, {10.0, 20.0, 30.0});

И обрезаем массив до трёх элементов (таким образом начиная с 4+ вставки мы будем всё время удалять 4 элемент, т.е. самое старое значение).

g_circular_array.Resize(3);

Получить нужное значение из массива можно с помощью GetArray метода, где под индексом 2 будет самое старое записанное значение, под индексом 1 будет предпоследнее, и под 0 индексом будет недавно записанное значение.

Оба варианта я не проверял, но должно работать.

 

[tonline_kms65_1]

@komashchenko, @Reiko1231,
Спасибо большое за предложения.
Я пока не в состоянии все это попробовать применить. Как только появится возможность - я попробую, обязательно.
В принципе для этой задачи не обязательно использовать именно "кольцевой буфер", это я использовал что бы было понятнее что именно мне нужно. Интересна сама реализация. Стараюсь избегать собственных функций движка (ArrayList), в будущем не будет возможности применить это на другом движке.
Я не совсем понимаю работу массивов, поэтому не могу найти решения, мне нужно будет понять принцип построения массивов. Для этого на след. неделе я заеду в наш политен, поговорю с математиками, интересны ихние предложения, бывают очень интересные решения.
Еще раз спасибо за примеры.

И вот такой вопрос, а можно пройти циклом по элементам массива, не касаясь индексов элементов? Не знаю понятно я объясняю или нет. Т.е. пройти как по текстовому файлу. Мне вот этот вопрос не ясен, поэтому у меня и куча сомнений.

 

[Reiko1231]

Стараюсь избегать собственных функций движка (ArrayList), в будущем не будет возможности применить это на другом движке.

Это есть в подавляющем большинстве движков и ЯП. В данном случае под ArrayList в SourceMod подразумевается очередь, а под ArrayStack - стэк.

Для этого на след. неделе я заеду в наш политен, поговорю с математиками, интересны ихние предложения, бывают очень интересные решения.

Сложность двух предложенных мной алгоритмов является O(1). Быстрее алгоритма быть не может, т.к. здесь постоянное время выполнения (не важен размер массива - для массивов длиной в один и миллиард элементов вставка и получение значения будет производиться за одно и то же одинаковое время)

мне нужно будет понять принцип построения массивов

Представьте тетрадь в клеточку. С каждой вставкой вы пишете в новую клеточку число. С каждым удалением вы вычёркиваете клеточку по указанному номеру. Вот весь принцип работы с массивами.

И вот такой вопрос, а можно пройти циклом по элементам массива, не касаясь индексов элементов? Не знаю понятно я объясняю или нет. Т.е. пройти как по текстовому файлу. Мне вот этот вопрос не ясен, поэтому у меня и куча сомнений.

То, что у вас нет индекса в явном виде не означает, что его нет. На самом деле есть указатель на текущую позицию (элемент) в файле. Получить его значение можно с помощью функции FilePosition, а установить значение с помощью FileSeek.