Multiset<T> Class

Definition

Namespace

Bodu.Collections.Generic

Assembly

Bodu.Collections.dll

Package

Bodu.Collections 1.0.0

Source

Multiset{T}.ICollection.cs

Represents an unordered collection that tracks the multiplicity (occurrence count) of each element. Unlike HashSet<T>, duplicate elements are permitted; unlike List<T>, element counts are tracked as integers rather than stored as repeated entries.

public sealed class Multiset<T> : ICollection<T>, IReadOnlyCollection<T>, IEnumerable<T>, ICollection, IEnumerable where T : notnull

Type Parameters

T

The type of elements in the multiset. Must not be null.

Inheritance

object

Multiset<T>

Implements

ICollection<T>

IReadOnlyCollection<T>

IEnumerable<T>

ICollection

IEnumerable

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.ReferenceEquals(object, object)

object.ToString()

Extension Methods

ComparableExtensions.AtLeast<T>(T, T, IComparer<T>)

ComparableExtensions.AtMost<T>(T, T, IComparer<T>)

ComparableExtensions.IsEqualTo<T>(T, T, IComparer<T>)

ComparableExtensions.Max<T>(T, T, IComparer<T>)

ComparableExtensions.Min<T>(T, T, IComparer<T>)

Examples

// Letter-frequency histogram.
var histogram = new Multiset<char>();
foreach (char c in "mississippi")
    histogram.Add(c);

Console.WriteLine(histogram.Count);         // 11 - total occurrences
Console.WriteLine(histogram.DistinctCount); // 4  - distinct letters
Console.WriteLine(histogram["s"[0]]);       // 4  - count for 's'

foreach (KeyValuePair<char, int> kv in histogram.Frequencies())
    Console.WriteLine($"{kv.Key}: {kv.Value}");

// Multiset algebra - combine two histograms without mutating either operand.
var other = new Multiset<char> { 'i', 'i', 's' };
Multiset<char> combined = histogram.Sum(other);

Remarks

A Multiset<T> is backed by a Dictionary<TKey, TValue> that maps each distinct element to its occurrence count. Add, remove, and lookup operations are O(1) on average, making this type well suited for frequency analysis, histogram construction, vote counting, and duplicate-aware set arithmetic.

The Count property returns the total element count including multiplicity. A multiset containing "a" twice and "b" once has a Count of 3 and a DistinctCount of 2. Enumerating the multiset yields each element as many times as it appears; use Distinct() to iterate over each distinct element once, or Frequencies() to obtain element-count pairs.

Set-theoretic operations (Union(Multiset<T>), Intersect(Multiset<T>), Except(Multiset<T>), Sum(Multiset<T>)) return new Multiset<T> instances and do not mutate either operand. The semantics follow multiset algebra:

• Union(Multiset<T>) - each element appears max(a, b) times.
• Intersect(Multiset<T>) - each element appears min(a, b) times; elements absent from either operand are omitted.
• Except(Multiset<T>) - each element appears max(0, a − b) times; elements whose count reaches zero are omitted.
• Sum(Multiset<T>) - each element appears a + b times.

Set operations produce correct results only when both operands use equivalent equality comparers. The result uses this instance's comparer.

Multiset<T> is not thread-safe. Concurrent reads and writes require external synchronization.

Constructors

Multiset()

Initializes a new instance of the Multiset<T> class that is empty and uses the default equality comparer.

public Multiset()

Multiset(IEnumerable<T>)

Initializes a new instance of the Multiset<T> class that contains elements copied from the specified collection and uses the default equality comparer.

public Multiset(IEnumerable<T> collection)

Parameters

collection IEnumerable<T>

The collection from which elements are copied. Must not be null.

Exceptions

ArgumentNullException

collection is null.

Multiset(IEnumerable<T>, IEqualityComparer<T>?)

Initializes a new instance of the Multiset<T> class that contains elements copied from the specified collection and uses the specified equality comparer.

public Multiset(IEnumerable<T> collection, IEqualityComparer<T>? comparer)

Parameters

collection IEnumerable<T>

The collection from which elements are copied. Must not be null.

comparer IEqualityComparer<T>

The equality comparer used to determine element equality. If null, the default equality comparer for T is used.

Exceptions

ArgumentNullException

collection is null.

Multiset(IEqualityComparer<T>?)

Initializes a new instance of the Multiset<T> class that is empty and uses the specified equality comparer.

public Multiset(IEqualityComparer<T>? comparer)

Parameters

