Binary Indexed Array

bia.hpp

/*
	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_