# Writing A Generic Stable Sort

One more post on writing generic algorithms. Let’s take a non-trivial non-generic algorithm and write a generic version. We’ll port a Java implementation of merge sort, and also look at some other interesting things we might do to some Java code when converting it to Swift.

Why bother with a merge sort? Well, the standard library comes with a very efficient in-place sort, based on the introsort, but it’s not a stable sort – that is, two otherwise equal entries aren’t guaranteed to stay in the same order, something that is often expected in things like grids that sort when you click a column header.

To start off, here is a Java version of a bottom-up merge sort, taken from Sedgewick, in all its Java-y C-for-loop-y zero-based-integer-index-y glory. Check out the vertigo-inducing braceless `for` loops!

```public class Merge {
private static Comparable[] aux;

private static void merge(Comparable[] a, int lo, int mid, int hi) {
int i = lo, j = mid+1;

for (int k = lo; k <= hi; k++)
aux[k] = a[k];

for (int k = lo; k <= hi; k++)
if      (i > mid)
a[k] = aux[j++];
else if (j > hi)
a[k] = aux[i++];
else if (aux[j].compareTo(aux[i]) < 0)
a[k] = aux[j++];
else
a[k] = aux[i++];
}

public static void sort(Comparable[] a) {
int N = a.length;
aux = new Comparable[N];
for (int sz = 1; sz < N; sz = sz+sz)
for (int lo = 0; lo < N-sz; lo += sz+sz)
merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));

}
}
```

This is generic on the array’s contents, but not on the container (not that you couldn’t write a container-generic version in Java too, but this isn’t a Java blog, I get quite enough Java in my day job thanks).

A good first step to turn this into a generic Swift algorithm would be just to port it to `Array` first. But even this presents some interesting problems – it’s not just a straight port, despite Java and Swift’s common ancestry. So let’s port it to Swift and make it more Swift-like at the same time, while keeping the algorithm broadly similar (speaking of which, yes, I know you can do it recursively but we’ll stick with the iterative version).

A first step would be ditching the very Java-esque practice of creating a class just to wrap some static methods. This passes for normal in the kingdom of nouns, but in Swift this would be more suited to an extension, with `self` taking the place of the `a` parameter:

```extension Array {
// really this ought to be marked rethrows but
// let’s ignore that to keep things simple...
public mutating func stableSortInPlace(
isOrderedBefore: (Element,Element)->Bool
) {
let N = self.count
// etc.
}
}
```

Why not write a version for `Array where Element: Comparable`? Well, `Comparable` conforms to `Equatable`, which has the following stern warning in its comment:

Equality implies substitutability. When x == y, x and y are interchangeable in any code that only depends on their values.

When needing a stable sort, the whole point is that you’re only comparing part of the values – you sort by last name, while wanting rows with the same last name to stay in the same order. Obviously that means that the two values you’re comparing are not substitutable. So it probably only makes sense to implement this sort with a comparator function. Never, ever, conform to `Comparable` by comparing only part of the visible properties of your type.

The first problem we face is that temporary storage array `aux`. Well, two problems really. The Java version does something that would be pretty monstrous in anything other than a textbook example – it uses a static variable. This would be fine for single-threaded code but if ever you used this same function simultaneously from two threads (even on two different arrays) then kerplowie. Brings back fond memories of debugging production problems from someone calling `strtok` from multiple threads. Sorry, did I say fond? I meant traumatic.

Anyway, even if you wanted to do it with a static property, you couldn’t, because you can’t add static variables to generic types in Swift. (if you wonder why – think about what would happen if there were a static property on `Array` – should there be just one static variable for both `[Int]` and `[String]`, or two different ones?)

So we need another way. We could just declare a new array inside `merge` every time, but that would allocate fresh array storage on every call, which would be horribly inefficient.

Alternatively, you could create the array once in the `sort` function, just like in the Java version, but then pass it as an argument into the `merge` function. This would ugly up the code a bit. But more importantly, it wouldn’t work with Swift arrays, because they are value types. If you created an array in `sort` then passed it into `merge`, it could be copied(-on-write), not re-used, which would be even worse than declaring a new one.

