# Remove code duplication inside of a loop preserving performance

I'm coding a 2D collision engine, and I need to merge adjacent axis-aligned bounding boxes depending on a direction (left, right, top, bottom).

The four cases are very similar, except for the if condition, and the push_back argument. Is there any way I can refactor this code without compromising performance?

vector<AABB> getMergedAABBSLeft(vector<AABB> mSource)
{
vector<AABB> result;

while(!mSource.empty())
{
bool merged{false}; AABB a{mSource.back()}; mSource.pop_back();

for(auto& b : mSource)
if(a.getRight() == b.getRight())
{
result.push_back(getMergedAABBVertically(a, b));
eraseRemove(mSource, b); merged = true; break;
}

if(!merged) result.push_back(a);
}

return result;
}

vector<AABB> getMergedAABBSRight(vector<AABB> mSource)
{
vector<AABB> result;

while(!mSource.empty())
{
bool merged{false}; AABB a{mSource.back()}; mSource.pop_back();

for(auto& b : mSource)
if(a.getLeft() == b.getLeft())
{
result.push_back(getMergedAABBVertically(a, b));
eraseRemove(mSource, b); merged = true; break;
}

if(!merged) result.push_back(a);
}

return result;
}

vector<AABB> getMergedAABBSTop(vector<AABB> mSource)
{
vector<AABB> result;

while(!mSource.empty())
{
bool merged{false}; AABB a{mSource.back()}; mSource.pop_back();

for(auto& b : mSource)
if(a.getBottom() == b.getBottom())
{
result.push_back(getMergedAABBHorizontally(a, b));
eraseRemove(mSource, b); merged = true; break;
}

if(!merged) result.push_back(a);
}

return result;
}

vector<AABB> getMergedAABBSBottom(vector<AABB> mSource)
{
vector<AABB> result;

while(!mSource.empty())
{
bool merged{false}; AABB a{mSource.back()}; mSource.pop_back();

for(auto& b : mSource)
if(a.getTop() == b.getTop())
{
result.push_back(getMergedAABBHorizontally(a, b));
eraseRemove(mSource, b); merged = true; break;
}

if(!merged) result.push_back(a);
}

return result;
}

-

I find this line hard to read:

bool merged{false}; AABB a{mSource.back()}; mSource.pop_back();


Please split variables up 1 per line.
Yes the new syntax allows {} for list initialization. But these are not lists so it seems confusing to me (this one is more personal bias so feel free to ignore).

bool   merged(false);
AABB   a(mSource.back());
mSource.pop_back();


Pass large parameters by const reference if you can.
It saves a copy and you don't seem to need the copy (since you are not modifying the value (Note the eraseRemove() call has no effect externally and does not effect the rest of the code)).

vector<AABB> getMergedAABBSLeft(vector<AABB> const&   mSource)
//     ^^^^^^^^


Since your four functions are identical apart from one method call you could write a generic version and pass that method as a parameter:

vector<AABB> getMergedAABBSLeft(vector<AABB> mSource)
{    return getMergedAABBSGeneric(mSource, &AABB::getRight);
}

-
Why isn't eraseRemove doing anything? It takes a (std::vector&) as a parameter, so I'm sure it is removing AABBs from mSource. Are you sure I can safely delete it? –  Vittorio Romeo Feb 18 '13 at 9:47
Its doing something locally. But mSource is not exported from this function so has no effect on anything else. The fact that you remove an element does not affect this algorithm. –  Loki Astari Feb 18 '13 at 14:38
@Loki Astari: You discourage the use of the {} because you say it is used for C++11's list initialization. This recommendation isn't correct, it's called the new C++11 "Uniform initialization" ( en.wikipedia.org/wiki/C%2B%2B11#Uniform_initialization ). It is encouraged for any type of initialization now, as it avoids problems from type narrowing, or the notorious Most Vexing Parse ( en.wikipedia.org/wiki/Most_vexing_parse ). –  Piotr99 Feb 28 '13 at 19:00
@Piotr99: Thanks for the extra information. That was a personal one for me (I am still learning C++11) and nothing I would have rejected code from a code review on. It would be helpful if you had a reference for "encouraged for any type of initialization now". –  Loki Astari Mar 1 '13 at 19:08
The most authoritative source for C++ always is Bjarne Stroustrup ;) stroustrup.com/C++11FAQ.html#uniform-init . OK, in this case he points out which problems uniform initialization solves, but he doesn't provide a clear recommendation (I still believe his statement is an implicit recommendation). Herb Sutter (also involved in the C++ standardization committee) states regarding uniform initialization "Use {} unless you have a reason not to." See his talk (and slides) advocating the new C++11 here: channel9.msdn.com/Events/GoingNative/GoingNative-2012/… –  Piotr99 Mar 1 '13 at 19:27

