I implemented a invert-range operation in a (logical) circular vector. A circular vector is a vector without a logical starting and ending object, or, equivalently, the successive element of the element at the last index of the vector is the element at index 0 (similarly for the previous element).
I'm not 100% sure it's correct. If it's correct, any suggestions to improve it (especially in terms of performance)?
#include <cmath>
...
vector<SomeObject> vec;
...
/*
* Invert the segment starting at object at index i and ending at object at index j.
* */
void invert(const int i, const int j) {
// assert i and j are in the bounds
if (vec.size() < 2 || i == j) {
return;
}
int segment_size;
if(j < i ){
segment_size = std::ceil(((vec.size() - i) + j) / 2.0);
} else {
segment_size = std::ceil(std::abs(j - i) / 2.0);
}
for (int x = 0, k = i, w = j; x < segment_size; ++x) {
std::swap(vec[k], vec[w]);
k = next(k);
w = previous(w);
}
}
where next
and previous
are the following procedures:
/*
* Returns the index to the object after the object at index i.
* */
int next(const int i) {
return (i + 1) % vec.size();
}
/*
* Returns the index to the object before the object at index i.
* */
int previous(const int i) {
return (i - 1) % vec.size();
}
Note: these functions were actually methods, i.e. part of a class, and they actually working on a field and not on, e.g., global variable.
1 Answer 1
Bug
Your previous()
function doesn't wrap around well:
int previous(const int i) {
return (i - 1) % vec.size();
}
When i
reaches 0, this function will return -1
, not vec.size() - 1
as you might be expecting. You could either go with:
int previous(const int i) {
return (i - 1 + vec.size()) % vec.size();
}
or perhaps:
int previous(const int i) {
if (i == 0)
return vec.size() - 1;
return i - 1;
}
Unnecessary use of float
The Floating Point PoliceTM disapprove of your unnecessary use of floating point here:
if(j < i ){ segment_size = std::ceil(((vec.size() - i) + j) / 2.0); } else { segment_size = std::ceil(std::abs(j - i) / 2.0); }
All you are doing is rounding up, so you could just do:
if(j < i ){
segment_size = (vec.size() - i) + j;
} else {
segment_size = j - i;
}
segment_size = (segment_size + 1) / 2;
Technically, there could be a problem with the above if your segment size can be INT_MAX
. If this is possible, then replace that last line with this instead:
segment_size = (segment_size / 2) + (segment_size & 1);
But if your segment size could be INT_MAX
, then your next()
function would need to be fixed as well.