Generyczna klasa zbioru

W projekcie, nad którym pracuję potrzebowałem przyzwoicie działającej klasy reprezentującej zbiór. Zbiór nie do końca w sensie teoriomnogościowym (o właściwościach takiego można przeczytać np. tu), posiadający jedną bardzo ważną cechę: przechowywanie unikalnych elementów.

Istniejące implementacje (Hashtable oraz HashSet) nie spełniały moich oczekiwań – elementów do wstawiania było na tyle dużo, że występowały kolizje z obliczonej przez GetHashCode() wartości. Ponieważ rozwiązanie zagadnienia było potrzebne „na wczoraj”, napisałem własną prostą implementację klasy Set<T>. Implementuje ona interfejs ICollection<T>, więc korzystanie z niej powinno być intuicyjne. Oprócz zestawu metod i właściwości oferowanych standardowo przez interfejs:

  • Add(T)
  • Clear()
  • Contains(T)
  • CopyTo(T[], int)
  • GetEnumerator()
  • Remove()
  • Count { get; }
  • Readonly { get; }

dodałem do klasy kilka użytecznych dla mnie na tym etapie rozszerzeń:

  • bool Overwrite { get; set; } – właściwość informująca o tym, jak obiekt ma się zachowywać w przypadku próby dodania duplikatu. Dla Overwrite == true element zostanie nadpisany, w przeciwnym wypadku metoda rzuci wyjątek ArgumentException
  • bool TryGetItem(T item, out T found); – próba znalezienia elementu równemu elementowi item. Jeżeli metoda zwróci true, znaleziony element jest zwracany przez parametr out, metoda zwraca false gdy nie znaleziono elementu
  • T GetItem(T item); – metoda analogiczna do powyższej. Jeżeli element nie zostanie znaleziony, metoda zwraca default(T) (null dla typów referencyjnych, wartość domyślna dla typów niereferencyjnych). Zalecam używanie TryGetItem(), GetItem() zostało dodane niejako dla kompletu.

Architektura

Pisałem już o klasie jako czarnej skrzynce, wiadomo co może robić, przyszła pora na odpowiedź na pytanie JAK?

Koncepcja jest prosta:

private Dictionary<int, List<T>> set;

Słownik, którego kluczami są wartości GetHashCode() dla danego elementu, natomiast wartościami – listy elementów (unikalnych!), o danej wartości zwracanej przez GetHashCode(). Dlaczego akurat takie rozwiązanie? Jako reakcja na jedno ze zdań z opisu metody GetHashCode():

If two objects compare as equal, the GetHashCode method for each object must return the same value. However, if two objects do not compare as equal, the GetHashCode methods for the two object do not have to return different values.

Jeżeli dwa elementy są różne, metoda może zwrócić takie same wartości dla obu elementów.

To może oczywiście sprawiać trochę problemów, ponieważ czas wykonania operacji dodawania, usuwania i sprawdzania istnienia elementu w zbiorze zależy niejako od ilości elementów o takiej samej wartości GetHashCode(), ale przeprowadzone przeze mnie wstępne testy są całkiem zadowalające.

Uwaga

Przy wstępnym projektowaniu klasy dostosowywałem ją do swoich potrzeb, dlatego chciałbym zwrócić uwagę na pewną specyficzną cechę:

Metody TryGetItem() oraz GetItem() służą do modyfikowania obiektów znajdujących się wewnątrz zbioru. Przy modyfikowaniu własności wpływających na wartość metody GetHashCode() działanie klasy może nie być zgodne z oczekiwanym.

Kod

Poniżej pełen kod klasy Set, pełen projekt (z testami jednostkowymi NUnit) do ściągnięcia również poniżej.

//*******************************************
// Written by Przemysław Czatrowski "czoper"
// 07.2010
//
// Feel free to use and modify the code,
// but leave this info as it is.
//
// THE CODE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED INCLUDING,
// WITHOUT LIMITATION, ANY WARRANTIES OR CONDITIONS OF TITLE, NON-INFRINGEMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
// Each User is solely responsible for determining the appropriateness of using and distributing the code and assumes all risks
// associated with its exercise, including but not limited to the risks and costs of program errors, compliance with applicable laws,
// damage to or loss of data, programs or equipment, and unavailability or interruption of operations.
//
//*******************************************
using System;
using System.Collections.Generic;

namespace Set
{
    public class Set<T> : ICollection<T>
    {
        #region Constructors
        public Set(bool overwrite)
        {
            set = new Dictionary<int, List<T>>();
            count = 0;
            this.overwrite = overwrite;
        }

        public Set(bool overwrite, IEnumerable<T> items)
        {
            this.overwrite = overwrite;
            set = new Dictionary<int, List<T>>();
            count = 0;

            foreach (T item in items)
                if (!Contains(item))
                    Add(item);
        }
        #endregion

        #region ICollection<T> Members
        public void Add(T item)
        {
            int hashCode = item.GetHashCode();

            // if list of elements with hashCode is empty
            // add list with one element
            if (!set.ContainsKey(hashCode))
            {
                set.Add(hashCode, new List<T> { item });
                ++count;
                return;
            }

            // if list of elements with hashCode is not empty
            // and it does not contain item, add item
            if (!set[hashCode].Contains(item))
            {
                set[hashCode].Add(item);
                ++count;
                return;
            }

            // item already in the set, and overwrite is true - overwrite
            if (overwrite)
            {
                int index = set[hashCode].IndexOf(item);
                set[hashCode][index] = item;
                return;
            }

            // item already in the set, and overwrite is false - throw appropriate Exception
            throw new ArgumentException("Item already in the collection");
        }

        public void Add(IEnumerable<T> collection)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");

            // If adding the same set, do nothing
            if (object.ReferenceEquals(collection, this))
                return;

            foreach (T item in collection)
                Add(item);
        }

        public void Clear()
        {
            foreach (KeyValuePair<int, List<T>> pair in set)
                pair.Value.Clear();
            set.Clear();

            count = 0;
        }

        public bool Contains(T item)
        {
            int hashCode = item.GetHashCode();

            if (!set.ContainsKey(hashCode))
                return false;

            return set[hashCode].Contains(item);
        }

        public void CopyTo(T[] array, int arrayIndex)
        {
            if (count == 0)
                return;

            if (arrayIndex < 0)
                throw new ArgumentNullException("arrayIndex", "arrayIndex cannot be negative");

            if (count + arrayIndex >= array.Length)
                throw new ArgumentException("Not enough space for elements in the array", "arrayIndex");

            int index = arrayIndex, i = 0;
            foreach (T item in this)
            {
                if (i >= count)
                    break;

                array[index] = item;
                ++index;
                ++i;
            }
        }

        public int Count
        {
            get { return count; }
        }

        public bool IsReadOnly
        {
            get { return false; }
        }

        public bool Remove(T item)
        {
            int hashCode = item.GetHashCode();

            if (!set.ContainsKey(hashCode))
                return false;

            if (!set[hashCode].Contains(item))
                return false;

            if (set[hashCode].Remove(item))
            {
                --count;
                return true;
            }

            return false;
        }
        #endregion

        #region Extracting items
        public bool TryGetItem(T item, out T foundItem)
        {
            int hashCode = item.GetHashCode();

            if (!set.ContainsKey(hashCode))
            {
                foundItem = default(T);
                return false;
            }

            if (set[hashCode].Contains(item))
            {
                int index = set[hashCode].IndexOf(item);
                foundItem = set[hashCode][index];
                return true;
            }

            foundItem = default(T);
            return false;
        }

        public T GetItem(T item)
        {
            T found;
            if (TryGetItem(item, out found))
                return found;
            return default(T);
        }
        #endregion

        #region IEnumerable<T> Members
        public IEnumerator<T> GetEnumerator()
        {
            foreach (KeyValuePair<int, List<T>> pair in set)
                foreach (T item in pair.Value)
                    yield return item;
        }
        #endregion

        #region IEnumerable Members
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
        #endregion

        #region Variables
        private Dictionary<int, List<T>> set;
        private int count;
        private bool overwrite;
        #endregion

        #region Properties
        public bool Overwrite
        {
            get { return overwrite; }
            set { overwrite = value; }
        }
        #endregion
    }
}

Projekt: Visual Studio C# Express Edition [.rar, 48kB]

Zachęcam do zapoznania się z artykułem na temat integrowania NUnit z Visual Studio w wersji Express

Be Sociable, Share!
czoper opublikowano dnia 2010-7-23 Kategoria: Programowanie | Tagi:, ,

Jedna odpowiedź Zostaw komentarz

  1. #1paszklar @ 2010-7-29 20:57

    Obawiam się, że się bez sensu narobiłeś. O ile elementy są unikalne co do implementacji metody Equals, interfejsu IEquatable, czy też dostarczonego do kolekcji IEqualityComparera, to HashSet, Hashtable jak i Dictionary pozwalają ci przechowywać je nawet jeżeli mają taką samą wartość GetHashCode. Nawet jeśli masz starszy framework i nie masz kolekcji HashSet możesz opakować którąś z pozostałych dwóch i elementy przechowywać w kluczach a jako wartości wrzucać nulle czy coś.

Zostaw odpowiedź

(Ctrl + Enter)