Are there any implementations of multiset for .Net

问题:

I'm looking for a .Net implementation of a multiset. Can anyone recommend a good one?

(A multiset, or bag, is a set that can have duplicate values, and on which you can do set operations: intersection, difference, etc. A shopping cart for instance could be thought of as a multiset because you can have multiple occurrences of the same product.)

回答1:

Anything calling itself a C# implementation of a multiset should not be based on a Dictionary internally. Dictionaries are hash tables, unordered collections. C++'s sets, multisets, maps, and multimaps are ordered. Internally each is represented as some flavor of a self-balancing binary search tree.

In C# we should then use a SortedDictionary as the basis of our implementation as according to Microsoft's own documentation a SortedDictionary "is a binary search tree with O(log n) retrieval". A basic multiset can be implemented as follows:

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

回答2:

I do not know about one, however you could use a Dictionary for that, in which the value is the quantity of the item. And when the item is added for the second time, you vould increase the value for it in the dictionary.

An other possibility would be to simply use a List of items, in which you could put duplicates. This might be a better approach for a shopping cart.

回答3:

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