The List Trifecta, Part 1

// Author: David Piepgrass
// License: LGPL
using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
using Loyc.Utilities;
using Loyc.Collections.Impl;
using NUnit.Framework;
using Loyc.Math;

namespace Loyc.Collections
{
	
	/// <summary>A mutable set.</summary>
	/// <remarks>This class uses less memory than <see cref="HashSet{T}"/> and, 
	/// under certain conditions, is faster. Specifically, this class is optimized
	/// for objects whose Equals() and GetHashCode() methods are fast, or for which
	/// equality is synonymous with "reference equality" so it is not necessary to
	/// call Equals() at all.
	/// </remarks>
	public class ObjectSet<T> : ICollection<T>, ICloneable<ObjectSet<T>>, ICount
		#if DotNet4
		, ISet<T>
		#endif
	{
		internal InternalSet<T> _set;
		internal IEqualityComparer<T> _comparer;
		internal int _count;
		
		public ObjectSet() { }
		public ObjectSet(IEnumerable<T> copy) { AddRange(copy); }
		public ObjectSet(IEnumerable<T> copy, IEqualityComparer<T> comparer) { _comparer = comparer; AddRange(copy); }
		public ObjectSet(IEqualityComparer<T> comparer) { _comparer = comparer; }
		public ObjectSet(InternalSet<T> set, IEqualityComparer<T> comparer) : this(set, comparer, set.Count()) { }
		internal ObjectSet(InternalSet<T> set, IEqualityComparer<T> comparer, int count)
		{
			_set = set;
			_comparer = comparer;
			_count = count;
			set.CloneFreeze();
		}

		internal InternalSet<T> InternalSet { get { return _set; } }
		public IEqualityComparer<T> Comparer { get { return _comparer; } }

		/// <summary>Adds the specified item to the set, or throws an exception if
		/// a matching item is already present.</summary>
		/// <exception cref="ArgumentException">The item already exists in the set.</exception>
		public void AddUnique(T item)
		{
			if (_set.Add(ref item, _comparer, false))
				_count++;
			throw new ArgumentException("The item already exists in the set.");
		}

		/// <summary>Searches for an item. If the item is found, the copy in the 
		/// set is returned in the 'item' parameter. Note: there is no reason to 
		/// call this method in a <see cref="SymbolSet"/> because the item reference
		/// will never change; call <see cref="Contains"/> instead.</summary>
		/// <returns>true if the item was found, false if not.</returns>
		public bool Find(ref T item)
		{
			return _set.Find(ref item, _comparer);
		}

		/// <summary>Adds the specified item to the set, and retrieves an existing 
		/// copy of the item if one existed. Note: there is no reason to call this
		/// method in a <see cref="SymbolSet"/> because if an item is found, it 
		/// will always be the exact same object that you searched for.</summary>
		/// <param name="item">An object to search for. If this method returns false,
		/// this parameter is changed to the existing value that was found in the
		/// collection.</param>
		/// <param name="replaceIfPresent">If true, and a matching item exists in
		/// the set, that item will be replaced with the specified new item. The
		/// old value will be returned in the 'item' parameter.</param>
		/// <returns>True if a new item was added, false if the item already 
		/// existed in the set.</returns>
		public bool AddOrFind(ref T item, bool replaceIfPresent)
		{
			if (_set.Add(ref item, _comparer, replaceIfPresent)) {
				_count++;
				return true;
			}
			return false;
		}

		/// <summary>Adds the specified item to the set.</summary>
		/// <param name="replaceIfPresent">If true, and a matching item is 
		/// already present in the set, the specified item replaces the existing 
		/// copy. If false, the existing copy is left alone. This parameter
		/// has no effect in a <see cref="SymbolSet"/>.</param>
		/// <returns>true if the item was new, false if it was already present.</returns>
		public bool Add(T item, bool replaceIfPresent)
		{
			return AddOrFind(ref item, replaceIfPresent);
		}

		/// <summary>Fast-clones the set in O(1) time.</summary>
		/// <remarks>
		/// Once the set is cloned, modifications to both sets take
		/// longer because portions of the set must be duplicated. See 
		/// <see cref="InternalSet{T}"/> for details about the fast-
		/// cloning technique.</remarks>
		public ObjectSet<T> Clone() { ObjectSet<T> c; Clone(out c); return c; }
		protected virtual void Clone(out ObjectSet<T> c)
		{
			c = new ObjectSet<T>(_set, _comparer, _count);
		}

		#region ICollection<T>

		/// <summary>Adds the specified item to the set if it is not present.</summary>
		/// <returns>true if the item was new, false if it was not added because
		/// it was already present.</returns>
		public bool Add(T item)
		{
			return AddOrFind(ref item, false);
		}
		void ICollection<T>.Add(T item) { Add(item); }
		public int AddRange(IEnumerable<T> items)
		{
			int added = _set.UnionWith(items, _comparer, true);
			_count += added;
			return added;
		}
		public void Clear()
		{
			_set.Clear();
			_count = 0;
		}
		public bool Contains(T item)
		{
			return _set.Find(ref item, _comparer);
		}
		public void CopyTo(T[] array, int arrayIndex)
		{
			if (_count > array.Length - arrayIndex)
				throw new ArgumentException(Localize.From("CopyTo: Insufficient space in supplied array"));
			_set.CopyTo(array, arrayIndex);
		}
		public int Count
		{
			get { return _count; }
		}
		public bool IsReadOnly
		{
			get { return false; }
		}
		public bool Remove(T item)
		{
			if (_set.Remove(item, _comparer)) {
				_count--;
				Debug.Assert(_count >= 0);
				return true;
			}
			return false;
		}
		public InternalSet<T>.Enumerator GetEnumerator()
		{
			return _set.GetEnumerator();
		}
		IEnumerator<T> IEnumerable<T>.GetEnumerator() { return GetEnumerator(); }
		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return GetEnumerator(); }

