14816556113

Committed 04 May 2025 01:49AM UTC coverage: 97.086% (-0.5%) from 97.623%

Build # 14816556113

Build Type

Pull #2

github

Committed by

web-flow

Commit Message

Merge 947e4829a into d0bfc09a2

Pull Request Pull Request #2: Break up bitlib_utils. Seed tests from the test case name to prevent varying coverage results

Run Details

1266 of 1304 relevant lines covered (97.09%)

16786579.26 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

90.63

/include/bitlib/bit-algorithms/rotate.hpp

// ================================= ROTATE ================================= //
// Project:         The Experimental Bit Algorithms Library
// Name:            rotate.hpp
// Description:     bit_iterator overloads for std::rotate
// Contributor(s):  Bryce Kille [2019]
// License:         BSD 3-Clause License
// ========================================================================== //
#ifndef _ROTATE_HPP_INCLUDED
#define _ROTATE_HPP_INCLUDED
// ========================================================================== //



// ============================== PREAMBLE ================================== //
// C++ standard library
#include <iostream>
// Project sources
#include "bit_algorithm.hpp"
// Third-party libraries
// Miscellaneous
namespace bit {
// ========================================================================== //

// Rotates a range by copying [first...n_first) to the stack, then shifting
// the range to the left and appending the copied section to the end.
//
// Note: distance(first, n_first) <= 3*digits
template <class ForwardIt, int BufferSize>
bit_iterator<ForwardIt> _rotate_via_copy_begin(
   bit_iterator<ForwardIt> first,
   bit_iterator<ForwardIt> n_first,
   bit_iterator<ForwardIt> last
) {
    // Types and constants
    using word_type = typename bit_iterator<ForwardIt>::word_type;
    using size_type = typename bit_iterator<ForwardIt>::size_type;
    constexpr size_type digits = binary_digits<word_type>::value;

    size_type k = distance(first, n_first);
    assert(k <= BufferSize*digits);
    word_type copy_arr[BufferSize];
    copy_arr[0] = *first.base();
    ForwardIt it = ++first.base();
    short unsigned int pos = 1;
    short int bits_left_to_copy = k - (digits - first.position());
    while (bits_left_to_copy > 0) {
        copy_arr[pos++] = *it++;
        bits_left_to_copy -= digits;
    }
    bit_iterator<ForwardIt> ret = shift_left(first, last, k);
    copy(
        bit_iterator<word_type*>(copy_arr, first.position()),
        bit_iterator<word_type*>(
                copy_arr,
                first.position()
        ) + k,
        ret
    );
    return ret;
}

// Rotates a range by copying [n_first, last) to the stack, then shifting
// the range to the right and prepending the copied section to the beginning.
//
// Note: distance(n_first, last) <= 3*digits
template <class ForwardIt, int BufferSize>
bit_iterator<ForwardIt> _rotate_via_copy_end(
   bit_iterator<ForwardIt> first,
   bit_iterator<ForwardIt> n_first,
   bit_iterator<ForwardIt> last
) {
    // Types and constants
    using word_type = typename bit_iterator<ForwardIt>::word_type;
    using size_type = typename bit_iterator<ForwardIt>::size_type;
    constexpr size_type digits = binary_digits<word_type>::value;

    size_type k = distance(n_first, last);
    assert(k <= BufferSize*digits);
    word_type copy_arr[BufferSize];
    copy_arr[0] = *n_first.base();
    ForwardIt it = ++n_first.base();
    short unsigned int pos = 1;
    short int bits_left_to_copy = k - (digits - n_first.position());
    while (bits_left_to_copy > 0) {
        copy_arr[pos++] = *it++;
        bits_left_to_copy -= digits;
    }
    bit_iterator<ForwardIt> ret = shift_right(first, last, k);
    copy(
        bit_iterator<word_type*>(copy_arr, n_first.position()),
        bit_iterator<word_type*>(
                copy_arr,
                n_first.position()
        ) + k,
        first
    );
    return ret;
}

// Rotates a range using random-access iterators. Algorithm logic from the GCC
// implementation
template <class RandomAccessIt>
bit_iterator<RandomAccessIt> _rotate_via_raw(
   bit_iterator<RandomAccessIt> first,
   bit_iterator<RandomAccessIt> n_first,
   bit_iterator<RandomAccessIt> last,
   std::random_access_iterator_tag
) {
    // Types and constants
    using word_type = typename bit_iterator<RandomAccessIt>::word_type;
    using size_type = typename bit_iterator<RandomAccessIt>::size_type;
    using difference_type =
        typename bit_iterator<RandomAccessIt>::difference_type;
    constexpr difference_type digits = binary_digits<word_type>::value;

    difference_type k = n_first - first;
    difference_type n = last - first;

    if (k == n - k) {
        swap_ranges(first, n_first, n_first);
        return n_first;
    }

    bit_iterator<RandomAccessIt> p = first;
    bit_iterator<RandomAccessIt> ret = first + (last - n_first);

    for (;;) {
        if (k < n - k) {
            if (k <= digits) {
                // BENCHMARK NOTE: may be better to do k <= 3*digits and use
                // the _rotate_via_copy method.
                word_type temp_word = get_word<word_type>(p, k);
                bit_iterator<RandomAccessIt> temp_it = shift_left(p, p + n, k);
                write_word<word_type>(temp_word, temp_it, k);
                return ret;
            }
            bit_iterator<RandomAccessIt> q = p + k;
            unsigned int full_swaps = (n - k) / k;
            size_type remainder = (n - k) - full_swaps*k;
            while (full_swaps > 0) {
                swap_ranges(p, q, q);
                p += k;
                q += k;
                --full_swaps;
            }
            swap_ranges(p, p + remainder, q);
            p += remainder;
            q += remainder;
            n %= k;
            if (n == 0)
                return ret;
            std::swap(n, k);
            k = n - k;
        } else {
            k = n - k;
            if (k <= digits) {
                word_type temp_word = get_word<word_type>(p + n - k, k);
                shift_right(p, p + n, k);
                write_word<word_type>(temp_word, p, k);
                return ret;
            }
            bit_iterator<RandomAccessIt> q = p + n;
            p = q - k;
            unsigned int full_swaps = (n - k) / k;
            size_type remainder = (n - k) - full_swaps*k;
            while (full_swaps > 0) {
                p -= k;
                q -= k;
                swap_ranges(p, q, q);
                --full_swaps;
            }
            p -= remainder;
            q -= remainder;
            swap_ranges(p, p + remainder, q);
            n %= k;
            if (n == 0)
                return ret;
            std::swap(n, k);
        }
    }
}

// Main function for implementing the bit overload of std::rotate.
template <class ForwardIt>
bit_iterator<ForwardIt> rotate(
   bit_iterator<ForwardIt> first,
   bit_iterator<ForwardIt> n_first,
   bit_iterator<ForwardIt> last
) {
    // Assertions
    _assert_range_viability(first, n_first);
    _assert_range_viability(n_first, last);
    _assert_range_viability(first, last);
    //if (first == n_first) return n_first;
    if (first == n_first) return last;

    // Types and constants
    using word_type = typename bit_iterator<ForwardIt>::word_type;
    using size_type = typename bit_iterator<ForwardIt>::size_type;
    using difference_type =
        typename bit_iterator<ForwardIt>::difference_type;
    constexpr difference_type digits = binary_digits<word_type>::value;

    // Initialization
    const bool is_first_aligned = first.position() == 0;
    const bool is_last_aligned = last.position() == 0;

    // Within the same word
    if (std::next(first.base(), is_last_aligned) == last.base()) {
        if (is_first_aligned && is_last_aligned) {
            *first.base() =
                (*first.base() >> n_first.position())
                |
                static_cast<word_type>(
                        *first.base() << (digits - n_first.position())
            );
            return std::next(first, digits - n_first.position());
        } else {
            size_type last_pos = is_last_aligned ? digits : last.position();
            size_type k = n_first.position() - first.position();
            size_type p = last_pos - n_first.position();
            size_type d = last_pos - first.position();

            word_type mask = ((1ULL << d) - 1) << first.position();
            word_type rotated = *first.base() & mask;
            rotated = static_cast<word_type>(rotated >> k)
                | static_cast<word_type>(rotated << p);
            *first.base() = _bitblend<word_type>(
                *first.base(),
                rotated,
                first.position(),
                d
            );
            return std::next(first, p);
        }
    }

    // Single word subcases
    if (is_within<digits>(first, n_first)) {
        size_type k = distance(first, n_first);
        word_type temp = get_word<word_type>(first, k);
        bit_iterator<ForwardIt> new_last = shift_left(first, last, k);
        write_word<word_type>(temp, new_last, static_cast<word_type>(k));
        return new_last;
    } else if (is_within<digits>(n_first, last)) {
        size_type p = distance(n_first, last);
        word_type temp = get_word<word_type>(n_first, p);
        auto new_last = shift_right(first, last, p);
        write_word(temp, first, static_cast<word_type>(p));
        return new_last;
    }
    return _rotate_via_raw(
            first,
            n_first,
            last,
            typename std::iterator_traits<ForwardIt>::iterator_category()
    );
}


// ========================================================================== //
} // namespace bit
#endif // _ROTATE_HPP_INCLUDED
// ========================================================================== //

