Original Dynamic Bitset

dynamic_bitset.cpp

// [dynamic_bitset.hpp]
#ifndef __DYNAMIC_BITSET_HPP__
#define __DYNAMIC_BITSET_HPP__

#include <string>
#include <vector>
#include <stdexcept>
#include "dynamic_bitset.h"

class dynamic_bitset {
private:
	size_t _byte_size;
	unsigned char *_pow;
	unsigned char *_count_table;
	
	std::vector<unsigned char> *data;
	std::pair<size_t, size_t> _current_size;
	size_t _capacity_size;

	void _common_init();

	inline std::pair<size_t, size_t> _get_pos(size_t);
	inline bool _in_capacity(size_t);
	inline bool _in_capacity(std::pair<size_t, size_t>);

	std::string _normalized_string(std::string);
	unsigned char _binstr2uchar(std::string);
	unsigned char _binstr2uchar_rev(std::string);
	std::string _ulint2binstr(unsigned long int);
	std::string _uchar2binstr(unsigned char);

	//unsigned long int _binary_floor(unsigned long int);

public:
	dynamic_bitset();
	dynamic_bitset(size_t);
	dynamic_bitset(std::string);
	~dynamic_bitset();

	//dynamic_bitset& operator=(dynamic_bitset);

	bool at(size_t);
	bool test(size_t);
	bool operator[](size_t);

	size_t size();
	size_t capacity();
	size_t count();

	bool any();
	bool none();

	dynamic_bitset set();
	dynamic_bitset set(size_t, bool);

	dynamic_bitset reset();
	dynamic_bitset reset(size_t);

	dynamic_bitset flip();
	dynamic_bitset flip(size_t);

	unsigned long int to_ulong();
	std::string to_string();
	std::string to_string(std::string);
	std::string to_dec_string();

	bool operator==(dynamic_bitset&);
	bool equals(dynamic_bitset&);
	bool operator!=(dynamic_bitset&);
	
	dynamic_bitset operator~();
	dynamic_bitset operator<<(size_t);
	dynamic_bitset operator>>(size_t);
	dynamic_bitset& operator<<=(size_t);
	dynamic_bitset& operator>>=(size_t);
	
	void info();
};

#endif

/***************************************************/

// [dynamic_bitset.cpp]

#include <iostream>
#include <algorithm>
#include "dynamic_bitset.h"

/*****************************************************************************/

const std::string out_of_range_message = "out-of-range exception";
const std::string overflow_message = "overflow exception";

const std::string at_message = "dynamic_bitset::at() thorws ";
const std::string test_message = "dynamic_bitset::test() thorws ";
const std::string op_at_message = "dynamic_bitset::ooperator[] thorws ";
const std::string to_ulong_message = "dynamic_bitset::to_ulong() thorws ";

/*****************************************************************************/

inline static size_t min(size_t a, size_t b) {return (a < b) ? a : b;}
inline static size_t max(size_t a, size_t b) {return (a > b) ? a : b;}

/*****************************************************************************/

void dynamic_bitset::_common_init() {
	_byte_size = sizeof(unsigned char) * 8;
	
	_pow = new unsigned char[_byte_size];
	_pow[0] = 1;
	for(size_t i=1; i<_byte_size; ++i) _pow[i] = _pow[i-1] << 1;
	
	_count_table = new unsigned char[0x100];
	_count_table[0] = 0;
	_count_table[1] = _count_table[2] = 1;
	_count_table[3] = 2;
	for(int i=0x04; i<0x10;  ++i)
		_count_table[i] = _count_table[i&0x03] + _count_table[i>>2];
	for(int i=0x10; i<0x100; ++i)
		_count_table[i] = _count_table[i&0x0F] + _count_table[i>>4];
}

dynamic_bitset::dynamic_bitset() {
	_common_init();
	
	_current_size = std::pair<size_t, size_t>(0, 0);
	_capacity_size = 1;
	
	data = new std::vector<unsigned char>(1);
	(*data)[0] = 0;
}

