filter

filter.fs

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

• 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