Collection Index and magic factor

An index is an indirect shortcut derived from and pointing into, a greater volume of values, data, information or knowledge. (wikipedia)

In general (however it is not the rule) in modern programming languages Index values start at 0 position and ends at "length - 1" position. A lot of fathers of Computer Science already pointed why numbering should start at zero. Swift is not the exception here. Swift index starts at 0.

Zero based index elementary school

let array = [10,20,30,40,50,60]  
array[0] // first element,  index 0, value 10  
array[1] // second element, index 1, value 20  
array[2] // third element,  index 2, value 30  
array[5] // last element,   index 5, value 60  

count of elements of array is 6, as so the last index is 5. Simple rules are:

let count = lastIndex + 1  
let lastIndex = count - 1  

Collections

Array is the CollectionType value. CollectionType is base protocol for all the collections structs. Collections are indexable, this is why CollectionType inherit from Indexable protocol.

protocol CollectionType : Indexable, SequenceType {  
    var startIndex: Self.Index { get }
    var endIndex: Self.Index { get }
}

Indexable protocol bring two properties: startIndex and endIndex to work with indexes. Let's see how it goes:

let array = [10,20,30,40,50,60]  
array.startIndex // 0  
array.endIndex   // 6  
array.count      // 6  

wait wait.... wait a minute. How come that endIndex is equal 6 while startIndex is 0 ? I just said that last index value is equal to length - 1. This array has 6 elements, last index should be 5!, not 6, which is obviously not true here. Something stinks here.

Let me check it:

array[array.endIndex] // fatal error: Array index out of range  

ups... as expected. Last index is 5 and 6 at the same time. Remember Schrödinger's cat a thought experiment ? This may be the case.

Now I know that last index is and is not 5 or 6. Clear? not at all. One more check, for my sanity:

let emptyArray:[Int] = []  
emptyArray.startIndex  // 0  
emptyArray.endIndex    // 0  
emptyArray.count       // 0  

so it is OK now. Start and ends at 0 position. Length is 0. This is all I want. But in fact, this looks like some kind of exception to the rule where endIndex is out or range. So I checked the headers and:

  • startIndex: The position of the first element in a non-empty collection.
  • endIndex: The collection's "past the end" position.

WAT? once more... WAT just happened? end index is not the index per se, it is length. Between startIndex and endIndex I start with zero indexed position and ends with 1 indexed position. And why the hell, empty array do follow zero indexed position?

Because there is another rule:

The position of the first element in a non-empty collection. In an empty collection, startIndex == endIndex.

The hell just opened the gates.

Why?

You know why?

"It's necessary to be able to represent an arbitrary subrange as a pair of indices." - anonymous source

ranges you said... right... ranges, how can I forgot:

let range = 0...0 // 0..<1  
range.startIndex  // 0  
range.endIndex    // 1  
range.count       // 1  

Again: CAN'T BELIEVE (dramatic stage movement). Look what just happened. I created 1 element range from 0 to 0 (included) and my range length is 1, start index is 0 and last index is (obviously) 1. The Lucifer ask you to join the table.

That said: count is not simply length, it is: endIndex value minus startIndex value:

var count: Self.Index.Distance {  
    return endIndex - startIndex
}

Magic factor

What kind of magic I need to go from 0, add 5 and ends with 6, you may ask. How about magic factor:

extension CollectionType {  
    /// Magic factor
    var lastIndex:Int {
        let magicFactor = (Double(arr.endIndex) - 1) / Double(arr.count)
        return Int(magicFactor * Double(arr.count))
    }
}

this is joke, but if you ever will implement your own CollectionType and override how count works - don't trust yourself... be aware.

Conclusion

Be aware. Collection Index is not what you think it is.