Skip to content
This repository was archived by the owner on Dec 22, 2023. It is now read-only.

Optimize binary search algorithm #124

Merged
merged 2 commits into from
Aug 7, 2019
Merged

Optimize binary search algorithm #124

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
eec67c3
Refactor and optimize binary search algorithm
zenangst Aug 7, 2019
981cdde
Fix macOS implementation
zenangst Aug 7, 2019
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
51 changes: 22 additions & 29 deletions Sources/Shared/Core/BinarySearch.swift
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -4,10 +4,12 @@ public class BinarySearch {
public init() {}

private func binarySearch(_ collection: [LayoutAttributes],
less: (LayoutAttributes) -> Bool,
match: (LayoutAttributes) -> Bool) -> Int? {
less: (LayoutAttributes) -> Bool,
match: (LayoutAttributes) -> Bool) -> Int? {
guard var upperBound = collection.indices.last else { return nil }
upperBound += 1
var lowerBound = 0
var upperBound = collection.count


while lowerBound < upperBound {
let midIndex = lowerBound + (upperBound - lowerBound) / 2
Expand All @@ -26,47 +28,38 @@ public class BinarySearch {
}

public func findElement(in collection: [LayoutAttributes],
less: (LayoutAttributes) -> Bool,
match: (LayoutAttributes) -> Bool) -> LayoutAttributes? {
guard let firstMatchIndex = binarySearch(collection, less: less, match: match) else {
return nil
upper: (LayoutAttributes) -> Bool,
lower: (LayoutAttributes) -> Bool,
less: (LayoutAttributes) -> Bool,
match: (LayoutAttributes) -> Bool) -> LayoutAttributes? {
guard let firstMatchIndex = binarySearch(collection,
less: less,
match: match) else {
return nil
}
return collection[firstMatchIndex]
}

public func findElements(in collection: [LayoutAttributes],
padding: Int = 0,
upper: (LayoutAttributes) -> Bool,
lower: (LayoutAttributes) -> Bool,
less: (LayoutAttributes) -> Bool,
match: (LayoutAttributes) -> Bool) -> [LayoutAttributes]? {
guard let firstMatchIndex = binarySearch(collection, less: less, match: match) else {
return nil
match: (LayoutAttributes) -> Bool) -> [LayoutAttributes] {
guard let firstMatchIndex = binarySearch(collection,
less: less,
match: match) else {
return []
}

var results = [LayoutAttributes]()
var counter = padding

for element in collection[..<firstMatchIndex].reversed() {
if !match(element) {
if padding > 1 {
counter -= 1
if counter == 0 { break }
} else {
break
}
}
guard upper(element) else { break }
results.append(element)
}

counter = padding
for element in collection[firstMatchIndex...] {
if !match(element) {
if padding > 1 {
counter -= 1
if counter == 0 { break }
} else {
break
}
}
guard lower(element) else { break }
results.append(element)
}

Expand Down
60 changes: 31 additions & 29 deletions Sources/Shared/Core/BlueprintLayout.swift
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -317,14 +317,22 @@
return nil
}

let compare: (LayoutAttributes) -> Bool
let lower: (LayoutAttributes) -> Bool
let upper: (LayoutAttributes) -> Bool
let less: (LayoutAttributes) -> Bool
#if os(macOS)
compare = { indexPath > $0.indexPath! }
upper = { $0.indexPath! >= indexPath }
lower = { $0.indexPath! <= indexPath }
less = { $0.indexPath! < indexPath }
#else
compare = { indexPath > $0.indexPath }
upper = { $0.indexPath >= indexPath }
lower = { $0.indexPath <= indexPath }
less = { $0.indexPath < indexPath }
#endif
let result = binarySearch.findElement(in: cachedItemAttributesBySection[indexPath.section],
less: compare,
upper: upper,
lower: lower,
less: less,
match: { indexPath == $0.indexPath })
return result
}
Expand All @@ -335,41 +343,35 @@
/// - Parameter rect: The rectangle (specified in the collection view’s coordinate system) containing the target views.
/// - Returns: An array of layout attribute objects containing the layout information for the enclosed items and views.
override open func layoutAttributesForElements(in rect: CGRect) -> LayoutAttributesForElements {
let closure: (LayoutAttributes) -> Bool = scrollDirection == .horizontal
? { rect.maxX >= $0.frame.minX }
: { rect.maxY >= $0.frame.minY }
var rect = rect
let offset: CGFloat

// Add offset to the visible rectangle to avoid rare rendering issues when using binary search.
// It simply makes the visible rectangle slightly larger to ensure that all items on screen
// get rendered correctly. It will use the item size to determine how much offset should be
// added as padding to the visible rectangle.
let upper: (LayoutAttributes) -> Bool
let lower: (LayoutAttributes) -> Bool
let less: (LayoutAttributes) -> Bool

switch scrollDirection {
case .horizontal:
offset = itemSize.width
rect.origin.x -= offset
rect.size.width += offset * 2
upper = { attributes in attributes.frame.maxX >= rect.minX }
lower = { attributes in attributes.frame.minX <= rect.maxX }
less = { attributes in attributes.frame.maxX <= rect.minX }
case .vertical:
offset = itemSize.height
rect.origin.y -= offset
rect.size.height += offset * 2
upper = { attributes in attributes.frame.maxY >= rect.minY }
lower = { attributes in attributes.frame.minY <= rect.maxY }
less = { attributes in attributes.frame.maxY <= rect.minY }
@unknown default:
fatalError("Case not implemented in current implementation")
}

let padding = Int(itemsPerRow ?? 1)
var items = binarySearch.findElements(in: cachedItemAttributes,
padding: padding,
less: { closure($0) },
match: { $0.frame.intersects(rect) }) ?? []
upper: upper,
lower: lower,
less: less,
match: { $0.frame.intersects(rect) })
let supplementary = binarySearch.findElements(in: cachedSupplementaryAttributes,
padding: padding,
less: { closure($0) },
match: { $0.frame.intersects(rect) }) ?? []
upper: upper,
lower: lower,
less: less,
match: { $0.frame.intersects(rect) })
items.append(contentsOf: supplementary)

return !items.isEmpty ? items : cachedItemAttributes.filter { $0.frame.intersects(rect) }
return items
}

open override func invalidateLayout(with context: LayoutInvalidationContext) {
Expand Down
2 changes: 1 addition & 1 deletion Tests/iOS+tvOS/HorizontalBlueprintLayoutTests+iOS+tvOS.swift
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -21,7 +21,7 @@ class HorizontalBlueprintLayoutTests_iOS_tvOS: XCTestCase {

let size: CGSize = .init(width: 50, height: 50)
XCTAssertEqual(horizontalLayout.layoutAttributesForElements(in: CGRect(origin: .init(x: 0, y: 0), size: size))?.count, 2)
XCTAssertEqual(horizontalLayout.layoutAttributesForElements(in: CGRect(origin: .init(x: 75, y: 0), size: size))?.count, 4)
XCTAssertEqual(horizontalLayout.layoutAttributesForElements(in: CGRect(origin: .init(x: 75, y: 0), size: size))?.count, 2)
XCTAssertEqual(horizontalLayout.layoutAttributesForElements(in: CGRect(origin: .init(x: 100, y: 0), size: size))?.count, 3)
XCTAssertEqual(horizontalLayout.layoutAttributesForElements(in: CGRect(origin: .init(x: 0, y: 0), size: .init(width: 500, height: 500)))?.count, 10)
}
Expand Down
8 changes: 4 additions & 4 deletions Tests/iOS+tvOS/VerticalBlueprintLayoutTests+iOS+tvOS.swift
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -19,12 +19,12 @@ class VerticalBlueprintLayoutTests_iOS_tvOS: XCTestCase {
verticalLayout.sectionInset = .init(top: 0, left: 0, bottom: 0, right: 0)
verticalLayout.prepare()

XCTAssertEqual(verticalLayout.layoutAttributesForElements(in: .zero)?.count, 1)
XCTAssertEqual(verticalLayout.layoutAttributesForElements(in: .zero)?.count, 4)

let size = CGSize(width: 50, height: 50)
XCTAssertEqual(verticalLayout.layoutAttributesForElements(in: CGRect(origin: .init(x: 0, y: 0), size: size))?.count, 2)
XCTAssertEqual(verticalLayout.layoutAttributesForElements(in: CGRect(origin: .init(x: 0, y: 25), size: size))?.count, 1)
XCTAssertEqual(verticalLayout.layoutAttributesForElements(in: CGRect(origin: .init(x: 0, y: 50), size: size))?.count, 1)
XCTAssertEqual(verticalLayout.layoutAttributesForElements(in: CGRect(origin: .init(x: 0, y: 0), size: size))?.count, 8)
XCTAssertEqual(verticalLayout.layoutAttributesForElements(in: CGRect(origin: .init(x: 0, y: 25), size: size))?.count, 8)
XCTAssertEqual(verticalLayout.layoutAttributesForElements(in: CGRect(origin: .init(x: 0, y: 50), size: size))?.count, 10)
XCTAssertEqual(verticalLayout.layoutAttributesForElements(in: CGRect(origin: .init(x: 0, y: 0), size: CGSize(width: 500, height: 500)))?.count, 10)
}
}
Expand Down
2 changes: 1 addition & 1 deletion Tests/macOS/HorizontalBlueprintLayoutTests+macOS.swift
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -24,7 +24,7 @@ class HorizontalBlueprintLayoutTests_macOS: XCTestCase {
XCTAssertEqual(horizontalLayout.layoutAttributesForElements(in: .zero).count, 1)

collectionView.contentOffset = .init(x: 75, y: 0)
XCTAssertEqual(horizontalLayout.layoutAttributesForElements(in: collectionView.enclosingScrollView!.documentVisibleRect).count, 4)
XCTAssertEqual(horizontalLayout.layoutAttributesForElements(in: collectionView.enclosingScrollView!.documentVisibleRect).count, 2)

collectionView.contentOffset = .init(x: 100, y: 0)
XCTAssertEqual(horizontalLayout.layoutAttributesForElements(in: collectionView.enclosingScrollView!.documentVisibleRect).count, 3)
Expand Down
6 changes: 3 additions & 3 deletions Tests/macOS/VerticalBlueprintLayoutTests+macOS.swift
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -21,13 +21,13 @@ class VerticalBlueprintLayoutTests_macOS: XCTestCase {

collectionView.enclosingScrollView?.frame.size = .init(width: 50, height: 50)
collectionView.contentOffset = .init(x: 0, y: 0)
XCTAssertEqual(verticalLayout.layoutAttributesForElements(in: collectionView.enclosingScrollView!.documentVisibleRect).count, 2)
XCTAssertEqual(verticalLayout.layoutAttributesForElements(in: collectionView.enclosingScrollView!.documentVisibleRect).count, 8)

collectionView.contentOffset = .init(x: 0, y: 25)
XCTAssertEqual(verticalLayout.layoutAttributesForElements(in: collectionView.enclosingScrollView!.documentVisibleRect).count, 1)
XCTAssertEqual(verticalLayout.layoutAttributesForElements(in: collectionView.enclosingScrollView!.documentVisibleRect).count, 8)

collectionView.contentOffset = .init(x: 0, y: 50)
XCTAssertEqual(verticalLayout.layoutAttributesForElements(in: collectionView.enclosingScrollView!.documentVisibleRect).count, 1)
XCTAssertEqual(verticalLayout.layoutAttributesForElements(in: collectionView.enclosingScrollView!.documentVisibleRect).count, 10)

collectionView.enclosingScrollView?.frame.size = CGSize(width: 500, height: 500)
collectionView.contentOffset = .init(x: 0, y: 0)
Expand Down