MergeSkylines could be O(n)

[briterator]

MergeSkylines calls erase in a loop potentially N times. Each call is O(n), making this function O(n^2).

If you use an algorithm like std::unique this function would be O(n).

pseudocode:

auto compare = [](SkylineNode& a, SkylineNode& b)
{
	if (a.y == b.y)
	{
		a.width += b.width;
		return true;
	}
	return false;
};
auto new_end = std::unique(skyLine.begin(), skyLine.end(), compare);
skyLine.erase( new_end , skyLine.end());

cppreference states that the predicate is not allowed to modify a and b in the above code which we are doing. To work around this limitation you could simply copy the implementation of std::unique found on cppreference and put it into your own algorithm. The reference implementation of std::unique that they provide should work fine with mutating the values. Alternatively you could just use the implementation of std::unique as inspiration for a specialized solution.

Thanks for providing this library!

[juj]

Thanks for reporting. Didn't yet have time to check into too close detail, but I think that MergeSkylines() can actually merge a skyline at most twice, since it is called after each new rectangle has been placed, so the skyline can at most line up on both left and right sides. So the loop would be able to find the location where that case happens, and return out immediately afterwards.

A location where such a quadratic erase could occur is at https://github.com/juj/RectangleBinPack/blob/master/SkylineBinPack.cpp#L246. Although that can be fixed by deferring the erases until after the end of the loop body, because the erase range is always contiguous.

[briterator]

MergeSkylines() can actually merge a skyline at most twice, since it is called after each new rectangle has been placed, so the skyline can at most line up on both left and right sides.

Ah, okay! If that is the case then maybe MergeSkylines can be simplified to only examine this more restricted domain of candidates around the recently added entry. That would be much better than what I suggested.

A location where such a quadratic erase could occur is at ...

I agree, that looks like it could be done as a single call to erase() after the loop.