		#endregion

		#region ISet<T>: UnionWith, ExceptWith, IntersectWith, SymmetricIntersectWith

		/// <summary>Adds all items in the other set to this set.</summary>
		/// <remarks>Any items that are already present are left unmodified.</remarks>
		public void UnionWith(IEnumerable<T> other) { UnionWith(other, false); }
		public void UnionWith(IEnumerable<T> other, bool replaceIfPresent) { _count += _set.UnionWith(other, _comparer, replaceIfPresent); }
		public void UnionWith(ObjectSetI<T> other, bool replaceIfPresent = false) { _count += _set.UnionWith(other.InternalSet, _comparer, replaceIfPresent); }
		public void UnionWith(ObjectSet<T> other, bool replaceIfPresent = false) { _count += _set.UnionWith(other.InternalSet, _comparer, replaceIfPresent); }

		/// <summary>Removes all items from this set that are present in 'other'.</summary>
		/// <param name="other">The set whose members should be removed from this set.</param>
		public void ExceptWith(IEnumerable<T> other) { _count -= _set.ExceptWith(other, _comparer); }
		public void ExceptWith(ObjectSetI<T> other) { _count -= _set.ExceptWith(other.InternalSet, _comparer); }
		public void ExceptWith(ObjectSet<T> other) { _count -= _set.ExceptWith(other.InternalSet, _comparer); }

		/// <inheritdoc cref="InternalSet{T}.IntersectWith(IEnumerable{T}, IEqualityComparer{T})"/>
		public void IntersectWith(IEnumerable<T> other)
		{
			var otherOSet = other as ObjectSet<T>;
			if (otherOSet != null)
				IntersectWith(otherOSet);
			else
				_set.IntersectWith(other, _comparer); // relatively costly unless other is ISet<T>
		}
		/// <summary>Removes all items from this set that are not present in 'other'.</summary>
		public void IntersectWith(ObjectSetI<T> other) { _count -= _set.IntersectWith(other.InternalSet, other.Comparer); }
		/// <summary>Removes all items from this set that are not present in 'other'.</summary>
		public void IntersectWith(ObjectSet<T> other) { _count -= _set.IntersectWith(other.InternalSet, other.Comparer); }
		/// <summary>Removes all items from this set that are not present in 'other'.</summary>
		public void IntersectWith(ISet<T> other) { _count -= _set.IntersectWith(other); }

		/// <summary>Modifies the current set to contain only elements that were
		/// present either in this set or in the other collection, but not both.</summary>
		public void SymmetricExceptWith(IEnumerable<T> other) { SymmetricExceptWith(other, false); }
		/// <inheritdoc cref="InternalSet{T}.SymmetricExceptWith(IEnumerable{T}, IEqualityComparer{T}, bool)"/>
		public void SymmetricExceptWith(IEnumerable<T> other, bool xorDuplicates)
		                                                      { _count += _set.SymmetricExceptWith(other, _comparer, xorDuplicates); }
		public void SymmetricExceptWith(ObjectSetI<T> other)  { _count += _set.SymmetricExceptWith(other.InternalSet, _comparer); }
		public void SymmetricExceptWith(ObjectSet<T> other)   { _count += _set.SymmetricExceptWith(other.InternalSet, _comparer); }

		#endregion

		#region ISet<T>: IsSubsetOf, IsSupersetOf, Overlaps, IsProperSubsetOf, IsProperSupersetOf, SetEquals

