Filtering out of scope pull request hunks search optimization O(n log m) vs O (m + n)

[TomKristie]

In-line PR comment suggesting:

If the create comment GitHub API specifies lines that are outside of the scope, the API returns an error. Therefore we do a preemptive filtration of suggestion hunks by removing hunks that are outside of the PR scope. Specifically, we have lists of hunk ranges for each file that we want to suggest, and several ranges for each file that is in scope for the PR, and return only the in-hunk-scope suggestions for each in-scope file.

let m be the total PR hunk scope
let n be the total suggestion hunks

Currently we assume that the PR total hunk scopes and the total suggestion hunks would vary. We also assume to encounter more cases where m >> n. And so the algorithm's current runtime is O(n log m)

We assume that if n > m or n == m on average, that the user should probably have a PR just dedicated to these changes, or a better system in place (if systematically there are a lot of suggestions to be made). i.e. the bulk of the PR changes should not be from the suggestion tool.

It may become ideal to test the performance threshold of n and mm for when O(n log m) becomes more advantage than O(n + m). From this test we can then in an if statement control which algorithm to use.

https://stackoverflow.com/questions/37418916/on-log-m-vs-onm-which-is-better

[chingor13]

#132 switched to O(n + m)