Skip to content

Instantly share code, notes, and snippets.

@gnaggnoyil
Last active January 2, 2016 19:10
Show Gist options
  • Save gnaggnoyil/1104d458ce73652ddbe7 to your computer and use it in GitHub Desktop.
Save gnaggnoyil/1104d458ce73652ddbe7 to your computer and use it in GitHub Desktop.
Binary Indexed Array
/*
Author: gnaggnoyil (gnaggnoyil at gmail.com)
License: WTFPL
*/
#ifndef _BIA_HPP_
#define _BIA_HPP_
#include <memory>
#include <utility>
#include <cstddef>
#include <new>
#include <type_traits>
#include <stdexcept>
inline size_t _lowbit(size_t x){
return x & ((~x) + 1);
}
template <typename Numerial, typename Allocator = std::allocator<Numerial>>
class BIA{
public:
BIA(size_t _size):size(_size){
if(_size == 0){
// According to Table 28 in 17.6.3.5 N4140, the return value is
// unspecfied if the number of elements that allocator is about
// to allocate is 0. Such situation must be avoided.
throw std::bad_alloc();
}
eleArray = allocator.allocate(size);
size_t i = 0;
try{
BIA **ptr = new BIA*(this);
for(i = 0;i < size;++i){
allocator.construct(eleArray + i, ptr, i);
}
}
catch(...){
for(--i;i >= 0;--i){
allocator.destroy<BIAElement>(eleArray + i);
}
allocator.deallocate(eleArray, size);
throw;
}
}
BIA(const BIA &_op):size(_op.size), allocator(_op.allocator){
eleArray = allocator.allocate(size);
size_t i = 0;
try{
BIA **ptr = new BIA*(this);
for(i = 0;i < size;++i){
allocator.construct(eleArray + i, *(_op.eleArray + i), ptr, i);
}
}
catch(...){
for(--i;i >= 0;--i){
allocator.destroy<BIAElement>(eleArray + i);
}
allocator.deallocate(eleArray, size);
throw;
}
}
BIA(BIA &&_op):BIA(std::move(_op), typename std::allocator_traits<AllocType>::propagate_on_container_move_assignment()){}
BIA &operator=(const BIA &_op){
if(this != &_op){
PointerType tmp = _op.allocator.allocate(_op.size);
size_t i = 0;
try{
BIA **ptr = new BIA*(this);
for(i = 0;i < size;++i){
_op.allocator.construct(tmp + i, *(_op.eleArray + i), ptr, i);
}
}
catch(...){
for(--i;i >= 0;--i){
_op.allocator.destroy<BIAElement>(tmp + i);
}
_op.allocator.deallocate(tmp, size);
throw;
}
delete eleArray->outer;
for(size_t i = 0;i < size;++i){
allocator.destroy(eleArray + i);
}
allocator.deallocate(eleArray, size);
size = _op.size;
allocator = _op.allocator;
eleArray = tmp;
}
return *this;
}
BIA &operator=(BIA &&_op){
if(this != &_op){
assignRv(_op, typename std::allocator_traits<AllocType>::propagate_on_container_move_assignment());
}
return *this;
}
~BIA(){
if(nullptr == eleArray){
// has been moved.
return ;
}
delete eleArray->outer;
for(size_t i = 0;i < size;++i){
allocator.destroy(eleArray + i);
}
allocator.deallocate(eleArray, size);
}
const size_t getSize() const{
return size;
}
template <typename NumerialRef>
void add(size_t _index, NumerialRef &&_delta){
if(_index > size){
throw std::out_of_range("BIA::add()");
}
for(size_t x = _index + 1;x <= size;x += _lowbit(x)){
(*(eleArray + x - 1)).num += std::forward<NumerialRef>(_delta);
}
}
template <typename NumerialRef>
void sub(size_t _index, NumerialRef &&_delta){
if(_index > size){
throw std::out_of_range("BIA::sub()");
}
for(size_t x = _index + 1;x <= size;x += _lowbit(x)){
(*(eleArray + x - 1)).num -= std::forward<NumerialRef>(_delta);
}
}
Numerial query(size_t _index) const{
if(_index > size){
throw std::out_of_range("BIA::query()");
}
Numerial res(0);
for(size_t x = _index + 1;x > 0;x -= _lowbit(x)){
res += (*(eleArray + x - 1)).num;
}
return res;
}
private:
class BIAElement{
public:
BIAElement(BIA **_outer, size_t _index):num(0), outer(_outer), index(_index){}
BIAElement(const BIAElement &_op, BIA **_outer, size_t _index):num(_op.num), outer(_outer), index(_index){}
BIAElement(BIAElement &&_op, BIA **_outer, size_t _index):num(std::move(_op.num)), outer(_outer), index(_index){}
BIAElement() = delete;
BIAElement(const BIAElement &) = delete;
BIAElement(BIAElement &&) = delete;
BIAElement &operator=(const BIAElement &) = delete;
BIAElement &operator=(BIAElement &&) = delete;
template <typename NumerialRef>
BIAElement &operator+=(NumerialRef &&_op){
(*outer)->add(index, std::forward<NumerialRef>(_op));
return *this;
}
template <typename NumerialRef>
BIAElement &operator-=(NumerialRef &&_op){
(*outer)->sub(index, std::forward<NumerialRef>(_op));
return *this;
}
~BIAElement(){
outer = nullptr;
}
Numerial num;
BIA **outer;
private:
size_t index;
};
BIA(BIA &&_op, std::true_type):size(std::move(_op.size)), allocator(std::move(_op.allocator)), eleArray(std::move(_op.eleArray)){
// case for moveable PointerType
eleArray->outer = this;
_op.eleArray = nullptr;
_op.size = 0;
}
BIA(BIA &&_op, std::false_type):size(std::move(_op.size)), allocator(std::move(_op.allocator)){
// case for unmoveable PointerType
eleArray = allocator.allocate(size);
size_t i = 0;
try{
BIA **ptr = new BIA*(this);
for(i = 0;i < size;++i){
allocator.construct(eleArray + i, std::move(*(_op.eleArray + i)), ptr, i);
}
}
catch(...){
for(--i;i >= 0;--i){
allocator.destroy<BIAElement>(eleArray + i);
}
allocator.deallocate(eleArray, size);
throw;
}
}
void assignRv(BIA &&_op, std::true_type){
size = std::move(_op.size);
allocator = std::move(_op.allocator);
eleArray = std::move(_op.eleArray);
*(eleArray->outer) = this;
_op.eleArray = nullptr;
_op.size = 0;
}
void assignRv(BIA &&_op, std::false_type){
PointerType tmp = _op.allocator.allocate(_op.size);
size_t i = 0;
try{
BIA **ptr = new BIA*(this);
for(i = 0;i < size;++i){
_op.allocator.construct(tmp + i, std::move(*(_op.eleArray + i)), ptr, i);
}
}
catch(...){
for(--i;i >= 0;--i){
allocator.destroy<BIAElement>(tmp + i);
}
allocator.deallocate(tmp, size);
throw;
}
delete eleArray->outer;
for(size_t i = 0;i < size;++i){
allocator.destroy(eleArray + i);
}
allocator.deallocate(eleArray, size);
size = std::move(_op.size);
allocator = std::move(_op.allocator);
eleArray = tmp;
}
public:
BIAElement &operator[](size_t n){
if(n >= size){
throw std::out_of_range("BIA::operator[]");
}
return *(eleArray + n);
}
private:
using AllocType = typename Allocator::template rebind<BIAElement>::other;
// According to N4140 17.6.3.5.4, PointerType shall always be a
// nullable pointer and random access iterator provided that
// AllocType satisfied the allocator requirements.
using PointerType = typename AllocType::pointer;
AllocType allocator;
PointerType eleArray;
size_t size;
};
#endif // _BIA_HPP_
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment