title: In Swift, an efficient function that separates an array into 2 arrays based on a predicate
body: <h3>Note: I'm currently still using Swift 2.2, but open to Swift 3 solutions as well</h3>
  
  <p>I'm looking to create a function that operates very closely to <code>filter</code>, except that it keeps the non-matching results as well, and maintains sort order. For instance, say you wanted to filter out numbers divisible by 3 in an array and still keep the list of numbers that aren't divisible by 3.</p>
  
  <hr>
  
  <h3>Option 1: Using <code>filter</code></h3>
  
  <p>With <code>filter</code>, you only get the list of numbers divisible by 3 and the original list stays unchanged. You can then filter the original list again with the opposite predicate, but this is an unnecessary second pass. The code looks like this:</p>
  
  <pre><code>let numbers = [1,2,3,4,5,6,7,8,9,10]
  let divisibleBy3 = numbers.filter { $0 % 3 == 0 } // [3,6,9]
  let theRest = numbers.filter { $0 % 3 != 0 }      // [1,2,4,5,7,8,10]
  </code></pre>
  
  <p>It's true that this is pretty readable, but the fact that it does 2 passes seems inefficient to me, especially if the predicate were more complicated. That's twice as many checks as are actually needed.</p>
  
  <h3>Option 2: Using custom <code>separate</code> function in <code>Collection</code> extension</h3>
  
  <p>My next attempt was extending <code>Collection</code> and making a function I called <code>separate</code>. This function would take the collection and go through the elements one at a time and add them to either the matching list or the non-matching list. The code looks like this:</p>
  
  <pre><code>extension Collection {
      func separate(predicate: (Generator.Element) -&gt; Bool) -&gt; (matching: [Generator.Element], notMatching: [Generator.Element]) {
          var groups: ([Generator.Element],[Generator.Element]) = ([],[])
          for element in self {
              if predicate(element) {
                  groups.0.append(element)
              } else {
                  groups.1.append(element)
              }
          }
          return groups
      }
  }
  </code></pre>
  
  <p>I can then use the function like this:</p>
  
  <pre><code>let numbers = [1,2,3,4,5,6,7,8,9,10]
  let groups = numbers.separate { $0 % 3 == 0 }
  let matching = groups.matching       // [3,6,9]
  let notMatching = groups.notMatching // [1,2,4,5,7,8,10]
  </code></pre>
  
  <p>This is also pretty clean, but the only thing I don't like is that I'm using a tuple as a return type. Maybe others will disagree, but I'd prefer returning the same type as <code>self</code> for chaining. But technically, you can just grab either <code>.matching</code> or <code>.notMatching</code>, which is the same type as <code>self</code>, and you can chain off of either of them.</p>
  
  <h3>Option 3: Using a custom, mutating <code>removeIf</code> function in <code>Array</code> extension</h3>
  
  <p>My issue with <code>separate</code> returning a tuple led me to try to make a function that would modify <code>self</code> by removing the matches as it found them and adding them to a new list, and returning the matches list at the end. The returned list is your matches, and the array is trimmed of those values. Order is preserved in both arrays. The code looks like this:</p>
  
  <pre><code>extension Array {
      mutating func removeIf(predicate: (Element) -&gt; Bool) -&gt; [Element] {
          var removedCount: Int = 0
          var removed: [Element] = []
  
          for (index,element) in self.enumerated() {
              if predicate(element) {
                  removed.append(self.remove(at: index-removedCount))
                  removedCount += 1
              }
          }
  
          return removed
      }
  }
  </code></pre>
  
  <p>And it is used like this:</p>
  
  <pre><code>var numbers = [1,2,3,4,5,6,7,8,9,10]
  let divisibleBy3 = numbers.removeIf { $0 % 3 == 0 }
  // divisibleBy3: [3,6,9]
  // numbers:      [1,2,4,5,7,8,10]
  </code></pre>
  
  <p>This function had to be implemented in an extension of <code>Array</code>, because the concept of removing an element at a particular index doesn't apply to regular <code>Collections</code> (an <code>Array</code> is defined as <code>public struct Array&lt;Element&gt; : RandomAccessCollection, MutableCollection</code>, and it directly defines the <code>remove(at:)</code> function, rather than getting it from inheritance or a protocol).</p>
  
  <h3>Option 4: Combination of Option 2 and 3</h3>
  
  <p>I'm a big fan of code reuse, and after coming up with Option 3, I realized I could probably reuse the <code>separate</code> function from Option 2. I came up with this:</p>
  
  <pre><code>extension Array {
      mutating func removeIf(predicate: (Element) -&gt; Bool) -&gt; [Element] {
          let groups = self.separate(predicate: predicate)
          self = groups.notMatching
          return groups.matching
      }
  }
  </code></pre>
  
  <p>And it's used just like in Option 3.</p>
  
  <p>I was concerned with performance, so I ran each Option through XCTest's <code>measure</code> with 1000 iterations. These were the results:</p>
  
  <pre><code>Option 1: 9 ms
  Option 2: 7 ms
  Option 3: 10 ms
  Option 4: 8 ms
  </code></pre>
  
  <hr>
  
  <h3>Option 5: Based on negaipro's answer</h3>
  
  <p>I knew about <code>partition</code>, but I wasn't going to consider it because it didn't preserve the sort order. negaipro's answer is essentially <code>partition</code>, but it got me thinking. The idea with <code>partition</code> is to swap elements that match with the pivot point, thus ensuring that everything on one side of the end pivot point will all match the predicate and the other side doesn't. I took that idea and changed the action to "move to the end". So matches are removed from their spot and added to the end.</p>
  
  <pre><code>extension Array {
      mutating func swapIfModified(predicate: (Element) -&gt; Bool) -&gt; Int {
          var matchCount = 0
          var index = 0
          while index &lt; (count-matchCount) {
              if predicate(self[index]) {
                  append(remove(at: index))
                  matchCount += 1
              } else {
                  index += 1
              }
          }
  
          return count-matchCount
      }
  }
  </code></pre>
  
  <p>Under my initial tests using an array with 10 numbers, it was comparable to the other Options. But I was concerned with the performance of the line <code>append(remove(at: index))</code>. So I tried all the Options again with arrays going from 1 to 1000, and this option was definitely the slowest.</p>
  
  <hr>
  
  <h3>Conclusion:</h3>
  
  <p>There isn't a big performance difference between these options. And since Option 4 was faster than Option 3 and reuses the code from Option 2, I'm inclined to throw out Option 3. So I'm leaning towards using plain old <code>filter</code> when I don't care about the unfiltered results (and, likewise, for when I don't care about the filtered results, since it's just using the opposite predicate), and then using either <code>separate</code> or <code>removeIf</code> when I care about keeping both the filtered and unfiltered results.</p>
  
  <h3>Question:</h3>
  
  <p>So, am I missing something built into Swift that does this already? Is there a better way to accomplish this? Is my extension syntax missing anything (anything that could make it apply this concept to more areas, for example)?</p>