		/// <summary>Returns true if all items in this set are present in the other set.</summary>
		public bool IsSubsetOf(IEnumerable<T> other) { return _set.IsSubsetOf(other, _comparer, _count); }
		public bool IsSubsetOf(ObjectSetI<T> other)  { return Count <= other.Count && _set.IsSubsetOf(other.InternalSet, other.Comparer); }
		public bool IsSubsetOf(ObjectSet<T> other)   { return Count <= other.Count &&_set.IsSubsetOf(other.InternalSet, other.Comparer); }
		public bool IsSubsetOf(ISet<T> other)        { return _set.IsSubsetOf(other, _count); }

		/// <summary>Returns true if all items in the other set are present in this set.</summary>
		public bool IsSupersetOf(IEnumerable<T> other) { return _set.IsSupersetOf(other, _comparer, _count); }
		public bool IsSupersetOf(ObjectSetI<T> other)  { return Count >= other.Count && _set.IsSupersetOf(other.InternalSet, _comparer); }
		public bool IsSupersetOf(ObjectSet<T> other)   { return Count >= other.Count && _set.IsSupersetOf(other.InternalSet, _comparer); }

		/// <summary>Returns true if this set contains at least one item from 'other'.</summary>
		public bool Overlaps(IEnumerable<T> other) { return _set.Overlaps(other, _comparer); }
		public bool Overlaps(ObjectSetI<T> other)  { return _set.Overlaps(other.InternalSet, _comparer); }
		public bool Overlaps(ObjectSet<T> other)   { return _set.Overlaps(other.InternalSet, _comparer); }

		/// <inheritdoc cref="InternalSet{T}.IsProperSubsetOf(ISet{T}, int)"/>
		public bool IsProperSubsetOf(ObjectSetI<T> other)  { return Count < other.Count && IsSubsetOf(other); }
		/// <inheritdoc cref="InternalSet{T}.IsProperSubsetOf(ISet{T}, int)"/>
		public bool IsProperSubsetOf(ObjectSet<T> other)   { return Count < other.Count && IsSubsetOf(other); }
		/// <inheritdoc cref="InternalSet{T}.IsProperSubsetOf(ISet{T}, int)"/>
		public bool IsProperSubsetOf(ISet<T> other)        { return _set.IsProperSubsetOf(other, _count); }
		/// <inheritdoc cref="InternalSet{T}.IsProperSubsetOf(IEnumerable{T}, IEqualityComparer{T}, int)"/>
		public bool IsProperSubsetOf(IEnumerable<T> other) { return _set.IsProperSubsetOf(other, _comparer, _count); }

		/// <inheritdoc cref="InternalSet{T}.IsProperSupersetOf(ISet{T}, IEqualityComparer{T}, int)"/>
		public bool IsProperSupersetOf(ObjectSetI<T> other)  { return Count > other.Count && IsSupersetOf(other); }
		/// <inheritdoc cref="InternalSet{T}.IsProperSupersetOf(ISet{T}, IEqualityComparer{T}, int)"/>
		public bool IsProperSupersetOf(ObjectSet<T> other)   { return Count > other.Count && IsSupersetOf(other); }
		/// <inheritdoc cref="InternalSet{T}.IsProperSupersetOf(ISet{T}, IEqualityComparer{T}, int)"/>
		public bool IsProperSupersetOf(ISet<T> other)        { return _set.IsProperSupersetOf(other, _comparer, _count); }
		/// <inheritdoc cref="InternalSet{T}.IsProperSupersetOf(IEnumerable{T}, IEqualityComparer{T}, int)"/>
		public bool IsProperSupersetOf(IEnumerable<T> other) { return _set.IsProperSupersetOf(other, _comparer, _count); }

		/// <inheritdoc cref="InternalSet{T}.SetEquals(ISet{T}, int)"/>
		public bool SetEquals(ObjectSetI<T> other) { return Count == other.Count && IsSubsetOf(other); }
		/// <inheritdoc cref="InternalSet{T}.SetEquals(ISet{T}, int)"/>
		public bool SetEquals(ObjectSet<T> other)   { return Count == other.Count && IsSubsetOf(other); }
		/// <inheritdoc cref="InternalSet{T}.SetEquals(ISet{T}, int)"/>
		public bool SetEquals(ISet<T> other)        { return _set.SetEquals(other, _count); }
		/// <inheritdoc cref="InternalSet{T}.SetEquals(IEnumerable{T}, IEqualityComparer{T}, int)"/>
		public bool SetEquals(IEnumerable<T> other) { return _set.SetEquals(other, _comparer, _count); }

		#endregion

		#region Operators: & | - ^
		// Note that if the two operands use different comparers or have different
		// types, the comparer and type of the left operand propagates to the 
		// result. When mixing ObjectSetI<T> and ObjectSet<T>, it is advisable
		// to use ObjectSetI<T> as the left-hand argument because the left-argument
		// is always freeze-cloned, which is a no-op for ObjectSetI<T>.

