¿Hay implementaciones de multiset para .Net?

Question

Estoy buscando una implementación .Net de un multiset. ¿Alguien puede recomendar una buena?

(Un multiset, o bolsa, es un conjunto que puede tener valores duplicados, y en el que puede realizar operaciones de conjunto: intersección, diferencia, etc. Un carrito de compras, por ejemplo, podría considerarse un multiset porque puede tener múltiples ocurrencias del mismo producto.)

Answer 1

No conozco ninguno, sin embargo puede usar un Dictionary para eso, en el cual el valor es la cantidad del artículo. Y cuando el artículo se agrega por segunda vez, debe aumentar el valor en el diccionario.

Otra posibilidad sería simplemente utilizar un List de elementos, en los que podría poner duplicados. Este podría ser un mejor enfoque para un carrito de compras.

Answer 2

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(); 
     } 
    } 
} 

Answer 3

Cualquier cosa que se llame a sí misma una implementación de C# de un multiset no se debe basar internamente en un diccionario. Los diccionarios son tablas hash, colecciones desordenadas. Se ordenan los conjuntos, multisedes, mapas y multimapas de C++. Internamente, cada uno se representa como un sabor de un árbol de búsqueda binaria autoequilibrante.

En C# deberíamos utilizar un SortedDictionary como base de nuestra implementación, ya que según la propia documentación de Microsoft, SortedDictionary "is a binary search tree with O(log n) retrieval". Un conjunto múltiple básica se puede implementar de la siguiente manera:

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(); 
    } 
}