1	// ================================= ROTATE ================================= //
2	// Project: The Experimental Bit Algorithms Library
3	// Name: rotate.hpp
4	// Description: bit_iterator overloads for std::rotate
5	// Contributor(s): Bryce Kille [2019]
6	// License: BSD 3-Clause License
7	// ========================================================================== //
8	#ifndef _ROTATE_HPP_INCLUDED
9	#define _ROTATE_HPP_INCLUDED
10	// ========================================================================== //
11
12
13
14	// ============================== PREAMBLE ================================== //
15	// C++ standard library
16	#include <iostream>
17	// Project sources
18	#include "bit_algorithm.hpp"
19	// Third-party libraries
20	// Miscellaneous
21	namespace bit {
22	// ========================================================================== //
23
24	// Rotates a range by copying [first...n_first) to the stack, then shifting
25	// the range to the left and appending the copied section to the end.
26	//
27	// Note: distance(first, n_first) <= 3*digits
28	template <class ForwardIt, int BufferSize>
29	bit_iterator<ForwardIt> _rotate_via_copy_begin(
30	bit_iterator<ForwardIt> first,
31	bit_iterator<ForwardIt> n_first,
32	bit_iterator<ForwardIt> last
33	) {
34	// Types and constants
35	using word_type = typename bit_iterator<ForwardIt>::word_type;
36	using size_type = typename bit_iterator<ForwardIt>::size_type;
37	constexpr size_type digits = binary_digits<word_type>::value;
38
39	size_type k = distance(first, n_first);
40	assert(k <= BufferSize*digits);
41	word_type copy_arr[BufferSize];
42	copy_arr[0] = *first.base();
43	ForwardIt it = ++first.base();
44	short unsigned int pos = 1;
45	short int bits_left_to_copy = k - (digits - first.position());
46	while (bits_left_to_copy > 0) {
47	copy_arr[pos++] = *it++;
48	bits_left_to_copy -= digits;
49	}
50	bit_iterator<ForwardIt> ret = shift_left(first, last, k);
51	copy(
52	bit_iterator<word_type*>(copy_arr, first.position()),
53	bit_iterator<word_type*>(
54	copy_arr,
55	first.position()
56	) + k,
57	ret
58	);
59	return ret;
60	}
61
62	// Rotates a range by copying [n_first, last) to the stack, then shifting
63	// the range to the right and prepending the copied section to the beginning.
64	//
65	// Note: distance(n_first, last) <= 3*digits
66	template <class ForwardIt, int BufferSize>
67	bit_iterator<ForwardIt> _rotate_via_copy_end(
68	bit_iterator<ForwardIt> first,
69	bit_iterator<ForwardIt> n_first,
70	bit_iterator<ForwardIt> last
71	) {
72	// Types and constants
73	using word_type = typename bit_iterator<ForwardIt>::word_type;
74	using size_type = typename bit_iterator<ForwardIt>::size_type;
75	constexpr size_type digits = binary_digits<word_type>::value;
76
77	size_type k = distance(n_first, last);
78	assert(k <= BufferSize*digits);
79	word_type copy_arr[BufferSize];
80	copy_arr[0] = *n_first.base();
81	ForwardIt it = ++n_first.base();
82	short unsigned int pos = 1;
83	short int bits_left_to_copy = k - (digits - n_first.position());
84	while (bits_left_to_copy > 0) {
85	copy_arr[pos++] = *it++;
86	bits_left_to_copy -= digits;
87	}
88	bit_iterator<ForwardIt> ret = shift_right(first, last, k);
89	copy(
90	bit_iterator<word_type*>(copy_arr, n_first.position()),
91	bit_iterator<word_type*>(
92	copy_arr,
93	n_first.position()
94	) + k,
95	first
96	);
97	return ret;
98	}
99
100	// Rotates a range using random-access iterators. Algorithm logic from the GCC
101	// implementation
102	template <class RandomAccessIt>
103	bit_iterator<RandomAccessIt> _rotate_via_raw(	3,056✔
104	bit_iterator<RandomAccessIt> first,
105	bit_iterator<RandomAccessIt> n_first,
106	bit_iterator<RandomAccessIt> last,
107	std::random_access_iterator_tag
108	) {
109	// Types and constants
110	using word_type = typename bit_iterator<RandomAccessIt>::word_type;
111	using size_type = typename bit_iterator<RandomAccessIt>::size_type;
112	using difference_type =
113	typename bit_iterator<RandomAccessIt>::difference_type;
114	constexpr difference_type digits = binary_digits<word_type>::value;	3,056✔
115
116	difference_type k = n_first - first;	3,056✔
117	difference_type n = last - first;	3,056✔
118
119	if (k == n - k) {	3,056✔
120	swap_ranges(first, n_first, n_first);	×
121	return n_first;	×
122	}
123
124	bit_iterator<RandomAccessIt> p = first;	3,056✔
125	bit_iterator<RandomAccessIt> ret = first + (last - n_first);	3,056✔
126
127	for (;;) {	6,384✔
128	if (k < n - k) {	9,440✔
129	if (k <= digits) {	5,760✔
130	// BENCHMARK NOTE: may be better to do k <= 3*digits and use
131	// the _rotate_via_copy method.
132	word_type temp_word = get_word<word_type>(p, k);	2,640✔
133	bit_iterator<RandomAccessIt> temp_it = shift_left(p, p + n, k);	2,640✔
134	write_word<word_type>(temp_word, temp_it, k);	2,640✔
135	return ret;	2,640✔
136	}
137	bit_iterator<RandomAccessIt> q = p + k;	3,120✔
138	unsigned int full_swaps = (n - k) / k;	3,120✔
139	size_type remainder = (n - k) - full_swaps*k;	3,120✔
140	while (full_swaps > 0) {	10,384✔
141	swap_ranges(p, q, q);	7,264✔
142	p += k;	7,264✔
143	q += k;	7,264✔
144	--full_swaps;	7,264✔
145	}
146	swap_ranges(p, p + remainder, q);	3,120✔
147	p += remainder;	3,120✔
148	q += remainder;	3,120✔
149	n %= k;	3,120✔
150	if (n == 0)	3,120✔
151	return ret;	×
152	std::swap(n, k);	3,120✔
153	k = n - k;	3,120✔
154	} else {
155	k = n - k;	3,680✔
156	if (k <= digits) {	3,680✔
157	word_type temp_word = get_word<word_type>(p + n - k, k);	400✔
158	shift_right(p, p + n, k);	400✔
159	write_word<word_type>(temp_word, p, k);	400✔
160	return ret;	400✔
161	}
162	bit_iterator<RandomAccessIt> q = p + n;	3,280✔
163	p = q - k;	3,280✔
164	unsigned int full_swaps = (n - k) / k;	3,280✔
165	size_type remainder = (n - k) - full_swaps*k;	3,280✔
166	while (full_swaps > 0) {	13,952✔
167	p -= k;	10,672✔
168	q -= k;	10,672✔
169	swap_ranges(p, q, q);	10,672✔
170	--full_swaps;	10,672✔
171	}
172	p -= remainder;	3,280✔
173	q -= remainder;	3,280✔
174	swap_ranges(p, p + remainder, q);	3,280✔
175	n %= k;	3,280✔
176	if (n == 0)	3,280✔
177	return ret;	16✔
178	std::swap(n, k);	3,264✔
179	}
180	}
181	}
182
183	// Main function for implementing the bit overload of std::rotate.
184	template <class ForwardIt>
185	bit_iterator<ForwardIt> rotate(	8,256✔
186	bit_iterator<ForwardIt> first,
187	bit_iterator<ForwardIt> n_first,
188	bit_iterator<ForwardIt> last
189	) {
190	// Assertions
191	_assert_range_viability(first, n_first);	8,256✔
192	_assert_range_viability(n_first, last);	8,256✔
193	_assert_range_viability(first, last);	8,256✔
194	//if (first == n_first) return n_first;
195	if (first == n_first) return last;	8,256✔
196
197	// Types and constants
198	using word_type = typename bit_iterator<ForwardIt>::word_type;
199	using size_type = typename bit_iterator<ForwardIt>::size_type;
200	using difference_type =
201	typename bit_iterator<ForwardIt>::difference_type;
202	constexpr difference_type digits = binary_digits<word_type>::value;	8,032✔
203
204	// Initialization
205	const bool is_first_aligned = first.position() == 0;	8,032✔
206	const bool is_last_aligned = last.position() == 0;	8,032✔
207
208	// Within the same word
209	if (std::next(first.base(), is_last_aligned) == last.base()) {	16,064✔
210	if (is_first_aligned && is_last_aligned) {	1,696✔
211	*first.base() =	×
212	(*first.base() >> n_first.position())	×
213	\|	×
214	static_cast<word_type>(	×
215	*first.base() << (digits - n_first.position())	×
216	);
217	return std::next(first, digits - n_first.position());	×
218	} else {
219	size_type last_pos = is_last_aligned ? digits : last.position();	1,696✔
220	size_type k = n_first.position() - first.position();	1,696✔
221	size_type p = last_pos - n_first.position();	1,696✔
222	size_type d = last_pos - first.position();	1,696✔
223
224	word_type mask = ((1ULL << d) - 1) << first.position();	1,696✔
225	word_type rotated = *first.base() & mask;	1,696✔
226	rotated = static_cast<word_type>(rotated >> k)	1,696✔
227	\| static_cast<word_type>(rotated << p);	1,696✔
228	*first.base() = _bitblend<word_type>(	2,688✔
229	*first.base(),	3,392✔
230	rotated,
231	first.position(),	704✔
232	d
233	);
234	return std::next(first, p);	3,392✔
235	}
236	}
237
238	// Single word subcases
239	if (is_within<digits>(first, n_first)) {	6,336✔
240	size_type k = distance(first, n_first);	2,976✔
241	word_type temp = get_word<word_type>(first, k);	2,976✔
242	bit_iterator<ForwardIt> new_last = shift_left(first, last, k);	2,976✔
243	write_word<word_type>(temp, new_last, static_cast<word_type>(k));	2,976✔
244	return new_last;	2,976✔
245	} else if (is_within<digits>(n_first, last)) {	3,360✔
246	size_type p = distance(n_first, last);	304✔
247	word_type temp = get_word<word_type>(n_first, p);	304✔
248	auto new_last = shift_right(first, last, p);	304✔
249	write_word(temp, first, static_cast<word_type>(p));	304✔
250	return new_last;	304✔
251	}
252	return _rotate_via_raw(	3,056✔
253	first,
254	n_first,
255	last,
256	typename std::iterator_traits<ForwardIt>::iterator_category()
257	);	3,056✔
258	}
259
260
261	// ========================================================================== //
262	} // namespace bit
263	#endif // _ROTATE_HPP_INCLUDED
264	// ========================================================================== //

PeterCDMcLean / BitLib / 14816556113

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous