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
