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 O(1) , složitost operace přidání prvku na konec fronty je O(1) .

Kód

Java

 /**
  * 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;
     }
 }

Princip

Složitost operací

Kód

Doporučujeme