eacasanovaspedre / flux.collections Goto Github PK

Create a Set version of Hamt.

• Rename current Hamt map to HamtMap
• Add the set implementation as HamtSet
• Add union, intersect and difference functions

Maybe creating an Enumerator is more efficient. Benchmarking could prove it.

Sometimes it's better to see the Hamt data as a sequence of pairs instead of a sequence of KVEntries

The if conditions are wrong. children is never empty, since it's the array of children when the node is a Branch, it's never empty and I ask if it's empty.
I have to ask if the newBitmap is empty instead.
The same happens for the elif condition. It's length is never 1. I must ask whether the newBitmap contains only one bit on.

| Branch (bitmap, children) ->
    let bitIndex = childBitIndex prefix

    if containsChild bitIndex bitmap then
        let childArrayIndex = childArrayIndex bitIndex bitmap

        match remove eqComparer targetKey targetHash (nextLayerPrefix prefix) (Array.item childArrayIndex children)
            with
        | NotFound -> NotFound
        | Removed child -> Removed(Branch(bitmap, Array.put child childArrayIndex children))
        | NothingLeft ->
            let newBitmap = Bitmap.clearBit bitIndex bitmap

            if Array.isEmpty children then
                NothingLeft
            elif Array.length children = 1 then
                Removed(Array.head children)
            else
                Removed(Branch(newBitmap, Array.remove childArrayIndex children))
    else
        NotFound

Functions to add:

• - ofSeq
• - ofSeqStructural
• - ofSeqWith
• - filter
• - exists
• - fold and foldBack (how much sense would foldBack make for an unordered collection)
• - forall
• - iter
• - map
• - partition
• - pick and tryPick
• - findKey and tryFindKey (I don't plan to do this)
• - change

Functions to optimize:

• - toSeq group of functions (Move to a separate issue #25)

Potentially more functions

Evaluate ,using the Benchmarks, the possibility of storing a comparer, like the dotnet's Dictionary.
Sources:
https://source.dot.net/#q=System.collections.generic.Dictionary
https://youtu.be/cFrUeV9H7OM