Skip to content

Instantly share code, notes, and snippets.

@hjroh0315
Created March 8, 2024 17:30
Show Gist options
  • Save hjroh0315/9095a95ff81a59fb0ebb9d6c894a9d76 to your computer and use it in GitHub Desktop.
Save hjroh0315/9095a95ff81a59fb0ebb9d6c894a9d76 to your computer and use it in GitHub Desktop.
fixed capacity ring buffer implementation (shit turned out long af)
#include<bits/stdc++.h>
using namespace std;
template<class T,ll sz>
struct buffer
{
array<T,sz>data;
ll L=0,R=0,Lm=0,Rm=0;
buffer():L(0),R(0),Lm(0),Rm(0){}
T& operator[](int i){ll t=Lm+i;if(t>=sz)t-=sz;return data[t];}
struct iterator
{
size_t idx;
buffer<T,sz>&par;
iterator&& operator++(int)
{
iterator pre=*this;
idx++;
return pre;
}
iterator& operator++()
{
idx++;
return *this;
}
iterator&& operator--(int)
{
iterator pre=*this;
idx--;
return pre;
}
iterator& operator--()
{
idx--;
return *this;
}
iterator& operator+=(int x)
{
idx+=x;
return *this;
}
iterator&& operator+(int x)
{
It temp=*this;
temp+=x;
return temp;
}
iterator& operator-=(int x)
{
idx-=x;
return *this;
}
iterator&& operator-(int x)
{
It temp=*this;
temp-=x;
return temp;
}
size_t operator-(const iterator& other)
{
//assert(&par!=&other.par);
return idx-other.idx;
}
T&operator[](size_t i)
{
return *(*this+i);
}
T&operator*()
{
return par[idx];
}
bool operator<(iterator r)
{
if(&r.par!=&par)return false;
else return idx<r.idx;
}
bool operator>(iterator r)
{
if(&r.par!=&par)return false;
else return idx>r.idx;
}
bool operator<=(iterator r)
{
if(&r.par!=&par)return false;
else return idx<=r.idx;
}
bool operator>=(iterator r)
{
if(&r.par!=&par)return false;
else return idx>=r.idx;
}
bool operator==(iterator r)
{
if(&r.par!=&par)return false;
else return r.idx==idx;
}
bool operator!=(iterator r)
{
if(&r.par!=&par)return true;
else return r.idx!=idx;
}
};
using It=iterator;
using const_iterator=const It;
using CIt=const_iterator;
T&front(){return data[Lm];}
T&back(){int t=Rm;t--;if(t<0)t+=sz;return data[t];}
void push_back(const T&val)
{
//if(R==L+sz)throw out_of_range("Circular Buffer Full"s);
//else
{
data[Rm]=val;
R++;Rm++;if(Rm>=sz)Rm-=sz;
}
}
void push_front(const T&val)
{
//if(R==L+sz)throw out_of_range("Circular Buffer Full"s);
//else
{
L--;Lm--;if(Lm<0)Lm+=sz;
data[Lm]=val;
}
}
void pop_back()
{
//if(R==L)throw out_of_range("Circular Buffer Empty"s);
//else
{
R--;Rm--;if(Rm<0)Rm+=sz;
}
}
void pop_front()
{
//if(R==L)throw out_of_range("Circular Buffer Empty"s);
//else
{
L++;Lm++;if(Lm>=sz)Lm-=sz;
}
}
It begin()
{
return It{0,*this};
}
size_t size()
{
return R-L;
}
It end()
{
return It{size(),*this};
}
bool empty()
{
return size()==0;
}
void swap(buffer<T,sz>&other)
{
swap(data,other.data);
swap(L,other.L);
swap(R,other.R);
}
It erase(It it)
{
//if(R==L)throw out_of_range("Circular Buffer Empty"s);
//if(it==end())throw out_of_range("Can't erase end");
It ii=it;
do
{
It tmp=it;++tmp;
*it=*tmp;++it;
}while(it!=end());
R--;Rm--;if(Rm<0)Rm+=sz;
return ii;
}
It insert(It it,const T& val)
{
//if(R==L+sz)throw out_of_range("Circular Buffer Full"s);
R++;Rm++;if(Rm>=sz)Rm-=sz;
It e=end();
while(e!=it)
{
--e;It tmp=e;--tmp;*e=*tmp;
}
*it=val;
return it;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment