More on rotate, Part 2


(Daryle Walker) #1

Actually, this is an independent thread, but before posting, I searched for previous discussions and saw one of my previous posts.

Sometimes, I make my own versions of code I see on the forums. One implementation reminded me of the "ring buffer" simulations used in some Sequence/Collection algorithms (which I've been reading lately because of split). I thought that the work of a ring buffer can be faked by playing around with rotations, and so I had to come up with rotation routines.

The code is in the "Rotate.swift" file of my latest Gist.

The plan for the "ring buffer" was to use in-place rotation, then I changed the buffer to keep a separate Array of indexes and copy it over during each rotation. That means that I have code for both versions, an in-place method (rotate) and a wrapping adapter type (RotatedCollection). I was greatly inspired by how reverse and reversed in the Standard Library work.

Since so much standard library code uses the names "first" and "last" for the end-cap elements, I'm surprised that (almost) no one, including myself, considered them as the names for the parameters until now! rotate(toFirst:) moves the element at that index to be at startIndex instead, which is a left rotation. rotate(toLast:) does a right rotation, moving the targeted element to index(before: endIndex). The parameter label names help because it took me a long time to remember which way "left" and "right" mean in data inside a computer memory chip.

While research previous posts, I wondered if we should add a two-parameter rotate with arbitrary endpoints:

public mutating func rotate(elementAt: Index, to: Index)

but, besides being harder to implement, I'm not sure it would really be used over the first and last variants. And I'm not sure what the return value(s), if any, should be.

(Currently, I brute-force the calculation of the optional return value of the index of where the original first element moved to. Is there a way to naturally find it properly through the algorithm?)

On RotatedCollection, I have a general question. I only slightly understand what LazySequenceProtocol does, and I have no idea what LazyCollectionProtocol brings to the table (besides Collection support). What do they do; when I reread the Standard Library's "Reverse.swift," why does their code only extended LazySequenceProtocol but not its Collection analog?

Looking at the other file in the Gist, where I used the "ring buffer" design, I copy the rotated buffer index array over itself each rotation. I could save copying by reseating the internal bounding iterator:

/// Rerotates the internal collection to start at the given index.  If `i != startIndex`, invalidates all outstanding `Index` instances.
mutating public func reseat(asNewFirst i: Index) {
    precondition(i.origin == origin)
    precondition(i.base != nil)

    origin = i.base!
/// Rerotates the internal collection to end after the given index.  If `i != indices.suffix(1).first!`, invalidates all outstanding `Index` instances.
mutating public func reseat(asNewLast i: Index) {
    let next = index(after: i)
    if next != endIndex {
        reseat(asNewFirst: next)

but I didn't keep these prototype methods. I still think they could be useful, should I put them back in? Are these good names?

There was another pair of prototype methods dropped: Index conversions between the original collection and the wrapper.

/// Returns the given wrapped-base index adapted to this rotated collection.
public func convertFromBase(index: Base.Index) -> Index {
    guard index != base.endIndex else { return Index(origin: origin, base: nil) }

    return Index(origin: origin, base: index)
/// Returns the wrapped-base index for the given rotated-collection index.
public func convertToBase(index: Index) -> Base.Index {
    precondition(index.origin == origin)
    guard let innerIndex = index.base else { return base.endIndex }

    return innerIndex

The now-public Index.base property eliminates the need for convertToBase, but there's no way to create a corresponding rotated index value from a given original-collection index value. Should I add convertFromBase back in?

At the end of the file are types for a Sequence version of rotation! It supports only left-rotation; right-rotation could only be supported by reading all the elements first, which means you could convert it to a Collection and use the previous functions. Is the looping dynamic a good idea when sequence's length is shorter than the skip length?

Until I researched old posts, I forgot there's already been a review for this idea. It dates before a lot of library philosophy changes. I'll try making a revised version. Should the Sequence rotation code be included in the new proposal?

The in-place rotation code in my file is only for forward iteration. But the proposal's code uses specialized code for bi-directional collections and more for random-access collections. Do those make a difference, or should I keep the current code forward-only?

A RingBuffer collection

I'll quote one of your previous posts

It seems like it would be much better to include a dedicated RingBuffer struct that could be made much faster than extending arbitrary Sequence/Collection. If someone cared about performance, they cannot use your methods, and if they don't care, they could just do foo = TheirType(RingBuffer(foo).rotate()) and unlike your approach it would be obvious that it's slow.

(Daryle Walker) #3

Rotation function/types are considered a notable capability to have in standard libraries; you can look at the previous attempt I implied before for a better motivation. I just unknowingly modernized it.

During writing these files, I was wondering about making a dedicated ring-buffer collection type, but it didn't seem that useful. Either you would have RangeReplaceableCollection support and deal with weird effects when an operation made the number of elements above the limit (If you do a single-element append or prepend on an already-full ring buffer, it's easy to determine which old element to kill, but what about in general?), or do what Dictionary and Set did and use a customized subset of RRC operations (which meant that they don't conform to RRC). If I add the reseat-index operations, the matching algorithm in the same Gist would be more efficient than if I change it to use a full-blown ring buffer.

(Daryle Walker) #4

I've massively updated the Gist. I added both the base-to-wrapped index conversion method (translate(baseIndex:)) and no-copying anchor-reseating methods (reseat(asFirst:) and reseat(asLast:)) to RotatedCollection. And I added a dedicated ring-buffer collection (RingBuffer<Element>) in a separate file, which the new primary search method firstMatch<Pattern, Result>(for: storingAs: by:) uses.