Circular Buffer Design

Description:

Circular buffer class design.

Example:

Note

Idea:

这个code我用来练习class OOP的语法。

FIFO property, similar to queue, but circular

First index is the first element Last index is one after the last element

Size is the number of elements in buffer capacity is the max number it can hold

full empty functions

Once full, push new element will overwrite the old ones.

Constructor, default Constructor Copy Constructor Copy Assignment Destructor

Code:

Version 1, use STL vector as storage.

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <utility>
#include <memory>
#include <cmath>
#include <stdexcept>

using namespace std;

template <typename T>
class CirBuffer{
public:
    CirBuffer()=default;

    CirBuffer(size_t cap): buffer_(cap), capacity_(cap), first_(0), last_(0), size_(0){
    }

    CirBuffer(const CirBuffer & other): 
        buffer_(other.buffer_), capacity_(other.capacity_), first_(other.first_), last_(other.last_), size_(other.size_){
    }

    CirBuffer & operator=(const CirBuffer & rhs){
        buffer_=rhs.buffer_;
        capacity_=rhs.capacity_;
        first_=rhs.first_;
        last_=rhs.last_;
        size_=rhs.size_;

        return *this;
    }

    void pop(){
        if(empty()){
            throw runtime_error("Buffer is empty! Nothing to pop!");
        }
        else{
            first_=(first_+1)%capacity_;
            size_--;
        }
    }

    T top() const{
        if(empty()){
            throw runtime_error("Buffer is empty! Nothing to top!");
        }
        else{
            return buffer_[first_];
        }        
    }

    void push(T input){
        buffer_[last_]=input;
        last_ = (last_+1)%capacity_;
        if(full()){
            first_ = (first_+1)%capacity_;
        }
        else{
            size_++;
        }
    }

    bool empty() const{
        return size_==0;
    }

    bool full() const{
        return size_==capacity_;
    }

    size_t size() const{
        return size_;
    }

    void printFirstLast() const{
        cout<<"First "<<first_<<" ,Last "<<last_<<'\n';
    }

    const T& operator[](size_t offset) const {
        if(offset>=size_){
            throw runtime_error("access out of the buffer range!");
        }
        else{
            return buffer_[(first_+offset)%capacity_];
        }
    }

    // Follow Scott Meyers in Effective C++, do not duplicate functions.
    T& operator[](size_t offset){
        return const_cast<T &>(static_cast<const CirBuffer &> (* this)[offset]);
    }

    ostream& print(ostream & stm = cout) const{
        if(!empty()){
            if(first_<last_){
                for(auto i=first_; i<last_; ++i){
                    stm<<buffer_[i]<<' ';
                }
            }
            else{
                for(auto i=first_; i<capacity_; ++i){
                    stm<<buffer_[i]<<' ';
                }
                for(auto i=0; i<last_; ++i){
                    stm<<buffer_[i]<<' ';
                }
            }
        }
        return stm;
    }

private:
    vector<T> buffer_;
    size_t first_;
    size_t last_;
    size_t size_;
    size_t capacity_;
};




int main(){
    CirBuffer<double> cbuf(10);
    cbuf.push(1);
    cbuf.push(3);
    cbuf.push(4);
    cbuf.push(2);

    cbuf.print()<<'\n';
    cout<<cbuf.size()<<endl;

    cout<<cbuf.top()<<endl;
    cbuf.pop();
    cbuf.pop();
    cbuf.print()<<'\n';
    cbuf.push(1);
    cbuf.push(3);
    cbuf.push(4);
    cbuf.push(2);
    cbuf.push(1);
    cbuf.push(3);
    cbuf.push(4);
    cbuf.push(2);
    cbuf.push(6);
    cbuf.push(6);
    cbuf.push(6);
    cbuf.push(6);
    cbuf.push(6);
    cbuf.push(6);
    cbuf.print()<<'\n';

    cout<<cbuf[0]<<endl;
    cbuf[0]=99;
    cbuf.print()<<'\n';
    cbuf.printFirstLast();

    const CirBuffer<double> cbuf2(cbuf);
    cbuf2.print()<<'\n';
    cout<<cbuf[0]<<endl;
    cbuf2.printFirstLast();
    // cbuf2[0]=98; // error! const return type

    CirBuffer<double> cbuf3(2);
    cbuf3=cbuf;
    cbuf3[0]=11;
    cbuf3.print()<<'\n';
    cbuf.print()<<"\n";
    cout<<cbuf3.empty()<<endl;
    cout<<cbuf3.full()<<endl;

}