(If you are thinking `inout` or `var` is the solution, you’re also out of luck there. Despite what that call-site ampersand might imply, `inout` in Swift is not pass-by-reference, but rather pass-by-value-then-copy-back. `var` is similarly no help – it’s just shorthand for declaring a second mutable variable and assigning it the value of the parameter. Plus `var` is going away soon, probably partly because it caused this kind of confusion. UPDATE: per @jckarter, the `inout` situation may not be so clear-cut and ought to work in this case)

You could use reference-type storage, like `NSArray`, instead. Or you could allocate some memory yourself using `UnsafeMutablePointer`. Or use a `Box` class to wrap an array in a reference type. But here’s a perhaps neater alternative – declare `merge` as an inner function, and make it a closure that captures a local array variable:

```extension Array {
public mutating func stableSortInPlace(
isOrderedBefore: (Element,Element)->Bool
) {
let N = self.count
// declare a local aux variable
var aux: [Element] = []
// make sure it has enough space
aux.reserveCapacity(self.count)

// local merge function that can operate on (capture) self
func merge(lo: Int, _ mid: Int, _ hi: Int) {
// merge captures the aux variable _by ref_
// we can now use aux to merge self
}

for etc. {
merge(etc.)
}

}
}
```

When a function closes over a variable, it captures it by reference. This means that `merge` and the outer sorting function will share the same instance, exactly what we want. Unlike the static approach, there’s no risk that a second call will use the same storage – `aux` is still local to the call to sort, and two different calls will use two different local storage arrays, and so will their inner variables. The one downside of this is we wouldn’t be able to expose our `merge` function publicly, even though it could be a useful algorithm in its own right.

By the way, even though we declared `merge` with `func`, it is still a closure – don’t conflate the term closure (functions plus captured environment), with closure expressions (the Swift term for the shorthand syntax for writing anonymous functions). Local functions declared with `func` are just as closurey as closure expressions.

OK that solves that problem, but there’s a second issue. In the Java version, the array is declared to be a given fixed size:

```    aux = new Comparable[N];
```

and then the `merge` function just plunges in and uses bits of it:

```    for (int k = lo; k <= hi; k++)
aux[k] = a[k];
```

Here’s another place where both Java and Swift start from their common ancestor, but then Java zigs while Swift zags. In C, you declare a variable, and then you can immediately read from it without giving it a value. Everyone agrees that this is all very horrible and monstrous, but to not have that you have to choose a path – give everything a default value, like in Java, or ban reading until you’ve written, like in Swift.

There are maybe performance reasons why Swift’s choice is better. But really, it was forced by other factors. In Java, everything is either a primitive type, or a reference. With such a limited set of types it’s reasonable to give everything a default value – either zero, empty, or null. But Swift isn’t so simple. It doesn’t even really have “primitive” types – even `Int` is a struct. And while it has references, they aren’t always nullable. So everything having a default isn’t really an option.

So it follows that in Swift you can’t have an `Array` where you just declare it to be a given size then plunge in getting and setting elements at arbitrary indices. I mean, you could write an array that worked like that, but then you’d have to track internally when values for given index had been set or not. So instead, to make an array have `n` elements, you have to put `n` in. You can do that easily with `Array(count: n, repeatedValue: ???)`, but for our purposes, what would you put as the value? `Element` is completely generic, you don’t know anything about it, so there’s no reasonable default.

One solution is to use an array of `Optional`. That way, you can set them all to `nil`. Probably this would be one of those rare legit uses of an implicitly-unwrapped optional – where you can prove that at the time you use the optional that it wil never be `nil`, so there’s no harm unwrapping it implicitly. In fact, you’d like it to assert if you ever unwrapped a `nil`, as this would mean there was something horribly wrong with your logic.

```extension Array {
public mutating func stableSortInPlace(
isOrderedBefore: (Element,Element)->Bool
) {
let N = self.count
var aux = Array<Element!>(count: N, repeatedValue: nil)

func merge(lo: Int, _ mid: Int, _ hi: Int) {
var i = lo, j = mid+1

for var k = lo; k <= hi; k++ {
aux[k] = self[k]
}

for var k = lo; k <= hi; k++ {
if      i > mid { self[k] = aux[j++] }
else if j > hi  { self[k] = aux[i++] }
else if isOrderedBefore(aux[j],aux[i])
{ self[k] = aux[j++] }
else            { self[k] = aux[i++] }
}
}

for var sz = 1; sz < N; sz = sz+sz {
for var lo = 0; lo < N-sz; lo += sz+sz {
merge(lo, lo+sz-1, min(lo+sz+sz-1, N-1))
}
}

}
}
```

