Maybe this has been addressed before on another topic, but why are minmax(),
minIndex(), maxIndex() and minmaxIndices() functions rather than read-only
properties? It seems like things would be much cleaner without the brackets,
and it’s shorter to implement in some cases as you can back it with a stored
property for caching. As functions, you'd need to write separate getters.
e.g.
struct Blah<T:Comparable> : Collection
{
var minIndex : Index?
var maxIndex : Index?
func insertElement(element: T)
{
// insert element
// compare with elements at stored minIndex, maxIndex
// update minIndex/maxIndex if necessary
}
}
Also, I’d favour “bounds”, “boundaries” or “limits” over minmax. There are
plenty of English words which better and more precisely describe what it
provides.
Karl
> Hello all,
>
> Attached is a draft of a proposal to expand the min and max sequence APIs to
> better handle collections and to support future sorted sequences/collections.
> The proposal is in a gist
> here<https://gist.github.com/natecook1000/d51267a6cf9e9463b9387bced4c65b16>and
> inlined below—would love to hear any comments or feedback before submitting
> the proposal.
>
> Nate
>
>
> Proposal: Expanded min/max algorithms
> This proposal would expand on the min() and max() sequence methods to add
> methods that return the corresponding index for a collection, efficiently
> find the minimum and maximum elements or indices at the same time, and
> provide extension points for sorted collections to provide all these results
> more efficiently.
>
> Related Bugs: SR-889<https://bugs.swift.org/browse/SR-889>and
> SR-890<https://bugs.swift.org/browse/SR-890>
> Motivation
> The Sequence protocol currently offers min() and max() methods that return
> the minimum and maximum elements of a sequence or collection. Unfortunately,
> there are applications where these methods do not provide enough flexibility
> to be useful.
>
> First, if the user of a collection wants not just to get the minimum value
> but also to operate on it in some way (e.g., mutation or just accessing it
> multiple times), she would need the index of the minimum element. The current
> APIs don't support that, so she would need to write her own.
>
> Second, the writer of a sorted collection is currently unable to provide
> efficient responses to the min() and max() methods when used in a generic
> context, even though these should be O(1) operations. Just like Set can
> respond quickly to contains(_:) even in a generic context, so too should new
> sorted collections be able to optimize their responses.
>
> Finally, getting the minimum and maximum elements (or indices) of a
> collection or sequence currently requires calling both min() and max(). With
> two calls, every element is iterated and compared twice. When you need both
> results, finding both the minimum and the maximum at the same time is more
> efficient, requiring only a single pass and 25% fewer comparisons.
>
> Proposed solution
> This proposal has three parts:
>
> Adding minIndex() and maxIndex() methods to Collection that return the index
> of the minimum and maximum elements, respectively.
>
> let numbers = [30, 40, 10, 20, 60, 50]
>
> if let i = numbers.minIndex() {
> print("\(i): \(numbers[i])") // 2: 10
> }
> Adding minmax() and minmaxIndices() methods to Sequence and Collection,
> respectively, to calculate the values (or indices) of the minimum and maximum
> elements simultaneously.
>
> if let result = numbers.minmax() {
> // result == (minimum: 10, maximum: 60)
> // ...
> }
> if let i = numbers.minmaxIndices() {
> // i == (minimum: 2, maximum: 4)
> print("\(i.minimum): \(numbers[i.minimum])")
> }
> Adding customization points for sequences and collections that can offer more
> efficient results:
> _customMinComparableElement()/_customMaxComparableElement() for Sequence and
> _customIndexOfMinComparableElement()/_customIndexOfMaxComparableElement()for
> Collection.
>
> Detailed design
> The following methods would be added to the visible public APIs of Sequence
> and Collection as default implementations.
>
> extension Sequence {
> /// Returns the minimum and maximum values of `self`, using
> /// `isOrderedBefore` to compare elements, or `nil` if the sequence
> /// has no elements.
> func minmax(@noescape isOrderedBefore isOrderedBefore:
> (Iterator.Element, Iterator.Element) throws ->Bool
> ) rethrows ->(min: Iterator.Element, max: Iterator.Element)?
> }
>
> extension Sequence where Iterator.Element: Comparable {
> /// Returns the minimum and maximum values of `self`, or `nil`
> /// if the sequence has no elements.
> func minmax() ->(min: Iterator.Element, max: Iterator.Element)?
> }
>
> extension Collection {
> /// Returns the index of the minimum element of `self`, using
> /// `isOrderedBefore` to compare elements, or `nil` if the
> /// collection has no elements.
> func minIndex(@noescape isOrderedBefore isOrderedBefore:
> (Iterator.Element, Iterator.Element) throws ->Bool
> ) rethrows ->Index?
>
> /// Returns the index of the maximum element of `self`, using
> /// `isOrderedBefore` to compare elements, or `nil` if the
> /// collection has no elements.
> func maxIndex(@noescape isOrderedBefore isOrderedBefore:
> (Iterator.Element, Iterator.Element) throws ->Bool
> ) rethrows ->Index?
>
> /// Returns the indices of the minimum and maximum elements of `self`,
> /// using `isOrderedBefore` to compare elements, or `nil` if the
> /// collection has no elements.
> func minmaxIndices(@noescape isOrderedBefore isOrderedBefore:
> (Iterator.Element, Iterator.Element) throws ->Bool
> ) rethrows ->(minIndex: Index, maxIndex: Index)?
> }
>
> extension Collection where Iterator.Element: Comparable {
> /// Returns the index of the minimum element of `self`, or `nil`
> /// if the collection has no elements.
> func minIndex() ->Index?
>
> /// Returns the index of the maximum element of `self`, or `nil`
> /// if the collection has no elements.
> func maxIndex() ->Index?
>
> /// Returns the indices of the minimum and maximum elements of `self`,
> /// or `nil` if the collection has no elements.
> func minmaxIndices() ->(minIndex: Index, maxIndex: Index)?
> }
> The customization points would be added to Sequence and Collection as
> protocol requirements, along with default implementations that return nil.
> The existing min()and max() methods would be updated to call the
> corresponding methods before iterating over the entire sequence.
>
> protocol Sequence {
> // ...
>
> /// Returns the minimum element as `Optional(element)` or `Optional(nil)`
> /// if the sequence has no elements. The uncustomized version returns
> /// `nil`.
> func _customMinComparableElement() ->Iterator.Element??
>
> /// Returns the maximum element as `Optional(element)` or `Optional(nil)`
> /// if the sequence has no elements. The uncustomized version returns
> /// `nil`.
> func _customMaxComparableElement() ->Iterator.Element??
> }
>
> protocol Collection {
> // ...
>
> /// Returns the index of the minimum element as `Optional(index)` or
> /// `Optional(nil)` if the sequence has no elements. The uncustomized
> /// version returns `nil`.
> func _customIndexOfMinComparableElement() ->Index??
>
> /// Returns the index of the maximum element as `Optional(index)` or
> /// `Optional(nil)` if the sequence has no elements. The uncustomized
> /// version returns `nil`.
> func _customIndexOfMaxComparableElement() ->Index??
> }
> Minmax Algorithm
>
> The minmax() algorithm finds the minimum and maximum elements of a sequence
> in one pass more efficiently than consecutive calls to min() and max(). This
> optimization comes from iterating over a sequence two elements at a time.
>
> In each iteration, two consecutive elements are compared with each other.
> Only the lesser element could be a minimum for the whole sequence, so it is
> compared with the current minimum, while only the greater element could be a
> maximum, so it is compared with the current maximum. This works out to 3
> comparisons for every 2 elements vs. 2 comparisons for every element when the
> minimum and maximum are found individually.
>
> Impact on existing code
> As new APIs these should have no effect on existing code.
>
> Alternatives considered
> None.
>
>
>
_______________________________________________
swift-evolution mailing list
[email protected]
https://lists.swift.org/mailman/listinfo/swift-evolution
