Я ищу .Net-реализацию мультимножества. Может кто-нибудь порекомендовать хороший?
(Мультимножество или сумка - это набор, который может иметь повторяющиеся значения и на котором вы можете выполнять операции: пересечение, разность и т.д. Например, корзину покупок можно рассматривать как мультимножество, потому что вы можете множественные вхождения одного и того же продукта.)
Я не знаю об одном, однако для этого можно использовать Dictionary, в котором значение представляет собой количество элемента. И когда элемент добавляется во второй раз, вы можете увеличить значение для него в словаре.
Другой возможностью было бы просто использовать List элементов, в которых вы могли бы разместить дубликаты. Это может быть лучшим подходом для корзины покупок.
Все, называющее себя реализацией мультимножества С#, не должно основываться на словаре внутри. Словари - это хеш-таблицы, неупорядоченные коллекции. Заказываются наборы С++, мультимножества, карты и мультимаксы. Внутренне каждый из них представлен как некоторый аромат самобалансирующегося двоичного дерева поиска.
В С# мы должны использовать SortedDictionary в качестве основы для нашей реализации, так как согласно собственной документации Microsoft SortedDictionary " является двоичным деревом поиска с O (log n) поиск". Базовый мультимножество может быть реализован следующим образом:
public class SortedMultiSet<T> : IEnumerable<T>
{
private SortedDictionary<T, int> _dict;
public SortedMultiSet()
{
_dict = new SortedDictionary<T, int>();
}
public SortedMultiSet(IEnumerable<T> items) : this()
{
Add(items);
}
public bool Contains(T item)
{
return _dict.ContainsKey(item);
}
public void Add(T item)
{
if (_dict.ContainsKey(item))
_dict[item]++;
else
_dict[item] = 1;
}
public void Add(IEnumerable<T> items)
{
foreach (var item in items)
Add(item);
}
public void Remove(T item)
{
if (!_dict.ContainsKey(item))
throw new ArgumentException();
if (--_dict[item] == 0)
_dict.Remove(item);
}
// Return the last value in the multiset
public T Peek()
{
if (!_dict.Any())
throw new NullReferenceException();
return _dict.Last().Key;
}
// Return the last value in the multiset and remove it.
public T Pop()
{
T item = Peek();
Remove(item);
return item;
}
public IEnumerator<T> GetEnumerator()
{
foreach(var kvp in _dict)
for(int i = 0; i < kvp.Value; i++)
yield return kvp.Key;
}
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
}
public class Multiset<T>: ICollection<T>
{
private readonly Dictionary<T, int> data;
public Multiset()
{
data = new Dictionary<T, int>();
}
private Multiset(Dictionary<T, int> data)
{
this.data = data;
}
public void Add(T item)
{
int count = 0;
data.TryGetValue(item, out count);
count++;
data[item] = count;
}
public void Clear()
{
data.Clear();
}
public Multiset<T> Except(Multiset<T> another)
{
Multiset<T> copy = new Multiset<T>(new Dictionary<T, int>(data));
foreach (KeyValuePair<T, int> kvp in another.data)
{
int count;
if (copy.data.TryGetValue(kvp.Key, out count))
{
if (count > kvp.Value)
{
copy.data[kvp.Key] = count - kvp.Value;
}
else
{
copy.data.Remove(kvp.Key);
}
}
}
return copy;
}
public Multiset<T> Intersection(Multiset<T> another)
{
Dictionary<T, int> newData = new Dictionary<T, int>();
foreach (T t in data.Keys.Intersect(another.data.Keys))
{
newData[t] = Math.Min(data[t], another.data[t]);
}
return new Multiset<T>(newData);
}
public bool Contains(T item)
{
return data.ContainsKey(item);
}
public void CopyTo(T[] array, int arrayIndex)
{
foreach (KeyValuePair<T, int> kvp in data)
{
for (int i = 0; i < kvp.Value; i++)
{
array[arrayIndex] = kvp.Key;
arrayIndex++;
}
}
}
public IEnumerable<T> Mode()
{
if (!data.Any())
{
return Enumerable.Empty<T>();
}
int modalFrequency = data.Values.Max();
return data.Where(kvp => kvp.Value == modalFrequency).Select(kvp => kvp.Key);
}
public int Count
{
get
{
return data.Values.Sum();
}
}
public bool IsReadOnly
{
get
{
return false;
}
}
public bool Remove(T item)
{
int count;
if (!data.TryGetValue(item, out count))
{
return false;
}
count--;
if (count == 0)
{
data.Remove(item);
}
else
{
data[item] = count;
}
return true;
}
public IEnumerator<T> GetEnumerator()
{
return new MultisetEnumerator<T>(this);
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return new MultisetEnumerator<T>(this);
}
private class MultisetEnumerator<T> : IEnumerator<T>
{
public MultisetEnumerator(Multiset<T> multiset)
{
this.multiset = multiset;
baseEnumerator = multiset.data.GetEnumerator();
index = 0;
}
private readonly Multiset<T> multiset;
private readonly IEnumerator<KeyValuePair<T, int>> baseEnumerator;
private int index;
public T Current
{
get
{
return baseEnumerator.Current.Key;
}
}
public void Dispose()
{
baseEnumerator.Dispose();
}
object System.Collections.IEnumerator.Current
{
get
{
return baseEnumerator.Current.Key;
}
}
public bool MoveNext()
{
KeyValuePair<T, int> kvp = baseEnumerator.Current;
if (index < (kvp.Value - 1))
{
index++;
return true;
}
else
{
bool result = baseEnumerator.MoveNext();
index = 0;
return result;
}
}
public void Reset()
{
baseEnumerator.Reset();
}
}
}