This now works, and is pretty much like the Java version. But implicitly-unwrapped optionals are a bit unpleasant, and anyone unhappy about the merge sort’s linear space requirements might blanche at the extra bits they take up. And the rest isn’t very Swift-y. Those `for` loops and `++` are not long for this world, and it’ll bit a bit painful to translate this into a fully generic function.

Instead, lets:

• Flip it around and have the merge logic copy into the `aux` array, then copy back into `self`, using `append`, removing the need to size it up at the beginning.
• At the same time, we can switch the `for` for a `while`, and ditch the `++`
• Switch from closed ranges (up-to-and-including `hi`) to half-open ranges (up-to but not including `hi`) since this is more the Swift convention (and will be easier in the next part)
• Use `appendContentsOf` and `replaceRange` instead of hand-rolled loop-and-assign

which gives us this merge function:

```  // ditch the optionals
var aux: [Element] = []
// make sure aux has enough memory to store a fully copy
// (note, does _not_ actually increase aux.count)
aux.reserveCapacity(N)

func merge(lo: Int, _ mid: Int, _ hi: Int) {
// wipe aux, but keep the memory buffer
// at full size each time around
aux.removeAll(keepCapacity: true)

var i = lo, j = mid
while i < mid && j < hi {
// append the lesser of either element
if isOrderedBefore(self[j],self[i]) {
aux.append(self[j])
j += 1
}
else {
aux.append(self[i])
i += 1
}
}
// then append the stragglers
// (one of the next 2 lines will be a no-op)
aux.appendContentsOf(self[i..<mid])
aux.appendContentsOf(self[j..<hi])
// then copy the sorted temp storage back into self
self.replaceRange(lo..<hi, with: aux)
}
```

Finally, we need to do the same for the sorting `for` loops:

```  for var sz = 1; sz < N; sz = sz+sz {
for var lo = 0; lo < N-sz; lo += sz+sz {
merge(lo, lo+sz-1, min(lo+sz+sz-1, N-1))
}
}
```

That outer `for` is kinda sneaky, since it’s doubling `sz` each time around the loop, so that needs a `while` rather than a `stride`. The inner one is a lot simpler though, it’s just striding over the array by a constant `sz*2` each time. Moving to half-open rather than closed ranges makes this a whole lot easier, since it gets rid of all the annoying `-1`s littered about:

```  var sz = 1
while sz < N {
for lo in 0.stride(to: N-sz, by: sz*2) {
merge(lo, lo+sz, min(lo+sz*2, N))
}
sz *= 2
}
```

This leaves us with a final version, Swiftified if not yet generic. It’s a little more verbose than the original Java, but mainly because of the loss of the compact `for` and `++` notation, and hopefully a bit more readable for it:

```extension Array {
public mutating func stableSortInPlace(
isOrderedBefore: (Element,Element)->Bool
) {
let N = self.count

var aux: [Element] = []
aux.reserveCapacity(N)

func merge(lo: Int, _ mid: Int, _ hi: Int) {

aux.removeAll(keepCapacity: true)

var i = lo, j = mid
while i < mid && j < hi {
if isOrderedBefore(self[j],self[i]) {
aux.append(self[j])
j += 1
}
else {
aux.append(self[i])
i += 1
}
}
aux.appendContentsOf(self[i..<mid])
aux.appendContentsOf(self[j..<hi])
self.replaceRange(lo..<hi, with: aux)
}

var sz = 1
while sz < N {
for lo in 0.stride(to: N-sz, by: sz*2) {
merge(lo, lo+sz, min(lo+sz*2, N))
}
sz *= 2
}
}
}
```

## Making it work on any random-access collection

OK, now to make it generic. A lot of that rework from before will make this easier.

First, to make this an extension of a protocol instead of protocol instead of `Array`. We actually used `self.replaceRange`, so let’s make it an extension of `RangeReplaceableCollectionType` (maybe a bit of an overconstraint – you could do without it and just make do with `MutableCollectionType`, but let’s ignore that). Plus the `where` clauses. We know the index needs to be random-access. We also rely on slicing, so per the previous article on this topic, we need to require `SubSequence` contains the same elements as the sequence:

