#define WRAP_METHOD_NAIVE 0
#define WRAP_METHOD_BINARY_SEARCH 1
#define WRAP_METHOD_FITSWITHINBOUNDS 2

#define WRAP_METHOD WRAP_METHOD_FITSWITHINBOUNDS

#include <SFML/Graphics/Font.hpp>
#include <SFML/Graphics/Text.hpp>
#include <SFML/Graphics/RenderWindow.hpp>
#include <SFML/Window/VideoMode.hpp>
#include <SFML/Window/Event.hpp>

#include <algorithm>

sf::Text g_text;
sf::Font g_font;

std::vector<std::string> tokenise(const std::string& in, char delimiter)
{
	std::vector<std::string> ret;

	size_t seekPtr = 0;
	size_t nextLineBreak;
	while ((nextLineBreak = in.find_first_of(delimiter, seekPtr)) != std::string::npos)
	{
		ret.emplace_back(in.substr(seekPtr, nextLineBreak - seekPtr));
		seekPtr = nextLineBreak + 1;
	}
	// remaining
	ret.emplace_back(in.substr(seekPtr, std::string::npos));

	return ret;
}

template <typename _urItStart, typename _urItEnd, typename _pred>
constexpr decltype(auto) binary_lower_bound(_urItStart&& start, _urItEnd&& end, _pred&& pred)
{
	static_assert(std::is_same_v< std::decay_t<decltype(start)>, std::decay_t<decltype(end)> >, "Iterators incompatible!");
	using _iterator = std::decay_t<decltype(start)>;

	_iterator
		low = start,
		high = end;

	while (low < high)
	{
		const typename std::iterator_traits<_iterator>::difference_type midpointIdx = std::distance(low, high) / 2;
		_iterator midpointIt = low;
		std::advance(midpointIt, (std::max<typename std::iterator_traits<_iterator>::difference_type>)(midpointIdx, 0u));

		if (pred(midpointIt))
		{
			low = midpointIt + 1;
		}
		else
		{
			high = midpointIt;
		}
	}
	return low;
}

void drawWrappedText(const std::string& str, float width, uint8_t fontSize, sf::RenderWindow& window)
{
	g_text.setFont(g_font);
	g_text.setCharacterSize(fontSize);

	auto lines = tokenise(str, '\n');

	// reasonable cutoff for this demo
	constexpr size_t maxLineCount = 100;

	for (size_t lineIdx = 0; lineIdx < std::min(lines.size(), maxLineCount); ++lineIdx)
	{
		g_text.setString(lines[lineIdx]);

		const auto wrapBegin = lines[lineIdx].begin();
		const auto wrapEndMax = lines[lineIdx].end();
#if WRAP_METHOD==WRAP_METHOD_NAIVE
		auto wrapEnd = wrapEndMax;
		for (auto it = wrapBegin; it != wrapEndMax; ++it)
		{
			size_t idx = std::distance(wrapBegin, it);
			if (g_text.findCharacterPos(idx).x >= width)
			{
				wrapEnd = it;
				break;
			}
		}
#elif WRAP_METHOD==WRAP_METHOD_BINARY_SEARCH
		auto wrapEnd = binary_lower_bound(wrapBegin, wrapEndMax,
			[&width, &wrapBegin](auto&& it)
			{
				size_t i = std::distance(wrapBegin, it);
				return g_text.findCharacterPos(i).x < width;
			});
		// Check lower bound validity
		if (wrapEnd != wrapBegin)
		{
			size_t i = std::distance(wrapBegin, wrapEnd);
			sf::Vector2f pos = sf::Vector2f(g_text.findCharacterPos(i));
			if (pos.x >= width)
			{
				wrapEnd--;
			}
		}
		else
		{
			continue;
		}
#elif WRAP_METHOD==WRAP_METHOD_FITSWITHINBOUNDS
		size_t oobIndex;
		if (g_text.fitsWithinBounds({ { 0, 0 }, { width, 9999999.0f } }, oobIndex))
		{
			continue;
		}
		auto wrapEnd = wrapBegin + oobIndex;
#endif

		// no wrap
		if (wrapEnd == wrapEndMax)
		{
			continue;
		}

		// seek backwards through any amount of whitespace
		while (wrapEnd != wrapBegin && *wrapEnd == ' ')
		{
			wrapEnd--;
		}

		if (wrapEnd != wrapBegin)
		{
			std::string&& newStr = { wrapEnd, wrapEndMax };
			lines[lineIdx].erase(wrapEnd, wrapEndMax);
			lines.insert(lines.begin() + lineIdx + 1, newStr);
		}
		else
		{
			lines[lineIdx].erase(wrapEnd, wrapEndMax);
		}
	}
	if (lines.size() >= maxLineCount)
	{
		lines.erase(lines.begin() + maxLineCount, lines.end());
	}

	if (!lines.empty())
	{
		sf::String finalStr = lines[0];
		for (size_t sfmlStrLineIdx = 1; sfmlStrLineIdx < lines.size(); ++sfmlStrLineIdx)
		{
			finalStr.insert(finalStr.getSize(), '\n');
			finalStr.insert(finalStr.getSize(), lines[sfmlStrLineIdx]);
		}

		g_text.setString(finalStr);
		window.draw(g_text);
	}
}

