Esistono implementazioni di multiset per .Net?

Question

Sto cercando un'implementazione .Net di un multiset. Qualcuno può consigliarne uno buono?

(Un multiset, o borsa, è un set che può avere valori duplicati e su cui è possibile eseguire operazioni di set: intersezione, differenza, ecc. Un carrello degli acquisti per esempio può essere pensato come un multiset perché è possibile hanno più occorrenze dello stesso prodotto.)

Answer 1

Non ne so nulla, tuttavia è possibile utilizzare uno Dictionary per il quale il valore è la quantità dell'articolo. E quando l'elemento viene aggiunto per la seconda volta, è possibile aumentare il valore per esso nel dizionario.

Un'altra possibilità sarebbe quella di utilizzare semplicemente uno List di elementi, in cui è possibile inserire duplicati. Questo potrebbe essere un approccio migliore per un carrello della spesa.

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

Qualsiasi cosa che si autodefinisce l'implementazione C# di un multiset non dovrebbe essere basata su un dizionario internamente. I dizionari sono tabelle hash, raccolte non ordinate. Vengono ordinati set, multiset, mappe e multimaps di C++. Internamente ciascuna è rappresentata come il sapore di un albero di ricerca binaria autoequilibrante.

In C# dovremmo quindi utilizzare un SortedDictionary come base della nostra implementazione come secondo la documentazione di Microsoft a SortedDictionary "is a binary search tree with O(log n) retrieval". Un multiset di base può essere implementato come segue:

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