```extension RangeReplaceableCollectionType
where
Index: RandomAccessIndexType,
SubSequence.Generator.Element == Generator.Element {
```

Doing this in Xcode will now show you all the places where you are relying on assumptions that no longer hold now you aren’t just writing against `Array` (though, more spring up as you fix these…)

Easy ones first. `Generator.Element` instead of just `Element`:

```    public mutating func stableSortInPlace(
isOrderedBefore: (Generator.Element,Generator.Element)->Bool
) {
let N = self.count

var aux: [Generator.Element] = []
```

Next, `aux.reserveCapacity`. We want to reserve the number of elements, but that comes (via `aux.count`) in the form of a `Self.Distance`. Remember, distances are always integers, but they might not be `Int`. We have to use `numericCast` to fix this:

```            aux.reserveCapacity(numericCast(N))
```

I admit, I haven’t quite got my head around whether this is an OK thing to do or not. For almost every reasonable circumstance, this will be a no-op, since `Distance` will be an `Int`. If for some reason you were using a class that used a smaller `Distance`, it will upconvert it. There’s a slim chance that `Distance` could be bigger than an `Int` – say if you’re on 32-bit platform but using a collection that used an explicit 64-bit index? Or maybe some giant virtual collection that used a `BigInt`? But for now I shall ignore these possibilities with reckless abandon.

So long as the `where` constraints above, the `merge` function is easy. You just make `lo`, `mid`, and `hi` an `Index` instead of an `Int`:

```    func merge(lo: Index, _ mid: Index, _ hi: Index) {
// the rest is the same
}
```

OK now for the interesting bit, the sorting loops:

```        var sz = 1
while sz < N {
for lo in 0.stride(to: N-sz, by: sz*2) {
merge(lo, lo+sz, min(lo+sz*2, N))
}
sz *= 2
}
```

The trick is, knowing which ones are indices, and which ones are distances (by which indices will be advanced).

`sz` is a distance. It’s the length by which each pass strides through the collection performing the merge, and which doubles each time around (giving the algorithm its linearithmic performance characteristic). To make that explicit, we need to annotate it with a type (otherwise it’s going to default to being an `Int`):

```    var sz: Index.Distance = 1
```

We already established `N` is the size of the collection and is also a distance, so this is fine (you can compare two distances, and you can double distances):

```  while sz < N {
// inner for stride
sz *= 2
}
```

Finally, the inner stride:

```  for lo in 0.stride(to: N-sz, by: sz*2) {
merge(lo, lo+sz, min(lo+sz*2, N))
}
```

`lo` is an `Index` – that’s what we pass in to `merge` as `lo`. The calculated `mid` and `hi` are indices too. When you see `0` as an index, that really means `startIndex` so we can substitute that.

The only other tricky part is `N`. With zero-based integer indices, `N` could mean two things: the length of the collection, or the end of the collection (i.e. `startIndex.advancedBy(N)`). Here, in this inner loop, it means the latter. So `N-sz` means “back from the end by `sz`“.

Similarly `min(lo+sz*2, N)` means “add `sz*2` to `lo`, or `endIndex` if that goes past the end”. So you could write `min(lo+sz*2, N)`. But there’s already a function for “go this far, but not past this point”. `advancedBy` is overloaded with a version that takes a `limit:` argument. So instead, you can write this as `lo.advancedBy(sz*2,limit: endIndex))`. This is arguably more correct as well, since it could be an error to add a distance to an index to take it past the end of the collection (like with `String` indices).

So we rewrite the inner loop as:

```  for lo in startIndex.stride(to: endIndex-sz, by: sz*2) {
merge(lo, lo+sz, lo.advancedBy(sz*2,limit: endIndex))
}
```

Again, if you’re doing this in Xcode, the compiler will help you along (for example, it will complain if you’re trying to take the minimum of an index and a distance, since you can’t do that, which is a hint you need an index instead of a distance).

One final gotcha. After you make all these changes and you’re sure everything is correct, the `stride` still won’t compile. We need one more constraint on the protocol: `Index.Distance == Index.Stride`. Yes, this should always be the case (that’s the whole point of making random-access indices strideable – so you can stride by `Distance`), but you still need to make it explicit.

