c# - ¿Hay alguna implementación de multiset para.Net?

data-structures bag

Question

Estoy buscando una implementación de .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 multiset porque puede tener múltiples apariciones de el mismo producto)

Answer 1

Cualquier cosa que se llame a sí misma una implementación de C # de un multiset no debería basarse en un diccionario internamente. 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 usar un SortedDictionary como base de nuestra implementación, ya que según la propia documentación de Microsoft, SortedDictionary " es un árbol de búsqueda binario con recuperación de O (log n) ". Un multiset básico 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();
    }
}

Answer 2

No sé de uno, sin embargo, podría 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 usar una List de elementos, en la que podría colocar duplicados. Este podría ser un mejor enfoque para un carrito de compras.

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