Gapotchenko.FX.Collections 2024.1.3

Overview

The module was started by borrowing an implementation of ConcurrentHashSet<T> from Mr. Bar Arnon.

Other than that, the module provides polyfills for missing functionality in .NET.

Collections

ConcurrentHashSet<T>

ConcurrentHashSet<T> provided by Gapotchenko.FX.Collections is a thread-safe implementation of HashSet<T>.

AssociativeArray<TKey, TValue>

AssociativeArray<TKey, TValue> provided by Gapotchenko.FX.Collections is a drop-in replacement for Dictionary<TKey, TValue> that can handle null keys.

Dictionary<TKey, TValue> cannot work with null keys and throws ArgumentNullException whenever a null key is encountered. AssociativeArray<TKey, TValue> resolves that by supporting a full space of keys without opinionated exclusions.

Deque<T>

Deque<T> provided by Gapotchenko.FX.Collections is a linear collection that supports element insertion and removal at both ends with O(1) algorithmic complexity.

Deque<T> can be seen as a List<T>, but in contrast to the List<T>, both ends of the collection support efficient addition and removal of elements.

Collection Construction Kits

A concept of a construction kit provided by Gapotchenko.FX.Collections module allows you to quickly and reliably build customized collection primitives.

<details> <summary>More information</summary>

ISet<T> Construction Kit

For example, let's imagine that we need to build a custom implementation of System.Collections.Generic.ISet<T> collection. In order to do that, we need to implement a plethora of methods such as UnionWith, IntersectWith, ExceptWith and others just to begin with. It gets complicated and nuanced quickly, while all we want is to build a simple custom ISet<T> implementation.

This is where the concept of a construction kit starts to shine. In our case, instead of implementing ISet<T> interface directly, we just derive our implementation from the one provided by the corresponding construction kit:

using Gapotchenko.FX.Collections.Generic.Kits;
using Gapotchenko.FX.Linq;
using System.Collections;

class MyBitSet(int capacity) : SetKit<int>
{
    public override bool Contains(int item) => m_Bits[item];

    public override bool Add(int item) => ChangeBit(item, true);

    public override bool Remove(int item) => ChangeBit(item, false);

    bool ChangeBit(int item, bool value)
    {
        if (m_Bits[item] != value)
        {
            m_Bits[item] = value;

            if (value)
                ++m_CachedCount;
            else
                --m_CachedCount;

            return true;
        }
        else
        {
            return false;
        }
    }

    public override void Clear()
    {
        m_Bits.SetAll(false);
        m_CachedCount = 0;
    }

    public override int Count => m_CachedCount ??= this.Stream().Count();

    int? m_CachedCount = 0;

    public override IEnumerator<int> GetEnumerator()
    {
        for (int i = 0, n = m_Bits.Count; i < n; ++i)
            if (m_Bits[i])
                yield return i;
    }

    protected BitArray Bits
    {
        get => m_Bits;
        set { m_Bits = value; m_CachedCount = null; }
    }

    BitArray m_Bits = new(capacity);
}

We implemented just several abstract methods and got a fully functional and compliant ISet<T> collection. All the remaining implementation details are covered by the construction kit our class is derived from.

Mind you, a generic implementation does not mean inefficient. If we have a more optimized way to do some operations, we just override the corresponding methods:

class MyHWAcceleratedBitSet(int capacity) : MyBitSet(capacity)
{
    public override bool Overlaps(IEnumerable<int> other)
    {
        if (other is MyBitSet bitSet)
            return Bits.And(bitSet.Bits).HasAnySet();
        else
            return base.Overlaps(other);
    }

    public override void IntersectWith(IEnumerable<int> other)
    {
        if (other is MyBitSet bitSet)
            Bits = Bits.And(bitSet.Bits);
        else
            base.IntersectWith(other);
    }

    public override void UnionWith(IEnumerable<int> other)
    {
        if (other is MyBitSet bitSet)
            Bits = Bits.Or(bitSet.Bits);
        else
            base.UnionWith(other);
    }

    public override void ExceptWith(IEnumerable<int> other)
    {
        if (other is MyBitSet bitSet)
            Bits = Bits.And(bitSet.Bits.Not());
        else
            base.ExceptWith(other);
    }

    public override void SymmetricExceptWith(IEnumerable<int> other)
    {
        if (other is MyBitSet bitSet)
            Bits = Bits.Xor(bitSet.Bits);
        else
            base.SymmetricExceptWith(other);
    }

    public override bool SetEquals(IEnumerable<int> other)
    {
        if (other is MyBitSet bitSet)
            return bitSet.Bits.Xor(bitSet.Bits).HasAnySet();
        else
            return base.SetEquals(other);
    }
}

Given that BitArray operations are hardware-accelerated in all modern .NET versions, it quickly boils from a generic ISet<T> implementation down to a highly-optimized one, leveraging AVX and SSE vector instructions provided by CPU. What a ride just within a screen of code.

</details>

Polyfills

AddRange<T>(IEnumerable<T>) for Collections

AddRange is a frequently used operation that allows you to add a sequence of elements to the end of a collection. Like this:

using Gapotchenko.FX.Collections.Generic;

var collection = new Collection<int>();
…
collection.AddRange(numbers.Where(x => x % 2 == 0)); // add even numbers

<details> <summary>Other polyfills</summary>

KeyValuePair Polyfill

.NET provides a versatile KeyValuePair<TKey, TValue> struct and suggests a default way for its instantiation:

new KeyValuePair<TKey, TValue>(key, value)

Which is, well, not handy as it often comes to this:

new KeyValuePair<BindingManagerDataErrorEventHandler, ICom2PropertyPageDisplayService>(key, value)

Gapotchenko.FX.Collections provides a better way to instantiate a KeyValuePair<TKey, TValue> struct:

using Gapotchenko.FX.Collections.Generic;

KeyValuePair.Create(key, value)

It leverages the automatic type inference provided by some .NET languages like C#.

Deconstruction

Gapotchenko.FX.Collections module comes with a function for KeyValuePair<TKey, TValue> deconstruction, so you can write this:

using Gapotchenko.FX.Collections.Generic;

void ProcessMap(IDictionary<string, int> map)
{
    foreach (var (key, value) in map)
    {
        …
    }
}

instead of a more verbose variant:

void ProcessMap(IDictionary<string, int> map)
{
    foreach (var i in map)
    {
        var key = i.Key;
        var value = i.Value;
        …
    }
}

A little detail, but sometimes it matters a lot when you are amid the heat of the code.

PriorityQueue Polyfill

PriorityQueue<TElement, TPriority> provided by Gapotchenko.FX.Collections module is an implementation of the prioritized queue available in .NET 6.0+. The polyfill makes it available to all other supported .NET versions.

</details>

Commonly Used Types

• Gapotchenko.FX.Collections.Concurrent.ConcurrentHashSet<T>
• Gapotchenko.FX.Collections.Generic.AssociativeArray<T>

Other Modules

Let's continue with a look at some other modules provided by Gapotchenko.FX:

• Gapotchenko.FX
• Gapotchenko.FX.AppModel.Information
• ➴ Gapotchenko.FX.Collections
• Gapotchenko.FX.Console
• Gapotchenko.FX.Data
• Gapotchenko.FX.Diagnostics
• Gapotchenko.FX.IO
• Gapotchenko.FX.Linq
• Gapotchenko.FX.Math
• Gapotchenko.FX.Memory
• Gapotchenko.FX.Security.Cryptography
• Gapotchenko.FX.Text
• Gapotchenko.FX.Threading
• Gapotchenko.FX.Tuples

Or look at the full list of modules.