After all this we finally have a fully generic random-access in-place merge sort:

```extension RangeReplaceableCollectionType
where
Index: RandomAccessIndexType,
SubSequence.Generator.Element == Generator.Element,
Index.Distance == Index.Stride {
public mutating func stableSortInPlace(
isOrderedBefore: (Generator.Element,Generator.Element)->Bool
) {
let N = self.count

var aux: [Generator.Element] = []
aux.reserveCapacity(numericCast(N))

func merge(lo: Index, _ mid: Index, _ hi: Index) {

aux.removeAll(keepCapacity: true)

var i = lo, j = mid
while i < mid && j < hi {
if isOrderedBefore(self[j],self[i]) {
aux.append(self[j])
j += 1
}
else {
aux.append(self[i])
i += 1
}
}
aux.appendContentsOf(self[i..<mid])
aux.appendContentsOf(self[j..<hi])
self.replaceRange(lo..<hi, with: aux)
}

var sz: Index.Distance = 1
while sz < N {
for lo in startIndex.stride(to: endIndex-sz, by: sz*2) {
merge(lo, lo+sz, lo.advancedBy(sz*2,limit: endIndex))
}
sz *= 2
}
}
}
```

I’d suggest you try it out on a mutable random-access collection that doesn’t have integer indices. Except, uh, there aren’t any. There are random-access collections without integer indices – reverse collections for example. Or (with a bit of extension-bullying) `String.UTF16View`. But unfortunately these aren’t mutable! So perhaps I’ve just totally wasted your time. But it was fun, right?

OK so there’s also a much more important benefit to this – it no longer relies on the index starting from zero. Yes, we could have done this for `CollectionType where Index: IntegerType`, but that would probably have been harder, since the compiler would not have helped as much when we made invalid assumptions. The `0` instead of `startIndex` might be easy to catch, but assumptions about when `N` means `endIndx` vs when `N` means `self.count` are much tricker.

Now that we’ve made this change, you can now apply the algorithm in-place to subranges, such as:

```var a = Array(1...5)
a[1..<4].stableSortInPlace(>)
// a = [1,4,3,2,5]
```

And finally, just to check it really is still a stable sort after all this futzing around (that property is easy to break if you make innocent-seeming changes to the order of your `i` and `j` comparisons – something I learned the hard way, forgot, then remembered the hard way during the course of writing this…)

```var pairs = [
(2,1), (2,2),
(3,1), (3,2),
(1,1), (1,2),
(1,3),(2,3),(3,3)
]

pairs.stableSortInPlace { \$0.0 < \$1.0 }
print(pairs.map { \$0.1 })
// if sort is stable, ought to print
// [1, 2, 3, 1, 2, 3, 1, 2, 3]
```

# Generic Collections, SubSequences and Overloading

So, you’ve figured out the whole indices versus distances situation, and now you’re feeling pretty happy and you start trying out some more generic collection algorithms. And before long you smack your head against one of the more confusing things about generic collections: a sequence’s `SubSequence` doesn’t necessarily contain the same element type as that sequence. This usually manifests itself in one of those compiler errors that has you yelling “what are you talking about you infernal machine” at the compiler before eventually realizing what you’ve done wrong and sheepishly fixing it.

For example, suppose you want to find the location of the first subsequence in a collection. Like `indexOf`, but for another sequence rather than an element. The simple brute-force approach would be to iterate over every subsequence, trying to match it. Something like this – except it won’t compile:

```extension CollectionType
where
Generator.Element: Equatable {

func search<
Other: SequenceType
where
Other.Generator.Element == Generator.Element
>(pattern: Other) -> Index? {

for idx in self.indices {
// error: cannot convert value of type 'Other'
// to expected argument type...
if suffixFrom(idx).startsWith(pattern) {
return idx
}
}
return nil
}
}
```

Until you know why, this can be very confusing. You’ve constrained the other sequence to have the same elements as the collection, so why can’t you use `startsWith` on it?

Except you’re not calling `startsWith` on `Self`. You’re calling it on `Self.SubSequence`, because that’s what `suffixFrom` returns – it’s a slicing operation. And `SubSequence.Generator.Element` isn’t guaranteed to be the same as `Self.Generator.Element`.

