LargeDynamicBitSet/DynamicBitSet.cpp at main · Twilight-Dream-Of-Magic/LargeDynamicBitSet · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include "DynamicBitSet.hpp"

namespace TwilightDream
{
	/* DynamicBitSet Iterators */

	DynamicBitSet::iterator DynamicBitSet::begin()
	{
		return iterator(true, &this->bitset, this->valid_number_of_bits());
	}

	DynamicBitSet::iterator DynamicBitSet::end()
	{
		return iterator(false, &this->bitset, this->valid_number_of_bits());
	}

	DynamicBitSet::const_iterator DynamicBitSet::cbegin() const
	{
		std::cerr << "Warning: Using a const DynamicBitSet with iterator is discouraged." << std::endl;
		return const_iterator(true, &this->bitset, this->valid_number_of_bits());
	}

	DynamicBitSet::const_iterator DynamicBitSet::cend() const
	{
		std::cerr << "Warning: Using a const DynamicBitSet with iterator is discouraged." << std::endl;
		return const_iterator(false, &this->bitset, this->valid_number_of_bits());
	}

	DynamicBitSet::reverse_iterator DynamicBitSet::rbegin()
	{
		return reverse_iterator(true, &this->bitset, this->valid_number_of_bits());
	}

	DynamicBitSet::reverse_iterator DynamicBitSet::rend()
	{
		return reverse_iterator(false, &this->bitset, this->valid_number_of_bits());
	}

	DynamicBitSet::const_reverse_iterator DynamicBitSet::crbegin() const
	{
		std::cerr << "Warning: Using a const DynamicBitSet with iterator is discouraged." << std::endl;
		return const_reverse_iterator(true, &this->bitset, this->valid_number_of_bits());
	}

	DynamicBitSet::const_reverse_iterator DynamicBitSet::crend() const
	{
		std::cerr << "Warning: Using a const DynamicBitSet with iterator is discouraged." << std::endl;
		return const_reverse_iterator(false, &this->bitset, this->valid_number_of_bits());
	}

	// Subscript Operator for non-const DynamicBitSet
	BitReference DynamicBitSet::operator[]( size_t index )
	{
		if ( index >= this->data_size )
			throw std::out_of_range( "Index out of range" );

		return BitReference( &(this->bitset[index / 32]), uint32_t(1) << index % 32 );
	}

	// Subscript Operator for non-const DynamicBitSet
	bool DynamicBitSet::operator[]( size_t index ) const
	{
		if ( index >= this->data_size )
			throw std::out_of_range( "Index out of range" );

		return this->bitset[ index / 32 ].bit_get( index % 32 );
	}

	// TODO: Is there a more efficient way to do this than converting to a binary string?
	// Bitwise left rotation (<<<=)
	void DynamicBitSet::rotate_left( size_t shift )
	{
		if ( shift == 0 || bitset.size() * 32 == shift || bitset.empty())
		{
			return;
		}

		if( shift >= 256 )
		{
			std::vector<bool> buffer = this->bit_vector_data();
			std::rotate(buffer.begin(), buffer.begin() + shift % buffer.size(), buffer.end());
			*this = DynamicBitSet(buffer);
			return;
		}

		DynamicBitSet left = *this;
		DynamicBitSet right = *this;
		left <<= shift;
		right >>= (bitset.size() * 32 - shift);
		*this = left | right;

		this->clear_leading_bit_zeros(false);

		data_size = this->valid_number_of_bits();
		data_capacity = this->bitset.size() * 32;
		data_chunk_count = this->bitset.size();
	}

	// TODO: Is there a more efficient way to do this than converting to a binary string?
	// Bitwise right rotation (>>>=)
	void DynamicBitSet::rotate_right( size_t shift )
	{
		if ( shift == 0 || bitset.size() * 32 == shift || bitset.empty() )
		{
			return;
		}

		if( shift >= 256 )
		{
			std::vector<bool> buffer = this->bit_vector_data();
			std::rotate(buffer.rbegin(), buffer.rbegin() + shift % buffer.size(), buffer.rend());
			*this = DynamicBitSet(buffer);
			return;
		}

		DynamicBitSet left = *this;
		DynamicBitSet right = *this;
		left >>= shift;
		right <<= (bitset.size() * 32 - shift);
		*this = left | right;

		this->clear_leading_bit_zeros(false);

		data_size = this->valid_number_of_bits();
		data_capacity = this->bitset.size() * 32;
		data_chunk_count = this->bitset.size();
	}

}  // namespace TwilightDream