int main()
{
	sf::RenderWindow window(sf::VideoMode({ 1280, 720 }), "example");
	sf::Vector2u halfWindowDims(window.getSize().x / 2, window.getSize().y / 2);

	bool res = g_font.loadFromFile("assets/verdana.ttf");
	assert(res);

	sf::Clock clockTextWrap;

	const std::string lorem =
R"(Lorem ipsum dolor sit amet, consectetur adipiscing elit.Pellentesque ut odio tristique purus congue finibus.Quisque sed nulla ac justo vehicula malesuada.Integer aliquet lacus ac enim pellentesque sagittis.Aliquam elementum nisi elit, sit amet egestas sem tincidunt ac.Suspendisse sapien massa, consectetur vel tristique at, facilisis id justo.In maximus mauris et dui finibus, non laoreet sem vehicula.Integer lobortis suscipit felis vitae ultrices.Aliquam laoreet gravida erat, sed elementum est.Fusce in massa nunc.Etiam vestibulum urna nec lorem pellentesque mattis.Vestibulum ut condimentum libero, id aliquam nibh.Nam commodo mauris at ipsum euismod ornare.
Nullam tristique massa nec lectus condimentum mattis.Pellentesque orci ante, cursus vel massa nec, dictum maximus tellus.Donec arcu felis, elementum quis massa eget, porttitor elementum dolor.Suspendisse imperdiet augue vel dolor vulputate, ut eleifend ligula egestas.Mauris in arcu facilisis, semper nunc et, lobortis massa.Phasellus gravida erat risus, sit amet dapibus sapien tristique at.Quisque congue luctus leo quis euismod.Aliquam rutrum imperdiet risus, mattis molestie eros.Duis auctor dolor eu risus interdum efficitur.
Nam gravida sem nec nisl sodales laoreet.Ut non mauris eu orci finibus ultrices vitae sed quam.Etiam et aliquam lacus.Donec pulvinar orci eget felis convallis blandit.Vivamus porttitor aliquet ipsum, vel ultrices ex pulvinar a.Pellentesque orci orci, mollis id elementum ut, feugiat ut ex.Curabitur egestas vitae nisl non vestibulum.Nulla nisl metus, suscipit quis pulvinar vitae, porttitor faucibus purus.Nulla consectetur blandit diam.Morbi porta risus massa, et ullamcorper lacus volutpat quis.Phasellus mollis turpis ac leo faucibus, at viverra ligula maximus.
Suspendisse potenti.Nulla urna diam, suscipit in ultricies nec, gravida vitae ipsum.Sed varius arcu sed scelerisque blandit.Ut fermentum tristique sapien ut scelerisque.Proin in sem non massa dapibus laoreet aliquam eu nisl.Nam blandit malesuada nibh, efficitur tincidunt felis.Maecenas purus risus, aliquet nec odio ut, tristique eleifend purus.Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia curae; Proin vel ligula et metus convallis fringilla et non urna.Morbi viverra, nulla hendrerit vehicula semper, erat neque pulvinar odio, eget convallis lacus sem sit amet turpis.Proin sodales non mi id porta.Pellentesque pellentesque eros justo, pulvinar aliquet tellus vulputate sit amet.Maecenas sed massa vel lacus luctus fringilla.
Donec imperdiet sollicitudin purus, at molestie turpis ultricies non.Donec rhoncus eleifend placerat.Curabitur sapien ex, efficitur at dignissim sit amet, luctus vel dolor.Nullam ac lorem at dui efficitur suscipit non id augue.Maecenas aliquam posuere quam, sed pellentesque felis.Nam eu mi eu leo auctor iaculis sit amet ac sem.Suspendisse potenti.)";

	while (window.isOpen())
	{
		sf::Event event;
		while (window.pollEvent(event))
		{
			if (event.type == sf::Event::Closed)
				window.close();
		}

		window.clear();

		float width  = halfWindowDims.x + (std::sin(clockTextWrap.getElapsedTime().asSeconds()) * halfWindowDims.x);
		drawWrappedText(lorem, width, 12, window);

		window.display();
	}

	return 0;
}