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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.