on Mon Jan 30 2017, Alexey Komnin <interfere.work-AT-gmail.com> wrote:
> Hello to everyone. > > Let me put my two cents. > >>> I didn’t want the SortedArray to conform to MutableCollection or >>> even RandomAccessCollection as I felt it was not needed just to >>> support binary search and prevent re-sorting. >> >> You are right not to support MutableCollection or >> RangeReplaceableCollection, as those would allow you to violate the >> “sorted” invariant. However, it should conform to >> RandomAccessCollection; that's really easy to implement and would >> improve ease-of-use a lot. > > Are we able to add some kind of type constraint which allows > append/prepend operations on a particular collection? Seems like a > good replacement for MutableCollection in this case. It should be > available to append elements greater or equal to the last element in > SortedArray, isn't it? I think we should handle that with a method like this /// Inserts `x` in the correct position, using `positionHint` /// to improve performance if it is accurate. func insert(_ x: Element, positionHint: Index) -> Index > > > Regards, > Alex Komnin. > > On Mon, Jan 30, 2017 at 3:21 AM, Dave Abrahams via swift-evolution > <[email protected]> wrote: >> >> Hi Cihat, >> >> Thanks for diving in here! For reference, here's the last thing I said >> about this topic (IIRC): >> >> https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160502/016729.html >> >> Also >> https://github.com/apple/swift/blob/master/test/Prototypes/Algorithms.swift.gyb#L679 >> >> Note: the comment there isn't quite right: >> <https://github.com/apple/swift/pull/7135> >> >> on Sun Jan 29 2017, Cihat Gündüz <[email protected]> wrote: >> >>> Hi guys, I know this topic is probably out of scope for Swift 4 >>> and a proposal was already rejected for Swift 3, but I’d like to share >>> my two cents on this as I just wrote a SortedArray class with support >>> for binary search in my open source library HandySwift. >>> >>> You can see my classes current implementation here: >>> https://github.com/Flinesoft/HandySwift/blob/cd7ae7041c8174cd655f24eae653f76697875a48/Sources/Structs/SortedArray.swift >>> >>> My goal was to provide only what is commonly needed when working with >>> big arrays in algorithms. For me this included: >>> >>> - having a type that keeps a sorted array to prevent re-sorting (solution: >>> the SortedArray class) >> >> Sounds consistent with my feedback... but it doesn't conform to >> RandomAccessCollection. Why not? >> >>> - have a method that can find an object using binary search (solution: the >>> index method) >> >> Please see the algorithms prototype >> >>> - allow partitioning the array into smaller parts (solution: subscript, >>> prefix & suffix methods) >> >> * The collection returned by the slicing subscript should obey the law >> >> a[i..<j][i] == a[i] >> >> Normally that means you want to make it a different type from a. >> >>> - prevent re-implementing the Array class (solution: a getter to the >>> stored internal array) >> >> Not sure I understand what this is supposed to mean. >> >>> Also note that the SortedArray in my approach allows all types that >>> conform to `Sequence` as input with `Comparable` elements and saves >>> them into a sorted array on initialization. That array is also >>> publicly read-accessible. Inserting and deleting objects from the >>> SortedArray are possible, too, but that’s just few of the >>> MutableCollection methods. >> >> Actually no, those are RangeReplaceableCollection methods. >> >>> I didn’t want the SortedArray to conform to MutableCollection or >>> even RandomAccessCollection as I felt it was not needed just to >>> support binary search and prevent re-sorting. >> >> You are right not to support MutableCollection or >> RangeReplaceableCollection, as those would allow you to violate the >> “sorted” invariant. However, it should conform to >> RandomAccessCollection; that's really easy to implement and would >> improve ease-of-use a lot. >> >> >>> Maybe my approach can somehow help forming the final solution to be >>> included into Swift once this features is tackled again. >>> >>> Best regards, >>> Cihat >>> _______________________________________________ >>> swift-evolution mailing list >>> [email protected] >>> https://lists.swift.org/mailman/listinfo/swift-evolution >>> >> >> -- >> -Dave >> >> _______________________________________________ >> swift-evolution mailing list >> [email protected] >> https://lists.swift.org/mailman/listinfo/swift-evolution -- -Dave _______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
