Created
March 8, 2024 17:30
-
-
Save hjroh0315/9095a95ff81a59fb0ebb9d6c894a9d76 to your computer and use it in GitHub Desktop.
fixed capacity ring buffer implementation (shit turned out long af)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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>∥ | |
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