Skip to content

Instantly share code, notes, and snippets.

@jackmott jackmott/filter.fs
Last active Aug 18, 2016

Embed
What would you like to do?
filter
let filterNew f (array: _[]) =
checkNonNull "array" array
let mutable i = 0
while i < array.Length && not (f array.[i]) do
i <- i + 1
if i <> array.Length then
let mutable element = array.[i]
let mutable count = 1
let mutable res = Array.zeroCreateUnchecked (((array.Length-i) >>> 2) + 1)
res.[i] <- element
i <- i + 1
while count < res.Length && i < array.Length do
element <- array.[i]
if f element then
res.[count] <- element
count <- count + 1
i <- i + 1
if i < array.Length then
let newRes = Array.zeroCreateUnchecked (res.Length+(array.Length-i))
Array.Copy(res,newRes,res.Length)
res <- newRes
while i < array.Length do
element <- array.[i]
if f element then
res.[count] <- element
count <- count + 1
i <- i + 1
if res.Length <> array.Length then
Array.subUnchecked 0 count res
else
res
else empty
@jackmott

This comment has been minimized.

Copy link
Owner Author

jackmott commented Aug 17, 2016

  • Scan the array to find the first element where the predicate is true
  • If we didn't find any, return empty
  • otherwise, allocate a result array 1/4 the size of the remaining space in array
  • iterate over array until the end, or the result array is full
  • if not done, reallocate result such that it can hold all remaining elements even if all are true
  • iterate until done
  • If nothing got filtered, skip the copy, avoid an allocation
  • Otherwise copy the sub section of the array and return
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.