comparer IEqualityComparer<T>

The equality comparer used to determine element equality. If null, the default equality comparer for T is used.

Properties

Comparer

Gets the equality comparer used to determine equality of elements in this Multiset<T>.

public IEqualityComparer<T> Comparer { get; }

Property Value

IEqualityComparer<T>

The IEqualityComparer<T> instance used to compare elements.

Count

Gets the total number of elements in the Multiset<T>, counting each duplicate occurrence separately.

public int Count { get; }

Property Value

int

The total element count including multiplicity. For the count of distinct elements, use DistinctCount.

DistinctCount

Gets the number of distinct elements in the Multiset<T>, regardless of their individual occurrence counts.

public int DistinctCount { get; }

Property Value

int

The number of unique elements. A multiset containing "a" three times and "b" once has a DistinctCount of 2 and a Count of 4.

Methods

Add(T)

Adds one occurrence of item to the Multiset<T>.

public void Add(T item)

Parameters

item T

The element to add.

Exceptions

OverflowException

The element's occurrence count or the total Count is already MaxValue. The multiset is unchanged when this exception is thrown.

Add(T, int)

Adds count occurrences of item to the Multiset<T>.

public void Add(T item, int count)

Parameters

item T

The element to add.

count int

The number of occurrences to add. Must be greater than zero.

Exceptions

ArgumentOutOfRangeException

count is less than or equal to zero.

OverflowException

Adding count would raise the element's occurrence count or the total Count above MaxValue. The multiset is unchanged when this exception is thrown.

Clear()

Removes all elements from the Multiset<T>.

public void Clear()

Contains(T)

Determines whether the Multiset<T> contains at least one occurrence of item.

public bool Contains(T item)

Parameters

item T

The element to locate.

Returns

bool

true if item occurs one or more times in the multiset; otherwise, false.

CopyTo(T[], int)

Copies all elements of the Multiset<T> to a one-dimensional array, starting at the specified array index. Each element is copied as many times as its occurrence count.

public void CopyTo(T[] array, int arrayIndex)

Parameters

array T[]

The destination array. Must not be null.

arrayIndex int

The zero-based starting index in array.

Exceptions

ArgumentNullException

array is null.

ArgumentOutOfRangeException

arrayIndex is less than zero.

ArgumentException

The number of elements in the multiset exceeds the available space from arrayIndex to the end of array.

CountOf(T)

Returns the number of times item appears in the Multiset<T>.

public int CountOf(T item)

Parameters

item T

The element whose occurrence count is to be returned.

Returns

int

The number of times item appears in the multiset, or 0 if the element is absent.

Distinct()

Returns an enumerable sequence that yields each distinct element in the Multiset<T> exactly once, regardless of its occurrence count.

public IEnumerable<T> Distinct()

Returns

IEnumerable<T>

An IEnumerable<T> that yields each distinct element once. The order of elements is not guaranteed.

Remarks

This method enumerates only the distinct elements in O(DistinctCount) time, avoiding the O( Count) cost of iterating the full multiset then de-duplicating. The sequence is invalidated by any structural modification; iterating after a modification throws InvalidOperationException.

Exceptions

InvalidOperationException

The multiset was modified after enumeration began.

Except(Multiset<T>)

Returns a new Multiset<T> containing the multiset difference of this instance minus other. Each element appears max(0, CountOf(x) − other.CountOf(x)) times; elements whose resulting count is zero are omitted.

public Multiset<T> Except(Multiset<T> other)

Parameters

other Multiset<T>

The multiset to subtract. Must not be null.

Returns

Multiset<T>

A new Multiset<T> using this instance's comparer in which each element x has count max(0, CountOf(x) − other.CountOf(x)).

Exceptions

ArgumentNullException

other is null.

Frequencies()

Returns an enumerable sequence of element-count pairs for each distinct element in the Multiset<T>.

public IEnumerable<KeyValuePair<T, int>> Frequencies()

Returns

IEnumerable<KeyValuePair<T, int>>

An IEnumerable<T> of KeyValuePair<TKey, TValue> where each key is a distinct element and each value is that element's occurrence count. The order of pairs is not guaranteed.

Remarks

The sequence is invalidated by any structural modification; iterating after a modification throws InvalidOperationException.

Exceptions

InvalidOperationException

The multiset was modified after enumeration began.

GetEnumerator()

Returns an enumerator that iterates all elements in the Multiset<T>, yielding each element as many times as its occurrence count.

public Multiset<T>.Enumerator GetEnumerator()

