|
//---------------------------------------------------------------------
// <copyright file="Set.cs" company="Microsoft">
// Copyright (c) Microsoft Corporation. All rights reserved.
// </copyright>
//
// @owner Microsoft
// @backupOwner Microsoft
//---------------------------------------------------------------------
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
using System.Linq;
namespace System.Data.Common.Utils {
// An interface for a set abstraction
internal class Set<TElement> : InternalBase, IEnumerable<TElement>
{
#region Fields
/// <summary>
/// Instance of set value comparer.
/// </summary>
internal static readonly IEqualityComparer<Set<TElement>> ValueComparer =
new SetValueComparer();
/// <summary>
/// Instance of empty set with default comparer.
/// </summary>
internal static readonly Set<TElement> Empty = new Set<TElement>().MakeReadOnly();
private readonly HashSet<TElement> _values;
private bool _isReadOnly;
#endregion
#region Constructors
/// <summary>
/// Initialize set with the same values and comparer as other set.
/// </summary>
internal Set(Set<TElement> other)
: this(other._values, other.Comparer)
{
}
/// <summary>
/// Initialize empty set with default comparer.
/// </summary>
internal Set()
: this(null, null)
{
}
/// <summary>
/// Initialize a set with the given elements and using default comparer.
/// </summary>
internal Set(IEnumerable<TElement> elements)
: this(elements, null)
{
}
/// <summary>
/// Initializes an empty set with the given comparer.
/// </summary>
internal Set(IEqualityComparer<TElement> comparer)
: this(null, comparer)
{
}
/// <summary>
/// Initialize a set with the given elements and comparer.
/// </summary>
internal Set(IEnumerable<TElement> elements, IEqualityComparer<TElement> comparer)
{
_values = new HashSet<TElement>(
elements ?? Enumerable.Empty<TElement>(),
comparer ?? EqualityComparer<TElement>.Default);
}
#endregion
#region Properties
/// <summary>
/// Gets the number of elements in this set.
/// </summary>
internal int Count
{
get
{
return _values.Count;
}
}
/// <summary>
/// Gets the comparer used to determine equality and hash codes for elements of the set.
/// </summary>
internal IEqualityComparer<TElement> Comparer
{
get
{
return _values.Comparer;
}
}
#endregion
#region Methods
/// <summary>
/// Determines whether the given element exists in the set.
/// </summary>
internal bool Contains(TElement element)
{
return _values.Contains(element);
}
/// <summary>
/// Requires: !IsReadOnly
/// Adds given element to the set. If the set already contains
/// the element, does nothing.
/// </summary>
internal void Add(TElement element)
{
AssertReadWrite();
_values.Add(element);
}
/// <summary>
/// Requires: !IsReadOnly
/// Adds given elements to the set. If the set already contains
/// one of the elements, does nothing.
/// </summary>
internal void AddRange(IEnumerable<TElement> elements)
{
AssertReadWrite();
foreach (TElement element in elements)
{
Add(element);
}
}
/// <summary>
/// Requires: !IsReadOnly
/// Removes given element from the set. If the set does not contain
/// the element, does nothing.
/// </summary>
internal void Remove(TElement element)
{
AssertReadWrite();
_values.Remove(element);
}
/// <summary>
/// Requires: !IsReadOnly
/// Removes all elements from the set.
/// </summary>
internal void Clear()
{
AssertReadWrite();
_values.Clear();
}
/// <summary>
/// Returns an array containing all elements of the set. Order is arbitrary.
/// </summary>
internal TElement[] ToArray()
{
return _values.ToArray();
}
/// <summary>
/// Requires: other set must not be null and must have the same comparer.
/// Returns true if this set contains the same elements as the other set.
/// </summary>
internal bool SetEquals(Set<TElement> other)
{
AssertSetCompatible(other);
return _values.Count == other._values.Count
&& _values.IsSubsetOf(other._values);
}
/// <summary>
/// Requires: other set must not be null and must have the same comparer.
/// Returns true if all elements in this set are contained in the other set.
/// </summary>
internal bool IsSubsetOf(Set<TElement> other)
{
AssertSetCompatible(other);
return _values.IsSubsetOf(other._values);
}
/// <summary>
/// Requires: other set must not be null and must have the same comparer.
/// Returns true if this set and other set have some elements in common.
/// </summary>
internal bool Overlaps(Set<TElement> other)
{
AssertSetCompatible(other);
return _values.Overlaps(other._values);
}
/// <summary>
/// Requires: !IsReadOnly
/// Requires: other collection must not be null.
/// Subtracts other set from this set, leaving the result in this.
/// </summary>
internal void Subtract(IEnumerable<TElement> other)
{
AssertReadWrite();
_values.ExceptWith(other);
}
/// <summary>
/// Requires: other collection must not be null.
/// Subtracts other set from this set, returning result.
/// </summary>
internal Set<TElement> Difference(IEnumerable<TElement> other)
{
Set<TElement> copy = new Set<TElement>(this);
copy.Subtract(other);
return copy;
}
/// <summary>
/// Requires: !IsReadOnly
/// Requires: other collection must not be null.
/// Unions other set with this set, leaving the result in this set.
/// </summary>
internal void Unite(IEnumerable<TElement> other)
{
AssertReadWrite();
_values.UnionWith(other);
}
/// <summary>
/// Requires: other collection must not be null.
/// Unions other set with this set, returning the result.
/// </summary>
internal Set<TElement> Union(IEnumerable<TElement> other)
{
Set<TElement> copy = new Set<TElement>(this);
copy.Unite(other);
return copy;
}
/// <summary>
/// Requires: !IsReadOnly
/// Requires: other set must not be null and must have the same comparer.
/// Intersects this set and other set, leaving the result in this set.
/// </summary>
internal void Intersect(Set<TElement> other)
{
AssertReadWrite();
AssertSetCompatible(other);
_values.IntersectWith(other._values);
}
/// <summary>
/// Returns a readonly version of this set.
/// </summary>
internal Set<TElement> AsReadOnly()
{
if (_isReadOnly)
{
// once it's readonly, it's always readonly
return this;
}
Set<TElement> copy = new Set<TElement>(this);
copy._isReadOnly = true;
return copy;
}
/// <summary>
/// Makes this set readonly and returns this set.
/// </summary>
internal Set<TElement> MakeReadOnly()
{
_isReadOnly = true;
return this;
}
/// <summary>
/// Returns aggregate hash code of all elements in this set.
/// </summary>
internal int GetElementsHashCode()
{
int hashCode = 0;
foreach (TElement element in this)
{
hashCode ^= Comparer.GetHashCode(element);
}
return hashCode;
}
/// <summary>
/// Returns typed enumerator over elements of the set.
/// Uses HashSet<TElement>.Enumerator to avoid boxing struct.
/// </summary>
public HashSet<TElement>.Enumerator GetEnumerator()
{
return _values.GetEnumerator();
}
[Conditional("DEBUG")]
private void AssertReadWrite()
{
Debug.Assert(!_isReadOnly, "attempting to modify readonly collection");
}
[Conditional("DEBUG")]
private void AssertSetCompatible(Set<TElement> other)
{
Debug.Assert(other != null, "other set null");
Debug.Assert(other.Comparer.GetType().Equals(this.Comparer.GetType()));
}
#endregion
#region IEnumerable<TElement> Members
public class Enumerator : IEnumerator<TElement>
{
private Dictionary<TElement, bool>.KeyCollection.Enumerator keys;
internal Enumerator(Dictionary<TElement, bool>.KeyCollection.Enumerator keys)
{
this.keys = keys;
}
public TElement Current { get { return keys.Current; } }
public void Dispose() { keys.Dispose(); }
object IEnumerator.Current { get { return ((IEnumerator)keys).Current; } }
public bool MoveNext() { return keys.MoveNext(); }
void System.Collections.IEnumerator.Reset() { ((System.Collections.IEnumerator)keys).Reset(); }
}
IEnumerator<TElement> IEnumerable<TElement>.GetEnumerator()
{
return this.GetEnumerator();
}
#endregion
#region IEnumerable Members
/// <summary>
/// Returns an untyped enumeration of elements in the set.
/// </summary>
/// <returns>Enumeration of set members.</returns>
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
#endregion
#region InternalBase
internal override void ToCompactString(StringBuilder builder)
{
StringUtil.ToCommaSeparatedStringSorted(builder, this);
}
#endregion
#region Nested types
private class SetValueComparer : IEqualityComparer<Set<TElement>>
{
bool IEqualityComparer<Set<TElement>>.Equals(Set<TElement> x, Set<TElement> y)
{
Debug.Assert(null != x && null != y, "comparer must be used only in context of Dictionary/HashSet");
return x.SetEquals(y);
}
int IEqualityComparer<Set<TElement>>.GetHashCode(Set<TElement> obj)
{
Debug.Assert(null != obj, "comparer must be used only in context of Dictionary/HashSet");
return obj.GetElementsHashCode();
}
}
#endregion
}
}
|