[swift-evolution] Changes to RangeReplaceableCollectionType

[Dmitri Gribenko]

On Thu, Mar 3, 2016 at 12:29 PM, Haravikk <swift-evolution at haravikk.me> wrote:
> 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.

Hi,

Thank you for preparing these APIs.  Could you explain what the
semantics of these new APIs are (in doc comments, for example), and
provide examples of generic algorithms that work on any collection
that implements the desired semantics in the minimal way?

Dmitri

> 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>
> 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>*/
>
>



-- 
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>*/