vector TreeIntersection()

in src/wfgoto.cpp [116:233]
84 lines of code
16 McCabe index (conditional complexity)

vector<PDNODE> TreeIntersection(vector<vector<PDNODE>>& trees)
{
	vector<PDNODE> result;

	if (trees.empty())
		return result;

	// If any tree is empty, return empty
	if (std::any_of(std::cbegin(trees), std::cend(trees), [](auto& tree) { return tree.size() == 0; }))
		return result;

	size_t maxOutput = 0;
	for (auto& tree : trees)
	{
		sort(tree.begin(), tree.end(), CompareNodes);
		if (tree.size() > maxOutput)
			maxOutput = tree.size();
	}

	// if just one, return it (after sort above)
	int count = trees.size();
	if (count == 1)
		return trees.at(0);

	// use up to two outputs and switch back and forth; lastOutput is last number output 
	vector<PDNODE> outputA(maxOutput);
	vector<PDNODE> outputB(maxOutput);
	vector<PDNODE> *combined = nullptr;
	size_t lastOutput = 0;

	// first is left side of merge; changes each time through the loop
	vector<PDNODE>* first = nullptr;

	// for all other result sets, merge
	for (int i = 1; i < count; i++)
	{
		size_t out = 0;			// always start writing to the beginning of the output

		size_t first1 = 0;		// scan index for last result in combined result (thus far)
		size_t last1;			// count of items in 'first'; set below

		if (i == 1)
		{
			// on first time through loop, output is A and 'first' is trees[0];
			first = &trees[0];
			last1 = first->size();
			combined = &outputA;
		}
		else if (i % 2 == 0)
		{
			// even passes: output is B and 'first' is outputA; create output B if it doesn't exist yet
			first = &outputA;
			last1 = lastOutput;

			combined = &outputB;
		}
		else
		{
			// odd passes except first: output is A and 'first' is B; both outputs already exist
			first = &outputB;
			last1 = lastOutput;
			combined = &outputA;
		}

		auto second = &trees[i];	// second results
		size_t first2 = 0;		// scan index for second results
		size_t last2 = second->size();	// end of second results

		// while results in both sets
		while (first1 < last1 && first2 < last2)
		{
			PDNODE& p1 = first->at(first1);
			PDNODE& p2 = second->at(first2);

			int wCmp = ParentOrdering(p1, p2);
			switch (wCmp)
			{
			case -2:
				// p1 is first in any case; skip first
				first1++;
				break;

			case -1:
				// p1 is prefix of p2; take p2; skip past p2
				combined->at(out) = p2;
				out++;
				first2++;
				break;

			case 0: // p1 == p2; take p1; skip both
				combined->at(out) = p1;
				out++;
				first1++;
				first2++;
				break;

			case 1: // p2 is prefix of p1; take p1; skip past p1
				combined->at(out) = p1;
				out++;
				first1++;
				break;

			case 2:
				// p2 is first in any case; skip second
				first2++;
				break;
			}
		}

		// shrink logical output to actual items written in each round
		lastOutput = out;
	}

	// shrink actual vector to final size
	combined->resize(lastOutput);

	return (*combined);
}