anchor.diff: -//----------------------------------------------------------------------------
  -// Copyright (c) 2002-2012 Microsoft Corporation.
  -//
  -// This source code is subject to terms and conditions of the Apache License, Version 2.0. A
  -// copy of the license can be found in the License.html file at the root of this distribution.
  -// By using this source code in any fashion, you are agreeing to be bound
  -// by the terms of the Apache License, Version 2.0.
  -//
  -// You must not remove this notice, or any other, from this software.
  -//----------------------------------------------------------------------------
  -
  -// Root of the distribution is at: https://github.com/fsharp/fsharp
  -// Modified Map implementation for FunScript/Fable
  +// Copyright (c) Microsoft Corporation.  All Rights Reserved.  See License.txt in the project root for license information.
   
   module Map
   
  -open System.Collections
   open System.Collections.Generic
   open Fable.Collections
   open Fable.Core
   
  -// [<CompilationRepresentation(CompilationRepresentationFlags.UseNullAsTrueValue)>]
  -// [<NoEquality; NoComparison>]
  -type MapTree<'Key,'Value when 'Key : comparison > =
  -    | MapEmpty
  -    | MapOne of 'Key * 'Value
  -    | MapNode of 'Key * 'Value * MapTree<'Key,'Value> *  MapTree<'Key,'Value> * int
  -    // REVIEW: performance rumour has it that the data held in MapNode and MapOne should be
  -    // exactly one cache line. It is currently ~7 and 4 words respectively.
  +[<NoEquality; NoComparison>]
  +[<AllowNullLiteral>]
  +type MapTree<'Key, 'Value>(k: 'Key, v: 'Value) =
  +    member _.Key = k
  +    member _.Value = v
  +
  +[<NoEquality; NoComparison>]
  +[<Sealed>]
  +[<AllowNullLiteral>]
  +type MapTreeNode<'Key, 'Value>(k:'Key, v:'Value, left:MapTree<'Key, 'Value>, right: MapTree<'Key, 'Value>, h: int) =
  +    inherit MapTree<'Key,'Value>(k, v)
  +
  +    member _.Left = left
  +    member _.Right = right
  +    member _.Height = h
   
   [<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
  -[<RequireQualifiedAccess>]
   module MapTree =
   
  -    let rec sizeAux acc m =
  -        match m with
  -        | MapEmpty -> acc
  -        | MapOne _ -> acc + 1
  -        | MapNode(_,_,l,r,_) -> sizeAux (sizeAux (acc+1) l) r
  +    let empty = null
  +
  +    let inline isEmpty (m:MapTree<'Key, 'Value>) = isNull m
  +
  +    let rec sizeAux acc (m:MapTree<'Key, 'Value>) =
  +        if isEmpty m then
  +            acc
  +        else
  +            match m with
  +            | :? MapTreeNode<'Key, 'Value> as mn -> sizeAux (sizeAux (acc+1) mn.Left) mn.Right
  +            | _ -> acc + 1
   
       let size x = sizeAux 0 x
   
  -    let empty = MapEmpty
  -
  -    let height  = function
  -        | MapEmpty -> 0
  -        | MapOne _ -> 1
  -        | MapNode(_,_,_,_,h) -> h
  -
  -    let isEmpty m =
  -        match m with
  -        | MapEmpty -> true
  -        | _ -> false
  -
  -    let mk l k v r =
  -        match l,r with
  -        | MapEmpty,MapEmpty -> MapOne(k,v)
  -        | _ ->
  -            let hl = height l
  -            let hr = height r
  -            let m = if hl < hr then hr else hl
  -            MapNode(k,v,l,r,m+1)
  -
  -    let rebalance t1 k v t2 =
  +// #if TRACE_SETS_AND_MAPS
  +//     let mutable traceCount = 0
  +//     let mutable numOnes = 0
  +//     let mutable numNodes = 0
  +//     let mutable numAdds = 0
  +//     let mutable numRemoves = 0
  +//     let mutable numLookups = 0
  +//     let mutable numUnions = 0
  +//     let mutable totalSizeOnNodeCreation = 0.0
  +//     let mutable totalSizeOnMapAdd = 0.0
  +//     let mutable totalSizeOnMapLookup = 0.0
  +//     let mutable largestMapSize = 0
  +//     let mutable largestMapStackTrace = Unchecked.defaultof<_>
  +
  +//     let report() =
  +//        traceCount <- traceCount + 1
  +//        if traceCount % 1000000 = 0 then
  +//            System.Console.WriteLine(
  +//                "#MapOne = {0}, #MapNode = {1}, #Add = {2}, #Remove = {3}, #Unions = {4}, #Lookups = {5}, avMapTreeSizeOnNodeCreation = {6}, avMapSizeOnCreation = {7}, avMapSizeOnLookup = {8}",
  +//                numOnes, numNodes, numAdds, numRemoves, numUnions, numLookups,
  +//                (totalSizeOnNodeCreation / float (numNodes + numOnes)), (totalSizeOnMapAdd / float numAdds),
  +//                (totalSizeOnMapLookup / float numLookups))
  +//            System.Console.WriteLine("#largestMapSize = {0}, largestMapStackTrace = {1}", largestMapSize, largestMapStackTrace)
  +
  +//     let MapOne n =
  +//         report()
  +//         numOnes <- numOnes + 1
  +//         totalSizeOnNodeCreation <- totalSizeOnNodeCreation + 1.0
  +//         MapTree n
  +
  +//     let MapNode (x, l, v, r, h) =
  +//         report()
  +//         numNodes <- numNodes + 1
  +//         let n = MapTreeNode (x, l, v, r, h)
  +//         totalSizeOnNodeCreation <- totalSizeOnNodeCreation + float (size n)
  +//         n
  +// #endif
  +
  +    let inline height (m: MapTree<'Key, 'Value>) =
  +        if isEmpty m then 0
  +        else
  +            match m with
  +            | :? MapTreeNode<'Key, 'Value> as mn -> mn.Height
  +            | _ -> 1
  +
  +    [<Literal>]
  +    let tolerance = 2
  +
  +    let mk l k v r : MapTree<'Key, 'Value> =
  +        let hl = height l
  +        let hr = height r
  +        let m = if hl < hr then hr else hl
  +        if m = 0 then // m=0 ~ isEmpty l && isEmpty r
  +            MapTree(k,v)
  +        else
  +            MapTreeNode(k,v,l,r,m+1) :> MapTree<'Key, 'Value>  // new map is higher by 1 than the highest
  +
  +    let inline private asNode(value:MapTree<'Key,'Value>) : MapTreeNode<'Key,'Value> =
  +        value :?> MapTreeNode<'Key,'Value>
  +
  +    let rebalance t1 (k: 'Key) (v: 'Value) t2 : MapTree<'Key, 'Value> =
           let t1h = height t1
           let t2h = height t2
  -        if  t2h > t1h + 2 then (* right is heavier than left *)
  -            match t2 with
  -            | MapNode(t2k,t2v,t2l,t2r,_) ->
  -                (* one of the nodes must have height > height t1 + 1 *)
  -                if height t2l > t1h + 1 then  (* balance left: combination *)
  -                    match t2l with
  -                    | MapNode(t2lk,t2lv,t2ll,t2lr,_) ->
  -                        mk (mk t1 k v t2ll) t2lk t2lv (mk t2lr t2k t2v t2r)
  -                    | _ -> failwith "rebalance"
  -                else (* rotate left *)
  -                    mk (mk t1 k v t2l) t2k t2v t2r
  -            | _ -> failwith "rebalance"
  -        else
  -            if  t1h > t2h + 2 then (* left is heavier than right *)
  -                match t1 with
  -                | MapNode(t1k,t1v,t1l,t1r,_) ->
  -                    (* one of the nodes must have height > height t2 + 1 *)
  -                    if height t1r > t2h + 1 then
  -                        (* balance right: combination *)
  -                        match t1r with
  -                        | MapNode(t1rk,t1rv,t1rl,t1rr,_) ->
  -                            mk (mk t1l t1k t1v t1rl) t1rk t1rv (mk t1rr k v t2)
  -                        | _ -> failwith "re  balance"
  +        if  t2h > t1h + tolerance then (* right is heavier than left *)
  +            let t2' = asNode(t2)
  +            (* one of the nodes must have height > height t1 + 1 *)
  +            if height t2'.Left > t1h + 1 then  (* balance left: combination *)
  +                let t2l = asNode(t2'.Left)
  +                mk (mk t1 k v t2l.Left) t2l.Key t2l.Value (mk t2l.Right t2'.Key t2'.Value t2'.Right)
  +            else (* rotate left *)
  +                mk (mk t1 k v t2'.Left) t2'.Key t2'.Value t2'.Right
  +        else
  +            if  t1h > t2h + tolerance then (* left is heavier than right *)
  +                let t1' = asNode(t1)
  +                (* one of the nodes must have height > height t2 + 1 *)
  +                if height t1'.Right > t2h + 1 then
  +                (* balance right: combination *)
  +                    let t1r = asNode(t1'.Right)
  +                    mk (mk t1'.Left t1'.Key t1'.Value t1r.Left) t1r.Key t1r.Value (mk t1r.Right k v t2)
  +                else
  +                    mk t1'.Left t1'.Key t1'.Value (mk t1'.Right k v t2)
  +            else mk t1 k v t2
  +
  +    let rec add (comparer: IComparer<'Key>) k (v: 'Value) (m: MapTree<'Key, 'Value>) : MapTree<'Key, 'Value> =
  +        if isEmpty m then MapTree(k,v)
  +        else
  +            let c = comparer.Compare(k,m.Key)
  +            match m with
  +            | :? MapTreeNode<'Key, 'Value> as mn ->
  +                if c < 0 then rebalance (add comparer k v mn.Left) mn.Key mn.Value mn.Right
  +                elif c = 0 then MapTreeNode(k,v,mn.Left,mn.Right,mn.Height) :> MapTree<'Key, 'Value>
  +                else rebalance mn.Left mn.Key mn.Value (add comparer k v mn.Right)
  +            | _ ->
  +                if c < 0   then MapTreeNode (k,v,empty,m,2) :> MapTree<'Key, 'Value>
  +                elif c = 0 then MapTree(k,v)
  +                else            MapTreeNode (k,v,m,empty,2) :> MapTree<'Key, 'Value>
  +
  +    let rec tryGetValue (comparer: IComparer<'Key>) k (v: ref<'Value>) (m: MapTree<'Key, 'Value>) =
  +        if isEmpty m then false
  +        else
  +            let c = comparer.Compare(k, m.Key)
  +            if c = 0 then v := m.Value; true
  +            else
  +                match m with
  +                | :? MapTreeNode<'Key, 'Value> as mn ->
  +                    tryGetValue comparer k v (if c < 0 then mn.Left else mn.Right)
  +                | _ -> false
  +
  +    let find (comparer: IComparer<'Key>) k (m: MapTree<'Key, 'Value>) =
  +        let mutable v = Unchecked.defaultof<'Value>
  +        if tryGetValue comparer k (ref v) m then
  +            v
  +        else
  +            raise (KeyNotFoundException())
  +
  +    let tryFind (comparer: IComparer<'Key>) k (m: MapTree<'Key, 'Value>) =
  +        let mutable v = Unchecked.defaultof<'Value>
  +        if tryGetValue comparer k (ref v) m then
  +            Some v
  +        else
  +            None
  +
  +    let partition1 (comparer: IComparer<'Key>) (f: OptimizedClosures.FSharpFunc<_, _, _>) k v (acc1, acc2) =
  +        if f.Invoke (k, v) then (add comparer k v acc1, acc2) else (acc1, add comparer k v acc2)
  +
  +    let rec partitionAux (comparer: IComparer<'Key>) (f: OptimizedClosures.FSharpFunc<_, _, _>) (m: MapTree<'Key, 'Value>) acc =
  +        if isEmpty m then acc
  +        else
  +            match m with
  +            | :? MapTreeNode<'Key, 'Value> as mn ->
  +                let acc = partitionAux comparer f mn.Right acc
  +                let acc = partition1 comparer f mn.Key mn.Value acc
  +                partitionAux comparer f mn.Left acc
  +            | _ -> partition1 comparer f m.Key m.Value acc
  +
  +    let partition (comparer: IComparer<'Key>) f m =
  +        partitionAux comparer (OptimizedClosures.FSharpFunc<_, _, _>.Adapt f) m (empty, empty)
  +
  +    let filter1 (comparer: IComparer<'Key>) (f: OptimizedClosures.FSharpFunc<_, _, _>) k v acc =
  +        if f.Invoke (k, v) then add comparer k v acc else acc
  +
  +    let rec filterAux (comparer: IComparer<'Key>) (f: OptimizedClosures.FSharpFunc<_, _, _>) (m: MapTree<'Key, 'Value>) acc =
  +        if isEmpty m then acc
  +        else
  +            match m with
  +            | :? MapTreeNode<'Key, 'Value> as mn ->
  +                let acc = filterAux comparer f mn.Left acc
  +                let acc = filter1 comparer f mn.Key mn.Value acc
  +                filterAux comparer f mn.Right acc
  +            | _ -> filter1 comparer f m.Key m.Value acc
  +
  +    let filter (comparer: IComparer<'Key>) f m =
  +        filterAux comparer (OptimizedClosures.FSharpFunc<_, _, _>.Adapt f) m empty
  +
  +    let rec spliceOutSuccessor (m: MapTree<'Key, 'Value>) =
  +        if isEmpty m then failwith "internal error: Map.spliceOutSuccessor"
  +        else
  +            match m with
  +            | :? MapTreeNode<'Key, 'Value> as mn ->
  +                if isEmpty mn.Left then mn.Key, mn.Value, mn.Right
  +                else let k3, v3, l' = spliceOutSuccessor mn.Left in k3, v3, mk l' mn.Key mn.Value mn.Right
  +            | _ -> m.Key, m.Value, empty
  +
  +    let rec remove (comparer: IComparer<'Key>) k (m: MapTree<'Key, 'Value>) =
  +        if isEmpty m then empty
  +        else
  +            let c = comparer.Compare(k, m.Key)
  +            match m with
  +            | :? MapTreeNode<'Key, 'Value> as mn ->
  +                if c < 0 then rebalance (remove comparer k mn.Left) mn.Key mn.Value mn.Right
  +                elif c = 0 then
  +                    if isEmpty mn.Left then mn.Right
  +                    elif isEmpty mn.Right then mn.Left
                       else
  -                        mk t1l t1k t1v (mk t1r k v t2)
  -                | _ -> failwith "rebalance"
  -            else mk t1 k v t2
  -
  -    let rec add (comparer: IComparer<'Value>) k v m =
  -        match m with
  -        | MapEmpty -> MapOne(k,v)
  -        | MapOne(k2,_) ->
  -            let c = comparer.Compare(k,k2)
  -            if c < 0   then MapNode (k,v,MapEmpty,m,2)
  -            elif c = 0 then MapOne(k,v)
  -            else            MapNode (k,v,m,MapEmpty,2)
  -        | MapNode(k2,v2,l,r,h) ->
  -            let c = comparer.Compare(k,k2)
  -            if c < 0 then rebalance (add comparer k v l) k2 v2 r
  -            elif c = 0 then MapNode(k,v,l,r,h)
  -            else rebalance l k2 v2 (add comparer k v r)
  -
  -    let rec find (comparer: IComparer<'Value>) k m =
  -        match m with
  -        | MapEmpty -> failwith "key not found"
  -        | MapOne(k2,v2) ->
  -            let c = comparer.Compare(k,k2)
  -            if c = 0 then v2
  -            else failwith "key not found"
  -        | MapNode(k2,v2,l,r,_) ->
  -            let c = comparer.Compare(k,k2)
  -            if c < 0 then find comparer k l
  -            elif c = 0 then v2
  -            else find comparer k r
  -
  -    let rec tryFind (comparer: IComparer<'Value>) k m =
  -        match m with
  -        | MapEmpty -> None
  -        | MapOne(k2,v2) ->
  -            let c = comparer.Compare(k,k2)
  -            if c = 0 then Some v2
  -            else None
  -        | MapNode(k2,v2,l,r,_) ->
  -            let c = comparer.Compare(k,k2)
  -            if c < 0 then tryFind comparer k l
  -            elif c = 0 then Some v2
  -            else tryFind comparer k r
  -
  -    let partition1 (comparer: IComparer<'Value>) f k v (acc1,acc2) =
  -        if f k v then (add comparer k v acc1,acc2) else (acc1,add comparer k v acc2)
  -
  -    let rec partitionAux (comparer: IComparer<'Value>) f s acc =
  -        match s with
  -        | MapEmpty -> acc
  -        | MapOne(k,v) -> partition1 comparer f k v acc
  -        | MapNode(k,v,l,r,_) ->
  -            let acc = partitionAux comparer f r acc
  -            let acc = partition1 comparer f k v acc
  -            partitionAux comparer f l acc
  -
  -    let partition (comparer: IComparer<'Value>) f s = partitionAux comparer f s (empty,empty)
  -
  -    let filter1 (comparer: IComparer<'Value>) f k v acc = if f k v then add comparer k v acc else acc
  -
  -    let rec filterAux (comparer: IComparer<'Value>) f s acc =
  -        match s with
  -        | MapEmpty -> acc
  -        | MapOne(k,v) -> filter1 comparer f k v acc
  -        | MapNode(k,v,l,r,_) ->
  -            let acc = filterAux comparer f l acc
  -            let acc = filter1 comparer f k v acc
  -            filterAux comparer f r acc
  -
  -    let filter (comparer: IComparer<'Value>) f s = filterAux comparer f s empty
  -
  -    let rec spliceOutSuccessor m =
  -        match m with
  -        | MapEmpty -> failwith "internal error: Map.spliceOutSuccessor"
  -        | MapOne(k2,v2) -> k2,v2,MapEmpty
  -        | MapNode(k2,v2,l,r,_) ->
  -            match l with
  -            | MapEmpty -> k2,v2,r
  -            | _ -> let k3,v3,l' = spliceOutSuccessor l in k3,v3,mk l' k2 v2 r
  -
  -    let rec remove (comparer: IComparer<'Value>) k m =
  -        match m with
  -        | MapEmpty -> empty
  -        | MapOne(k2,_) ->
  -            let c = comparer.Compare(k,k2)
  -            if c = 0 then MapEmpty else m
  -        | MapNode(k2,v2,l,r,_) ->
  -            let c = comparer.Compare(k,k2)
  -            if c < 0 then rebalance (remove comparer k l) k2 v2 r
  -            elif c = 0 then
  -                match l,r with
  -                | MapEmpty,_ -> r
  -                | _,MapEmpty -> l
  -                | _ ->
  -                    let sk,sv,r' = spliceOutSuccessor r
  -                    mk l sk sv r'
  -                    else rebalance l k2 v2 (remove comparer k r)
  -
  -    let rec mem (comparer: IComparer<'Value>) k m =
  -        match m with
  -        | MapEmpty -> false
  -        | MapOne(k2,_) -> (comparer.Compare(k,k2) = 0)
  -        | MapNode(k2,_,l,r,_) ->
  -            let c = comparer.Compare(k,k2)
  -            if c < 0 then mem comparer k l
  -            else (c = 0 || mem comparer k r)
  -
  -    let rec iter f m =
  -        match m with
  -        | MapEmpty -> ()
  -        | MapOne(k2,v2) -> f k2 v2
  -        | MapNode(k2,v2,l,r,_) -> iter f l; f k2 v2; iter f r
  -
  -    let rec tryPick f m =
  -        match m with
  -        | MapEmpty -> None
  -        | MapOne(k2,v2) -> f k2 v2
  -        | MapNode(k2,v2,l,r,_) ->
  -            match tryPick f l with
  -            | Some _ as res -> res
  -            | None ->
  -                match f k2 v2 with
  +                        let sk, sv, r' = spliceOutSuccessor mn.Right
  +                        mk mn.Left sk sv r'
  +                else rebalance mn.Left mn.Key mn.Value (remove comparer k mn.Right)
  +            | _ ->
  +                if c = 0 then empty else m
  +
  +    let rec change (comparer: IComparer<'Key>) k (u: 'Value option -> 'Value option) (m: MapTree<'Key, 'Value>) : MapTree<'Key,'Value> =
  +        if isEmpty m then
  +            match u None with
  +                | None -> m
  +                | Some v -> MapTree (k, v)
  +        else
  +            match m with
  +            | :? MapTreeNode<'Key, 'Value> as mn ->
  +                let c = comparer.Compare(k, mn.Key)
  +                if c < 0 then
  +                    rebalance (change comparer k u mn.Left) mn.Key mn.Value mn.Right
  +                elif c = 0 then
  +                    match u (Some mn.Value) with
  +                    | None ->
  +                        if isEmpty mn.Left then mn.Right
  +                        elif isEmpty mn.Right then mn.Left
  +                        else
  +                            let sk, sv, r' = spliceOutSuccessor mn.Right
  +                            mk mn.Left sk sv r'
  +                    | Some v -> MapTreeNode (k, v, mn.Left, mn.Right, mn.Height) :> MapTree<'Key,'Value>
  +                else
  +                    rebalance mn.Left mn.Key mn.Value (change comparer k u mn.Right)
  +            | _ ->
  +                let c = comparer.Compare(k, m.Key)
  +                if c < 0 then
  +                    match u None with
  +                    | None -> m
  +                    | Some v -> MapTreeNode (k, v, empty, m, 2) :> MapTree<'Key,'Value>
  +                elif c = 0 then
  +                    match u (Some m.Value) with
  +                    | None -> empty
  +                    | Some v -> MapTree (k, v)
  +                else
  +                    match u None with
  +                    | None -> m
  +                    | Some v -> MapTreeNode (k, v, m, empty, 2) :> MapTree<'Key,'Value>
  +
  +    let rec mem (comparer: IComparer<'Key>) k (m: MapTree<'Key, 'Value>) =
  +        if isEmpty m then false
  +        else
  +            let c = comparer.Compare(k, m.Key)
  +            match m with
  +            | :? MapTreeNode<'Key, 'Value> as mn ->
  +                if c < 0 then mem comparer k mn.Left
  +                else (c = 0 || mem comparer k mn.Right)
  +            | _ -> c = 0
  +
  +    let rec iterOpt (f: OptimizedClosures.FSharpFunc<_, _, _>) (m: MapTree<'Key, 'Value>) =
  +        if isEmpty m then ()
  +        else
  +            match m with
  +            | :? MapTreeNode<'Key, 'Value> as mn -> iterOpt f mn.Left; f.Invoke (mn.Key, mn.Value); iterOpt f mn.Right
  +            | _ -> f.Invoke (m.Key, m.Value)
  +
  +    let iter f m =
  +        iterOpt (OptimizedClosures.FSharpFunc<_, _, _>.Adapt f) m
  +
  +    let rec tryPickOpt (f: OptimizedClosures.FSharpFunc<_, _, _>) (m: MapTree<'Key, 'Value>) =
  +        if isEmpty m then None
  +        else
  +            match m with
  +            | :? MapTreeNode<'Key, 'Value> as mn ->
  +                match tryPickOpt f mn.Left with
                   | Some _ as res -> res
                   | None ->
  -                    tryPick f r
  -
  -    let rec exists f m =
  -        match m with
  -        | MapEmpty -> false
  -        | MapOne(k2,v2) -> f k2 v2
  -        | MapNode(k2,v2,l,r,_) -> exists f l || f k2 v2 || exists f r
  -
  -    let rec forall f m =
  -        match m with
  -        | MapEmpty -> true
  -        | MapOne(k2,v2) -> f k2 v2
  -        | MapNode(k2,v2,l,r,_) -> forall f l && f k2 v2 && forall f r
  -
  -    let rec map f m =
  -        match m with
  -        | MapEmpty -> empty
  -        | MapOne(k,v) -> MapOne(k,f v)
  -        | MapNode(k,v,l,r,h) ->
  -            let l2 = map f l
  -            let v2 = f v
  -            let r2 = map f r
  -            MapNode(k,v2,l2, r2,h)
  -
  -    let rec mapi f m =
  -        match m with
  -        | MapEmpty -> empty
  -        | MapOne(k,v) -> MapOne(k,f k v)
  -        | MapNode(k,v,l,r,h) ->
  -            let l2 = mapi f l
  -            let v2 = f k v
  -            let r2 = mapi f r
  -            MapNode(k,v2, l2, r2,h)
  -
  -    let rec foldBack f m x =
  -        match m with
  -        | MapEmpty -> x
  -        | MapOne(k,v) -> f k v x
  -        | MapNode(k,v,l,r,_) ->
  -            let x = foldBack f r x
  -            let x = f k v x
  -            foldBack f l x
  -
  -    let rec fold f x m  =
  -        match m with
  -        | MapEmpty -> x
  -        | MapOne(k,v) -> f x k v
  -        | MapNode(k,v,l,r,_) ->
  -            let x = fold f x l
  -            let x = f x k v
  -            fold f x r
  -
  -    let rec foldFromTo (comparer: IComparer<'Value>) lo hi f m x =
  -        match m with
  -        | MapEmpty -> x
  -        | MapOne(k,v) ->
  -            let cLoKey = comparer.Compare(lo,k)
  -            let cKeyHi = comparer.Compare(k,hi)
  -            let x = if cLoKey <= 0 && cKeyHi <= 0 then f k v x else x
  -            x
  -        | MapNode(k,v,l,r,_) ->
  -            let cLoKey = comparer.Compare(lo,k)
  -            let cKeyHi = comparer.Compare(k,hi)
  -            let x = if cLoKey < 0                then foldFromTo comparer lo hi f l x else x
  -            let x = if cLoKey <= 0 && cKeyHi <= 0 then f k v x                     else x
  -            let x = if cKeyHi < 0                then foldFromTo comparer lo hi f r x else x
  -            x
  -
  -    let foldSection (comparer: IComparer<'Value>) lo hi f m x =
  -        if comparer.Compare(lo,hi) = 1 then x else foldFromTo comparer lo hi f m x
  -
  -    let rec loop m acc =
  -        match m with
  -        | MapEmpty -> acc
  -        | MapOne(k,v) -> (k,v)::acc
  -        | MapNode(k,v,l,r,_) -> loop l ((k,v)::loop r acc)
  -
  -    let toList m =
  +                match f.Invoke (mn.Key, mn.Value) with
  +                | Some _ as res -> res
  +                | None ->
  +                tryPickOpt f mn.Right
  +            | _ -> f.Invoke (m.Key, m.Value)
  +
  +    let tryPick f m =
  +        tryPickOpt (OptimizedClosures.FSharpFunc<_, _, _>.Adapt f) m
  +
  +    let rec existsOpt (f: OptimizedClosures.FSharpFunc<_, _, _>) (m: MapTree<'Key, 'Value>) =
  +        if isEmpty m then false
  +        else
  +            match m with
  +            | :? MapTreeNode<'Key, 'Value> as mn -> existsOpt f mn.Left || f.Invoke (mn.Key, mn.Value) || existsOpt f mn.Right
  +            | _ -> f.Invoke (m.Key, m.Value)
  +
  +    let exists f m =
  +        existsOpt (OptimizedClosures.FSharpFunc<_, _, _>.Adapt f) m
  +
  +    let rec forallOpt (f: OptimizedClosures.FSharpFunc<_, _, _>) (m: MapTree<'Key, 'Value>) =
  +        if isEmpty m then true
  +        else
  +            match m with
  +            | :? MapTreeNode<'Key, 'Value> as mn -> forallOpt f mn.Left && f.Invoke (mn.Key, mn.Value) && forallOpt f mn.Right
  +            | _ -> f.Invoke (m.Key, m.Value)
  +
  +
  +    let forall f m =
  +        forallOpt (OptimizedClosures.FSharpFunc<_, _, _>.Adapt f) m
  +
  +    let rec map (f:'Value -> 'Result) (m: MapTree<'Key, 'Value>) : MapTree<'Key, 'Result> =
  +        if isEmpty m then empty
  +        else
  +            match m with
  +            | :? MapTreeNode<'Key, 'Value> as mn ->
  +                let l2 = map f mn.Left
  +                let v2 = f mn.Value
  +                let r2 = map f mn.Right
  +                MapTreeNode (mn.Key, v2, l2, r2, mn.Height) :> MapTree<'Key, 'Result>
  +            | _ -> MapTree (m.Key, f m.Value)
  +
  +    let rec mapiOpt (f: OptimizedClosures.FSharpFunc<'Key, 'Value, 'Result>) (m: MapTree<'Key, 'Value>) =
  +        if isEmpty m then empty
  +        else
  +            match m with
  +            | :? MapTreeNode<'Key, 'Value> as mn ->
  +                let l2 = mapiOpt f mn.Left
  +                let v2 = f.Invoke (mn.Key, mn.Value)
  +                let r2 = mapiOpt f mn.Right
  +                MapTreeNode (mn.Key, v2, l2, r2, mn.Height) :> MapTree<'Key, 'Result>
  +            | _ -> MapTree (m.Key, f.Invoke (m.Key, m.Value))
  +
  +    let mapi f m =
  +        mapiOpt (OptimizedClosures.FSharpFunc<_, _, _>.Adapt f) m
  +
  +    let rec foldBackOpt (f: OptimizedClosures.FSharpFunc<_, _, _, _>) (m: MapTree<'Key, 'Value>) x =
  +        if isEmpty m then x
  +        else
  +            match m with
  +            | :? MapTreeNode<'Key, 'Value> as mn ->
  +                let x = foldBackOpt f mn.Right x
  +                let x = f.Invoke (mn.Key, mn.Value, x)
  +                foldBackOpt f mn.Left x
  +            | _ -> f.Invoke (m.Key, m.Value, x)
  +
  +    let foldBack f m x =
  +        foldBackOpt (OptimizedClosures.FSharpFunc<_, _, _, _>.Adapt f) m x
  +
  +    let rec foldOpt (f: OptimizedClosures.FSharpFunc<_, _, _, _>) x (m: MapTree<'Key, 'Value>) =
  +        if isEmpty m then x
  +        else
  +            match m with
  +            | :? MapTreeNode<'Key, 'Value> as mn ->
  +                let x = foldOpt f x mn.Left
  +                let x = f.Invoke (x, mn.Key, mn.Value)
  +                foldOpt f x mn.Right
  +            | _ -> f.Invoke (x, m.Key, m.Value)
  +
  +    let fold f x m =
  +        foldOpt (OptimizedClosures.FSharpFunc<_, _, _, _>.Adapt f) x m
  +
  +    let foldSectionOpt (comparer: IComparer<'Key>) lo hi (f: OptimizedClosures.FSharpFunc<_, _, _, _>) (m: MapTree<'Key, 'Value>) x =
  +        let rec foldFromTo (f: OptimizedClosures.FSharpFunc<_, _, _, _>) (m: MapTree<'Key, 'Value>) x =
  +            if isEmpty m then x
  +            else
  +                match m with
  +                | :? MapTreeNode<'Key, 'Value> as mn ->
  +                    let cLoKey = comparer.Compare(lo, mn.Key)
  +                    let cKeyHi = comparer.Compare(mn.Key, hi)
  +                    let x = if cLoKey < 0 then foldFromTo f mn.Left x else x
  +                    let x = if cLoKey <= 0 && cKeyHi <= 0 then f.Invoke (mn.Key, mn.Value, x) else x
  +                    let x = if cKeyHi < 0 then foldFromTo f mn.Right x else x
  +                    x
  +                | _ ->
  +                    let cLoKey = comparer.Compare(lo, m.Key)
  +                    let cKeyHi = comparer.Compare(m.Key, hi)
  +                    let x = if cLoKey <= 0 && cKeyHi <= 0 then f.Invoke (m.Key, m.Value, x) else x
  +                    x
  +
  +        if comparer.Compare(lo, hi) = 1 then x else foldFromTo f m x
  +
  +    let foldSection (comparer: IComparer<'Key>) lo hi f m x =
  +        foldSectionOpt comparer lo hi (OptimizedClosures.FSharpFunc<_, _, _, _>.Adapt f) m x
  +
  +    let toList (m: MapTree<'Key, 'Value>) =
  +        let rec loop (m: MapTree<'Key, 'Value>) acc =
  +            if isEmpty m then acc
  +            else
  +                match m with
  +                | :? MapTreeNode<'Key, 'Value> as mn -> loop mn.Left ((mn.Key, mn.Value) :: loop mn.Right acc)
  +                | _ -> (m.Key, m.Value) :: acc
           loop m []
   
  -    let ofList comparer l = Seq.fold (fun acc (k,v) -> add comparer k v acc) empty l
  +    let toArray m =
  +        m |> toList |> Array.ofList
  +
  +    let ofList comparer l =
  +        List.fold (fun acc (k, v) -> add comparer k v acc) empty l
   
       let rec mkFromEnumerator comparer acc (e : IEnumerator<_>) =
           if e.MoveNext() then
  -            let (x,y) = e.Current
  +            let (x, y) = e.Current
               mkFromEnumerator comparer (add comparer x y acc) e
           else acc
   
  -    let ofArray comparer (arr : array<_>) =
  +    let ofArray comparer (arr : array<'Key * 'Value>) =
           let mutable res = empty
  -        for i = 0 to arr.Length - 1 do
  -            let x,y = arr.[i]
  +        for (x, y) in arr do
               res <- add comparer x y res
           res
   
       let ofSeq comparer (c : seq<'Key * 'T>) =
  -    //      match c with
  -    //      | :? array<'Key * 'T> as xs -> ofArray comparer xs
  -    //      | :? list<'Key * 'T> as xs -> ofList comparer xs
  -    //      | _ ->
  -        use ie = c.GetEnumerator()
  -        mkFromEnumerator comparer empty ie
  -
  -
  -    let copyToArray s (arr: _[]) i =
  +        match c with
  +        | :? array<'Key * 'T> as xs -> ofArray comparer xs
  +        | :? list<'Key * 'T> as xs -> ofList comparer xs
  +        | _ ->
  +            use ie = c.GetEnumerator()
  +            mkFromEnumerator comparer empty ie
  +
  +    let copyToArray m (arr: _[]) i =
           let mutable j = i
  -        s |> iter (fun x y -> arr.[j] <- KeyValuePair(x,y); j <- j + 1)
  -
  +        m |> iter (fun x y -> arr.[j] <- KeyValuePair(x, y); j <- j + 1)
   
       /// Imperative left-to-right iterators.
       [<NoEquality; NoComparison>]
  -    type MapIterator<'Key,'Value when 'Key : comparison > =
  -        { /// invariant: always collapseLHS result
  -          mutable stack: MapTree<'Key,'Value> list;
  -          /// true when MoveNext has been called
  -          mutable started : bool }
  +    type MapIterator<'Key, 'Value when 'Key : comparison > =
  +         { /// invariant: always collapseLHS result
  +           mutable stack: MapTree<'Key, 'Value> list
  +
  +           /// true when MoveNext has been called
  +           mutable started : bool }
   
       // collapseLHS:
       // a) Always returns either [] or a list starting with MapOne.
       // b) The "fringe" of the set stack is unchanged.
  -    let rec collapseLHS stack =
  +    let rec collapseLHS (stack:MapTree<'Key, 'Value> list) =
           match stack with
  -        | []                           -> []
  -        | MapEmpty             :: rest -> collapseLHS rest
  -        | MapOne _         :: _ -> stack
  -        | (MapNode(k,v,l,r,_)) :: rest -> collapseLHS (l :: MapOne (k,v) :: r :: rest)
  -
  -    let mkIterator s = { stack = collapseLHS [s]; started = false }
  +        | [] -> []
  +        | m :: rest ->
  +            if isEmpty m then collapseLHS rest
  +            else
  +                match m with
  +                | :? MapTreeNode<'Key, 'Value> as mn -> collapseLHS (mn.Left :: MapTree (mn.Key, mn.Value) :: mn.Right :: rest)
  +                | _ -> stack
  +
  +    let mkIterator m =
  +        { stack = collapseLHS [m]; started = false }
   
       let notStarted() = failwith "enumeration not started"
   
  
positive.code:     let current i =
          if i.started then
              match i.stack with
              | MapOne (k,v) :: _ -> KeyValuePair<_,_>(k,v)
              | []            -> alreadyFinished()
              | _             -> failwith "Please report error: Map iterator, unexpected stack for current"
          else
              notStarted()
  
      let rec moveNext i =
          if i.started then
              match i.stack with
              | MapOne _ :: rest ->
                  i.stack <- collapseLHS rest
                  not i.stack.IsEmpty
              | [] -> false
              | _ -> failwith "Please report error: Map iterator, unexpected stack for moveNext"
          else
              i.started <- true;  (* The first call to MoveNext "starts" the enumeration. *)
              not i.stack.IsEmpty
  
      type mkIEnumerator'<'Key,'Value when 'Key: comparison>(s) =
          let mutable i = mkIterator s
          interface IEnumerator<KeyValuePair<'Key,'Value>> with
              member __.Current = current i
          interface IEnumerator with
              member __.Current = box (current i)
              member __.MoveNext() = moveNext i
              member __.Reset() = i <- mkIterator s
          interface System.IDisposable with
              member __.Dispose() = ()
  
      let mkIEnumerator s = new mkIEnumerator'<_,_>(s) :> _ IEnumerator
  
      let toSeq s =
          let en = mkIEnumerator s
  
negative.code:     interface System.Collections.IEnumerable with
          member __.GetEnumerator() = (MapTree.mkIEnumerator tree :> System.Collections.IEnumerator)
  
      interface System.IComparable with
          member m.CompareTo(obj: obj) =
              match obj with
              | :? Map<'Key, 'Value>  as m2->
                  Seq.compareWith
                     (fun (kvp1 : KeyValuePair<_, _>) (kvp2 : KeyValuePair<_, _>)->
                         let c = comparer.Compare(kvp1.Key, kvp2.Key) in
                         if c <> 0 then c else Unchecked.compare kvp1.Value kvp2.Value)
                     m m2
              | _ ->
                  invalidArg "obj" "not comparable"
  
      interface IMutableMap<'Key,'Value> with
          member this.size = this.Count
          member __.clear() = failwith "Map cannot be mutated"
  