Inside swift collections generators and sequences

A swift collection type is any class that implements the Collection or the mutable counterpart MutableCollection protocol.

The collection has two main responsibilities; to associate an item at a specific index (of type IndexType) and return it through object subscript function, and to stream the elements in the collection through implementing the Sequence protocol.

Its important to note that the collection main responsibilities are as simple as:

• Object subscripting item = collection[IndexType]
• Creating a generator for item streaming item = collection.generator().next()

Collection Subscript

The collection associated type IndexType specifies which type is used to index the collection. Any type that implements ForwardIndex can be used as the IndexType.

The ForwardIndex is an index that can only be incremented, for example a forward index of value 0 can be incremented to 1,2,3 etc…, This protocol internally inherits from Equatable and _Incrementable protocols.
In order to adhere to the ForwardIndex protocol successor() -> Self method and the Equatable protocols must be implemented.

The bellow is the simplest ForwardIndex implementation.

class MyForwardIndex: ForwardIndex {
 private var _index = 0
 init(index: Int) {
 _index = index;
 }
 func successor() -> MyForwardIndex {
 return MyForwardIndex(index:_index++)
 }
}
func ==(lhs: MyForwardIndex, rhs: MyForwardIndex) -> Bool {
 return lhs._index == rhs._index
}

Array type uses Int as its collection IndexType since Intimplements the ForwardIndex protocol deep inside its hierarchy (Int -> SignedInteger -> Integer -> RandomAccessIndex -> BidirectionalIndex -> ForwardIndex)

1.successor() //prints 2

The BidirectionalIndex is a ForwardIndex that can also go backward (hence the name), calling predecessor() will decrement the index

2.predecessor() //prints 1

RandomAccessIndex is an Index that can be advanced by more than 1 at once.

0.advancedBy(10) //prints 10
0.advancedBy(-10) //prints -10

Collection Generator

Collection also implements the Sequence protocol in order to provide the for _ in iteration functionality.
Sequence is a protocol that gives the functionality of streaming the elements. This protocol declares generate() -> GeneratorType that returns a GeneratorType. The GeneratorType is any type that implement the Generator protocol.

The Generator protocol declares next() -> Element? method to return the next item in the Collection. The generator protocol also declares Element as an associated type that specify the type that this generator will return when next is called.

The following is how each protocol participates in the for _ in obj in loop:

1. The runtime will call Sequence.generate() -> GeneratorType in order to create a generator object to use in the iteration
2. For each iteration the runtime will call GeneratorType.next() to produce the new element to use, if next returns nil iteration stops.

An implementing of both the protocols needed for a class to be used in the for-in loop iterator would look like:

class MyClass: Sequence, Generator {
 var counter = 0;
 func next() -> String? {
 counter++;
 return counter > 5 ? nil : “Some Value”
 }
 func generate() -> Self {
 return self
 }
}
//Usage
for _ in MyClass() { }

Swift provides a bunch of built in Generators.

IndexingGenerator

The simplest generator provided by swift is the IndexingGenerator. when the indexing generator is initialised it reads the startIndex and stores it in its _position ivar, at each next() method call the generator will check if _position equals the collection’s endIndex if it does it returns nil.

If the _position does not equal endIndex it will return the collection[_position] and then increment the _position by calling _position.successor()

An implementation for the IndexingGenerator would be similar to:

class MyIndexingGenerator<C: Collection>: Generator {
 var _colletion: C
 var _index: C.IndexType
 func next() -> C.GeneratorType.Element? {
 var item:C.GeneratorType.Element?
 if _index == _colletion.endIndex {
 item = nil
 } else {
 item = _colletion[_index]
 }
 _index = _index.successor()
 return item
 }
 init(_ colletion: C) {
 _colletion = colletion;
 _index = _colletion.startIndex
 }
}

GeneratorOf

Swift also provides a GeneratorOf<T> as a struct that implements both Generator and Sequence, this closure should return a new element each time its executed since it will be called each time the generator’s next method is called

var count = 0;
var gen = GeneratorOf<Int> {
 count++
 return count >= 5 ? nil : count
}
for _ in gen {}

EnumerateGenerator

Calling enumerate with a sequence will create an EnumerateGenerator which is a special type of Generator that for each next call will return a tuple of index/value (index / collection[index])

var arr = [1,2,3,4,5]
var enumerator = enumerate(arr)
var (index, value) = enumerator.next()!
index //0
value //1
var dictionary = [“k1":”v1", “k2":”v2"]
var enumerator = enumerate(dictionary)
var (index, value) = enumerator.next()!
index //0
value //a tuple with .0 = “k1" , .1 = “v1"

Collection Types

Swift defines multiple high level concrete collection types:

• Array Types: Array, ContiguousArray, Slice
• Dictionary
• Repeat
• Range

Array

In order to be treated as an array a type should implement the ArrayType protocol, this protocol defines common method that an array should have.

Swift defines the following classes that implement the ArrayType protocol; Array, ContiguousArray, Slice.

Swift Array is the main class that represents arrays, The array is a generic class that takes 1 type, An array of integers will have the type of Array<Int>, creating an integer array:

var myArray = Array<Int>()

However swift comes with its sugar coated syntaxes, the above can be rewritten to

var myArray = [Int]() 

Slice is an array with an internal implementation that makes removing elements from the top of the array computationally cheap. The following will perform good on a Slice type

var arr = [1,2,3,4,5]
arr[1…4]

There is not much documentation regarding the ContiguousArray, but from its name one can guess that it has to do with the internal array storage, probably the elements are stored in Contiguous Memory Allocation layout.

Dictionary

Dictionary is the Hash map data structure implementation for Swift. Its a generic class that takes two types, The key implements the Hashable protocol and the value can be any type.

//Creating a Dictionary and setting a value in it
var dic = Dictionary<Int,String>()
dic[1] = “1"
//Create a Dictionary with a value
dic = [1:”1"]

Dictionary stores the items as (Key,Value) tuples that are indexed using DictionaryIndex index type, this index is an opaque type that does not have a public init. However we can fetch the index from startIndex var:

var dic = [“Key1":”Value1", “Key2":”Value2"]
var index = dic.startIndex

Dictionary stores the first index it used in the startIndex variable, and provide two different subscript, a subscript that takes a DictionaryIndex and another that takes the KeyType

Calling the dictionary’s DictionaryIndex subscript will return the key/value tuple stored at that index

dic[dic.startIndex].0 //returns the key for the startIndex
dic[dic.startIndex].1 //returns the value for the startIndex
var (key, value) = dic[dic.startIndex]

The KeyType subscript will return the value associated with the passed key

dic[“Key1"] //returns “Value1"

Repeat

Repeat is a simple sequence that gets initialised with a count and a value to repeat, Repeat uses Int as its index type

var repeat = Repeat<Int>(count: 5, repeatedValue: 1)
Repeat<Int>.self 

Range

Swift ranges are yet another generic class that implements the Collection protocol, a range has a start and end point. Range can be created using the Range class initialiser or by using the swift syntactic sugar initialiser

var range1 = (1..<10)
var range2 = Range(start: 1, end: 10)
//range1 and range2 are equivalent
var range3 = (1…10)
var range4 = Range(start: 1, end: 11)
//range3 and range4 are equivalent