open System.Collections.Generic
open Microsoft.FSharp.Collections


[<RequireQualifiedAccess>]
module Folds =

    // These are the fast implementations we actually want to use


    /// Tail-recursive left fold
    let inline foldl (stepfn:'b->'a->'b)(acc:'b)(coll:#seq<'a>) : 'b = 
        use enumer = coll.GetEnumerator()
        let rec loop acc' = 
            match enumer.MoveNext() with
            | false     ->  acc'  
            | true      ->  loop ( stepfn acc' enumer.Current ) 
        loop acc 
    

    let inline foldlpost (stepfn:'b->'a->'b)(postfn:'b->'c)(acc:'b)(coll:#seq<'a>) : 'c = 
        use enumer = coll.GetEnumerator()
        let rec loop acc' = 
            match enumer.MoveNext() with
            | false     ->  postfn acc'  
            | true      ->  loop ( stepfn acc' enumer.Current ) 
        loop acc 
    
//    let inline unfold 
//        (stepfn)(acc)
//        (pred)(mapElm)(inc)(seed) =
//        let rec loop acc' state =
//            match pred state with
//            | false     -> acc'
//            | true      -> loop (stepfn acc' (mapElm state)) (inc state)
//        loop acc seed     

    let inline unfold 
        (stepfn:'c->'b->'c)(acc:'c)
        (pred:'a->bool)(mapElm:'a->'b)(inc:'a->'a)(seed:'a) : 'c =
        let rec loop acc' state =
            match pred state with
            | false     -> acc'
            | true      -> loop (stepfn acc' (mapElm state)) (inc state)
        loop acc seed        
           
    /// Tail-recursive left unfold
    let inline unfoldlsl (pred:'a->bool)(mapElm:'a->'b)(inc:'a->'a)(seed:'a) : 'b list =
        let rec loop acc' state =
            match pred state with
            | false     -> acc'
            | true      -> loop (mapElm state::acc') (inc state)
        loop [] seed 

    let inline unfoldls pred mapElm inc seed = unfoldlsl pred mapElm inc seed |> List.rev


    let inline unfoldpost
        (stepfn:'c->'b->'c) (acc:'c)
        (postfn:'c->'d)
        (pred:'a->bool)(mapElm:'a->'b)(inc:'a->'a)(seed:'a): 'd  =
        let rec loop acc' state =
            match pred state with
            | false     -> postfn acc'
            | true      -> loop(stepfn acc' (mapElm state)) (inc state)
        loop acc seed 




   // let hyloUnfold h f g = hylo h (f ) (unfold g)


   // TODO implement scan


    [<RequireQualifiedAccess>]
    module Left =

        let  map ( f :'a->'b ) ( collection:#seq<'a> ) =   
            foldl ( fun acc elm -> (f elm)::acc) [] collection

        let  filter (pred:'a -> bool) (collection:#seq<'a>) = 
            foldl ( fun acc elm -> if pred elm then elm::acc  else acc ) [] collection        

        let  collect ( f :'a->'b list ) ( collection:#seq<'a> ) =   
            let cons xs x = x::xs
            foldl ( fun acc elm -> foldl cons acc (f elm)) [] collection


        let  take num (collection:#seq<'a>)   = 
            match num with 
            | 0             -> []
            | x when x < 0  -> 
                invalidArg "num" (sprintf "args for take must be postive, value passed in was %d" num )
            | _ ->
            use numer = collection.GetEnumerator()
            let rec loop (acc:'a list) (cnt:int) = 
                match numer.MoveNext(), cnt < num-1 with
                | true, true  ->  loop (numer.Current::acc) (cnt+1) 
                | _           ->  acc
            match numer.MoveNext() with
            | true  -> loop (numer.Current::[]) 0
            | false -> []


        let  takeSafe num (collection:#seq<'a>)   = 
            match num with 
            | x when x <= 0  -> []
            | _ ->
            use numer = collection.GetEnumerator()
            let rec loop (acc:'a list) (cnt:int) = 
                match numer.MoveNext(), cnt < num-1 with
                | true, true  ->  loop (numer.Current::acc) (cnt+1) 
                | _           ->  acc
            match numer.MoveNext() with
            | true  -> loop (numer.Current::[]) 0
            | false -> []



        let  takeWhile pred (collection:#seq<'a>)   = 
            use numer = collection.GetEnumerator()
            let rec loop (acc:'a list) = 
                match numer.MoveNext(), pred numer.Current with
                | true, true  ->  loop (numer.Current::acc) 
                | _           ->  acc
            match numer.MoveNext() with
            | true  -> loop (numer.Current::[]) 
            | false -> []  


        let  skip num (collection:#seq<'a>) =
            use numer = collection.GetEnumerator()
            let rec takeRest (acc:'a list) =
                match numer.MoveNext() with
                | true  ->  takeRest (numer.Current::acc) 
                | false ->  acc
            let rec loop (acc:'a list) (cnt:int) = 
                match numer.MoveNext(), cnt < num-1 with
                | true, true  ->  loop acc (cnt+1) 
                | _           ->  takeRest acc
            match numer.MoveNext() with
            | true  -> loop [] 0
            | false -> [] 


        let  skipWhile pred (collection:#seq<'a>) =
            use numer = collection.GetEnumerator()
            let rec takeRest (acc:'a list) =
                match numer.MoveNext() with
                | true  ->  takeRest (numer.Current::acc) 
                | false ->  acc
            let rec loop (acc:'a list)  = 
                match numer.MoveNext(), pred numer.Current with
                | true, true  ->  loop acc  
                | _           ->  takeRest (numer.Current::acc)
            match numer.MoveNext() with
            | true  -> loop [] 
            | false -> []


        let  indexFrom start (collection:#seq<'a>)   = 
            use numer = collection.GetEnumerator()
            let rec loop (acc:(int*'a)list) (cnt:int) v = 
                match numer.MoveNext() with
                | true  ->  loop ((cnt,v)::acc) (cnt+1) (numer.Current)
                | false ->  (cnt,v)::acc
            match numer.MoveNext() with
            | true  -> loop [] start numer.Current
            | false -> []

        let  index collection =
            indexFrom 0 collection


        let  partitionAll num (collection:#seq<'a>)= 
            use numer = collection.GetEnumerator()
            let rec addUntil cnt (acc:'a list list) (input:'a)  =
                match numer.MoveNext() with
                | false -> 
                    match acc with
                    | []  ->  [input]::[]
                    | ahd::atl ->   
                        match  cnt < num with
                        | true  ->  (input::ahd)::atl
                        | false ->  [input]::(ahd::atl)
                | true when cnt < num -> 
                    match acc with
                    | []        -> addUntil (cnt+1) ([input]::[]) numer.Current
                    | ahd::atl  -> addUntil (cnt+1) ((input::ahd)::atl) numer.Current
                | true -> 
                    match acc with
                    | []  ->  []
                    | ls  ->  addUntil 1 ([input]::ls) numer.Current
            match numer.MoveNext() with
            | true  -> addUntil 0 [] numer.Current
            | false -> []
    

        let  partition pred (collection:#seq<'a>) =
            let sift (accTrue,accFalse) input   =
                match pred input with
                | true  ->  input::accTrue,accFalse
                | false ->  accTrue,input::accFalse    
            foldl sift ([],[]) collection


        let  private unique (exists:HashSet<_>) hashfn acc input =
            match exists.Add (hashfn input) with
            | true   -> input::acc
            | false  -> acc

        let  distinct (collection:#seq<'a>) =
            let exists = HashSet<int>()
            let unique' acc input = unique exists hash acc input
            foldl unique' [] collection


        let  distinctBy (proj:'a->'key) (collection:#seq<'a>) =
            let exists = HashSet<'key>()
            let unique' acc input = unique exists proj acc input
            foldl unique' [] collection


        let  distinctFrom (exists:HashSet<int>) (collection:#seq<'a>)  =
            let unique' acc input = unique exists hash acc input
            foldl unique' [] collection


    // end of module Left

    let  map ( f :'a->'b ) ( collection:#seq<'a> ) =   
        Left.map f collection |> List.rev 


    let  filter (pred:'a -> bool) (collection:#seq<'a>) = 
        Left.filter pred collection |> List.rev 


    let  collect ( f :'a->'b list ) ( collection:#seq<'a> ) =   
        Left.collect f collection |> List.rev 
        

    let take num (collection:#seq<'a>)   = 
        Left.take num collection |> List.rev 


    let takeWhile pred (collection:#seq<'a>)   = 
        Left.takeWhile pred collection |> List.rev 


    let skip num (collection:#seq<'a>)  =
        Left.skip num collection |> List.rev 


    let skipWhile pred (collection:#seq<'a>)  =
        Left.skipWhile pred collection |> List.rev 


    let index  (collection:#seq<'a>)   = 
        Left.index  collection |> List.rev 

    let indexFrom start (collection:#seq<'a>)   = 
        Left.indexFrom start collection |> List.rev 

    let partition pred (collection:#seq<'a>) =
        let accTrue,accFalse = Left.partition pred collection
        accTrue |> List.rev, accFalse |> List.rev 


    let partitionAll num (collection:#seq<'a>)= 
        use numer = collection.GetEnumerator()
        let rec addUntil cnt (acc:'a list list) (input:'a)  =
            match numer.MoveNext() with
            | false -> 
                match acc with
                | []  ->  [input]::[]
                | hd::tl -> 
                    match  cnt < num with
                    | true  ->  (input::hd|>List.rev)::tl
                    | false ->  [input]::((hd|>List.rev)::tl)
            | true when cnt < num -> 
                match acc with
                | []        -> addUntil (cnt+1) ([input]::[]) numer.Current
                | hd::tl  -> addUntil (cnt+1) ((input::hd)::tl) numer.Current
            | true -> 
                match acc with
                | []  ->  []
                | hd::tl  ->  addUntil 1 ([input]::((hd|>List.rev)::tl)) numer.Current
        match numer.MoveNext() with
        | true  -> addUntil 0 [] numer.Current
        | false -> []
        |> List.rev


    let distinct (collection:#seq<'a>) =
        Left.distinct collection |> List.rev


    let distinctBy (proj:'a->'key) (collection:#seq<'a>) =
        Left.distinctBy proj collection |> List.rev


    let distinctFrom (exists:HashSet<int>) (collection:#seq<'a>)  =
        Left.distinctFrom exists collection |> List.rev


    let inline private findWith func acc input =
        match acc with
        | Some x -> Some (func x input)
        | None   -> Some input


    let inline private optLoop func (collection:#seq<'a>) =
        use numer = collection.GetEnumerator()
        let rec loop acc input = 
            match numer.MoveNext() with
            | true  ->  loop (func acc input) (numer.Current)
            | false ->  func acc input
        match numer.MoveNext() with
        | true  -> loop None numer.Current
        | false -> None


    let  minOption (collection:#seq<'a>) =
        optLoop (findWith min) collection


    let maxOption (collection:#seq<'a>) =
        optLoop (findWith max) collection


    let inline sumOption (collection:#seq< ^T> when ^T : (static member (+) : ^T * ^T -> ^T)) =
        optLoop (findWith (+)) collection


    let inline avgOption (collection:#seq<'T> when ^T : (static member (+) : ^T * ^T -> ^T)) : float option =
        if Option.isNone (sumOption collection) then None else
        float (sumOption collection).Value  /  float (Seq.length collection) |> Some