Heap Sequence conformance

Here’s another possibility: make Heap conform to RawRepresentable, with a RawValue of Array. Unconventional, sure, but it certainly fits the description.

I’ve often used this approach when implementing types that exist to wrap another type. It immediately conveys a lot of useful information about what a type is for (that is, providing context for and making guarantees of the raw value). In fact, you could do this for any implicit data structure.

I don't hate elements.

Heap.unordered comes from OrderedSet, where it provides a SetAlgebra view with an unordered sense of equality.

However, OrderedSet also provides an elements view that simply exposes the underlying array storage.

Heap's view is not an exact match to either of these. It isn't exactly like OrderedSet.unordered because heap's view (an array) uses lexicographical equality, and it isn't exactly like OrderedSet.elements because the ordering is unspecified.

There is something to the discoverability argument for elements, but it doesn't feel overly convincing to me. I'm happy to trade some discoverability for better call-site clarity.

I guess the question boils down to: is it going to be clear enough to readers/reviewers that the code below encodes heap contents in an unspecified order?

var container = encoder.unkeyedContainer()
for item in heap.elements { try encoder.encode($0) }

One of the common ways Set and Dictionary have tripped people is when they assume that equal dictionaries will encode into the same data. Heap has the same gotcha -- at least for common sense definitions of equality, e.g., based on the list of items that would be returned by popMin. (A large portion of these issues came from build systems that used encoded dictionaries to determine what needed to be rebuilt, which started misbehaving more often when we introduced per-instance random seeding. (Incidentally, OrderedDictionary doesn't really help this use case.))

(RawRepresentable is also an option -- it feels vaguely similar to std::priority_queue in the STL, although there the rawValue isn't directly exposed. But Heap would need to modify its rawValue in its initializer, and this behavior doesn't feel like a good match with the spirit of RawRepresentable.)

You could just make that initializer return nil if the array needs modification.

That would not be very practical.

Like you noted, I’m pretty sure that initializer requires any resulting instance to use the input as its raw value. If it conformed to RawRepresentable, it’d be best done like this:

struct Heap<Element: Comparable>: RawRepresentable {
  var rawValue: [Element]

  init?(rawValue: RawValue) {...}

  init<S>(_ elements: S) where S : Sequence, Element == S.Element {...}
}

Alternatively, of course, it could just not conform to RawRepresentable. While that protocol is sorely underutilized, it isn’t suitable for everything.

I agree. These properties are not really views - they basically make a parallel copy of the data structure iterate that instead, doing extra work to maintain a perfect heap structure across every call to next(), when it'd almost certainly be better to just sort the contiguous array once in advance.

What these properties really should be, if they are to be included at all, are Arrays. Once you sort the elements, the data no longer has anything to do with a heap data structure; they just happen to be the same elements as are also contained in some heap somewhere. The type for "an ordered collection of elements" is Array.

Users can trivially turn instance methods into a Sequence using AnySequence.init<I>(_: () -> I), so there is generally not much point in adding a property like that unless some form of additional optimization is being made or it is a very common use case.

Since we seem to have settled on Heap not being treated as a proxy for the underlying array, it seems rather pointless to include methods and properties that could simply be called on that array directly.

I would think that someone not familiar with Heap might misunderstand, but then I think they would also misunderstand using .unordered too in such a case (as it would presume unfamiliarity with the data structure).

I think the discoverability would overweigh (IMHO) - perhaps extra clarifying documentation of elements that they are unordered and to not use it for encode/decode carelessly might alleviate some of those concerns.

Terms of Service

Privacy Policy

Cookie Policy