Returns

Multiset<T>.Enumerator

An Multiset<T>.Enumerator for the multiset.

Remarks

The enumerator captures a structural-version token at creation. Any subsequent structural modification - including Add(T), Remove(T), RemoveAll(T), and Clear() - invalidates the enumerator. The next call to MoveNext() or Reset() throws InvalidOperationException.

Intersect(Multiset<T>)

Returns a new Multiset<T> containing the multiset intersection of this instance and other. Each element appears as many times as the minimum of its counts in both operands; elements absent from either operand are omitted.

public Multiset<T> Intersect(Multiset<T> other)

Parameters

other Multiset<T>

The multiset to compute the intersection with. Must not be null.

Returns

Multiset<T>

A new Multiset<T> using this instance's comparer in which each element x has count min(CountOf(x), other.CountOf(x)), with elements at zero count omitted.

Exceptions

ArgumentNullException

other is null.

Remove(T)

Removes one occurrence of item from the Multiset<T>.

public bool Remove(T item)

Parameters

item T

The element to remove one occurrence of.

Returns

bool

true if an occurrence of item was found and removed; false if the element does not appear in the multiset.

RemoveAll(T)

Removes all occurrences of item from the Multiset<T>.

public bool RemoveAll(T item)

Parameters

item T

The element whose occurrences are to be removed.

Returns

bool

true if one or more occurrences of item were removed; false if the element does not appear in the multiset.

Sum(Multiset<T>)

Returns a new Multiset<T> containing the multiset sum of this instance and other. Each element appears CountOf(x) + other.CountOf(x) times.

public Multiset<T> Sum(Multiset<T> other)

Parameters

other Multiset<T>

The multiset to sum with. Must not be null.

Returns

Multiset<T>

A new Multiset<T> using this instance's comparer in which each element x has count CountOf(x) + other.CountOf(x).

Exceptions

ArgumentNullException

other is null.

OverflowException

An element's combined occurrence count, or the total element count of the sum, would exceed MaxValue.

Union(Multiset<T>)

Returns a new Multiset<T> containing the multiset union of this instance and other. Each element appears as many times as the maximum of its counts in either operand.

public Multiset<T> Union(Multiset<T> other)

Parameters

other Multiset<T>

The multiset to compute the union with. Must not be null.

Returns

Multiset<T>

A new Multiset<T> using this instance's comparer in which each element x has count max(CountOf(x), other.CountOf(x)).

Exceptions

ArgumentNullException

other is null.

OverflowException

The total element count of the union would exceed MaxValue.

Explicit Interface Implementations

ICollection<T>.IsReadOnly

Gets a value indicating whether the Multiset<T> is read-only.

bool ICollection<T>.IsReadOnly { get; }

Returns

bool

Always false; Multiset<T> is always mutable.

IEnumerable<T>.GetEnumerator()

Returns an enumerator that iterates through the collection.

IEnumerator<T> IEnumerable<T>.GetEnumerator()

Returns

IEnumerator<T>

An enumerator that can be used to iterate through the collection.

ICollection.CopyTo(Array, int)

Copies all elements of the Multiset<T> to a one-dimensional Array, starting at the specified index. Each element is copied as many times as its occurrence count.

void ICollection.CopyTo(Array array, int index)

Parameters

array Array

The destination array. Must be a single-dimensional, zero-based array of a compatible type.

index int

The zero-based starting index in array.

Exceptions

ArgumentNullException

array is null.

ArgumentOutOfRangeException

index is less than zero.

ArgumentException

array is multidimensional, not zero-based, or has an incompatible element type; or the number of elements in the multiset exceeds the available space from index to the end of array. When thrown for an incompatible element type, array is left unmodified (no elements are written).

ICollection.IsSynchronized

Gets a value indicating whether access to the Multiset<T> is synchronized (thread-safe). Always returns false; Multiset<T> is not thread-safe.

bool ICollection.IsSynchronized { get; }

Returns

bool

Always false.

Remarks

External synchronization is the caller's responsibility.

ICollection.SyncRoot

Gets a lazily-initialized object that can be used to synchronize access to the Multiset<T>.

object ICollection.SyncRoot { get; }

Returns

object

A non-null object suitable as a Monitor target.

IEnumerable.GetEnumerator()

Returns an enumerator that iterates through a collection.

IEnumerator IEnumerable.GetEnumerator()

Returns

IEnumerator

An IEnumerator object that can be used to iterate through the collection.

Applies to

Product	Versions
.NET	8, 10