Without knowing much about the AABB type, I'm assuming it has the operations getBottom(), and it's top-left-right couterparts.

What you could do is set up functions which returns the appropiate result and pass it as an argument to the general function. I only show the process for the top/left/right/bottom. The horizontally/vertically part goes the same way. Something like:

    typedef elem_type (*selector)(AABB*);
elem_type getRightSelector(AABB* obj)
{
return obj->getRight(); // Return value is of elem_type
}
// Same for the others (left, top...)

vector<AABB> getMergedAABBS(vector<AABB> mSource, selector sel )
{
(...)
for(auto& b : mSource)
if(sel(a) == sel(b))
{
// We'd need another pointer here
result.push_back(getMergedAABBHorizontally(a, b));
eraseRemove(mSource, b); merged = true; break;
}

(...)
return result;
}

// Any particular one:
vector<AABB> getMergedAABBSRight(vector<AABB> mSource )
{
return getMergedAABBS(mSource, getRightSelector);
}


Then you'd call the general function from each suffixed function (ie. getMergedAABBTop, etc.) passing the appropriate selector function.

Note this may be achieved in a cleaner way with C++11 features, what I'm not so certain about is the performance impact. Here you are adding one function call with respect to your code inside the loop, plus one function call from the specialized functions to the general one. Consider inlining, too.

-

This looks like a perfect opportunity for templates, maybe something like this:

template<typename C, typename T, T(C::*Selector)() const, C(*MergeFn)(C, C)> struct static_merger {

std::vector<C> run(std::vector<C> mSource) {
std::vector<C> result;
while(!mSource.empty())
{
bool merged = false;
AABB a = mSource.back();
mSource.pop_back();

for(auto & b : mSource) {
if((a.*Selector)() == (b.*Selector)())
{
result.push_back((*MergeFn)(a, b));
eraseRemove(mSource, b);
merged = true;
break;
}
}
if(!merged) {
result.push_back(a);
}
}
return result;
}
};


Usage is simple:

std::vector<AABB> orig / * = ... */;
static_merger<AABB, int, &AABB::getLeft, &mergeVertically> mergl;
static_merger<AABB, int, &AABB::getRight, &mergeVertically> mergr;
static_merger<AABB, int, &AABB::getTop, &mergeHorizontally> mergt;
static_merger<AABB, int, &AABB::getBottom, &mergeHorizontally> mergb;
std::vector<AABB> mergedl = mergl.run(orig);
std::vector<AABB> mergedr = mergr.run(orig);
std::vector<AABB> mergedt = mergt.run(orig);
std::vector<AABB> mergedb = mergb.run(orig);


Notice that with this approach, you need to create 4 different instances of our static_merger since the callbacks are being passed as template arguments.

If you want to be able to decide at runtime which callbacks to use, you can use this one:

template<typename C, typename T> struct dynamic_merger {

std::vector<C> run(std::vector<C> const & mSource, T(C::*selector)() const, C(*merge_fn)(C, C)) {
std::vector<C> result;
while(!mSource.empty())
{
bool merged = false;
AABB a = mSource.back();
mSource.pop_back();

for(auto & b : mSource) {
if((a.*selector)() == (b.*selector)())
{
result.push_back((*merge_fn)(a, b));
eraseRemove(mSource, b);
merged = true;
break;
}
}
if(!merged) {
result.push_back(a);
}
}
return result;
}
};


Usage is also simple:

std::vector<AABB> orig / * = ... */;
dynamic_merger<AABB, int> merg;
std::vector<AABB> mergedl = merg.run(orig, &AABB::getLeft, &mergeVertically);
std::vector<AABB> mergedr = merg.run(orig, &AABB::getRight, &mergeVertically);
std::vector<AABB> mergedt = merg.run(orig, &AABB::getTop, &mergeHorizontally);
std::vector<AABB> mergedb = merg.run(orig, &AABB::getBottom, &mergeHorizontally);


One last thing, as Loki Astari suggested you should pass your original data by (const) reference instead of by value, this avoids expensive copying, resulting in (possibly) faster execution times.

-