dynamic_bitset::dynamic_bitset(size_t init_size) {
	_common_init();
	
	_current_size = std::pair<size_t, size_t>(
		init_size / _byte_size, init_size % _byte_size
	);
	size_t vec_init_size = _current_size.first
		+ ((_current_size.second == 0) ? 0 : 1);
	_capacity_size = vec_init_size * _byte_size;
	
	data = new std::vector<unsigned char>(vec_init_size);
	for(size_t i=0; i<vec_init_size; ++i) (*data)[i] = 0;
}

dynamic_bitset::dynamic_bitset(std::string str) {
	_common_init();
	
	std::string _str = _normalized_string(str);
	
	size_t str_size = _str.size();
	_current_size = std::pair<size_t, size_t>(
		str_size / _byte_size, str_size % _byte_size
	);
	size_t vec_init_size = _current_size.first
		+ ((_current_size.second == 0) ? 0 : 1);
	_capacity_size = vec_init_size * _byte_size;
	
	std::string zero_padding = "";
	for(size_t i=0; i<_byte_size-_current_size.second; ++i)
		zero_padding += '0';
	_str += zero_padding;
	
	data = new std::vector<unsigned char>(vec_init_size);
	for(size_t i=0; i<vec_init_size; ++i)
		(*data)[i] = _binstr2uchar_rev( _str.substr(i*_byte_size, _byte_size) );
}

dynamic_bitset::~dynamic_bitset() {
	//if(_pow != NULL) delete _pow;
	//if(_count_table != NULL) delete _count_table;
	//if(data != NULL) delete data;
}

/*****************************************************************************/
/*
dynamic_bitset& dynamic_bitset::operator=(dynamic_bitset bitset) {
	size_t new_size = bitset.size();
	_current_size = std::pair<size_t, size_t>(
		new_size / _byte_size, new_size % _byte_size
	);
	size_t vec_init_size = _current_size.first
		+ ((_current_size.second == 0) ? 0 : 1);
	_capacity_size = vec_init_size * _byte_size;
	
	//if(data != NULL) delete data;
	
	std::string _str = bitset.to_string();
	data = new std::vector<unsigned char>(vec_init_size);
	for(size_t i=0; i<vec_init_size; ++i)
		(*data)[i] = _binstr2uchar_rev( _str.substr(i*_byte_size, _byte_size) );
	
	return *this;
}
*/
/*****************************************************************************/

size_t dynamic_bitset::size()
	{return _current_size.first * _byte_size + _current_size.second;}

size_t dynamic_bitset::capacity()
	{return _capacity_size * _byte_size;}

size_t dynamic_bitset::count() {
	size_t value = 0;
	for(size_t i=0; i<_current_size.first; ++i)
		value += _count_table[(*data)[i]];
	value += _count_table[
		(*data)[_current_size.first] & (_pow[_current_size.second]-1)
	];
	return value;
}

/*****************************************************************************/

bool dynamic_bitset::at(size_t pos) {
	std::pair<size_t, size_t> _pos = _get_pos(pos);
	if(!_in_capacity(_pos))
		throw std::out_of_range(at_message + out_of_range_message);
	return ( ( (*data)[_pos.first] >> _pos.second ) & 1 == 1);
}

bool dynamic_bitset::test(size_t pos) {
	std::pair<size_t, size_t> _pos = _get_pos(pos);
	if(!_in_capacity(_pos))
		throw std::out_of_range(test_message + out_of_range_message);
	return ( ( (*data)[_pos.first] >> _pos.second ) & 1 == 1);
}

bool dynamic_bitset::operator[](size_t pos) {
	std::pair<size_t, size_t> _pos = _get_pos(pos);
	if(!_in_capacity(_pos))
		throw std::out_of_range(at_message + out_of_range_message);
	return ( ( (*data)[_pos.first] >> _pos.second ) & 1 == 1);
}

/*****************************************************************************/

dynamic_bitset dynamic_bitset::set() {
	unsigned char fill = (1 << _byte_size) - 1;
	for(size_t i=0; i<_current_size.first; ++i) (*data)[i] = fill;
	(*data)[_current_size.first] = _pow[_current_size.second]-1;
	return *this;
}

