1
\$\begingroup\$

According to the .NET documentation, HashSet<T> does not maintain order when enumerated so I implemented my own using F#.

Can anyone help review if this is threadsafe and correct?

open System
open System.Collections
open System.Collections.Generic

type LinkedHashSet<'a when 'a : equality> () =
    let mutable index = 0
    let indexed = SortedDictionary<int, 'a> ()
    let hash = HashSet<'a> ()
    let theLock = obj ()

    interface ICollection<'a> with
        member __.Count = lock theLock (fun () -> hash.Count)
        member __.IsReadOnly = false
        member __.Add e =
            lock theLock (fun () -> 
                if hash.Add e
                then
                    indexed.[index] <- e
                    index <- index + 1
            )            
        member __.Clear () =
            lock theLock (fun () ->
                index <- 0
                indexed.Clear ()
                hash.Clear ()
            )            
        member __.Contains e =
            lock theLock (fun () -> hash.Contains e)
        member __.CopyTo (array, arrayIndex) =
            lock theLock (fun () ->
                let kvps = 
                    Seq.toArray indexed
                let kvpLength = Array.length kvps            
                for i in arrayIndex..kvpLength - 1 do
                    array.[i - arrayIndex] <- kvps.[i].Value
            )            
        member __.GetEnumerator () =
            let values = lock theLock (fun () ->
                indexed
                |> Seq.map (fun kvp -> kvp.Value)
            )
            values.GetEnumerator ()           
        member this.GetEnumerator () : IEnumerator =
            (this :> IEnumerable<'a>).GetEnumerator ()
            :> IEnumerator
        member __.Remove e =
            let matcher (kvp: KeyValuePair<int, 'a>) = kvp.Value = e
            lock theLock (fun () ->
                if hash.Remove e
                then
                    let kvps = indexed :> seq<KeyValuePair<int, 'a>>
                    match Seq.tryFind matcher kvps with
                    | Some x -> indexed.Remove x.Key
                    | None -> false
                else false
            )

Usage (distinctChar takes a string aabbb and returns ab):

let distinctChars (s: string) =
    s.ToCharArray ()
    |> Array.fold (fun (set: ICollection<char>) e -> set.Add e; set) (LinkedHashSet () :> ICollection<char>)
    |> Seq.toArray
    |> String
\$\endgroup\$
  • \$\begingroup\$ Enumeration is not thread-safe. \$\endgroup\$ – Fyodor Soikin Dec 18 '17 at 2:43
  • \$\begingroup\$ I thought it's threadsafe in a way that if the IEnumerable is modified when enumerated, it will throw an exception? \$\endgroup\$ – rexcfnghk Dec 18 '17 at 2:45
  • \$\begingroup\$ That's not "thread-safe". Throwing exceptions during enumeration makes it impossible to use this thing in multiple concurrent computations, which means that it can only be used in single-threaded scenarios, which defeats the idea. \$\endgroup\$ – Fyodor Soikin Dec 18 '17 at 2:50
  • \$\begingroup\$ member this.GetEnumerator () : IEnumerator is infinitely recursive. \$\endgroup\$ – Fyodor Soikin Dec 18 '17 at 2:51
  • \$\begingroup\$ Thanks. Updated this.GetEnumerator () : IEnumerator. \$\endgroup\$ – rexcfnghk Dec 18 '17 at 3:15

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.