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?
Regards,
Alex Komnin.
···
On Mon, Jan 30, 2017 at 3:21 AM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:
Hi Cihat,
Thanks for diving in here! For reference, here's the last thing I said
about this topic (IIRC):[swift-evolution] [Review] SE-0074: Implementation of Binary Search functions
Also
https://github.com/apple/swift/blob/master/test/Prototypes/Algorithms.swift.gyb#L679Note: the comment there isn't quite right: <https://github.com/apple/swift/pull/7135>
on Sun Jan 29 2017, Cihat Gündüz <swift-evolution@swift.org> 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.swiftMy 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
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution--
-Dave_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution