<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=""><br class=""><div><blockquote type="cite" class=""><div class="">On Feb 20, 2017, at 7:38 AM, Ole Begemann <<a href="mailto:ole@oleb.net" class="">ole@oleb.net</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><blockquote type="cite" class=""><div class=""><br class="Apple-interchange-newline">On 17 Feb 2017, at 01:39, Ben Cohen via swift-evolution <<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><p class="" style="box-sizing: border-box; margin-bottom: 16px; color: rgb(51, 51, 51); font-family: -apple-system, BlinkMacSystemFont, 'Segoe UI', Helvetica, Arial, sans-serif, 'Apple Color Emoji', 'Segoe UI Emoji', 'Segoe UI Symbol'; font-size: 14px; background-color: rgb(255, 255, 255); margin-top: 0px !important;">Hi swift-evolution,</p><p class="" style="box-sizing: border-box; margin-bottom: 16px; color: rgb(51, 51, 51); font-family: -apple-system, BlinkMacSystemFont, 'Segoe UI', Helvetica, Arial, sans-serif, 'Apple Color Emoji', 'Segoe UI Emoji', 'Segoe UI Symbol'; font-size: 14px; background-color: rgb(255, 255, 255); margin-top: 0px !important;">Following up on Ted’s post regarding the opening up of stage 2, I’m starting a thread to discuss additive algorithms for <code class="" style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, 'Liberation Mono', Menlo, Courier, monospace; font-size: 11.600000381469727px; padding: 0.2em 0px; margin: 0px; background-color: rgba(0, 0, 0, 0.0392157); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;">Sequence</code> and <code class="" style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, 'Liberation Mono', Menlo, Courier, monospace; font-size: 11.600000381469727px; padding: 0.2em 0px; margin: 0px; background-color: rgba(0, 0, 0, 0.0392157); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;">Collection</code>.</p><p class="" style="box-sizing: border-box; margin-top: 0px; margin-bottom: 16px; color: rgb(51, 51, 51); font-family: -apple-system, BlinkMacSystemFont, 'Segoe UI', Helvetica, Arial, sans-serif, 'Apple Color Emoji', 'Segoe UI Emoji', 'Segoe UI Symbol'; font-size: 14px; background-color: rgb(255, 255, 255);">Here is a list of commonly requested algorithms to operate on <code class="" style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, 'Liberation Mono', Menlo, Courier, monospace; font-size: 11.600000381469727px; padding: 0.2em 0px; margin: 0px; background-color: rgba(0, 0, 0, 0.0392157); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;">Sequence</code> or <code class="" style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, 'Liberation Mono', Menlo, Courier, monospace; font-size: 11.600000381469727px; padding: 0.2em 0px; margin: 0px; background-color: rgba(0, 0, 0, 0.0392157); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;">Collection</code>:</p><ul class="" style="box-sizing: border-box; padding-left: 2em; margin-top: 0px; margin-bottom: 16px; color: rgb(51, 51, 51); font-family: -apple-system, BlinkMacSystemFont, 'Segoe UI', Helvetica, Arial, sans-serif, 'Apple Color Emoji', 'Segoe UI Emoji', 'Segoe UI Symbol'; font-size: 14px; background-color: rgb(255, 255, 255);"><li class="" style="box-sizing: border-box;">In-place transformations:<ul class="" style="box-sizing: border-box; padding-left: 2em; margin-top: 0px; margin-bottom: 0px;"><li class="" style="box-sizing: border-box;">transform elements in a <code class="" style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, 'Liberation Mono', Menlo, Courier, monospace; font-size: 11.600000381469727px; padding: 0.2em 0px; margin: 0px; background-color: rgba(0, 0, 0, 0.0392157); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;">MutableCollection</code> using a closure i.e. in-place <code class="" style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, 'Liberation Mono', Menlo, Courier, monospace; font-size: 11.600000381469727px; padding: 0.2em 0px; margin: 0px; background-color: rgba(0, 0, 0, 0.0392157); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;">map</code></li><li class="" style="box-sizing: border-box; margin-top: 0.25em;"><code class="" style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, 'Liberation Mono', Menlo, Courier, monospace; font-size: 11.600000381469727px; padding: 0.2em 0px; margin: 0px; background-color: rgba(0, 0, 0, 0.0392157); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;">remove(where:)</code> that takes a predicate i.e. in-place <code class="" style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, 'Liberation Mono', Menlo, Courier, monospace; font-size: 11.600000381469727px; padding: 0.2em 0px; margin: 0px; background-color: rgba(0, 0, 0, 0.0392157); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;">filter</code></li><li class="" style="box-sizing: border-box; margin-top: 0.25em;"><code class="" style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, 'Liberation Mono', Menlo, Courier, monospace; font-size: 11.600000381469727px; padding: 0.2em 0px; margin: 0px; background-color: rgba(0, 0, 0, 0.0392157); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;">remove(indices:)</code> that takes a <code class="" style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, 'Liberation Mono', Menlo, Courier, monospace; font-size: 11.600000381469727px; padding: 0.2em 0px; margin: 0px; background-color: rgba(0, 0, 0, 0.0392157); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;">Sequence</code> of <code class="" style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, 'Liberation Mono', Menlo, Courier, monospace; font-size: 11.600000381469727px; padding: 0.2em 0px; margin: 0px; background-color: rgba(0, 0, 0, 0.0392157); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;">Index</code></li></ul></li></ul></div></div></blockquote><div class="">Is it possible to implement this (efficiently) with RangeReplaceableCollection's current feature set?</div></div></div></blockquote><div><br class=""></div><div>In-place, I don’t think so, because of the shuffling-down-being-O(n) problem. </div><div><br class=""></div><div>It is possible with a combo of MutableCollection and RangeReplaceableCollection, because MutableCollection implies constant-time mutation of a single element:</div><div><br class=""></div><div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #0433ff" class="">extension</span><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #3495af" class="">MutableCollection</span><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #0433ff" class="">where</span><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #0433ff" class="">Self</span><span style="font-variant-ligatures: no-common-ligatures" class="">: RangeReplaceableCollection {</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #0433ff" class="">mutating</span><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #0433ff" class="">func</span><span style="font-variant-ligatures: no-common-ligatures" class=""> remove(where predicate: (Iterator.Element) -> </span><span style="font-variant-ligatures: no-common-ligatures; color: #3495af" class="">Bool</span><span style="font-variant-ligatures: no-common-ligatures" class="">) {</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #0433ff" class="">guard</span><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #0433ff" class="">var</span><span style="font-variant-ligatures: no-common-ligatures" class=""> i = </span><span style="font-variant-ligatures: no-common-ligatures; color: #3495af" class="">index</span><span style="font-variant-ligatures: no-common-ligatures" class="">(where: predicate) </span><span style="font-variant-ligatures: no-common-ligatures; color: #0433ff" class="">else</span><span style="font-variant-ligatures: no-common-ligatures" class=""> { </span><span style="font-variant-ligatures: no-common-ligatures; color: #0433ff" class="">return</span><span style="font-variant-ligatures: no-common-ligatures" class=""> }</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #0433ff" class="">var</span><span style="font-variant-ligatures: no-common-ligatures" class=""> j = </span><span style="font-variant-ligatures: no-common-ligatures; color: #3495af" class="">index</span><span style="font-variant-ligatures: no-common-ligatures" class="">(after: i)</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #0433ff" class="">while</span><span style="font-variant-ligatures: no-common-ligatures" class=""> j != </span><span style="font-variant-ligatures: no-common-ligatures; color: #3495af" class="">endIndex</span><span style="font-variant-ligatures: no-common-ligatures" class=""> {</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #0433ff" class="">let</span><span style="font-variant-ligatures: no-common-ligatures" class=""> e = </span><span style="font-variant-ligatures: no-common-ligatures; color: #0433ff" class="">self</span><span style="font-variant-ligatures: no-common-ligatures" class="">[j]</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #0433ff" class="">if</span><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #3495af" class="">!</span><span style="font-variant-ligatures: no-common-ligatures" class="">predicate(e) {</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(0, 143, 0);" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> </span><span style="font-variant-ligatures: no-common-ligatures" class="">// here's where you need MutableCollection...</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #0433ff" class="">self</span><span style="font-variant-ligatures: no-common-ligatures" class="">[i] = e</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #3495af" class="">formIndex</span><span style="font-variant-ligatures: no-common-ligatures" class="">(after: &i)</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> }</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #3495af" class="">formIndex</span><span style="font-variant-ligatures: no-common-ligatures" class="">(after: &j)</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> }</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(0, 143, 0);" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> </span><span style="font-variant-ligatures: no-common-ligatures" class="">// and this is the part you need RRC for...</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(52, 149, 175);" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> </span><span style="font-variant-ligatures: no-common-ligatures" class="">removeSubrange</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">(i..<</span><span style="font-variant-ligatures: no-common-ligatures" class="">endIndex</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">)</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> }</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures" class="">}</span></div><div class=""><span style="font-variant-ligatures: no-common-ligatures" class=""><br class=""></span></div><div class="">But if you tried to implement this with RRC alone, you’d hit the challenge of single-element replacement not necessarily being O(n). String is the poster child for this problem since the graphemes you might be wanting to remove are variable width.</div><div class=""><span style="font-variant-ligatures: no-common-ligatures" class=""><br class=""></span></div><div class=""><span style="font-variant-ligatures: no-common-ligatures" class="">Making this a full-fledged member of one of RangeReplaceableCollection would allow types that can’t offer constant-time single element replacement, but <i class="">can</i> implement an algorithm that slides down values over the top of others efficiently in one pass, to provide an efficient implementation. Additionally, types like Array or String that are backed by contiguous storage might be able to make use of lower-level memory operations. The default</span> implementation could be to rebuild self from scratch using lazy filter, which while sub-optimal can at least be done in linear time.</div></div><br class=""><blockquote type="cite" class=""><div class=""><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><div class=""> Since replaceSubrange(_:with:) potentially invalidates indices, you can't call it repeatedly and expect that the passed-in indices are still valid.</div><div class=""><br class=""></div></div></div></blockquote><blockquote type="cite" class=""><div class=""><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><div class="">I suppose it's possible to create a new empty collection, then iterate over the existing collection's indices and append each element that doesn't match one of the indices to be removed, but that sounds a bit awkward to me. Is there a better solution?</div><br class=""><blockquote type="cite" class=""><div class=""><div class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><ul class="" style="box-sizing: border-box; padding-left: 2em; margin-top: 0px; margin-bottom: 16px; color: rgb(51, 51, 51); font-family: -apple-system, BlinkMacSystemFont, 'Segoe UI', Helvetica, Arial, sans-serif, 'Apple Color Emoji', 'Segoe UI Emoji', 'Segoe UI Symbol'; font-size: 14px; background-color: rgb(255, 255, 255);"><li class="" style="box-sizing: border-box;"><ul class="" style="box-sizing: border-box; padding-left: 2em; margin-top: 0px; margin-bottom: 0px;"><li class="" style="box-sizing: border-box; margin-top: 0.25em;">bulk operations (<code class="" style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, 'Liberation Mono', Menlo, Courier, monospace; font-size: 11.600000381469727px; padding: 0.2em 0px; margin: 0px; background-color: rgba(0, 0, 0, 0.0392157); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;">replace</code>, <code class="" style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, 'Liberation Mono', Menlo, Courier, monospace; font-size: 11.600000381469727px; padding: 0.2em 0px; margin: 0px; background-color: rgba(0, 0, 0, 0.0392157); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;">remove</code>, <code class="" style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, 'Liberation Mono', Menlo, Courier, monospace; font-size: 11.600000381469727px; padding: 0.2em 0px; margin: 0px; background-color: rgba(0, 0, 0, 0.0392157); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;">insert</code>) on <code class="" style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, 'Liberation Mono', Menlo, Courier, monospace; font-size: 11.600000381469727px; padding: 0.2em 0px; margin: 0px; background-color: rgba(0, 0, 0, 0.0392157); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;">RangeReplaceableCollection</code> for a <code class="" style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, 'Liberation Mono', Menlo, Courier, monospace; font-size: 11.600000381469727px; padding: 0.2em 0px; margin: 0px; background-color: rgba(0, 0, 0, 0.0392157); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px;">Sequence</code> of subranges</li></ul></li></ul></div></div></blockquote></div><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">This relates to my question above. Is there a better way to implement this than creating an new empty collection and iterating over the existing elements, replacing/skipping/inserting at the passed-in subranges?</span></div></blockquote></div><br class=""><div class="">In-place operations avoid having to allocate/free a whole new buffer, avoid copying the initial prefix of retained elements unnecessarily (a big deal if you are removing a small proportion of the whole, especially if you sometimes remove none), and also enable customized efficient implementations for specific types. Collections that didn’t implement them could just get a default that builds up from scratch like you describe.</div><div class=""><br class=""></div><div class=""><div class="">If we had multi-range bulk remove, you could also implement remove(where:) using it, at the cost of having to do it in two passes.</div><div class=""><br class=""></div></div></body></html>