// only handles coplexity on top level, if you have a node with 1M children, you are out of luck
// changes in clipped parts are not detected, so if somebody deleted nodes in clipped, scrollbar is not updated until user actually scrolls
// scrolling and changes refresh the clipper == that part is as slow as no clipping at all
// only single list in BeginChild/EndChild is tested
struct TreeViewClipper {
	// persist
	float cursor_end = 0;
	float cursor_visible_start = 0;
	uint first_visible_index = 0;
	float last_scroll = 0;
	float cursor_visible_end = 0;
	uint visible_end_index = 0;
	bool full_pass = true;

	// valid only between begin end
	bool scrolled;
	bool met_visible;
	bool last_is_visible;
	uint idx;
	float y;
	bool finished;
	uint count;

	// returns index of first visible top-level node
	uint Begin(uint _count) {
		count = _count;
		scrolled = ImGui::GetScrollY() != last_scroll;
		if (scrolled) full_pass = true;
		if (full_pass) Refresh();

		// skip invisible space
		ImGui::SetCursorPosY(cursor_visible_start);

		// init runtime data
		met_visible = false;
		last_is_visible = true;
		idx = first_visible_index;
		finished = idx >= count;

		return idx;
	}

	void Refresh() {
		full_pass = false;
		last_scroll = ImGui::GetScrollY();
		first_visible_index = 0;
		cursor_visible_start = 0;
		cursor_end = 0;
	}

	bool BeginNode() {
		y = ImGui::GetCursorPosY();
		return !finished;
	}

	void EndNode() {
		const bool visible = ImGui::IsItemVisible();
		const bool is_first_visible = visible && !met_visible;
		if (is_first_visible) {
			met_visible = true;
			first_visible_index = idx;
			cursor_visible_start = y;
		}
		if (met_visible && !visible) {
			last_is_visible = false;
			y = ImGui::GetCursorPosY();
			if (cursor_end != 0) {
				// something has expended or collapsed
				if (y != cursor_visible_end && cursor_visible_end != 0) full_pass = true;
				if (idx != visible_end_index && visible_end_index != 0) full_pass = true;
				finished = true;
				cursor_visible_end = y;
				visible_end_index = idx;
			}
		}
		++idx;
		if (idx == count) finished = true;
	}

	void End() {
		if (cursor_end == 0 || last_is_visible) {
			cursor_end = ImGui::GetCursorPosY();
		}
		else {
			ImGui::SetCursorPosY(cursor_end - 2); // TODO why -2
		}
	}
};

// example
if (ImGui::BeginChild(...)) {
	static TreeViewClipper clipper;
	clipper.Begin((uint)_root->children.size());

	while (clipper.BeginNode()) {
		node_ui(&_root->children[clipper.idx]);
		clipper.EndNode();
	}
	clipper.End();
}