Created
January 20, 2013 19:47
-
-
Save tpetrina/4581209 to your computer and use it in GitHub Desktop.
Naive implementation of HashSet<T> using Dictionary<T, bool> for Windows Phone 7.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections; | |
using System.Collections.Generic; | |
using System.Linq; | |
namespace Common | |
{ | |
public interface ISet<T> : ICollection<T>, IEnumerable<T>, IEnumerable | |
{ | |
bool Add(T item); | |
void ExceptWith(IEnumerable<T> other); | |
void IntersectWith(IEnumerable<T> other); | |
bool IsProperSubsetOf(IEnumerable<T> other); | |
bool IsProperSupersetOf(IEnumerable<T> other); | |
bool IsSubsetOf(IEnumerable<T> other); | |
bool IsSupersetOf(IEnumerable<T> other); | |
bool Overlaps(IEnumerable<T> other); | |
bool SetEquals(IEnumerable<T> other); | |
void SymmetricExceptWith(IEnumerable<T> other); | |
void UnionWith(IEnumerable<T> other); | |
} | |
public class HashSet<T> : ISet<T>, ICollection<T>, IEnumerable<T>, IEnumerable | |
{ | |
private Dictionary<T, bool> _data; | |
#region Implementation of public methods | |
public HashSet() | |
{ | |
_data = new Dictionary<T, bool>(); | |
} | |
public HashSet(IEnumerable<T> collection) | |
{ | |
if (collection == null) | |
throw new ArgumentNullException("collection", "parameter must not be null"); | |
_data = new Dictionary<T, bool>(); | |
AddRange(collection); | |
} | |
public HashSet(IEqualityComparer<T> comparer) | |
{ | |
_data = new Dictionary<T, bool>(comparer); | |
} | |
public HashSet(IEnumerable<T> collection, IEqualityComparer<T> comparer) | |
{ | |
_data = new Dictionary<T, bool>(comparer); | |
AddRange(collection); | |
} | |
public IEqualityComparer<T> Comparer { get { return _data.Comparer; } } | |
public int Count { get { return _data.Count; } } | |
public bool Add(T item) | |
{ | |
if (_data.ContainsKey(item)) | |
return false; | |
_data.Add(item, true); | |
return true; | |
} | |
public void Clear() | |
{ | |
_data.Clear(); | |
} | |
public bool Contains(T item) | |
{ | |
return _data.ContainsKey(item); | |
} | |
public void CopyTo(T[] array) | |
{ | |
if (array == null) | |
throw new ArgumentNullException("array"); | |
AddRange(array); | |
} | |
public void CopyTo(T[] array, int arrayIndex) | |
{ | |
if (array == null) | |
throw new ArgumentNullException("array"); | |
if (arrayIndex < 0) | |
throw new ArgumentOutOfRangeException("arrayIndex"); | |
if (arrayIndex >= array.Length) | |
throw new ArgumentException("arrayIndex must not be greater than or equal to the array's length"); | |
AddRange(array.Skip(arrayIndex)); | |
} | |
public void CopyTo(T[] array, int arrayIndex, int count) | |
{ | |
if (array == null) | |
throw new ArgumentNullException("array"); | |
if (arrayIndex < 0) | |
throw new ArgumentOutOfRangeException("arrayIndex"); | |
if (count < 0) | |
throw new ArgumentOutOfRangeException("count", "count must be greater than zero"); | |
if (arrayIndex >= array.Length) | |
throw new ArgumentException("arrayIndex must not be greater than or equal to the array's length"); | |
if (arrayIndex + count > array.Length) | |
throw new ArgumentException("arrayIndex and count specify more items than possible"); | |
AddRange(array.Skip(arrayIndex).Take(count)); | |
} | |
public void ExceptWith(IEnumerable<T> other) | |
{ | |
if (other == null) | |
throw new ArgumentNullException("other"); | |
foreach (var item in other) | |
_data.Remove(item); | |
} | |
public IEnumerator<T> GetEnumerator() | |
{ | |
return _data.Keys.GetEnumerator(); | |
} | |
public void IntersectWith(IEnumerable<T> other) | |
{ | |
if (other == null) | |
throw new ArgumentNullException("other"); | |
var result = _data.Keys.Where(other.Contains).ToList(); | |
_data = new Dictionary<T, bool>(); | |
AddRange(result); | |
} | |
public bool IsProperSubsetOf(IEnumerable<T> other) | |
{ | |
if (other == null) | |
throw new ArgumentNullException("other"); | |
var otherSet = new HashSet<T>(other); | |
return (Count < otherSet.Count && _data.Keys.All(otherSet.Contains)); | |
} | |
public bool IsProperSupersetOf(IEnumerable<T> other) | |
{ | |
if (other == null) | |
throw new ArgumentNullException("other"); | |
if (Count == 0) | |
return false; | |
var otherSet = new HashSet<T>(other); | |
return (Count > otherSet.Count && otherSet.All(Contains)); | |
} | |
public bool IsSubsetOf(IEnumerable<T> other) | |
{ | |
if (other == null) | |
throw new ArgumentNullException("other"); | |
if (Count == 0) | |
return true; | |
var otherSet = new HashSet<T>(other); | |
return (Count <= otherSet.Count && _data.Keys.All(otherSet.Contains)); | |
} | |
public bool IsSupersetOf(IEnumerable<T> other) | |
{ | |
if (other == null) | |
throw new ArgumentNullException("other"); | |
return other.All(Contains); | |
} | |
public bool Overlaps(IEnumerable<T> other) | |
{ | |
if (other == null) | |
throw new ArgumentNullException("other"); | |
return (other.Any(Contains)); | |
} | |
public bool Remove(T item) | |
{ | |
if (!_data.ContainsKey(item)) | |
return false; | |
_data.Remove(item); | |
return true; | |
} | |
public int RemoveWhere(Predicate<T> match) | |
{ | |
if (match == null) | |
throw new ArgumentNullException("match"); | |
var result = _data.Keys.Where(i => match(i)).ToList(); | |
var removed = (Count - result.Count); | |
Clear(); | |
AddRange(result); | |
return removed; | |
} | |
public bool SetEquals(IEnumerable<T> other) | |
{ | |
if (other == null) | |
throw new ArgumentNullException("other"); | |
var otherSet = new HashSet<T>(); | |
foreach (var item in other) | |
{ | |
if (!Contains(item)) | |
return false; | |
otherSet.Add(item); | |
} | |
return (otherSet.Count == Count); | |
} | |
public void SymmetricExceptWith(IEnumerable<T> other) | |
{ | |
if (other == null) | |
throw new ArgumentNullException("other"); | |
foreach (var item in other.Where(Contains)) | |
Remove(item); | |
} | |
public void TrimExcess() | |
{ | |
} | |
public void UnionWith(IEnumerable<T> other) | |
{ | |
if (other == null) | |
throw new ArgumentNullException("other"); | |
AddRange(other); | |
} | |
#endregion | |
private void AddRange(IEnumerable<T> items) | |
{ | |
if (items == null) | |
throw new ArgumentNullException("items"); | |
foreach (var item in items) | |
Add(item); | |
} | |
#region Remaining interface implementations | |
void ICollection<T>.Add(T item) | |
{ | |
Add(item); | |
} | |
bool ICollection<T>.IsReadOnly | |
{ | |
get { return false; } | |
} | |
IEnumerator IEnumerable.GetEnumerator() | |
{ | |
return _data.Keys.GetEnumerator(); | |
} | |
#endregion | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment