using System; using System.Collections; using System.Collections.Generic; using System.Runtime.Serialization; using System.Text; namespace Ewbi { /* Copyright (c) 2007 E. W. Bachtal, Inc. Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. The software is provided "as is", without warranty of any kind, express or implied, including but not limited to the warranties of merchantability, fitness for a particular purpose and noninfringement. In no event shall the authors or copyright holders be liable for any claim, damages or other liability, whether in an action of contract, tort or otherwise, arising from, out of or in connection with the software or the use or other dealings in the software. -------------------------------------------------------------------------------------------------------- UniqueList Generic class that stores unique objects of any type in one Add step. Uses an open addressing hash table with prime modulo bucket determination and linear probing for collision resolution. Uses any IEqualityComparer based type for hash codes and equality checks. Objects are kept in an array to preserve order for enumeration and indexed lookups. Sensitive to clustering, needs good hash distribution and load factor management. Supports serialization, but it's up to the caller to make sure the list's type and the IEqualityComparer are serializable (if not, expect a runtime exception during serialization). Not thread safe. http://ewbi.blogs.com/develops/2007/05/uniquelistt_for.html v1.0 Original */ [Serializable] public sealed class UniqueList : IList { private const double loadFactor = .58; private IEqualityComparer comparer; private List items; private List itemCounts; private int capacity; [NonSerialized()] private int[] buckets; [NonSerialized()] private int maxLoad; [OnDeserialized()] private void OnDeserialized(StreamingContext context) { buckets = new int[capacity]; ReindexItems(); } #region Constructors public UniqueList() : this(0) { } public UniqueList(int capacity) : this(capacity, null) { } public UniqueList(IEqualityComparer comparer) : this(0, comparer) { } public UniqueList(IEnumerable collection) : this(collection, null) { } public UniqueList(IEnumerable collection, IEqualityComparer comparer) : this(0, comparer) { AddRange(collection); } public UniqueList(int capacity, IEqualityComparer comparer) { if (capacity < 0) throw new ArgumentOutOfRangeException("capacity"); this.comparer = comparer; if (this.comparer == null) this.comparer = EqualityComparer.Default; Initialize(capacity); } #endregion #region IList implementation public int IndexOf(T item) { if (item == null) return -1; int index = GetIndex(item); return buckets[index] - 1; } public void Insert(int index, T item) { throw new NotSupportedException(); } public void RemoveAt(int index) { throw new NotSupportedException(); } public T this[int index] { get { return items[index]; } set { throw new NotSupportedException(); } } #endregion #region ICollection implementation public void Add(T item) { if (item == null) return; int index = GetIndex(item); if (buckets[index] == 0) { items.Add(item); itemCounts.Add(1); buckets[index] = items.Count; if (items.Count > maxLoad) Expand(); } else { itemCounts[buckets[index] - 1]++; } } public void Clear() { Initialize(0); } public bool Contains(T item) { return (IndexOf(item) != -1); } public void CopyTo(T[] array, int arrayIndex) { CopyTo(0, array, arrayIndex, items.Count); } public int Count { get { return items.Count; } } public bool IsReadOnly { get { return false; } } public bool Remove(T item) { throw new NotSupportedException(); } #endregion #region IEnumerable/IEnumerable implementation IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } public IEnumerator GetEnumerator() { return items.GetEnumerator(); } #endregion #region List-like methods public void AddRange(IEnumerable collection) { if (collection == null) throw new ArgumentNullException("collection"); foreach (T item in collection) { Add(item); } } public void CopyTo(T[] array) { CopyTo(array, 0); } public void CopyTo(int index, T[] array, int arrayIndex, int count) { items.CopyTo(index, array, arrayIndex, count); } public T[] ToArray() { return items.ToArray(); } #endregion #region Item count methods public void CopyItemCountsTo(int[] array) { CopyItemCountsTo(array, 0); } public void CopyItemCountsTo(int[] array, int arrayIndex) { CopyItemCountsTo(0, array, arrayIndex, itemCounts.Count); } public void CopyItemCountsTo(int index, int[] array, int arrayIndex, int count) { itemCounts.CopyTo(index, array, arrayIndex, count); } public int GetItemCount(T item) { if (item == null) return 0; int index = GetIndex(item); if (buckets[index] == 0) return 0; return GetItemCountByIndex(buckets[index] - 1); } public int GetItemCountByIndex(int index) { return itemCounts[index]; } public IEnumerable GetItemCounts() { foreach (int count in itemCounts) { yield return count; } } public IEnumerable GetItemsAndCounts() { for (int i = 0; i < items.Count; i++) { yield return new ListItem(items[i], itemCounts[i]); } } public int[] ItemCountsToArray() { return itemCounts.ToArray(); } #endregion #region Private logic private static int GetPrime(int min) { for (int i = min | 1; i < 0x7fffffff; i += 2) { if (IsPrime(i)) return i; } return min; } private static bool IsPrime(int candidate) { if ((candidate & 1) == 0) return (candidate == 2); int halfway = (int) Math.Sqrt((double) candidate); for (int i = 3; i <= halfway; i += 2) { if ((candidate % i) == 0) return false; } return true; } private void Initialize(int size) { capacity = GetPrime(size); items = new List(capacity); itemCounts = new List(capacity); buckets = new int[capacity]; maxLoad = (int) (capacity * loadFactor); } private void Expand() { capacity = GetPrime(capacity * 2); buckets = new int[capacity]; ReindexItems(); } private void ReindexItems() { maxLoad = (int) (capacity * loadFactor); for (int itemIndex = 0; itemIndex < items.Count; itemIndex++) { buckets[GetIndex(items[itemIndex])] = itemIndex + 1; } } private int GetIndex(T item) { int hashCode = comparer.GetHashCode(item) & 0x7fffffff; int index = hashCode % capacity; int increment = (index > 1) ? index : 1; int i = capacity; while (0 < i--) { int itemIndex = buckets[index]; if (itemIndex == 0) return index; // Empty bucket. if (comparer.Equals(items[itemIndex - 1], item)) return index; // Bucket item match. index = (index + increment) % capacity; // Probe. } throw new InvalidOperationException("Failed to locate a bucket for item."); } #endregion #region ListItem struct [Serializable] public struct ListItem { private T value; private int count; public ListItem(T value, int count) { this.value = value; this.count = count; } public T Value { get { return value; } } public int Count { get { return count; } } public override string ToString() { return String.Format("[{0}, {1}]", value, count); } } #endregion } }