dynamic_bitset dynamic_bitset::set(size_t pos, bool val) {
	std::pair<size_t, size_t> _pos = _get_pos(pos);
	if(!_in_capacity(_pos)) return *this;
	
	unsigned char mask = _pow[_pos.second];
	if(val)	(*data)[_pos.first] |=  mask;
	else	(*data)[_pos.first] &= ~mask;
	return *this;
}

/*****************************************************************************/

dynamic_bitset dynamic_bitset::reset() {
	for(size_t i=0; i<=_current_size.first; ++i) (*data)[i] = 0x00;
	return *this;
}

dynamic_bitset dynamic_bitset::reset(size_t pos) {
	std::pair<size_t, size_t> _pos = _get_pos(pos);
	if(!_in_capacity(_pos)) return *this;
	(*data)[_pos.first] &= ~_pow[_pos.second];
	return *this;
}

/*****************************************************************************/

dynamic_bitset dynamic_bitset::flip() {
	for(size_t i=0; i<=_current_size.first; ++i) (*data)[i] = ~(*data)[i];
	(*data)[_current_size.first] &= _pow[_current_size.second]-1;
	return *this;
}

dynamic_bitset dynamic_bitset::flip(size_t pos) {
	std::pair<size_t, size_t> _pos = _get_pos(pos);
	if(!_in_capacity(_pos))	return *this;
	
	unsigned char mask = _pow[_pos.second];
	bool val = ((*data)[_pos.first] >> _pos.second) & 1 != 1;
	if(val)	(*data)[_pos.first] |=  mask;
	else	(*data)[_pos.first] &= ~mask;
	return *this;
}

/*****************************************************************************/

bool dynamic_bitset::any() {
	for(size_t i=0; i<=_current_size.first; ++i)
		if((*data)[i] != 0)	return true;
	return false;
}

bool dynamic_bitset::none() {return !any();}

/*****************************************************************************/

bool dynamic_bitset::operator==(dynamic_bitset& b) {
	size_t width = size();
	if(b.size() != width)	return false;
	for(size_t i=0; i<width; ++i) if(b[i] != at(i)) return false;
	return true;
}

bool dynamic_bitset::operator!=(dynamic_bitset& b) {
	size_t width = size();
	if(b.size() != width)	return true;
	for(size_t i=0; i<width; ++i) if(b[i] != at(i)) return true;
	return false;
}

bool dynamic_bitset::equals(dynamic_bitset& b) {
	size_t size_a = size();
	size_t size_b = b.size();
	
	if(size_a < size_b) {
		for(size_t i=0; i<size_a; ++i)      if(b[i] != at(i)) return false;
		for(size_t i=size_a; i<size_b; ++i) if(b[i]         ) return false;
	} else {
		for(size_t i=0; i<size_b; ++i)      if(b[i] != at(i)) return false;
		for(size_t i=size_b; i<size_a; ++i) if(at(i)        ) return false;
	}
	return true;
}

/*****************************************************************************/

dynamic_bitset dynamic_bitset::operator~() {
	dynamic_bitset new_bitset(to_string());
	new_bitset = new_bitset.flip();
	return new_bitset;
}

dynamic_bitset dynamic_bitset::operator<<(size_t n) {
	std::string padding_zero = "";
	for(size_t i=0; i<n; ++i) padding_zero += "0";
	return dynamic_bitset(to_string() + padding_zero);
}

dynamic_bitset dynamic_bitset::operator>>(size_t n) {
	std::string binary = to_string();
	size_t binary_size = size();
	return dynamic_bitset(binary.erase(binary_size-n));
}

dynamic_bitset& dynamic_bitset::operator<<=(size_t n) {
	info();
	std::pair<size_t, size_t> delta = std::pair<size_t, size_t>(
		n / _byte_size, n % _byte_size
	);
	delta.second  = (delta.second + _current_size.second) % _byte_size;
	delta.first  += (delta.second + _current_size.second) / _byte_size;
	
	std::cout << delta.first << ", " << delta.second << std::endl;
	
	
	return *this;
}

dynamic_bitset& dynamic_bitset::operator>>=(size_t n) {
	info();
	
	
	return *this;
}

/*****************************************************************************/

