0:06 In this episode, we'll continue adding functionality to IndexSet by
conforming to more protocols. By conforming to Sequence in the last episode,
we were able to iterate over the values, and we gained helper methods like
map, filter, and contains.
Now we want to make our IndexSet conform to Collection as well, which will
look similar to a lot of stuff we did when we implemented SortedArray, our
first example of a custom collection. This time, it'll be more complicated
because IndexSet doesn't have a simple index type like Int. We need a new
index type that allows us to index into the ranges and consequently into an
element of a range.
1:37 We create an Index struct nested inside IndexSet. It has two
properties: an index for the range, and one for the element in that range, for
which we use the index type of last episode'sRangeType:
To conform to the Collection protocol, we have to implement startIndex,
endIndex, subscript, and index(after:).
Creating startIndex and endIndex
2:22 The startIndex is the index of the first element of the first
range, so its rangeIndex will simply be the startIndex of ranges, and the
elementIndex is the first range's startIndex. However, this is an optional
because there could be no ranges at all. In such a case, we return a zero for
elementIndex, which isn't an integer but rather a RangeType.Index. For this
dummy zero index, we return the startIndex of a fake range:
3:40 The endIndex is somewhat similar but perhaps less
straightforward. It has to meet three conditions:
The endIndex must be out of bounds.
The endIndex is equal to startIndex if the collection is empty.
All valid indices of the collection should compare as less than the
For the rangeIndex, we can return the endIndex of ranges, which already
places the entire index out of bounds. For elementIndex, we use the same dummy
value as before, which satisfies the second condition:
4:59 To meet the third condition, the index type needs to be
Comparable. We make our Index conform to this protocol in another extension
by writing the functions == and <. The equals function is pretty easy; it's
true if both subindices are equal:
The less than comparison has some more cases to consider. Firstly, we can
compare the rangeIndex of both sides — if they compare less than, we can
already return true. If they compare equal, we're in the same range and we can
return the comparison of the two sides' elementIndex. In all other cases, we
can return false:
7:38 The subscript function takes an Index and returns the
collection's element type: Int. We can simply return the corresponding value
without checking the bounds. This means we can cause a crash, but that's in fact
the expected behavior:
8:27 The tricky part is index(after:), in which we have to return the
next index. Again, there are a few cases: we have to return either a next index
within the same range or the first index of a next range, or we should return
endIndex, which signifies the end of the collection.
First we'll take the range of the given Index. If the range's next index is
still in bounds, we can return it:
11:35 That's a lot of typing, and it's easy to make mistakes here. Plus,
writing an integer-based collection would be less complicated than our compound
index type, so the question is how much we've gained by doing it this way. For
example, we can try to use subscript with startIndex to get the first index
12:31 We have to remember to actually declare our Collection
13:04 By implementing Collection on top of Sequence, we didn't
really gain a lot of extra functionality. We can count:
set.count// returns 5
But for other methods, like last, we'd have to also implement
BidirectionalCollection by adding index(before:).
14:08 You could look at conforming to protocols as a statement about
your type, and not just as a means to gain functionality. By implementing
Collection, you're saying it's OK to iterate over this type multiple times.
With a Sequence, you might only be able to iterate over it once, e.g. standard
input. Our IndexSet can be iterated over as many times as we want, so making
it into a Collection makes more sense.
14:39 Also, a Collection promises that using subscript takes a
constant time, which, in this case, is a requirement we can fulfill. Array, on
the other hand, also implements RandomAccessCollection, which we could
technically implement, but the protocol has the soft requirement that you can
perform count in constant time. We can't promise that because our type has
different characteristics. As such, we shouldn't conform to that protocol.
15:17 Another important aspect to note when working with indices is the
fact that stored indices might become invalid when you mutate the collection.
For example, if you remove an element from an IndexSet, its range could split
into two ranges. The same goes for Arrays: if you remove an element, all the
indices after that element will point to different elements or they'll be out of
16:21 So that's it for our custom collection type. Implementing these
protocols turned out to be not much work. If you have a data type that works
like a collection, it could be worth the effort to improve readability or