Hi,
I'd like to get some thoughts on this potential addition to the algorithms library:
-
Do you think this is useful?
-
Do you think this is a good fit for the algorithms package?
-
What do you think about the naming? Is "overlay" clear about what this does?
-
What do you think about the use of a namespace struct?
-
Do you know of any similar features in other languages/libraries? I haven't been able to find anything.
Thanks
Overlay
Pull Request
Compose collections by overlaying the elements of one collection
over an arbitrary region of another collection.
Swift offers many interesting collections, for instance:
-
Range<Int> allows us to express the numbers in 0..<1000
in an efficient way that does not allocate storage for each number.
-
Repeated<Int> allows us to express, say, one thousand copies of the same value,
without allocating space for a thousand values.
-
LazyMapCollection allows us to transform the elements of a collection on-demand,
without creating a copy of the source collection and eagerly transforming every element.
-
The collections in this package, such as .chunked, .cycled, .joined, and .interspersed,
similarly compute their elements on-demand.
While these collections can be very efficient, it is difficult to compose them in to arbitrary datasets.
If we have the Range 5..<10, and want to insert a 0 in the middle of it, we would need to allocate storage
for the entire collection, losing the benefits of Range<Int>. Similarly, if we have some numbers in storage
(say, in an Array) and wish to insert a contiguous range in the middle of it, we have to allocate storage
in the Array and cannot take advantage of Range<Int> memory efficiency.
The OverlayCollection allows us to form arbitrary compositions without mutating
or allocating storage for the result.
// 'numbers' is a composition of:
// - Range<Int>, and
// - CollectionOfOne<Int>
let numbers = (5..<10).overlay.inserting(0, at: 7)
for n in numbers {
// n: 5, 6, 0, 7, 8, 9
// ^
}
// 'numbers' is a composition of:
// - Array<Int>, and
// - Range<Int>
let rawdata = [3, 6, 1, 4, 6]
let numbers = rawdata.overlay.inserting(contentsOf: 5..<10, at: 3)
for n in numbers {
// n: 3, 6, 1, 5, 6, 7, 8, 9, 4, 6
// ^^^^^^^^^^^^^
}
We can also insert elements in to a LazyMapCollection:
enum ListItem {
case product(Product)
case callToAction
}
let products: [Product] = ...
var listItems: some Collection<ListItem> {
products
.lazy.map { ListItem.product($0) }
.overlay.inserting(.callToAction, at: min(4, products.count))
}
for item in listItems {
// item: .product(A), .product(B), .product(C), .callToAction, .product(D), ...
// ^^^^^^^^^^^^^
}
Detailed Design
An .overlay member is added to all collections:
extension Collection {
public var overlay: OverlayCollectionNamespace<Self> { get }
}
This member returns a wrapper structure, OverlayCollectionNamespace,
which provides a similar suite of methods to the standard library's RangeReplaceableCollection protocol.
However, while RangeReplaceableCollection methods mutate the collection they are applied to,
these methods return a new OverlayCollection value which substitutes the specified elements on-demand.
extension OverlayCollectionNamespace {
// Multiple elements:
public func replacingSubrange<Overlay>(
_ subrange: Range<Elements.Index>, with newElements: Overlay
) -> OverlayCollection<Elements, Overlay>
public func appending<Overlay>(
contentsOf newElements: Overlay
) -> OverlayCollection<Elements, Overlay>
public func inserting<Overlay>(
contentsOf newElements: Overlay, at position: Elements.Index
) -> OverlayCollection<Elements, Overlay>
public func removingSubrange(
_ subrange: Range<Elements.Index>
) -> OverlayCollection<Elements, EmptyCollection<Elements.Element>>
// Single elements:
public func appending(
_ element: Elements.Element
) -> OverlayCollection<Elements, CollectionOfOne<Elements.Element>>
public func inserting(
_ element: Elements.Element, at position: Elements.Index
) -> OverlayCollection<Elements, CollectionOfOne<Elements.Element>>
public func removing(
at position: Elements.Index
) -> OverlayCollection<Elements, EmptyCollection<Elements.Element>>
}
OverlayCollection conforms to BidirectionalCollection when both the base and overlay collections conform.
Conditional Overlays
In order to allow overlays to be applied conditionally, another function is added to all collections:
extension Collection {
public func overlay<Overlay>(
if condition: Bool,
_ makeOverlay: (OverlayCollectionNamespace<Self>) -> OverlayCollection<Self, Overlay>
) -> OverlayCollection<Self, Overlay>
}
If the condition parameter is true, the makeOverlay closure is invoked to apply the desired overlay.
If condition is false, the closure is not invoked, and the function returns a no-op overlay,
containing the same elements as the base collection.
This allows overlays to be applied conditionally while still being usable as opaque return types:
func getNumbers(shouldInsert: Bool) -> some Collection<Int> {
(5..<10).overlay(if: shouldInsert) { $0.inserting(0, at: 7) }
}
for n in getNumbers(shouldInsert: true) {
// n: 5, 6, 0, 7, 8, 9
}
for n in getNumbers(shouldInsert: false) {
// n: 5, 6, 7, 8, 9
}
