#pragma once
#include<cstdint>usingnamespacestd;namespaceHashMapImpl{usingu32=uint32_t;usingu64=uint64_t;template<typenameKey,typenameData>structHashMapBase;template<typenameKey,typenameData>structitrB:iterator<bidirectional_iterator_tag,Data,ptrdiff_t,Data*,Data&>{usingbase=iterator<bidirectional_iterator_tag,Data,ptrdiff_t,Data*,Data&>;usingptr=typenamebase::pointer;usingref=typenamebase::reference;u32i;HashMapBase<Key,Data>*p;explicitconstexpritrB():i(0),p(nullptr){}explicitconstexpritrB(u32_i,HashMapBase<Key,Data>*_p):i(_i),p(_p){}explicitconstexpritrB(u32_i,constHashMapBase<Key,Data>*_p):i(_i),p(const_cast<HashMapBase<Key,Data>*>(_p)){}friendvoidswap(itrB&l,itrB&r){swap(l.i,r.i),swap(l.p,r.p);}friendbooloperator==(constitrB&l,constitrB&r){returnl.i==r.i;}friendbooloperator!=(constitrB&l,constitrB&r){returnl.i!=r.i;}constrefoperator*()const{returnconst_cast<constHashMapBase<Key,Data>*>(p)->data[i];}refoperator*(){returnp->data[i];}ptroperator->()const{return&(p->data[i]);}itrB&operator++(){assert(i!=p->cap&&"itr::operator++()");do{i++;if(i==p->cap)break;if(p->occupied_flag[i]&&!p->deleted_flag[i])break;}while(true);return(*this);}itrBoperator++(int){itrBit(*this);++(*this);returnit;}itrB&operator--(){do{i--;if(p->occupied_flag[i]&&!p->deleted_flag[i])break;assert(i!=0&&"itr::operator--()");}while(true);return(*this);}itrBoperator--(int){itrBit(*this);--(*this);returnit;}};template<typenameKey,typenameData>structHashMapBase{usingu32=uint32_t;usingu64=uint64_t;usingiterator=itrB<Key,Data>;usingitr=iterator;protected:template<typenameK>inlineu64randomized(constK&key)const{returnu64(key)^r;}template<typenameK,enable_if_t<is_same<K,Key>::value,nullptr_t>=nullptr,enable_if_t<is_integral<K>::value,nullptr_t>=nullptr>inlineu32inner_hash(constK&key)const{return(randomized(key)*11995408973635179863ULL)>>shift;}template<typenameK,enable_if_t<is_same<K,Key>::value,nullptr_t>=nullptr,enable_if_t<is_integral<decltype(K::first)>::value,nullptr_t>=nullptr,enable_if_t<is_integral<decltype(K::second)>::value,nullptr_t>=nullptr>inlineu32inner_hash(constK&key)const{u64a=randomized(key.first),b=randomized(key.second);a*=11995408973635179863ULL;b*=10150724397891781847ULL;return(a+b)>>shift;}template<typenameK,enable_if_t<is_same<K,Key>::value,nullptr_t>=nullptr,enable_if_t<is_integral<typenameK::value_type>::value,nullptr_t>=nullptr>inlineu32inner_hash(constK&key)const{staticconstexpru64mod=(1LL<<61)-1;staticconstexpru64base=950699498548472943ULL;u64res=0;for(auto&elem:key){__uint128_tx=__uint128_t(res)*base+(randomized(elem)&mod);res=(x&mod)+(x>>61);}__uint128_tx=__uint128_t(res)*base;res=(x&mod)+(x>>61);if(res>=mod)res-=mod;returnres>>(shift-3);}template<typenameD=Data,enable_if_t<is_same<D,Key>::value,nullptr_t>=nullptr>inlineu32hash(constD&dat)const{returninner_hash(dat);}template<typenameD=Data,enable_if_t<is_same<decltype(D::first),Key>::value,nullptr_t>=nullptr>inlineu32hash(constD&dat)const{returninner_hash(dat.first);}template<typenameD=Data,enable_if_t<is_same<D,Key>::value,nullptr_t>=nullptr>inlineKeydata_to_key(constD&dat)const{returndat;}template<typenameD=Data,enable_if_t<is_same<decltype(D::first),Key>::value,nullptr_t>=nullptr>inlineKeydata_to_key(constD&dat)const{returndat.first;}voidreallocate(u32ncap){vector<Data>ndata(ncap);vector<bool>nf(ncap);shift=64-__lg(ncap);for(u32i=0;i<cap;i++){if(occupied_flag[i]&&!deleted_flag[i]){u32h=hash(data[i]);while(nf[h])h=(h+1)&(ncap-1);ndata[h]=move(data[i]);nf[h]=true;}}data.swap(ndata);occupied_flag.swap(nf);cap=ncap;occupied=s;deleted_flag.resize(cap);fill(std::begin(deleted_flag),std::end(deleted_flag),false);}inlineboolextend_rate(u32x)const{returnx*2>=cap;}inlineboolshrink_rate(u32x)const{returnHASHMAP_DEFAULT_SIZE<cap&&x*10<=cap;}inlinevoidextend(){reallocate(cap<<1);}inlinevoidshrink(){reallocate(cap>>1);}public:u32cap,s,occupied;vector<Data>data;vector<bool>occupied_flag,deleted_flag;u32shift;staticu64r;staticconstexpruint32_tHASHMAP_DEFAULT_SIZE=4;explicitHashMapBase():cap(HASHMAP_DEFAULT_SIZE),s(0),occupied(0),data(cap),occupied_flag(cap),deleted_flag(cap),shift(64-__lg(cap)){}itrbegin()const{u32h=0;while(h!=cap){if(occupied_flag[h]&&!deleted_flag[h])break;h++;}returnitr(h,this);}itrend()const{returnitr(this->cap,this);}frienditrbegin(constHashMapBase&h){returnh.begin();}frienditrend(constHashMapBase&h){returnh.end();}itrfind(constKey&key)const{u32h=inner_hash(key);while(true){if(occupied_flag[h]==false)returnthis->end();if(data_to_key(data[h])==key){if(deleted_flag[h]==true)returnthis->end();returnitr(h,this);}h=(h+1)&(cap-1);}}boolcontain(constKey&key)const{returnfind(key)!=this->end();}itrinsert(constData&d){u32h=hash(d);while(true){if(occupied_flag[h]==false){if(extend_rate(occupied+1)){extend();h=hash(d);continue;}data[h]=d;occupied_flag[h]=true;++occupied,++s;returnitr(h,this);}if(data_to_key(data[h])==data_to_key(d)){if(deleted_flag[h]==true){data[h]=d;deleted_flag[h]=false;++s;}returnitr(h,this);}h=(h+1)&(cap-1);}}// tips for speed up :// if return value is unnecessary, make argument_2 false.itrerase(itrit,boolget_next=true){if(it==this->end())returnthis->end();s--;if(!get_next){this->deleted_flag[it.i]=true;if(shrink_rate(s))shrink();returnthis->end();}itrnxt=it;nxt++;this->deleted_flag[it.i]=true;if(shrink_rate(s)){Datad=data[nxt.i];shrink();it=find(data_to_key(d));}returnnxt;}itrerase(constKey&key){returnerase(find(key));}intcount(constKey&key){returnfind(key)==end()?0:1;}boolempty()const{returns==0;}intsize()const{returns;}voidclear(){fill(std::begin(occupied_flag),std::end(occupied_flag),false);fill(std::begin(deleted_flag),std::end(deleted_flag),false);s=occupied=0;}voidreserve(intn){if(n<=0)return;n=1<<min(23,__lg(n)+2);if(cap<u32(n))reallocate(n);}};template<typenameKey,typenameData>uint64_tHashMapBase<Key,Data>::r=chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count();}// namespace HashMapImpl/**
* @brief Hash Map(base) (ハッシュマップ・基底クラス)
*/
#line 2 "hashmap/hashmap-base.hpp"
#include<cstdint>usingnamespacestd;namespaceHashMapImpl{usingu32=uint32_t;usingu64=uint64_t;template<typenameKey,typenameData>structHashMapBase;template<typenameKey,typenameData>structitrB:iterator<bidirectional_iterator_tag,Data,ptrdiff_t,Data*,Data&>{usingbase=iterator<bidirectional_iterator_tag,Data,ptrdiff_t,Data*,Data&>;usingptr=typenamebase::pointer;usingref=typenamebase::reference;u32i;HashMapBase<Key,Data>*p;explicitconstexpritrB():i(0),p(nullptr){}explicitconstexpritrB(u32_i,HashMapBase<Key,Data>*_p):i(_i),p(_p){}explicitconstexpritrB(u32_i,constHashMapBase<Key,Data>*_p):i(_i),p(const_cast<HashMapBase<Key,Data>*>(_p)){}friendvoidswap(itrB&l,itrB&r){swap(l.i,r.i),swap(l.p,r.p);}friendbooloperator==(constitrB&l,constitrB&r){returnl.i==r.i;}friendbooloperator!=(constitrB&l,constitrB&r){returnl.i!=r.i;}constrefoperator*()const{returnconst_cast<constHashMapBase<Key,Data>*>(p)->data[i];}refoperator*(){returnp->data[i];}ptroperator->()const{return&(p->data[i]);}itrB&operator++(){assert(i!=p->cap&&"itr::operator++()");do{i++;if(i==p->cap)break;if(p->occupied_flag[i]&&!p->deleted_flag[i])break;}while(true);return(*this);}itrBoperator++(int){itrBit(*this);++(*this);returnit;}itrB&operator--(){do{i--;if(p->occupied_flag[i]&&!p->deleted_flag[i])break;assert(i!=0&&"itr::operator--()");}while(true);return(*this);}itrBoperator--(int){itrBit(*this);--(*this);returnit;}};template<typenameKey,typenameData>structHashMapBase{usingu32=uint32_t;usingu64=uint64_t;usingiterator=itrB<Key,Data>;usingitr=iterator;protected:template<typenameK>inlineu64randomized(constK&key)const{returnu64(key)^r;}template<typenameK,enable_if_t<is_same<K,Key>::value,nullptr_t>=nullptr,enable_if_t<is_integral<K>::value,nullptr_t>=nullptr>inlineu32inner_hash(constK&key)const{return(randomized(key)*11995408973635179863ULL)>>shift;}template<typenameK,enable_if_t<is_same<K,Key>::value,nullptr_t>=nullptr,enable_if_t<is_integral<decltype(K::first)>::value,nullptr_t>=nullptr,enable_if_t<is_integral<decltype(K::second)>::value,nullptr_t>=nullptr>inlineu32inner_hash(constK&key)const{u64a=randomized(key.first),b=randomized(key.second);a*=11995408973635179863ULL;b*=10150724397891781847ULL;return(a+b)>>shift;}template<typenameK,enable_if_t<is_same<K,Key>::value,nullptr_t>=nullptr,enable_if_t<is_integral<typenameK::value_type>::value,nullptr_t>=nullptr>inlineu32inner_hash(constK&key)const{staticconstexpru64mod=(1LL<<61)-1;staticconstexpru64base=950699498548472943ULL;u64res=0;for(auto&elem:key){__uint128_tx=__uint128_t(res)*base+(randomized(elem)&mod);res=(x&mod)+(x>>61);}__uint128_tx=__uint128_t(res)*base;res=(x&mod)+(x>>61);if(res>=mod)res-=mod;returnres>>(shift-3);}template<typenameD=Data,enable_if_t<is_same<D,Key>::value,nullptr_t>=nullptr>inlineu32hash(constD&dat)const{returninner_hash(dat);}template<typenameD=Data,enable_if_t<is_same<decltype(D::first),Key>::value,nullptr_t>=nullptr>inlineu32hash(constD&dat)const{returninner_hash(dat.first);}template<typenameD=Data,enable_if_t<is_same<D,Key>::value,nullptr_t>=nullptr>inlineKeydata_to_key(constD&dat)const{returndat;}template<typenameD=Data,enable_if_t<is_same<decltype(D::first),Key>::value,nullptr_t>=nullptr>inlineKeydata_to_key(constD&dat)const{returndat.first;}voidreallocate(u32ncap){vector<Data>ndata(ncap);vector<bool>nf(ncap);shift=64-__lg(ncap);for(u32i=0;i<cap;i++){if(occupied_flag[i]&&!deleted_flag[i]){u32h=hash(data[i]);while(nf[h])h=(h+1)&(ncap-1);ndata[h]=move(data[i]);nf[h]=true;}}data.swap(ndata);occupied_flag.swap(nf);cap=ncap;occupied=s;deleted_flag.resize(cap);fill(std::begin(deleted_flag),std::end(deleted_flag),false);}inlineboolextend_rate(u32x)const{returnx*2>=cap;}inlineboolshrink_rate(u32x)const{returnHASHMAP_DEFAULT_SIZE<cap&&x*10<=cap;}inlinevoidextend(){reallocate(cap<<1);}inlinevoidshrink(){reallocate(cap>>1);}public:u32cap,s,occupied;vector<Data>data;vector<bool>occupied_flag,deleted_flag;u32shift;staticu64r;staticconstexpruint32_tHASHMAP_DEFAULT_SIZE=4;explicitHashMapBase():cap(HASHMAP_DEFAULT_SIZE),s(0),occupied(0),data(cap),occupied_flag(cap),deleted_flag(cap),shift(64-__lg(cap)){}itrbegin()const{u32h=0;while(h!=cap){if(occupied_flag[h]&&!deleted_flag[h])break;h++;}returnitr(h,this);}itrend()const{returnitr(this->cap,this);}frienditrbegin(constHashMapBase&h){returnh.begin();}frienditrend(constHashMapBase&h){returnh.end();}itrfind(constKey&key)const{u32h=inner_hash(key);while(true){if(occupied_flag[h]==false)returnthis->end();if(data_to_key(data[h])==key){if(deleted_flag[h]==true)returnthis->end();returnitr(h,this);}h=(h+1)&(cap-1);}}boolcontain(constKey&key)const{returnfind(key)!=this->end();}itrinsert(constData&d){u32h=hash(d);while(true){if(occupied_flag[h]==false){if(extend_rate(occupied+1)){extend();h=hash(d);continue;}data[h]=d;occupied_flag[h]=true;++occupied,++s;returnitr(h,this);}if(data_to_key(data[h])==data_to_key(d)){if(deleted_flag[h]==true){data[h]=d;deleted_flag[h]=false;++s;}returnitr(h,this);}h=(h+1)&(cap-1);}}// tips for speed up :// if return value is unnecessary, make argument_2 false.itrerase(itrit,boolget_next=true){if(it==this->end())returnthis->end();s--;if(!get_next){this->deleted_flag[it.i]=true;if(shrink_rate(s))shrink();returnthis->end();}itrnxt=it;nxt++;this->deleted_flag[it.i]=true;if(shrink_rate(s)){Datad=data[nxt.i];shrink();it=find(data_to_key(d));}returnnxt;}itrerase(constKey&key){returnerase(find(key));}intcount(constKey&key){returnfind(key)==end()?0:1;}boolempty()const{returns==0;}intsize()const{returns;}voidclear(){fill(std::begin(occupied_flag),std::end(occupied_flag),false);fill(std::begin(deleted_flag),std::end(deleted_flag),false);s=occupied=0;}voidreserve(intn){if(n<=0)return;n=1<<min(23,__lg(n)+2);if(cap<u32(n))reallocate(n);}};template<typenameKey,typenameData>uint64_tHashMapBase<Key,Data>::r=chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count();}// namespace HashMapImpl/**
* @brief Hash Map(base) (ハッシュマップ・基底クラス)
*/