Version 2, use dynamic array as storage.

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <utility>
#include <memory>
#include <cmath>
#include <stdexcept>

using namespace std;

template <typename T>
class CirBuffer{
public:
    CirBuffer()=default;

    CirBuffer(size_t cap): buffer_(new T[cap]), capacity_(cap), first_(0), last_(0), size_(0){
    }

    CirBuffer(const CirBuffer & other): 
        buffer_(new T[other.capacity_]), capacity_(other.capacity_), first_(other.first_), last_(other.last_), size_(other.size_){
            for(size_t i=0; i<capacity_; ++i){
                buffer_[i] = other.buffer_[i];
            }
    }

    CirBuffer & operator=(const CirBuffer & rhs){
        if(this == &rhs) return *this;

        capacity_=rhs.capacity_;
        first_=rhs.first_;
        last_=rhs.last_;
        size_=rhs.size_;

        // Exception safe assignment
        T * orig_buffer = buffer_;
        buffer_=new T[capacity_];
        for(size_t i=0; i<capacity_; ++i){
            buffer_[i]=rhs.buffer_[i];
        }
        delete [] orig_buffer;

        return *this;
    }

    ~CirBuffer(){
        delete[] buffer_;
    }

    void pop(){
        if(empty()){
            throw runtime_error("Buffer is empty! Nothing to pop!");
        }
        else{
            first_=(first_+1)%capacity_;
            size_--;
        }
    }

    T top() const{
        if(empty()){
            throw runtime_error("Buffer is empty! Nothing to top!");
        }
        else{
            return buffer_[first_];
        }        
    }

    void push(T input){
        buffer_[last_]=input;
        last_ = (last_+1)%capacity_;
        if(full()){
            first_ = (first_+1)%capacity_;
        }
        else{
            size_++;
        }
    }

    bool empty() const{
        return size_==0;
    }

    bool full() const{
        return size_==capacity_;
    }

    size_t size() const{
        return size_;
    }

    void printFirstLast() const{
        cout<<"First "<<first_<<", Last "<<last_<<'\n';
    }

    const T& operator[](size_t offset) const {
        if(offset>=size_){
            throw runtime_error("access out of the buffer range!");
        }
        else{
            return buffer_[(first_+offset)%capacity_];
        }
    }

    // Follow Scott Meyers in Effective C++, do not duplicate functions.
    T& operator[](size_t offset){
        return const_cast<T &>(static_cast<const CirBuffer &> (* this)[offset]);
    }

    ostream& print(ostream & stm = cout) const{
        if(!empty()){
            if(first_<last_){
                for(auto i=first_; i<last_; ++i){
                    stm<<buffer_[i]<<' ';
                }
            }
            else{
                for(auto i=first_; i<capacity_; ++i){
                    stm<<buffer_[i]<<' ';
                }
                for(auto i=0; i<last_; ++i){
                    stm<<buffer_[i]<<' ';
                }
            }
        }
        return stm;
    }

private:
    T * buffer_;
    size_t first_;
    size_t last_;
    size_t size_;
    size_t capacity_;
};




int main(){
    CirBuffer<double> cbuf(10);
    cbuf.push(1);
    cbuf.push(3);
    cbuf.push(4);
    cbuf.push(2);

    cbuf.print()<<'\n';
    cout<<cbuf.size()<<endl;

    cout<<cbuf.top()<<endl;
    cbuf.pop();
    cbuf.pop();
    cbuf.print()<<'\n';
    cbuf.push(1);
    cbuf.push(3);
    cbuf.push(4);
    cbuf.push(2);
    cbuf.push(1);
    cbuf.push(3);
    cbuf.push(4);
    cbuf.push(2);
    cbuf.push(6);
    cbuf.push(6);
    cbuf.push(6);
    cbuf.push(6);
    cbuf.push(6);
    cbuf.push(6);
    cbuf.print()<<'\n';

    cout<<cbuf[0]<<endl;
    cbuf[0]=99;
    cbuf.print()<<'\n';
    cbuf.printFirstLast();

    const CirBuffer<double> cbuf2(cbuf);
    cbuf2.print()<<'\n';
    cout<<cbuf[0]<<endl;
    cbuf2.printFirstLast();
    // cbuf2[0]=98; // error! const return type

    CirBuffer<double> cbuf3(2);
    cbuf3=cbuf;
    cbuf3[0]=11;
    cbuf3.print()<<'\n';
    cbuf.print()<<"\n";
    cout<<cbuf3.empty()<<endl;
    cout<<cbuf3.full()<<endl;

}