Kruhový buffer
Kruhový buffer (Circular buffer) je implementací fronty (FIFO) nad polem, která se používá především jako vyrovnávací paměť datových tocích.
Princip
Kruhový buffer se skládá z pole fixní délky a dvou ukazatelů. První z ukazatelů míří na první obsazený prvek, druhý na první volné místo v poli. V okamžiku, kdy je do bufferu přidán nový prvek, tak se druhý ukazatel zinkrementuje, v případě odstranění prvního prvku fronty dojde k inkrementaci prvního ukazatele (a k přemazání příslušného paměťového segmentu). Jelikož jsou obě inkrementace prováděny modulárně (pokud je přidáván prvek a konec pole je již obsazen, tak je prvek přidán na uvolněný začátek pole), tak struktura bufferu tvoří kruh.
Složitost operací
Asymptotická složitost výběru a čtení prvku na prvním indexu je , složitost operace přidání prvku na konec fronty je
.
Kód
/**
* Kruhovy buffer - fronta nad polem
* @author Pavel Micka
*/
public class CircularBuffer<ENTITY> {
private int size;
private Object[] array;
private int pointer; //prvni volny index
/**
* Konstruktor
* @param length velikost bufferu
*/
public CircularBuffer(int length) {
this.array = new Object[length];
this.size = 0;
pointer = 0;
}
/**
* Pridej prvek na konec bufferu
* @param i prvek
*/
public void addLast(ENTITY i) {
if (this.size == array.length) {
throw new IllegalStateException("Buffer is full");
}
array[pointer] = i;
pointer = modulo((pointer + 1), array.length);
size++;
}
/**
* Vrat a smaz prvni prvek
* @return prvni prvek
*/
public ENTITY getFirst() {
if (this.size == 0) {
throw new IllegalStateException("Buffer is empty");
}
ENTITY value = (ENTITY) array[modulo((pointer - size), array.length)];
array[modulo((pointer - size), array.length)] = null;
size--;
return value;
}
/**
* Precti prvni prvek
* @return prvni prvek
*/
public ENTITY readFirst() {
if (this.size == 0) {
throw new IllegalStateException("Buffer is empty");
}
ENTITY value = (ENTITY) array[modulo((pointer - size), array.length)];
return value;
}
/**
* x ≡ number mod(modulo)
* @param number number
* @param modulo modulo
* @return nejmensi nezaporne residuum
*/
private int modulo(int number, int modulo) {
if (number >= 0) {
return number % modulo;
}
int result = number % modulo;
return result == 0 ? 0 : result + modulo;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("Content: ");
for (int i = 0; i < size; i++) {
builder.append(array[modulo((pointer - size + i), array.length)]).append(" ");
}
builder.append("\nfirst index: ").append(modulo((pointer - size), array.length)).append(", last index:").append(pointer - 1).append(", size: ").append(size);
return builder.toString();
}
/**
* Pocet obsazenych prvku
* @return pocet prvku v bufferu
*/
public int getSize() {
return this.size;
}
/**
* Velikost bufferu
* @return maximalni pocet prvku v bufferu
*/
public int getLength() {
return array.length;
}
}
