[BUG] UpdateMaxCounts can contaminate the sorted state

[Validark]

The UpdateMaxCounts function updates the termFrequencyCountChildMax field, which is also the field by which the Node.Children Lists are sorted. Since the sort call comes before the UpdateMaxCounts call in the following code, each layer is not actually guaranteed to be in sorted order.

PruningRadixTrie/PruningRadixTrie/PruningRadixTrie.cs

Lines 126 to 136 in 40b01f3

	else
	{
	curr.Children.Add((term, new Node(termFrequencyCount)));
	//sort children descending by termFrequencyCountChildMax to start lookup with most promising branch
	curr.Children.Sort((x, y) => y.Item2.termFrequencyCountChildMax.CompareTo(x.Item2.termFrequencyCountChildMax));
	}
	termCount++;
	UpdateMaxCounts(nodeList, termFrequencyCount);
	}
	catch (Exception e) { Console.WriteLine("exception: " + term + " " + e.Message); }
	}

And there is no sort call after this UpdateMaxCounts:

PruningRadixTrie/PruningRadixTrie/PruningRadixTrie.cs

Lines 56 to 61 in 40b01f3

	if ((common == term.Length) && (common == key.Length))
	{
	if (node.termFrequencyCount == 0) termCount++;
	node.termFrequencyCount += termFrequencyCount;
	UpdateMaxCounts(nodeList, node.termFrequencyCount);
	}

In practice, this can subtly worsen performance.

Also, because UpdateMaxCounts updates termFrequencyCountChildMax in potentially all ancestor nodes, those layers would need to be sorted as well if every layer is supposed to maintain sorted order.

[wolfgarbe]

Thanks. I will look into it.