Here’s the relevant declaration:

```protocol CollectionType {
typealias SubSequence : Indexable, SequenceType = Slice<Self>
}
```

There’s nothing about this definition that forces the elements of `SubSequence` to be anything specific. Really, this needs a `where` clause on the typealias – something that Swift doesn’t currently support:1

```protocol CollectionType {
typealias SubSequence : Indexable, SequenceType
// not (yet?) valid Swift
where SubSequence.Generator.Element == Generator.Element
}
```

So, in the mean-time, the way around this is to specify any requirements like this as part of the declaration. A fix that might seem to work, but is over-constraining, would be to require subsequences be the same type:

```extension CollectionType
where
Generator.Element: Equatable,
SubSequence == Self {
// etc
}
```

This would compile, and it would work fine with types whose slices are the same type as themselves, like strings:

```// a slice of a String.CharacterView is
// a String.CharacterView, so this is fine
"hello".characters.search("ll".characters)
```

but not for arrays, who have an `ArraySlice` type, or arbitrary collections, that have the default `Slice` implementation.

```// "type of expression is ambiguous without more context", apparently
[1,2,3,4].search(2…4)
// "ambiguous reference to member '..<'" uhhh what?
(0..<5).search(2...4)
```

Instead, you can constrain the elements to be the same while allowing the slice type itself to differ:

```extension CollectionType
where
Generator.Element: Equatable,
// guarantee subsequences contain the same element
SubSequence.Generator.Element == Generator.Element {

func search<
Other: SequenceType
where
Other.Generator.Element == Generator.Element
>(pattern: Other) -> Index? {

for idx in self.indices {
// and now this line will happily compile...
if suffixFrom(idx).startsWith(pattern) {
return idx
}
}
return nil
}
}

[1,2,3,4].search(2...4) // returns 1
(0..<5).search([3,4])   // returns 3
```

## Optimizing for Random Access

It’s often the case that you can optimize a collection algorithm if you know it has random access. For example, given the above algorithm, you can tweak it to avoid searching for a pattern that is longer than what remains of the collection, so long as both the collection and the pattern are random access and therefore able to calculate their lengths (and the lengths of their collection) in constant time. OK, maybe it’s not Boyer-Moore, but it’s better than nothing and the code to do this is pretty simple, in fact it’s more constraints than code at this point:

```extension CollectionType
where
Generator.Element: Equatable,
Index: RandomAccessIndexType,
SubSequence.Generator.Element == Generator.Element {
func search<
Other: CollectionType
where
Other.Index: RandomAccessIndexType,
Other.Index.Distance == Index.Distance,
Other.Generator.Element == Generator.Element
>(pat: Other) -> Index? {

// if pattern is longer, this cannot match, exit early
guard !isEmpty && pat.count <= count else { return nil }

// otherwise, search from the start up to the
// end less the space for the pattern
for i in startIndex...endIndex.advancedBy(-pat.count) {
// check if a slice from this point
// starts with the pattern
if self.suffixFrom(i).startsWith(pat) {
// if it does, we've found it
return i
}
}
// otherwise, not found
return nil
}
}
```

(one part of the where clause, `Other.Index.Distance == Index.Distance`, is maybe overconstraining, but the alternative would be fiddling around with casts – non-`Int` distances aren’t exactly common, even `Bit`’s distance is an `Int`).

We’ve talked about overload priority a long time ago, and it still pertains even with protocol extensions. The most specific function wins. Here, if your two collections are random access, this version will be called because it is more tightly constrained than the first version. So:

```// calls the version that works for any index
"hello".characters.search("ll".characters)
// calls the version optimized for random-access
[1,2,3,4].search(2...4) // returns 1?
```

Now, there is a potentially nasty bug you could stumble into here, and the compiler won’t save you from it. Try removing the constraints requiring the indices be random access on the second version. It still compiles! Except, now this version will be called strings as well. But in the case of non-random indices, it’s not an optimized version, it’s potentially slower. The reason being, `pat.count` and `endIndex.advancedBy` aren’t constant time, they’re linear, because they involve incrementing the index one by one. Now it could be worse – at least it’s not accidentally quadratic, but other examples could easily be (imagine implementing a sort that assumed constant-time advance but didn’t get it), so it’s something to watch out for.

