*We will look at the implementation of the function **suffix** in collections in terms of the evolution of computational complexity from the basic protocol **Sequence** to the **RandomAccessCollection** protocol.*


:::info
Before reading this article, get acquainted with the concept of [computational complexity.](https://en.wikipedia.org/wiki/Computational_complexity#:\~:text=In%20computer%20science%2C%20the%20computational,resources%20required%20to%20run%20it.&text=The%20study%20of%20the%20complexity,is%20called%20computational%20complexity%20theory.)

:::

Each Swift developer used features from the ***Sequence*** family of protocols. It comes from the Sequence protocol and includes ***Sequence***, ***Collection***, ***BidirectionalCollection***, ***RandomAccessCollection***, and other protocols related to asynchrony, laziness, collection variability. Here, we'll look at the most basic protocols that provide read-only access: ***Sequence***, ***Collection***, ***BidirectionalCollection***, and ***RandomAccessCollection*** protocols.

We use the functions and properties of collections (e.g., *prefix*, *sort*, *count*) without thinking about internal implementation, although the implementation initially looks simple. However, a feature available at different levels of these protocols' hierarchy can be implemented differently and with diverse computational complexity.

\
Each new protocol in the protocol hierarchy from ***Sequence*** to ***RandomAccessCollection*** announces new basic capabilities. They allow you to implement new default functions in the protocol extension and optimize existing ones declared in inherited protocols.
We'll see the evolution of implementation based on new functions at each level of the protocol hierarchy on the example of the standard implementation of the *suffix* function for the ***Sequence***, ***Collection***, ***BidirectionalCollection***, and ***RandomAccessCollection***. The *suffix* function returns a subsequence of the last *k* elements.

## Sequence

The ***Sequence*** is the base protocol in the hierarchy of collections. The primary ability is to iterate one by one element from some set due to the iterator. This set can be limited or unlimited, and an iteration of elements can be destructive or non-destructive. The protocol doesn't say anything about it.

\
***Sequence*** does not have property *count*, but there is an *underestimatedCount* property. On the simple principle of iterating elements, it becomes possible to write many amazing functions, such as *prefix*, *suffix*, *contains*, *first*, *min*, *max*, *drop*, *sorted*, *map*, etc. The protocol has a default implementation for these functions. They may be suboptimal; for example, we cannot access an element using an index with computational complexity *O(1)*, based only on the principle of iterative elements. The simplicity of this protocol limits the ability to implement functions. We can only iterate the elements. That's it.

### What about function 'suffix' in Sequence?

Only one simple function allows us to iterate over a set of elements from start to finish at this protocol level. The only way to get the last *k* elements is to enumerate every ***Sequence*** component, putting the current part into a ring buffer structure. The default implementation of this function defines *RingBuffer* with the capacity of *k* elements.

\
The first element from the ***Sequence*** is put into the first cell of the ring buffer. The second element puts to *2*-nd cell, *k*-th element puts to *k*-th cell, *k+1*-th puts to the *1*-st cell of buffer (while previous items stay in their cells), and further every current piece rewrite an old one. Thus, when we get the last element of the sequence, all the last *k* elements are in the ring buffer. The only thing we should do is cut and glue the result array from the buffer with the right index equal to *(count of elements in the sequence+1) % k*. This function's computational complexity is *O(n)* since iterate over all the elements.

\
 ![](https://cdn.hackernoon.com/images/mXQzCT9hWCeOFe2o7E2JPWJt4Zr2-x813sce.png)*A code snippet of [the current implementation](https://github.com/apple/swift/blob/main/stdlib/public/core/Sequence.swift)*

## Collection

The ***Collection*** protocol has the same capabilities as the ***Sequence*** protocol, but it declares non-destructive iteration of the elements multiple times and provides access to the items by index.


In addition, iteration over elements provides the same order as the elements when indexing. Iterating through the elements by an index is only available in one direction. You can get an element by index, calculate the following index, get the next item by this index, calculate the following index, and so on. However, you cannot calculate the index in reverse order.

For example, for simplicity, suppose that we have a collection whose indices are *Int* numbers. To get the first element, we should use the *startIndex* property available in the protocol (also, there is *endIndex*), which will be *0*. Then we get the following index of our collection, next to the initial index — *index(after: 0)*, will be *1*. However, in ***Collection***, there is no way to define the index preceding index *1*. ***BidirectionalCollection*** adds this ability.

### What about function 'suffix' in Collection?

In ***Collection***, we can call the subscript of a collection by range to get the elements we need, and it seems like a simple operation at first. We need to get the start index and call collection's subscript *\[suffixStartIndex .. <endIndex\]*. The last function will work with *O(1)* complexity, but there is a problem with getting the start index of the last *k* elements. We do not have a function for getting the *i*-th index with complexity *O(1)* to obtain it. The protocol only provides the ability to get the next index in *O(1)*, — *index(after:)*. To reach the *i*-th index, first, we need to calculate *startIndex + 1*, *startIndex + 2*, and so on, and then up to our index *suffixStartIndex*.

Thus, the *suffix* function in ***Collection*** has a different default implementation based on index calculation rather than iteration over all elements, but the complexity of this function remains *O(n)*.

\
 ![](https://cdn.hackernoon.com/images/mXQzCT9hWCeOFe2o7E2JPWJt4Zr2-s823sf7.png)*[index(_: offsetBy: limitedBy)](https://github.com/apple/swift/blob/main/stdlib/public/core/Collection.swift) has complexity O(n)*

## BidirectionalCollection

A collection that has just one additional base function *index(before:)* adds new features. For example, the property *last* (computed as an item at the index preceding *endIndex*) and reversed (returns another ***ReversedCollection*** structure, passing our collection as a parameter to the initializer).

\
Yes, until now, we haven't been able to implement these functions in previous protocols because they would have been highly ineffective. For instance, we could iterate over all the elements on the ***Sequence*** protocol and take the last one.
In reality, there is no such function, but if we call the *suffix(1)* function, such an algorithm will be used.

### What about function 'suffix' in BidirectionalCollection?

The ***BidirectionalCollection*** provides one new primary feature, which is to get the following index backward order. As we remember, in the ***Collection*** protocol, the starting index of the required subsequence was calculated from the very beginning.

\
However, implementing the *suffix* function in the ***BidirectionalCollection*** protocol uses the ability to compute the previous index; it calculates the index of the starting element of the subsequence, starting from the end. This approach can have its advantages, especially if *k* is a small number.


It looks like it is possible to optimize the *suffix* function here by calculating how profitable it is to go from start to end or end to start to compute the subsequence's starting index. But to make such a comparison, you need to call the *count* property, which has *O(n)* complexity in this protocol.

\
Therefore, the implementation assumes that the number of elements *k* is less than half of *n*. Otherwise, the function execution will not be the most efficient.

\
 ![](https://cdn.hackernoon.com/images/mXQzCT9hWCeOFe2o7E2JPWJt4Zr2-jm33s12.png)*[index(_: offsetBy: limitedBy)](https://github.com/apple/swift/blob/main/stdlib/public/core/BidirectionalCollection.swift) has complexity O(k) and works in a reverse way: from the end to the beginning (it was not available in inherited protocols)*

## RandomAccessCollection

Each new protocol in the protocol hierarchy, in addition to new capabilities, provides more efficient implementations of the functions defined in the base protocols. The peculiarity of this protocol is that it doesn't offer new primary functions, but it defines the requirements for the complexity of working with indices; calculating the distance between the indices and getting the index at some distance from the given one must be implemented with complexity *O(1)*.

In the previous protocol, the complexity of these functions could be *O(k)*, where *k* is the number of indices between two given ones, but now these functions have a complexity of *O(1)*. Many functions can be significantly optimized based on this, for example, the *count* property, which now has a computational complexity of *O(1)*.

### What about function 'suffix' in RandomAccessCollection?

***RandomAccessCollection*** doesn't provide any new core functions, but it declares that the *index(_: offsetBy:)* and *distance(from: to:)* functions must operate with complexity *O(1)*, which gives us the ability to calculate the starting index of our *suffix* instantly.

Moreover, there is no need to invent any new algorithm or implementation. It’s enough to use the old implementation but of much greater complexity - *O(1)*.

## Conclusion

With these simple examples, we've seen how the capabilities of the sequence protocols from ***Sequence*** to ***RandomAccessCollection*** evolve. I hope you've raised your awareness of the protocol choices for your custom sequences, and you'll understand better the default implementations in these protocols and the logic of the functions based on the protocols' core capabilities.

\


Apple

Glue

Instantly

2022 - HackerNoon Contributor of the Year - Algorithms

2022 - HackerNoon Contributor of the Year - Swift

2022 - Ios Writer of the Year

Nominated for 2022 - Ios Writer of the Year

Nominated for 2022 - HackerNoon Contributor of the Year - Swift

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Too Long; Didn't Read

Cassandra Forward a free Cassandra-focused community event

On The Way From Sequence to  
RandomAccessCollection in Swift

On The Way From Sequence to RandomAccessCollection in Swift

Too Long; Didn't Read

Companies Mentioned

@pplotnikov

RELATED STORIES