<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">Hi all,<div class=""><br class=""></div><div class="">This is a crack at a proposal to revise the API of the collection partition method, called out as an open issue in the standard library. What's below is a much shorter revision of a prior proposal, focused only on the partition method. I welcome any feedback you might have!</div><div class=""><br class=""></div><div class="">Thanks,</div><div class="">Nate</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">––––</div><div class=""><p style="-webkit-print-color-adjust: exact; margin: 15px 0px; font-family: Helvetica, arial, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);" class="">This proposal revises the signature for the collection partition algorithm. Partitioning is a foundational API for sorting and for searching through sorted collections.</p><ul style="-webkit-print-color-adjust: exact; margin: 15px 0px; padding-left: 30px; font-family: Helvetica, arial, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);" class=""><li style="-webkit-print-color-adjust: exact; margin: 0px;" class="">Swift-evolution thread: <a href="https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160502/016729.html" style="-webkit-print-color-adjust: exact; color: rgb(65, 131, 196); margin-top: 0px;" class="">Feedback from standard library team</a></li><li style="-webkit-print-color-adjust: exact; margin: 0px;" class="">Swift Bug: <a href="https://bugs.swift.org/browse/SR-1965" style="-webkit-print-color-adjust: exact; color: rgb(65, 131, 196); margin-top: 0px;" class="">SR-1965</a></li></ul><h2 id="toc_2" style="-webkit-print-color-adjust: exact; margin: 20px 0px 10px; padding: 0px; -webkit-font-smoothing: antialiased; cursor: text; position: relative; font-size: 24px; border-bottom-width: 1px; border-bottom-style: solid; border-bottom-color: rgb(204, 204, 204); font-family: Helvetica, arial, sans-serif; background-color: rgb(255, 255, 255);" class="">Motivation</h2><p style="-webkit-print-color-adjust: exact; margin: 15px 0px; font-family: Helvetica, arial, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);" class="">Based on feedback during the review of proposal <a href="https://github.com/apple/swift-evolution/blob/master/proposals/0074-binary-search.md" style="-webkit-print-color-adjust: exact; color: rgb(65, 131, 196);" class="">SE-0074, Implementation of Binary Search Functions</a> and the <a href="https://gist.github.com/gribozavr/37e811f12b27c6365fc88e6f9645634d" style="-webkit-print-color-adjust: exact; color: rgb(65, 131, 196);" class="">list of open issues affecting standard library API stability</a>, this is a revised proposal focused only on the existing collection partition method.</p><p style="-webkit-print-color-adjust: exact; margin: 15px 0px; font-family: Helvetica, arial, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);" class="">The standard library's current <code style="-webkit-print-color-adjust: exact; margin: 0px 2px; padding: 0px 5px; white-space: nowrap; border: 1px solid rgb(234, 234, 234); background-color: rgb(248, 248, 248); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;" class="">partition</code> methods, which partition a mutable collection using a binary predicate based on the value of the first element of a collection, are used by the standard library's sorting algorithm but don't offer more general partitioning functionality. A more general partition algorithm using a unary (single-argument) predicate would be more flexible and generally useful.</p><h2 id="toc_3" style="-webkit-print-color-adjust: exact; margin: 20px 0px 10px; padding: 0px; -webkit-font-smoothing: antialiased; cursor: text; position: relative; font-size: 24px; border-bottom-width: 1px; border-bottom-style: solid; border-bottom-color: rgb(204, 204, 204); font-family: Helvetica, arial, sans-serif; background-color: rgb(255, 255, 255);" class="">Proposed solution</h2><p style="-webkit-print-color-adjust: exact; margin: 15px 0px; font-family: Helvetica, arial, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);" class="">The standard library should replace the existing <code style="-webkit-print-color-adjust: exact; margin: 0px 2px; padding: 0px 5px; white-space: nowrap; border: 1px solid rgb(234, 234, 234); background-color: rgb(248, 248, 248); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;" class="">partition</code> methods with a single method taking a unary predicate. This new method, <code style="-webkit-print-color-adjust: exact; margin: 0px 2px; padding: 0px 5px; white-space: nowrap; border: 1px solid rgb(234, 234, 234); background-color: rgb(248, 248, 248); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;" class="">partition(where:)</code>, is a mutating method that accepts a unary predicate. The elements of the collection are rearranged according to the predicate, so that there is a pivot index <code style="-webkit-print-color-adjust: exact; margin: 0px 2px; padding: 0px 5px; white-space: nowrap; border: 1px solid rgb(234, 234, 234); background-color: rgb(248, 248, 248); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;" class="">p</code> where no element before <code style="-webkit-print-color-adjust: exact; margin: 0px 2px; padding: 0px 5px; white-space: nowrap; border: 1px solid rgb(234, 234, 234); background-color: rgb(248, 248, 248); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;" class="">p</code> satisfies the predicate and every element at and after <code style="-webkit-print-color-adjust: exact; margin: 0px 2px; padding: 0px 5px; white-space: nowrap; border: 1px solid rgb(234, 234, 234); background-color: rgb(248, 248, 248); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;" class="">p</code> <em style="-webkit-print-color-adjust: exact;" class="">does</em> satisfy the predicate. </p><div style="-webkit-print-color-adjust: exact; font-family: Helvetica, arial, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);" class=""><pre class=" language-swift" style="-webkit-print-color-adjust: exact; margin-top: 0.5em; margin-bottom: 0.5em; background-color: rgb(245, 242, 240); border: 1px solid rgb(204, 204, 204); font-size: 13px; line-height: 1.5; overflow: auto; padding: 1em; border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px; text-shadow: white 0px 1px; font-family: Consolas, Monaco, 'Andale Mono', 'Ubuntu Mono', monospace; word-spacing: normal; word-break: normal; word-wrap: normal; tab-size: 4; -webkit-hyphens: none;"><code class=" language-swift" style="-webkit-print-color-adjust: exact; margin: 0px; padding: 0px; border: none; border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px; background-image: none; text-shadow: white 0px 1px; font-family: Consolas, Monaco, 'Andale Mono', 'Ubuntu Mono', monospace; word-spacing: normal; word-break: normal; word-wrap: normal; line-height: 1.5; tab-size: 4; -webkit-hyphens: none;"><span class="token keyword" style="-webkit-print-color-adjust: exact; color: rgb(0, 119, 170);">var</span> n <span class="token operator" style="-webkit-print-color-adjust: exact; color: rgb(166, 127, 89); background-color: rgba(255, 255, 255, 0.498039); background-position: initial initial; background-repeat: initial initial;">=</span> <span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">[</span><span class="token number" style="-webkit-print-color-adjust: exact; color: rgb(153, 0, 85);">30</span><span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">,</span> <span class="token number" style="-webkit-print-color-adjust: exact; color: rgb(153, 0, 85);">40</span><span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">,</span> <span class="token number" style="-webkit-print-color-adjust: exact; color: rgb(153, 0, 85);">20</span><span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">,</span> <span class="token number" style="-webkit-print-color-adjust: exact; color: rgb(153, 0, 85);">30</span><span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">,</span> <span class="token number" style="-webkit-print-color-adjust: exact; color: rgb(153, 0, 85);">30</span><span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">,</span> <span class="token number" style="-webkit-print-color-adjust: exact; color: rgb(153, 0, 85);">60</span><span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">,</span> <span class="token number" style="-webkit-print-color-adjust: exact; color: rgb(153, 0, 85);">10</span><span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">]</span>
<span class="token keyword" style="-webkit-print-color-adjust: exact; color: rgb(0, 119, 170);">let</span> p <span class="token operator" style="-webkit-print-color-adjust: exact; color: rgb(166, 127, 89); background-color: rgba(255, 255, 255, 0.498039); background-position: initial initial; background-repeat: initial initial;">=</span> n<span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">.</span><span class="token function" style="-webkit-print-color-adjust: exact; color: rgb(221, 74, 104);">partition</span><span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">(</span><span class="token keyword" style="-webkit-print-color-adjust: exact; color: rgb(0, 119, 170);">where</span><span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">:</span> <span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">{</span> $<span class="token number" style="-webkit-print-color-adjust: exact; color: rgb(153, 0, 85);">0</span> <span class="token operator" style="-webkit-print-color-adjust: exact; color: rgb(166, 127, 89); background-color: rgba(255, 255, 255, 0.498039); background-position: initial initial; background-repeat: initial initial;">></span> <span class="token number" style="-webkit-print-color-adjust: exact; color: rgb(153, 0, 85);">30</span> <span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">}</span><span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">)</span>
<span class="token comment" spellcheck="true" style="-webkit-print-color-adjust: exact; color: rgb(112, 128, 144);">// n == [30, 10, 20, 30, 30, 60, 40]</span>
<span class="token comment" spellcheck="true" style="-webkit-print-color-adjust: exact; color: rgb(112, 128, 144);">// p == 5</span></code></pre></div><p style="-webkit-print-color-adjust: exact; margin: 15px 0px; font-family: Helvetica, arial, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);" class="">After partitioning, the predicate returns <code style="-webkit-print-color-adjust: exact; margin: 0px 2px; padding: 0px 5px; white-space: nowrap; border: 1px solid rgb(234, 234, 234); background-color: rgb(248, 248, 248); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;" class="">false</code> for every element in <code style="-webkit-print-color-adjust: exact; margin: 0px 2px; padding: 0px 5px; white-space: nowrap; border: 1px solid rgb(234, 234, 234); background-color: rgb(248, 248, 248); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;" class="">n.prefix(upTo: p)</code>and <code style="-webkit-print-color-adjust: exact; margin: 0px 2px; padding: 0px 5px; white-space: nowrap; border: 1px solid rgb(234, 234, 234); background-color: rgb(248, 248, 248); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;" class="">true</code> for every element in <code style="-webkit-print-color-adjust: exact; margin: 0px 2px; padding: 0px 5px; white-space: nowrap; border: 1px solid rgb(234, 234, 234); background-color: rgb(248, 248, 248); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;" class="">n.suffix(from: p)</code>.</p><h2 id="toc_4" style="-webkit-print-color-adjust: exact; margin: 20px 0px 10px; padding: 0px; -webkit-font-smoothing: antialiased; cursor: text; position: relative; font-size: 24px; border-bottom-width: 1px; border-bottom-style: solid; border-bottom-color: rgb(204, 204, 204); font-family: Helvetica, arial, sans-serif; background-color: rgb(255, 255, 255);" class="">Detailed design</h2><p style="-webkit-print-color-adjust: exact; margin: 15px 0px; font-family: Helvetica, arial, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);" class=""><code style="-webkit-print-color-adjust: exact; margin: 0px 2px; padding: 0px 5px; white-space: nowrap; border: 1px solid rgb(234, 234, 234); background-color: rgb(248, 248, 248); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;" class="">partition(where:)</code> should be added as a <code style="-webkit-print-color-adjust: exact; margin: 0px 2px; padding: 0px 5px; white-space: nowrap; border: 1px solid rgb(234, 234, 234); background-color: rgb(248, 248, 248); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;" class="">MutableCollection</code> requirement with default implementations for mutable and bidirectional mutable collections. Any mutable collection can be partitioned, but the bidirectional algorithm generally performs far fewer copies. The other two methods can be provided in an extension of the <code style="-webkit-print-color-adjust: exact; margin: 0px 2px; padding: 0px 5px; white-space: nowrap; border: 1px solid rgb(234, 234, 234); background-color: rgb(248, 248, 248); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;" class="">Collection</code> protocol.</p><p style="-webkit-print-color-adjust: exact; margin: 15px 0px; font-family: Helvetica, arial, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);" class="">The proposed APIs are collected here:</p><div style="-webkit-print-color-adjust: exact; font-family: Helvetica, arial, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);" class=""><pre class=" language-swift" style="-webkit-print-color-adjust: exact; margin-top: 0.5em; margin-bottom: 0.5em; background-color: rgb(245, 242, 240); border: 1px solid rgb(204, 204, 204); font-size: 13px; line-height: 1.5; overflow: auto; padding: 1em; border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px; text-shadow: white 0px 1px; font-family: Consolas, Monaco, 'Andale Mono', 'Ubuntu Mono', monospace; word-spacing: normal; word-break: normal; word-wrap: normal; tab-size: 4; -webkit-hyphens: none;"><code class=" language-swift" style="-webkit-print-color-adjust: exact; margin: 0px; padding: 0px; border: none; border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px; background-image: none; text-shadow: white 0px 1px; font-family: Consolas, Monaco, 'Andale Mono', 'Ubuntu Mono', monospace; word-spacing: normal; word-break: normal; word-wrap: normal; line-height: 1.5; tab-size: 4; -webkit-hyphens: none;">protocol <span class="token builtin" style="-webkit-print-color-adjust: exact; color: rgb(102, 153, 0);">MutableCollection</span> <span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">{</span>
<span class="token comment" spellcheck="true" style="-webkit-print-color-adjust: exact; color: rgb(112, 128, 144);">// existing requirements</span>
<span class="token comment" spellcheck="true" style="-webkit-print-color-adjust: exact; color: rgb(112, 128, 144);">/// Reorders the elements of the collection such that all the</span>
<span class="token comment" spellcheck="true" style="-webkit-print-color-adjust: exact; color: rgb(112, 128, 144);">/// elements that match the predicate are ordered after all the</span>
<span class="token comment" spellcheck="true" style="-webkit-print-color-adjust: exact; color: rgb(112, 128, 144);">/// elements that do not match the predicate.</span>
<span class="token comment" spellcheck="true" style="-webkit-print-color-adjust: exact; color: rgb(112, 128, 144);">///</span>
<span class="token comment" spellcheck="true" style="-webkit-print-color-adjust: exact; color: rgb(112, 128, 144);">/// - Returns: The index of the first element in the reordered</span>
<span class="token comment" spellcheck="true" style="-webkit-print-color-adjust: exact; color: rgb(112, 128, 144);">/// collection that matches the predicate.</span>
<span class="token comment" spellcheck="true" style="-webkit-print-color-adjust: exact; color: rgb(112, 128, 144);">/// - Complexity: O(n)</span>
@discardableResult
<span class="token keyword" style="-webkit-print-color-adjust: exact; color: rgb(0, 119, 170);">mutating</span> <span class="token keyword" style="-webkit-print-color-adjust: exact; color: rgb(0, 119, 170);">func</span> <span class="token function" style="-webkit-print-color-adjust: exact; color: rgb(221, 74, 104);">partition</span><span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">(</span>
<span class="token keyword" style="-webkit-print-color-adjust: exact; color: rgb(0, 119, 170);">where</span> predicate<span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">:</span> @noescape <span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">(</span><span class="token builtin" style="-webkit-print-color-adjust: exact; color: rgb(102, 153, 0);">Iterator</span><span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">.</span><span class="token builtin" style="-webkit-print-color-adjust: exact; color: rgb(102, 153, 0);">Element</span><span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">)</span> <span class="token keyword" style="-webkit-print-color-adjust: exact; color: rgb(0, 119, 170);">throws</span><span class="token operator" style="-webkit-print-color-adjust: exact; color: rgb(166, 127, 89); background-color: rgba(255, 255, 255, 0.498039); background-position: initial initial; background-repeat: initial initial;">-</span><span class="token operator" style="-webkit-print-color-adjust: exact; color: rgb(166, 127, 89); background-color: rgba(255, 255, 255, 0.498039); background-position: initial initial; background-repeat: initial initial;">></span> <span class="token builtin" style="-webkit-print-color-adjust: exact; color: rgb(102, 153, 0);">Bool</span>
<span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">)</span> <span class="token keyword" style="-webkit-print-color-adjust: exact; color: rgb(0, 119, 170);">rethrows</span> <span class="token operator" style="-webkit-print-color-adjust: exact; color: rgb(166, 127, 89); background-color: rgba(255, 255, 255, 0.498039); background-position: initial initial; background-repeat: initial initial;">-</span><span class="token operator" style="-webkit-print-color-adjust: exact; color: rgb(166, 127, 89); background-color: rgba(255, 255, 255, 0.498039); background-position: initial initial; background-repeat: initial initial;">></span> <span class="token builtin" style="-webkit-print-color-adjust: exact; color: rgb(102, 153, 0);">Index</span>
<span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">}</span>
<span class="token keyword" style="-webkit-print-color-adjust: exact; color: rgb(0, 119, 170);">extension</span> <span class="token builtin" style="-webkit-print-color-adjust: exact; color: rgb(102, 153, 0);">MutableCollection</span> <span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">{</span>
@discardableResult
<span class="token keyword" style="-webkit-print-color-adjust: exact; color: rgb(0, 119, 170);">mutating</span> <span class="token keyword" style="-webkit-print-color-adjust: exact; color: rgb(0, 119, 170);">func</span> <span class="token function" style="-webkit-print-color-adjust: exact; color: rgb(221, 74, 104);">partition</span><span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">(</span>
<span class="token keyword" style="-webkit-print-color-adjust: exact; color: rgb(0, 119, 170);">where</span> predicate<span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">:</span> @noescape <span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">(</span><span class="token builtin" style="-webkit-print-color-adjust: exact; color: rgb(102, 153, 0);">Iterator</span><span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">.</span><span class="token builtin" style="-webkit-print-color-adjust: exact; color: rgb(102, 153, 0);">Element</span><span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">)</span> <span class="token keyword" style="-webkit-print-color-adjust: exact; color: rgb(0, 119, 170);">throws</span><span class="token operator" style="-webkit-print-color-adjust: exact; color: rgb(166, 127, 89); background-color: rgba(255, 255, 255, 0.498039); background-position: initial initial; background-repeat: initial initial;">-</span><span class="token operator" style="-webkit-print-color-adjust: exact; color: rgb(166, 127, 89); background-color: rgba(255, 255, 255, 0.498039); background-position: initial initial; background-repeat: initial initial;">></span> <span class="token builtin" style="-webkit-print-color-adjust: exact; color: rgb(102, 153, 0);">Bool</span>
<span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">)</span> <span class="token keyword" style="-webkit-print-color-adjust: exact; color: rgb(0, 119, 170);">rethrows</span> <span class="token operator" style="-webkit-print-color-adjust: exact; color: rgb(166, 127, 89); background-color: rgba(255, 255, 255, 0.498039); background-position: initial initial; background-repeat: initial initial;">-</span><span class="token operator" style="-webkit-print-color-adjust: exact; color: rgb(166, 127, 89); background-color: rgba(255, 255, 255, 0.498039); background-position: initial initial; background-repeat: initial initial;">></span> <span class="token builtin" style="-webkit-print-color-adjust: exact; color: rgb(102, 153, 0);">Index</span>
<span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">}</span>
<span class="token keyword" style="-webkit-print-color-adjust: exact; color: rgb(0, 119, 170);">extension</span> <span class="token builtin" style="-webkit-print-color-adjust: exact; color: rgb(102, 153, 0);">MutableCollection</span> <span class="token keyword" style="-webkit-print-color-adjust: exact; color: rgb(0, 119, 170);">where</span> <span class="token keyword" style="-webkit-print-color-adjust: exact; color: rgb(0, 119, 170);">Self</span><span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">:</span> <span class="token builtin" style="-webkit-print-color-adjust: exact; color: rgb(102, 153, 0);">BidirectionalCollection</span> <span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">{</span>
@discardableResult
<span class="token keyword" style="-webkit-print-color-adjust: exact; color: rgb(0, 119, 170);">mutating</span> <span class="token keyword" style="-webkit-print-color-adjust: exact; color: rgb(0, 119, 170);">func</span> <span class="token function" style="-webkit-print-color-adjust: exact; color: rgb(221, 74, 104);">partition</span><span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">(</span>
<span class="token keyword" style="-webkit-print-color-adjust: exact; color: rgb(0, 119, 170);">where</span> predicate<span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">:</span> @noescape <span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">(</span><span class="token builtin" style="-webkit-print-color-adjust: exact; color: rgb(102, 153, 0);">Iterator</span><span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">.</span><span class="token builtin" style="-webkit-print-color-adjust: exact; color: rgb(102, 153, 0);">Element</span><span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">)</span> <span class="token keyword" style="-webkit-print-color-adjust: exact; color: rgb(0, 119, 170);">throws</span><span class="token operator" style="-webkit-print-color-adjust: exact; color: rgb(166, 127, 89); background-color: rgba(255, 255, 255, 0.498039); background-position: initial initial; background-repeat: initial initial;">-</span><span class="token operator" style="-webkit-print-color-adjust: exact; color: rgb(166, 127, 89); background-color: rgba(255, 255, 255, 0.498039); background-position: initial initial; background-repeat: initial initial;">></span> <span class="token builtin" style="-webkit-print-color-adjust: exact; color: rgb(102, 153, 0);">Bool</span>
<span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">)</span> <span class="token keyword" style="-webkit-print-color-adjust: exact; color: rgb(0, 119, 170);">rethrows</span> <span class="token operator" style="-webkit-print-color-adjust: exact; color: rgb(166, 127, 89); background-color: rgba(255, 255, 255, 0.498039); background-position: initial initial; background-repeat: initial initial;">-</span><span class="token operator" style="-webkit-print-color-adjust: exact; color: rgb(166, 127, 89); background-color: rgba(255, 255, 255, 0.498039); background-position: initial initial; background-repeat: initial initial;">></span> <span class="token builtin" style="-webkit-print-color-adjust: exact; color: rgb(102, 153, 0);">Index</span>
<span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">}</span></code></pre></div><p style="-webkit-print-color-adjust: exact; margin: 15px 0px; font-family: Helvetica, arial, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);" class="">A full implementation of the two default implementations can be found <a href="https://gist.github.com/natecook1000/70f36608ecd6236552ce0e9f79b98cff" style="-webkit-print-color-adjust: exact; color: rgb(65, 131, 196);" class="">in this gist</a>.</p><h2 id="toc_5" style="-webkit-print-color-adjust: exact; margin: 20px 0px 10px; padding: 0px; -webkit-font-smoothing: antialiased; cursor: text; position: relative; font-size: 24px; border-bottom-width: 1px; border-bottom-style: solid; border-bottom-color: rgb(204, 204, 204); font-family: Helvetica, arial, sans-serif; background-color: rgb(255, 255, 255);" class="">Impact on existing code</h2><p style="-webkit-print-color-adjust: exact; margin: 15px 0px; font-family: Helvetica, arial, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);" class="">The current sorting algorithms would need to be modified to use the new <code style="-webkit-print-color-adjust: exact; margin: 0px 2px; padding: 0px 5px; white-space: nowrap; border: 1px solid rgb(234, 234, 234); background-color: rgb(248, 248, 248); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;" class="">partition(where:)</code> method. Other uses of the existing <code style="-webkit-print-color-adjust: exact; margin: 0px 2px; padding: 0px 5px; white-space: nowrap; border: 1px solid rgb(234, 234, 234); background-color: rgb(248, 248, 248); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;" class="">partition</code> methods could be flagged or in theory could be replaced programmatically. The replacement code, on a mutable collection <code style="-webkit-print-color-adjust: exact; margin: 0px 2px; padding: 0px 5px; white-space: nowrap; border: 1px solid rgb(234, 234, 234); background-color: rgb(248, 248, 248); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;" class="">c</code>:</p><div style="-webkit-print-color-adjust: exact; font-family: Helvetica, arial, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);" class=""><pre class=" language-swift" style="-webkit-print-color-adjust: exact; margin-top: 0.5em; margin-bottom: 0.5em; background-color: rgb(245, 242, 240); border: 1px solid rgb(204, 204, 204); font-size: 13px; line-height: 1.5; overflow: auto; padding: 1em; border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px; text-shadow: white 0px 1px; font-family: Consolas, Monaco, 'Andale Mono', 'Ubuntu Mono', monospace; word-spacing: normal; word-break: normal; word-wrap: normal; tab-size: 4; -webkit-hyphens: none;"><code class=" language-swift" style="-webkit-print-color-adjust: exact; margin: 0px; padding: 0px; border: none; border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px; background-image: none; text-shadow: white 0px 1px; font-family: Consolas, Monaco, 'Andale Mono', 'Ubuntu Mono', monospace; word-spacing: normal; word-break: normal; word-wrap: normal; line-height: 1.5; tab-size: 4; -webkit-hyphens: none;"><span class="token comment" spellcheck="true" style="-webkit-print-color-adjust: exact; color: rgb(112, 128, 144);">// old</span>
c<span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">.</span><span class="token function" style="-webkit-print-color-adjust: exact; color: rgb(221, 74, 104);">partition</span><span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">(</span><span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">)</span>
<span class="token comment" spellcheck="true" style="-webkit-print-color-adjust: exact; color: rgb(112, 128, 144);">// new</span>
<span class="token keyword" style="-webkit-print-color-adjust: exact; color: rgb(0, 119, 170);">if</span> <span class="token keyword" style="-webkit-print-color-adjust: exact; color: rgb(0, 119, 170);">let</span> <span class="token builtin" style="-webkit-print-color-adjust: exact; color: rgb(102, 153, 0);">first</span> <span class="token operator" style="-webkit-print-color-adjust: exact; color: rgb(166, 127, 89); background-color: rgba(255, 255, 255, 0.498039); background-position: initial initial; background-repeat: initial initial;">=</span> c<span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">.</span><span class="token builtin" style="-webkit-print-color-adjust: exact; color: rgb(102, 153, 0);">first</span> <span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">{</span>
c<span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">.</span><span class="token function" style="-webkit-print-color-adjust: exact; color: rgb(221, 74, 104);">partition</span><span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">(</span><span class="token keyword" style="-webkit-print-color-adjust: exact; color: rgb(0, 119, 170);">where</span><span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">:</span> <span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">{</span> $<span class="token number" style="-webkit-print-color-adjust: exact; color: rgb(153, 0, 85);">0</span> <span class="token operator" style="-webkit-print-color-adjust: exact; color: rgb(166, 127, 89); background-color: rgba(255, 255, 255, 0.498039); background-position: initial initial; background-repeat: initial initial;">>=</span> <span class="token builtin" style="-webkit-print-color-adjust: exact; color: rgb(102, 153, 0);">first</span> <span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">}</span><span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">)</span>
<span class="token punctuation" style="-webkit-print-color-adjust: exact; color: rgb(153, 153, 153);">}</span></code></pre></div><p style="-webkit-print-color-adjust: exact; margin: 15px 0px; font-family: Helvetica, arial, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);" class="">A thorough, though not exhaustive, search of GitHub for the existing <code style="-webkit-print-color-adjust: exact; margin: 0px 2px; padding: 0px 5px; white-space: nowrap; border: 1px solid rgb(234, 234, 234); background-color: rgb(248, 248, 248); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;" class="">partition</code> method found no real evidence of its use. The evident uses of a <code style="-webkit-print-color-adjust: exact; margin: 0px 2px; padding: 0px 5px; white-space: nowrap; border: 1px solid rgb(234, 234, 234); background-color: rgb(248, 248, 248); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;" class="">partition</code> method were mainly either tests from the Swift project or third-party implementations similar to the one proposed.</p><h2 id="toc_6" style="-webkit-print-color-adjust: exact; margin: 20px 0px 10px; padding: 0px; -webkit-font-smoothing: antialiased; cursor: text; position: relative; font-size: 24px; border-bottom-width: 1px; border-bottom-style: solid; border-bottom-color: rgb(204, 204, 204); font-family: Helvetica, arial, sans-serif; background-color: rgb(255, 255, 255);" class="">Alternatives considered</h2><p style="-webkit-print-color-adjust: exact; margin: 15px 0px; font-family: Helvetica, arial, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255);" class="">To more closely match the existing API, the <code style="-webkit-print-color-adjust: exact; margin: 0px 2px; padding: 0px 5px; white-space: nowrap; border: 1px solid rgb(234, 234, 234); background-color: rgb(248, 248, 248); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;" class="">partition(where:)</code> method could be added only as a default implementation for mutable bidirectional collections. This would unnecessarily limit access to the algorithm for mutable forward collections.</p></div></body></html>