Here’s an example implementation of a CountingSet. This one also supports negatives and empty counts (configurable). Hasn’t been tested much, but maybe it’ll help you come up with something simpler.
using System;
using System.Collections;
using System.Collections.Generic;
namespace SpecialCollections.Sets {
/// <summary>
/// A set that copes with repeating keys/elements by counting the repeats.
/// In practical terms, each key has an associated count (int). Optionally,
/// zero or negative counts can be prevented from being stored (i.e.
/// removing the last element would remove the key altogether, instead of
/// simply recording a 0.)
/// </summary>
/// <typeparam name="T"></typeparam>
public class CountingSet<T> : IEnumerable<KeyValuePair<T, int>> {
Dictionary<T, int> _dict = new Dictionary<T, int>();
/// <summary />
public CountingSet() : this(false, false) {}
/// <summary />
/// <param name="keepNegativeCount">If set to false, all keys with counts less than 0 will be removed.</param>
/// <param name="keepZeroCount">If set to false, all keys with counts of 0 will be removed.</param>
public CountingSet(bool keepNegativeCount, bool keepZeroCount) {
KeepNegativeCount = keepNegativeCount;
KeepZeroCount = keepZeroCount;
}
/// <summary />
public CountingSet(IEnumerable<T> collection) : this(collection, false, false) {}
/// <summary />
/// <param name="keepNegativeCount">If set to false, all keys with counts less than 0 will be removed.</param>
/// <param name="keepZeroCount">If set to false, all keys with counts of 0 will be removed.</param>
public CountingSet(IEnumerable<T> collection, bool keepNegativeCount, bool keepZeroCount) : this(keepNegativeCount, keepZeroCount) {
foreach(var item in collection) AddItem(item);
}
/// <summary />
public CountingSet(HashSet<T> set) : this(set, false, false) {}
/// <summary />
/// <param name="keepNegativeCount">If set to false, all keys with counts less than 0 will be removed.</param>
/// <param name="keepZeroCount">If set to false, all keys with counts of 0 will be removed.</param>
public CountingSet(HashSet<T> set, bool keepNegativeCount, bool keepZeroCount) : this(keepNegativeCount, keepZeroCount) {
foreach(var item in set) AddItem(item);
}
/// <summary />
public CountingSet(CountingSet<T> set) : this(set, false, false) {}
/// <summary />
/// <param name="keepNegativeCount">If set to false, all keys with counts less than 0 will be removed.</param>
/// <param name="keepZeroCount">If set to false, all keys with counts of 0 will be removed.</param>
public CountingSet(CountingSet<T> set, bool keepNegativeCount, bool keepZeroCount) : this(keepNegativeCount, keepZeroCount) {
foreach(var item in set) Add(item.Key, item.Value);
}
static public CountingSet<T> FromDictionary(IDictionary<T, int> dict, bool keepNegativeCount, bool keepZeroCount) {
if(dict == null) throw new ArgumentNullException(nameof(dict));
var cset = new CountingSet<T>(keepNegativeCount, keepZeroCount);
foreach(var item in dict) cset.Add(item.Key, item.Value);
return cset;
}
// ----------------------------------------------------------------------------------
/// <summary>
/// Read-only property. If set to true, negative counts will be preserved.
/// </summary>
public bool KeepNegativeCount { get; } = false;
/// <summary>
/// Read-only property. If set to true, zero counts will be preserved.
/// </summary>
public bool KeepZeroCount { get; } = false;
/// <summary>
/// Total count of all keys (each counts as 1; cheap).
/// </summary>
public int KeyCount => _dict.Count;
/// <summary>
/// Count of key repeats.
/// </summary>
public int CountOf(T item) => Contains(item)? _dict[item] : throw new KeyNotFoundException();
/// <summary>
/// True count of all keys (expensive).
/// </summary>
public int TotalCount { get {
int total = 0;
foreach(var item in _dict) total += item.Value;
return total;
} }
// ----------------------------------------------------------------------------------
public Dictionary<T, int>.KeyCollection Keys => _dict.Keys;
public Dictionary<T, int>.ValueCollection Counts => _dict.Values;
// ----------------------------------------------------------------------------------
/// <summary>
/// Registers key once or in multiples. Negative values will Remove instead.
/// </summary>
/// <returns>Returns true if successful, false otherwise.</returns>
public bool Add(T item, int count = 1) {
if(count == 0) return false;
if(count < 0) return Remove(item, -count);
bool existed = true;
if(!_dict.TryGetValue(item, out int storedCount)) {
existed = false;
storedCount = 0;
}
assignAccordingToFlags(item, existed, storedCount + count);
return true;
}
/// <summary>
/// Unregisters key once or in multiples. Negative values will Add instead.
/// </summary>
/// <returns>Returns true if successful, false otherwise.</returns>
public bool Remove(T item, int count = 1) {
if(count == 0) return false;
if(count < 0) return Add(item, -count);
bool existed = true;
if(!_dict.TryGetValue(item, out int storedCount)) {
existed = false;
storedCount = 0;
}
assignAccordingToFlags(item, existed, storedCount - count);
return true;
}
// ----------------------------------------------------------------------------------
public bool Contains(T item) => _dict.ContainsKey(item);
// ----------------------------------------------------------------------------------
/// <summary>
/// Adds the specified key with a count of 0, if it didn't already exist.
/// </summary>
/// <returns>Returns true if successful, false otherwise.</returns>
public bool AddItem(T item) {
if(!Contains(item) && KeepZeroCount) {
_dict.Add(item, 0);
return true;
}
return false;
}
/// <summary>
/// Removes the specified key completely, regardless of its count value.
/// </summary>
/// <returns>Returns true if successful, false otherwise.</returns>
public bool RemoveItem(T item) => _dict.Remove(item);
/// <summary>
/// Clears the set of all items.
/// </summary>
public void Clear() => _dict.Clear();
// ----------------------------------------------------------------------------------
void assignAccordingToFlags(T item, bool itemExists, int count) {
bool shouldRemoveItem = checkZeroOrNegative(count, !KeepNegativeCount, !KeepZeroCount);
if(shouldRemoveItem) {
if(itemExists) RemoveItem(item);
return;
}
_dict[item] = count;
}
bool checkZeroOrNegative(int count, bool isNegative = true, bool isZero = true)
=> (isZero && count == 0) || (isNegative && count < 0);
// ----------------------------------------------------------------------------------
/// <summary>
/// Removes all keys that meet the set criteria.
/// </summary>
public void Flush(bool flushNegativeCounts = true, bool flushZeroCounts = true)
=> flush_internal(flushNegativeCounts, flushZeroCounts, false);
/// <summary>
/// Set all key counts to 1 (if positive), -1 (if negative), 0 otherwise.
/// </summary>
public void Normalize() => flush_internal(false, false, true);
public void FlushAndNormalize(bool flushNegativeCounts = true, bool flushZeroCounts = true)
=> flush_internal(flushNegativeCounts, flushZeroCounts, true);
void flush_internal(bool fneg, bool fzero, bool norm) {
var selected = new HashSet<T>();
HashSet<T> toFlush = null;
if(fneg || fzero) toFlush = new HashSet<T>();
foreach(var key in _dict.Keys) {
int count = _dict[key];
if(checkZeroOrNegative(count, fneg, fzero)) { toFlush.Add(key); selected.Add(key); }
else if(!checkZeroOrNegative(count, false, true)) selected.Add(key); // add only non-zero counts
}
foreach(var key in selected) {
if(toFlush != null && toFlush.Contains(key)) RemoveItem(key);
else if(norm) _dict[key] = (_dict[key] < 0)? -1 : 1;
}
}
// ----------------------------------------------------------------------------------
public IEnumerator<KeyValuePair<T, int>> GetEnumerator() => _dict.GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
// ----------------------------------------------------------------------------------
/// <summary>
/// Returns true if the two collections are equal, element-wise.
/// </summary>
public bool SetEquals(IEnumerable<T> other) {
if(other == null) return false;
var count = 0;
foreach(var key in other)
if(Contains(key) && ++count >= KeyCount)
return count == KeyCount;
return false;
}
/// <summary>
/// Returns true if the two sets are equal, element-wise.
/// </summary>
public bool SetEquals(HashSet<T> other) {
if(other == null) return false;
if(other.Count == 0) return other.Count == KeyCount;
if(other.Count != KeyCount) return false;
var count = 0;
foreach(var key in _dict.Keys)
if(other.Contains(key) && ++count >= KeyCount)
return count == KeyCount;
return false;
}
/// <summary>
/// Returns true if the two sets are equal, element-wise.
/// Doesn't take counts into consideration, only keys.
/// </summary>
public bool SetEquals(CountingSet<T> other) {
if(other == null) return false;
if(other.KeyCount == 0) return other.KeyCount == KeyCount;
if(other.KeyCount != KeyCount) return false;
var count = 0;
foreach(var key in _dict.Keys)
if(other.Contains(key) && ++count >= KeyCount)
return count == KeyCount;
return false;
}
/// <summary>
/// Returns true if the two collections share at least one element.
/// </summary>
public bool SetOverlaps(IEnumerable<T> other) {
if(other == null) return false;
foreach(var key in other)
if(Contains(key)) return true;
return false;
}
/// <summary>
/// Returns true if the two sets share at least one element.
/// </summary>
public bool SetOverlaps(HashSet<T> other) {
if(other == null) return false;
foreach(var key in _dict.Keys)
if(other.Contains(key)) return true;
return false;
}
/// <summary>
/// Returns true if the two sets share at least one element.
/// </summary>
public bool SetOverlaps(CountingSet<T> other) {
if(other == null) return false;
foreach(var key in _dict.Keys)
if(other.Contains(key)) return true;
return false;
}
// ----------------------------------------------------------------------------------
/// <summary>
/// Modifies the current set so that it contains
/// all elements that are are present in the current set,
/// in the specified collection, or in both.
/// Doesn't take counts into consideration, only keys.
/// </summary>
public void UnionWith(IEnumerable<T> other) {
if(other == null) throw new ArgumentNullException(nameof(other));
foreach(var key in other) AddItem(key);
}
/// <summary>
/// Modifies the current set so that it contains
/// all elements that are are present in the current set,
/// in the specified set, or in both.
/// Doesn't take counts into consideration, only keys.
/// </summary>
public void UnionWith(HashSet<T> other) {
if(other == null) throw new ArgumentNullException(nameof(other));
if(other.Count == 0) return;
foreach(var key in other) AddItem(key);
}
/// <summary>
/// Modifies the current set so that it contains
/// all elements that are are present in the current set,
/// in the specified set, or in both.
/// Takes counts into consideration (result: current set + specified set).
/// </summary>
public void UnionWith(CountingSet<T> other) {
if(other == null) throw new ArgumentNullException(nameof(other));
if(other.KeyCount == 0) return;
foreach(var item in other) Add(item.Key, item.Value);
}
/// <summary>
/// Removes all elements in the specified collection from the current set.
/// Doesn't take counts into consideration, only keys.
/// </summary>
public void ExceptWith(IEnumerable<T> other) {
if(other == null) throw new ArgumentNullException(nameof(other));
foreach(var key in other) RemoveItem(key);
}
/// <summary>
/// Removes all elements in the specified set from the current set.
/// Doesn't take counts into consideration, only keys.
/// </summary>
public void ExceptWith(HashSet<T> other) {
if(other == null) throw new ArgumentNullException(nameof(other));
if(other.Count == 0) return;
foreach(var key in other) RemoveItem(key);
}
/// <summary>
/// Removes all elements in the specified set from the current set.
/// Takes counts into consideration (result: current set - specified set).
/// </summary>
public void ExceptWith(CountingSet<T> other) {
if(other == null) throw new ArgumentNullException(nameof(other));
if(other.KeyCount == 0) return;
foreach(var item in other) Remove(item.Key, item.Value);
}
// ----------------------------------------------------------------------------------
/// <summary>
/// Modifies the current set so that it contains only
/// elements that are also in a specified set.
/// Doesn't take counts into consideration, only keys.
/// </summary>
public void IntersectWith(HashSet<T> other) {
if(other == null) throw new ArgumentNullException(nameof(other));
if(other.Count == 0) { Clear(); return; }
var forRemoval = new List<T>();
foreach(var item in _dict)
if(!other.Contains(item.Key)) forRemoval.Add(item.Key);
foreach(var key in forRemoval) RemoveItem(key);
}
/// <summary>
/// Modifies the current set so that it contains only
/// elements that are also in a specified set.
/// Takes counts into consideration (result: exact mechanism configurable).
/// </summary>
public void IntersectWith(CountingSet<T> other, CountOp countOperation = CountOp.Min) {
if(other == null) throw new ArgumentNullException(nameof(other));
if(other.KeyCount == 0) { Clear(); return; }
var forRemoval = new List<T>();
var forAdding = new List<T>();
foreach(var item in _dict) {
if(CountOf(item.Key) <= 0 || item.Value <= 0)
forRemoval.Add(item.Key);
else
forAdding.Add(item.Key);
}
foreach(var key in forRemoval) RemoveItem(key);
foreach(var key in forAdding) Add(key, processCountOp(_dict[key], other._dict[key], countOperation));
}
int processCountOp(int count1, int count2, CountOp op) {
switch(op) {
case CountOp.Min: return (count1 < count2)? 0 : count1 - count2; // 5 +0 = 5 ; 8 +(5 - 8) = 5 (minimum)
case CountOp.Max: return (count1 > count2)? 0 : count2 - count1; // 5 +(8 - 5) = 8 ; 8 +0 = 8 (maximum)
case CountOp.Dif: return -count2; // a -b (difference)
default: return +count2; // a +b (sum)
}
}
public enum CountOp {
Sum,
Dif,
Min,
Max
}
/// <summary>
/// Modifies the current set so that it contains only
/// elements that are present either in the current set
/// or in the specified set, but not both.
/// Doesn't take counts into consideration, only keys.
/// </summary>
public void SymmetricExceptWith(HashSet<T> other) {
if(other == null) throw new ArgumentNullException(nameof(other));
if(other.Count == 0) return;
var forRemoval = new List<T>();
foreach(var key in other)
if(Contains(key)) forRemoval.Add(key); else AddItem(key);
foreach(var key in forRemoval) RemoveItem(key);
}
/// <summary>
/// Modifies the current set so that it contains only
/// elements that are present either in the current set
/// or in the specified set, but not both.
/// Takes counts into consideration.
/// </summary>
public void SymmetricExceptWith(CountingSet<T> other) {
if(other == null) throw new ArgumentNullException(nameof(other));
if(other.KeyCount == 0) return;
var forRemoval = new List<T>();
var forAdding = new Dictionary<T, int>();
foreach(var item in _dict) {
if(CountOf(item.Key) > 0 && item.Value > 0)
forRemoval.Add(item.Key);
else
forAdding.Add(item.Key, item.Value);
}
foreach(var key in forRemoval) RemoveItem(key);
foreach(var item in forAdding) Add(item.Key, item.Value);
}
// ----------------------------------------------------------------------------------
/// <summary>
/// Applies an <paramref name="action" /> to every item in the set.
/// </summary>
public void ForEach(Action<T, int> action) {
if(action == null) throw new ArgumentNullException(nameof(action));
foreach(var item in _dict) action(item.Key, item.Value);
}
/// <summary>
/// Returns a counting set with items whose counts match the specified <paramref name="count" />.
/// </summary>
public CountingSet<T> Where(int count, bool absolute = false) {
var result = new CountingSet<T>(KeepNegativeCount, KeepZeroCount);
foreach(var item in _dict)
if(item.Value == count || (absolute && -item.Value == count))
result.Add(item.Key, count);
return result;
}
/// <summary>
/// Returns a counting set with items whose counts matches the specified interval
/// (bounds are inclusive).
/// </summary>
public CountingSet<T> Where(int min, int max = int.MaxValue) {
var result = new CountingSet<T>(KeepNegativeCount, KeepZeroCount);
foreach(var item in _dict)
if(item.Value >= min && item.Value <= max) result.Add(item.Key, item.Value);
return result;
}
/// <summary>
/// Returns a counting set that is filtered with an external validation callback.
/// </summary>
public CountingSet<T> Where(ItemTestCallback test, bool breakOnFail = false) {
if(test == null) throw new ArgumentNullException(nameof(test));
var result = new CountingSet<T>(KeepNegativeCount, KeepZeroCount);
foreach(var item in _dict)
if(test(item.Key, item.Value)) result.Add(item.Key, item.Value);
else if(breakOnFail) break;
return result;
}
public delegate bool ItemTestCallback(T item, int count);
// ----------------------------------------------------------------------------------
public override int GetHashCode() => _dict.GetHashCode() ^ 0x4564138e;
public override string ToString() => $"[CountedSet - Unique items: {KeyCount}]";
// ----------------------------------------------------------------------------------
public new CountingSet<T> MemberwiseClone()
=> new CountingSet<T>(this, KeepNegativeCount, KeepZeroCount);
public void CopyTo(T[] array) => Keys.CopyTo(array, 0);
public void CopyTo(T[] array, int arrayIndex) => Keys.CopyTo(array, arrayIndex);
public HashSet<T> ToHashSet() => new HashSet<T>(_dict.Keys);
public Dictionary<T, int> ToDictionary => new Dictionary<T, int>(_dict);
}
}