inline std::pair<size_t, size_t> dynamic_bitset::_get_pos(size_t pos)
	{return std::pair<size_t, size_t>(pos / _byte_size, pos % _byte_size);}

inline bool dynamic_bitset::_in_capacity(size_t pos) {
	std::pair<size_t, size_t> _pos = _get_pos(pos);
	return !(
		_pos.first > _current_size.first || 
		(
			_pos.first == _current_size.first  &&
			_pos.second > _current_size.second
		)
	);
}

inline bool dynamic_bitset::_in_capacity(std::pair<size_t, size_t> _pos) {
	return !(
		_pos.first > _current_size.first || 
		(
			_pos.first == _current_size.first  &&
			_pos.second > _current_size.second
		)
	);
}

/*****************************************************************************/

unsigned long int dynamic_bitset::to_ulong() {
	if(
		_current_size.first > sizeof(unsigned long int) ||
		(
			_current_size.first == sizeof(unsigned long int) &&
			_current_size.second > 0
		)
	)
		throw std::overflow_error(to_ulong_message + overflow_message);
	
	unsigned long int value = 0;
	for(size_t i=0; i<=_current_size.first; ++i)
		value += (*data)[i] << (i * _byte_size);
	value += (
			(*data)[_current_size.first] & (_pow[_current_size.second] - 1)
		) << (_current_size.first * _byte_size);
	return value;
}

/*****************************************************************************/

std::string dynamic_bitset::_normalized_string(std::string str) {
	std::string _str = "";
	size_t length = str.size();
	for(size_t i=0; i<length; ++i) {
		switch(str[i]) {
			case '0':	_str = '0' + _str;	break;
			case '1':	_str = '1' + _str;	break;
			default:	break;
		}
	}
	return _str;
}

unsigned char dynamic_bitset::_binstr2uchar(std::string str) {
	unsigned char value = 0;
	for(int i=0; i<_byte_size; ++i) if(str[i]=='1') value += 1<<(_byte_size-1-i);
	return value;
}

unsigned char dynamic_bitset::_binstr2uchar_rev(std::string str) {
	unsigned char value = 0;
	for(int i=_byte_size-1; i>=0; --i) if(str[i]=='1') value += 1<<i;
	return value;
}

std::string dynamic_bitset::_ulint2binstr(unsigned long int n) {
	std::string str = "";
	unsigned long int max = 1 << (sizeof(unsigned long int) * _byte_size - 1);
	for(unsigned long int i=max; i>=1; n&=i-1, i>>=1)
		str += (n / i == 1) ? '1': '0';
	return str;
}

std::string dynamic_bitset::_uchar2binstr(unsigned char n) {
	std::string str = "";
	unsigned long int max = 1 << (_byte_size - 1);
	for(unsigned char i=max; i>=1; n&=i-1, i>>=1)
		str += (n / i == 1) ? '1' : '0';
	return str;
}

std::string dynamic_bitset::to_string() {
	std::string str = "";
	for(size_t i=0; i<_current_size.first; ++i)
		str = _uchar2binstr((*data)[i]) + str;
	str = _uchar2binstr((*data)[_current_size.first]) + str;
	return str.erase(0, _byte_size-_current_size.second);
}

std::string dynamic_bitset::to_string(std::string separate) {
	std::string str = "";
	for(size_t i=0; i<_current_size.first; ++i)
		str = separate + _uchar2binstr((*data)[i]) + str;
	str = _uchar2binstr((*data)[_current_size.first]) + str;
	return str.erase(0, 8-_current_size.second);
}

std::string dynamic_bitset::to_dec_string() {
	
	// Stub
	
}

/*****************************************************************************/

void dynamic_bitset::info() {
	std::cout << "_current_size: " << _current_size.first << ", " << _current_size.second << std::endl;
	std::cout << "_capacity_size: " << _capacity_size << std::endl;
	//std::cout << "[debug] " << _ulint2binstr(16+32+64) << std::endl;
}

/*
unsigned long int dynamic_bitset::_binary_floor(unsigned long int n) {
	unsigned long int floor = 1;
	while(n >= floor) floor = floor << 1;
	return floor;
}
*/