[swift-evolution] Changes to RangeReplaceableCollectionType

Thu Mar 3 14:29:16 CST 2016

Okay so I’ve been tweaking the protocols that I’m using. For my own use I’ve ended up with two protocols:

ExtendableCollectionType: Which implements .insert() and .insertContentsOf() methods, as well as a non-binding concept of capacity.
RangeRemoveableCollectionType: Which implements most basic removal methods that don’t involve replacing anything (i.e- they don’t include insertions at specific indices). This is therefore safe for self-ordering collections as while insertion can’t support an index (can’t guarantee item will end up where it’s placed), removing them should have no such restrictions that I can see.

This effectively leaves RangeReplaceCollectionType with index based insertions, append (insert at end) and range replacement methods. Other proposed changes include removing the initialisers (since these restrict implementations), and possibly changing the .replaceRange() method to accept a sequence rather than a collection as I don’t believe a collection should be required?

Here’s a quick, simplified, example of how everything would look:

// Extension of a collection by adding new contents
protocol ExtendableCollectionType : CollectionType {
    var capacity:Index.Distance { get }

    mutating func insert(element:Self.Generator.Element)
    mutating func insertContentsOf<S:SequenceType where S.Generator.Element == Self.Generator.Element>(elements:S)

    mutating func reserveCapacity(minimumCapacity:Bool)
}

extension ExtendableCollectionType {
    var capacity:Index.Distance { return self.count }
    mutating func insertContentsOf<S:SequenceType where S.Generator.Element == Self.Generator.Element>(elements:S) {
        for element in elements { self.insert(element) }
    }
}

extension ExtendableCollectionType where Self:RangeReplaceableCollectionType {
    mutating func insert(element:Self.Generator.Element) { self.append(element) }
    mutating func insertContentsOf<S:SequenceType where S.Generator.Element == Self.Generator.Element>(elements:S) { self.appendContentsOf(elements) }
}

// Removal of specific indices
protocol RangeRemoveableCollectionType : ExtendableCollectionType {
    mutating func removeAll(keepCapacity keepCapacity:Bool)
    mutating func removeAtIndex(index:Index) -> Self.Generator.Element
    mutating func removeRange(subRange:Range<Index>)
}

extension RangeRemoveableCollectionType {
    mutating func removeAll(keepCapacity keepCapacity:Bool) { self.removeRange(self.startIndex ..< self.endIndex) }
    mutating func removeFirst() -> Self.Generator.Element? { … }
    mutating func removeFirst(n:Index.Distance) { self.removeRange(self.startIndex ..< self.startIndex.advancedBy(n)) }
}

extension RangeRemoveableCollectionType where Self.Index:BidirectionalIndexType {
    mutating func removeLast() -> Self.Generator.Element? { … }
    mutating func removeLast(n:Index.Distance) { self.removeRange(self.endIndex.advancedBy(-n) ..< self.endIndex) }
}

// Insertion/replacement at specific indices
protocol RangeReplaceableCollectionType : RangeRemoveableCollectionType {
    mutating func append(element:Self.Generator.Element)
    mutating func appendContentsOf<S:SequenceType where S.Generator.Element == Self.Generator.Element>(elements:S)
    mutating func insert(element:Self.Generator.Element, atIndex:Index)
    mutating func insertContentsOf<S:SequenceType where S.Generator.Element == Self.Generator.Element>(elements:S, atIndex:Index)
    mutating func replaceRange<S:SequenceType where S.Generator.Element == Self.Generator.Element>(subRange:Range<Index>, with elements:S)
}

This is just to give an idea, there may be some accidental omissions and some stuff is simplified or omitted on purpose, but it hopefully shows the separation and structure that I’m aiming for.

I was originally going to put all of the RangeRemovableCollectionType methods into ExtendableCollectionType, however that would mean tying the ability to add and to remove together, which may still be limiting; a collection could for example be designed to be consumed internally, or even to just expire its own contents (e.g- a cache type) so may not wish to externally expose methods that would remove elements.

Also, naming is absolutely up for debate too, all feedback appreciated!

P.S- I know that naming conventions are currently up for debate, so I’m just sticking with the way things are right now for simplicity, obviously everything would be tweaked to match whatever decision is made for whichever version this ends up in =)

> On 29 Feb 2016, at 21:16, Dmitri Gribenko <gribozavr at gmail.com> wrote:
> 
> On Mon, Feb 29, 2016 at 1:13 PM, Haravikk <swift-evolution at haravikk.me <mailto:swift-evolution at haravikk.me>> wrote:
>> 
>> On 29 Feb 2016, at 11:11, Dmitri Gribenko <gribozavr at gmail.com> wrote:
>> 
>> On Mon, Feb 29, 2016 at 2:54 AM, Haravikk <swift-evolution at haravikk.me>
>> wrote:
>> 
>> How would you decide equality?  You would have two collections, one on
>> the left, and one on the right, and each of those has a different
>> concept of equality via the stored 'isOrderedBefore' closure.
>> 
>> 
>> To me two collections are equal so long as their contents are the same, and
>> in the same order. In other words the actual closure isn’t necessary to the
>> comparison, though obviously it will affect it, since elements stored in
>> ascending numeric order clearly won’t match the same elements in descending
>> numeric order.
>> 
>> I'm not opposed to adding a new protocol.  What seems strange to me is
>> that you are describing various collections that clearly can't
>> implement RangeReplaceableCollection, and trying to weaken protocol's
>> guarantees so that they can.
>> 
>> 
>> I’m not trying to weaken its guarantees; the only thing directly affecting
>> RangeReplaceableCollectionType would be removing the initialisers, as I
>> don’t think they’re necessary to implementing that type (though of course I
>> welcome any description as to why they may be necessary).
>> 
>> Otherwise a new protocol is exactly what I’m interested in; you mentioned an
>> ExpandableCollectionType, which I think is a start, though it should
>> probably have add() and addContentsOf()
> 
> Set calls this operation 'insert'.
> 
>> methods rather than appends (this
>> way they place no guarantees on where elements will go, only that they are
>> added). While the add() method would be a synonym of append() for arrays, it
>> would be useful for aligning with Set I think.
>> 
>> Moving the removeRange() and related methods (removeAtIndex etc.) would take
>> them away from RangeReplaceableCollectionType (it should extend whatever new
>> protocol is added), but the idea is to separate the concept of removing
>> things by index, and replacing them/performing insertions.
>> 
>> Basically I’d like to tweak the protocols such that a generic collection can
>> be expanded, and its elements accessed in an order, but that order may be
>> defined by the type itself; to me, inserting a value directly at a specific
>> index is a more specialist type.
> 
> Sound like a plan.  Please make sure to design the protocol in such a
> way that there are useful generic algorithms that can be written over
> such a protocol.
> 
> Dmitri
> 
> -- 
> main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
> (j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr at gmail.com <mailto:gribozavr at gmail.com>>*/

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160303/e6d19fa2/attachment.html>