		public static ObjectSet<T> operator &(ObjectSet<T> a, ObjectSet<T> b)
			{ var r = a.Clone(); r.IntersectWith(b); return r; }
		public static ObjectSet<T> operator |(ObjectSet<T> a, ObjectSet<T> b)
			{ var r = a.Clone(); r.UnionWith(b); return r; }
		public static ObjectSet<T> operator -(ObjectSet<T> a, ObjectSet<T> b)
			{ var r = a.Clone(); r.ExceptWith(b); return r; }
		public static ObjectSet<T> operator ^(ObjectSet<T> a, ObjectSet<T> b)
			{ var r = a.Clone(); r.SymmetricExceptWith(b); return r; }
		public static ObjectSet<T> operator &(ObjectSet<T> a, ObjectSetI<T> b)
			{ var r = a.Clone(); r.IntersectWith(b); return r; }
		public static ObjectSet<T> operator |(ObjectSet<T> a, ObjectSetI<T> b)
			{ var r = a.Clone(); r.UnionWith(b); return r; }
		public static ObjectSet<T> operator -(ObjectSet<T> a, ObjectSetI<T> b)
			{ var r = a.Clone(); r.ExceptWith(b); return r; }
		public static ObjectSet<T> operator ^(ObjectSet<T> a, ObjectSetI<T> b)
			{ var r = a.Clone(); r.SymmetricExceptWith(b); return r; }
		public static explicit operator ObjectSet<T>(ObjectSetI<T> a)
			{ return new ObjectSet<T>(a.InternalSet, a.Comparer, a.Count); }

		#endregion
	}

	/// <summary>
	/// A mutable set of symbols.
	/// </summary><remarks>
	/// This is a very simple hashtrie optimized for symbols, based on 
	/// <see cref="InternalSet{T}"/>.
	/// <para/>
	/// Sorry, <c>null</c> is not permitted as a member of the set.
	/// </remarks>
	public class SymbolSet : ObjectSet<Symbol>, ICloneable<SymbolSet>
	{
		public SymbolSet() : base((IEqualityComparer<Symbol>)null) { }
		public SymbolSet(IEnumerable<Symbol> copy) : base(copy, null) { }
		public SymbolSet(InternalSet<Symbol> set) : base(set, null) { }
		internal SymbolSet(InternalSet<Symbol> set, int count) : base(set, null, count) { }

		public new SymbolSet Clone() { SymbolSet s; Clone(out s); return s; }
		protected sealed override void Clone(out ObjectSet<Symbol> c) { SymbolSet s; Clone(out s); c = s; }
		protected virtual void Clone(out SymbolSet s) { s = new SymbolSet(_set, _count); }
		
		#region Operators: & | - ^
		// Note that if the two operands use different comparers or have different
		// types, the comparer and type of the left operand propagates to the 
		// result. When mixing ObjectSetI<T> and ObjectSet<T>, it is advisable
		// to use ObjectSetI<T> as the left-hand argument because the left-argument
		// is always freeze-cloned, which is a no-op for ObjectSetI<T>.

		public static SymbolSet operator &(SymbolSet a, SymbolSet b)
			{ var r = a.Clone(); r.IntersectWith(b); return r; }
		public static SymbolSet operator |(SymbolSet a, SymbolSet b)
			{ var r = a.Clone(); r.UnionWith(b); return r; }
		public static SymbolSet operator -(SymbolSet a, SymbolSet b)
			{ var r = a.Clone(); r.ExceptWith(b); return r; }
		public static SymbolSet operator ^(SymbolSet a, SymbolSet b)
			{ var r = a.Clone(); r.SymmetricExceptWith(b); return r; }
		public static SymbolSet operator &(SymbolSet a, SymbolSetI b)
			{ var r = a.Clone(); r.IntersectWith(b); return r; }
		public static SymbolSet operator |(SymbolSet a, SymbolSetI b)
			{ var r = a.Clone(); r.UnionWith(b); return r; }
		public static SymbolSet operator -(SymbolSet a, SymbolSetI b)
			{ var r = a.Clone(); r.ExceptWith(b); return r; }
		public static SymbolSet operator ^(SymbolSet a, SymbolSetI b)
			{ var r = a.Clone(); r.SymmetricExceptWith(b); return r; }
		public static explicit operator SymbolSet(SymbolSetI a)
			{ return new SymbolSet(a.InternalSet, a.Count); }

		#endregion
	}

	[TestFixture]
	public class SymbolSetTests
	{
		[Test]
		public void Test()
		{
			// ObjectSet, ObjectSetI, SymbolSet, SymbolSetI and InternalSet remain
			// COMPLETELY UNTESTED!!!!
		}
	}
}