## Protocols, Extensions and Dynamic Dispatch

Once upon a time, it was harder to have made this mistake. In earlier versions of the standard library there were two ways to advance an index: a free `advance` function, that was `O(1)` for random access indices and `O(n)` otherwise, and then there was an `advancedBy` method on only the `RandomAccessIndexType`.

As part of the great extensionizing, the free `advance` function went away, and `advancedBy` moved into `ForwardIndexType`. So now you can call it on any index type, but you’ll get different performance characteristics depending on the type you call it on.

If you look at the declaration of `ForwardIndex.advancedBy`, you’ll see that it’s declared twice. Once inside the protocol:

```public protocol ForwardIndexType : _Incrementable {
public func advancedBy(n: Self.Distance) -> Self
}
```

and then again just below, as an extension:

```extension ForwardIndexType {
public func advancedBy(n: Self.Distance) -> Self
}
```

This seems a little weird. Why declare it twice? Why not just declare it once as an extension? It has to do with static versus dynamic dispatch, and which actual implementation is called.

To show this, let’s create our own toy index, initially without random access:

```struct MyIndex {
let i: Int
}

extension MyIndex: BidirectionalIndexType {
func successor() -> MyIndex {
print("successing!")
return MyIndex(i: i+1)
}
func predecessor() -> MyIndex {
print("predecessing!")
return MyIndex(i: i-1)
}
}

// indices need to be Equatable
func == (lhs: MyIndex, rhs: MyIndex) -> Bool {
return lhs.i == rhs.i
}
```

I’ve put prints in there so you can tell when the functions are called. Now, this index type will have the default `advancedBy` implementation, which just calls `successor()` multiple times. And because of the `print`, you can see it happening:

```func castHolyHandGrenadeOfAntioch<
I: ForwardIndexType
>(idx: I) {
idx.advancedBy(3)
}

let idx = MyIndex(i: 1)
castHolyHandGrenadeOfAntioch(idx)
// prints “successing!” 3 times
```

OK, now, we conform the type to be random access by giving it advance and distance functions:

```extension MyIndex: RandomAccessIndexType {
func advancedBy(n: Int) -> MyIndex {
return MyIndex(i: i+n)
}
func distanceTo(end: MyIndex) -> Int {
return end.i - i
}
}
```

and now, when we call the `castHolyHandGrenadeOfAntioch`, we see nothing printed. Instead, even though the function only required a forward index, it uses the better `advancedBy` implementation of the random-access index.

But… this only works because `advancedBy` had been declared in the original `ForwardIndexType` protocol declaration. If, on the other hand, we added another method as an extension to different index types – say, a `retreatedBy` function – this would not happen.

First, let’s do that for `BidirectionalIndexType`:

```extension BidirectionalIndexType {
// just an example, you don't have to do this!
// since BidirectionalIndexType also supports
// advancedBy(-distance)
func retreatedBy(n: Distance) -> Self {
var i = n
var result = self
// since Distance isn’t strideable, this
// is a rare case where you might mourn the
// loss of C-style for and the ++ operator…
while i > 0 {
result = result.predecessor()
i -= 1
}
return result
}
}
```

and then, an optimized version for `RandomAccessIndexType`:

```extension RandomAccessIndexType {
func retreatedBy(n: Distance) -> Self {
return self.advancedBy(-n)
}
}
```

But now, if we repeat our earlier experiment but calling this function, we get a different result:

```// only requires bidirectional access
func runAway<I: BidirectionalIndexType>(idx: I) {
idx.retreatedBy(10)
}

// and even though MyIndex is random access
let braveSirRobin = MyIndex(i: 10)

// the bidirectional version is called...
runAway(braveSirRobin)
// prints “predecessing!” 10 times
```

So we can see the difference between default implementations that are also declared as part of the protocol, versus ones just created as extensions. With the former, generic functions get to take advantage of specialized implementations, whereas with the latter, only the implementation that matches the generic constraint will be called. This is why you often see functions declared twice in the standard library. For example, on `SequenceType`, `underestimateCount` is declared like this, so that if you pass in a collection to a function that takes a sequence, it can check it’s length if it’s a collection, without risking consuming the sequence.

1. That’s assuming that there isn’t a legitimate reason to vary elements in subsequences which I don’t… think… there is?