Here's a support function, that I already unit-tested:
extension Collection {
public func heapPivot(childrenPerNode: Int = 2, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Index
}
Now, I'm trying out a type that uses it:
public struct Heap<Base: RandomAccessCollection> {
public typealias Element = Base.Element
// more properties...
@usableFromInline let areInIncreasingOrder: (Element, Element) -> Bool
// more properties...
init(_ base: Base, childrenPerNode: Int, by areInIncreasingOrder: @escaping (Element, Element) -> Bool
)
}
I got one of the basic initializers to work:
extension Heap {
public init?(
confirming base: Base,
childrenPerNode: Int = 2,
by areInIncreasingOrder: @escaping (Element, Element) -> Bool
) {
let limit = base.heapPivot(childrenPerNode: childrenPerNode,
by: areInIncreasingOrder)
guard limit == base.endIndex else { return nil }
self.init(base, childrenPerNode: childrenPerNode,
by: areInIncreasingOrder)
}
}
But when I tried to make an initializer that stops at just the matching prefix:
extension Heap /*where Base.SubSequence == Base*/ {
public init<T: RandomAccessCollection>(
prefixOf base: T,
childrenPerNode: Int = 2,
by areInIncreasingOrder: @escaping (Element, Element) -> Bool
) where T.SubSequence == Base {
let limit = base.heapPivot(childrenPerNode: childrenPerNode, by: areInIncreasingOrder) // 1
self.init(base[..<limit], childrenPerNode: childrenPerNode, by: areInIncreasingOrder)
}
}
The compiler chokes. On the line marked (1), the compiler flags on the "h" of the .heapPivot
call:
Type of expression is ambiguous without more context
(Let's call it Version 1.) When I change the constraint on T
to Collection
, since only the directly used type needs to be random-access, I get an improvement(?):
Cannot convert value of type '(Heap<Base>.Element, Heap<Base>.Element) -> Bool' (aka '(Base.Element, Base.Element) -> Bool') to expected argument type '(T.Element, T.Element) throws -> Bool'
and it's on the "a" of the areInIncreasingOrder
argument reference. (Let's call it Version 2.)
It seems like the original code should have worked, even before I un-refined the constraint to Collection
. With the T.SubSequence == Base
constraint, aren't Base.Element
and T.Element
the same type? I first wondered if the compiler couldn't see that, but adding a
T.Element == Base.Element
constraint didn't improve matters (still Version 2).
Is this a bug? Or did I miss something?
...
When I changed line (1) to:
let limit: Base.Index = base.heapPivot(childrenPerNode: childrenPerNode, by: areInIncreasingOrder)
to force the issue, I got different errors
-
Line (1) still had the Version 2 error but added:
Cannot convert value of type 'T.Index' to specified type 'Base.Index'
-
The last line gained two errors.
Cannot convert value of type 'T.SubSequence' to expected argument type 'Base' (Had fix-it to "Insert ' as! Base'.") Subscript 'subscript(_:)' requires the types 'T.Index' and 'Base.Index' be equivalent
Why is the matching broken?! I already constrained T.SubSequence
to be the same as Base
, and so their Element
types should be the same, and their Index
types should be the same.
Oh, I changed the explicit Base.Index
typing to T.Index
, line (1) had the Version 2 error by itself. And the following line kept the only first error and its Fix-it.