DescriptionRefactor NGLayoutOpportunityIterator to use 3-nodes spatial tree
This patch introduces a new layout opportunity iterator algorithm which is based on 3-nodes spatial tree. The new approach has several benefits from the existing one:
- improved runtime complexity to find layout opportunities: O(N log N)
- ability to reuse the tree, e.g. just insert a new exclusion down into the tree. Insert operation shouldn't take longer than 2 x log N time.
BUG=635619
Committed: https://crrev.com/e871b54f5e65f69b58ab4344f490f8d04faa06ab
Cr-Commit-Position: refs/heads/master@{#425391}
Patch Set 1 #
Total comments: 6
Patch Set 2 : Update LayoutOpportunitiesTwoInMiddle tests expectations #
Total comments: 3
Patch Set 3 : add LayoutOpportunitiesWithOutOfBoundsExclusions test case #
Total comments: 7
Patch Set 4 : fix minor comments #Messages
Total messages: 33 (21 generated)
|