[Proposal] Add Array binary search to the standard library

[Alexey_Komnin]

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#L679

Note: the comment there isn't quite right: <https://github.com/apple/swift/pull/7135&gt;

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.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
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

[nnnnnnnn (Nate Cook)]

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've been playing around with a protocol-based approach to these questions. A mutable sorted collection can easily allow operations that maintain the collection's order (basically just insertion with the collection deciding where to put the element or elements and removal of one or more elements). I suppose it's possible to allow appending / prepending if we require that the elements be (a) sorted and (b) wouldn't change the sort of the collection.

You can see my current version here: SortedCollection.swift · GitHub — it defines two protocols along with a mutable SortedArray and an immutable SortedView.

-Nate

···

On Jan 30, 2017, at 2:47 AM, Alexey Komnin via swift-evolution <swift-evolution@swift.org> wrote:

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#L679

Note: the comment there isn't quite right: <https://github.com/apple/swift/pull/7135&gt;

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.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
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

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

[dabrahams (Dave Abrahams)]

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

···

on Mon Jan 30 2017, Alexey Komnin <interfere.work-AT-gmail.com> wrote:

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#L679

Note: the comment there isn't quite right: <https://github.com/apple/swift/pull/7135&gt;

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.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
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

--
-Dave

[dabrahams (Dave Abrahams)]

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've been playing around with a protocol-based approach to these
questions. A mutable sorted collection can easily allow operations
that maintain the collection's order (basically just insertion with
the collection deciding where to put the element or elements and
removal of one or more elements). I suppose it's possible to allow
appending / prepending if we require that the elements be (a) sorted
and (b) wouldn't change the sort of the collection.

This would require (well, should use) a protocol that would be refined
by RangeReplaceableCollection, which means it needs to happen in before ABI
stability sets in.

You can see my current version here:
SortedCollection.swift · GitHub
— it defines two protocols along with a mutable SortedArray and an
immutable SortedView.

Cool; looking forward to the full proposal! ;-)

···

on Mon Jan 30 2017, Nate Cook <natecook-AT-gmail.com> wrote:

On Jan 30, 2017, at 2:47 AM, Alexey Komnin via swift-evolution <swift-evolution@swift.org> wrote:

--
-Dave