The List Trifecta, Part 1

namespace Loyc.Collections
{
	using System;
	using System.Diagnostics;
	using System.Threading;
	using System.Linq;

	/// <summary>The tail of a VList contains only one or two items. To improve 
	/// efficiency slightly, these two-item lists are represented by a
	/// VListBlockOfTwo, which is more compact than VListBlockArray.</summary>
	/// <remarks>
	/// TODO: create a more efficient version using a "fixed T _array2[2]" in an
	/// unsafe code block (assuming it is generics-compatible).
	/// </remarks>
	public sealed class VListBlockOfTwo<T> : VListBlock<T>
	{
		internal T _1;
		internal T _2;

		/// <summary>Initializes a mutable block with no items.</summary>
		public VListBlockOfTwo()
		{
			_immCount = MutableFlag;
		}
		public VListBlockOfTwo(T firstItem, bool mutable)
		{
			_1 = firstItem;
			_immCount = mutable ? MutableFlag : 1;
		}
		/// <summary>Initializes a block with two items.</summary>
		/// <remarks>The secondItem is added second, so it will occupy position [0]
		/// of a FVList or position [1] of an RVList.</remarks>
		public VListBlockOfTwo(T firstItem, T secondItem, bool mutable)
		{
			_1 = firstItem;
			_2 = secondItem;
			_immCount = mutable ? MutableFlag : 2;
		}

		public override int PriorCount { get { return 0; } }
		public override FVList<T> Prior { get { return new FVList<T>(); } }
		
		public override int Capacity { get { return 2; } }

		public override T this[int localIndex]
		{
			get {
				Debug.Assert(localIndex == 0 || localIndex == 1);
				if (localIndex == 0)
					return _1;
				else
					return _2;
			}
			set {
				Debug.Assert(localIndex >= ImmCount);
				Debug.Assert(localIndex == 0 || localIndex == 1);
				if (localIndex == 0)
					_1 = value;
				else
					_2 = value;
			}
		}
		public override T FGet(int index, int localCount)
		{
			Debug.Assert((uint)localCount <= 2);
			if ((uint)index >= (uint)localCount)
				throw new IndexOutOfRangeException();
			return index + 1 >= localCount ? _1 : _2;
		}
		public override bool FGet(int index, int localCount, ref T value)
		{
			Debug.Assert((uint)localCount <= 2);
			if ((uint)index >= (uint)localCount)
				return false;
			value = (index + 1 >= localCount ? _1 : _2);
			return true;
		}
		public override T RGet(int index, int localCount)
		{
			Debug.Assert((uint)localCount <= 2);
			if ((uint)index >= (uint)localCount)
				throw new IndexOutOfRangeException();
			return index == 0 ? _1 : _2;
		}
		public override bool RGet(int index, int localCount, ref T value)
		{
			Debug.Assert((uint)localCount <= 2);
			if ((uint)index >= (uint)localCount)
				return false;
			value = (index == 0 ? _1 : _2);
			return true;
		}

		public override T Front(int localCount)
		{
			Debug.Assert(localCount == 1 || localCount == 2);
			if (localCount == 1)
				return _1;
			else
				return _2;
		}

		public override VListBlock<T> Add(int localIndex, T item)
		{
			// localIndex == 0 is impossible, as the caller is only supposed to Add
			// items to the end of an immutable block, which is never empty.
			Debug.Assert(localIndex == 1 || localIndex == 2);

			if (localIndex == 1 && _immCount == 1) {
				if (Interlocked.CompareExchange(ref _immCount, 2, 1) == 1) {
					_2 = item;
					return this;
				}
			}
			return new VListBlockArray<T>(new FVList<T>(this, localIndex), item);
		}

		public override FVList<T> SubList(int localIndex)
		{
			if (localIndex <= 0)
				return new FVList<T>(); // empty
			else {
				Debug.Assert(localIndex <= Math.Min(_immCount, 2) && ImmCount <= 2);
				return new FVList<T>(this, localIndex);
			}
		}

		public override void MuClear(int localCountWithMutables)
		{
			Debug.Assert(IsMutable);
			Debug.Assert(ImmCount <= localCountWithMutables && localCountWithMutables <= 2);
			// If _localCount == 0 then there are no shared copies of this object, 
			// so this object is about to become garbage, and there is no need to 
			// clear the items. If _localCount is 2, there is nothing to clear.
			if (_immCount == 1)
				_2 = default(T);
			_immCount &= ImmCountMask;
		}

		protected override void BlockToArray(T[] array, int arrayOffset, int localCount, bool isRList)
		{
			if (localCount == 1) {
				array[arrayOffset] = _1;
			} else if (localCount == 2) {
				if (isRList) {
					array[arrayOffset] = _1;
					array[arrayOffset+1] = _2;
				} else {
					array[arrayOffset] = _2;
					array[arrayOffset+1] = _1;
				}
			} else
				Debug.Assert(localCount == 0);
		}

		#region LINQ-like methods

		public override FVList<T> Where(int localCount, Predicate<T> keep, WListProtected<T> forWList)
		{
			// Optimization
			
			Debug.Assert(localCount > 0);
			if (keep(_1))
			{
				if (localCount == 2) {
					if (keep(_2)) {
						_immCount = 2; // Mark immutable if it isn't already
						return MakeResult(this, 2, forWList);
					}
				}

				if (_immCount == MutableFlag)
					_immCount = 1; // Ensure first item is immutable

				return MakeResult(this, 1, forWList);
			}
			else
			{
				if (localCount == 2 && keep(_2))
					return MakeResult(_2, forWList);
				else
					return new FVList<T>();
			}
		}

		public override FVList<T> SmartSelect(int _localCount, Func<T, T> map, WListProtected<T> forWList)
		{
			// Optimization
			
			T item, item2;

			Debug.Assert(_localCount > 0);
			if (EqualityComparer.Equals(item = map(_1), _1))
			{
				if (_localCount == 2) {
					if (EqualityComparer.Equals(item2 = map(_2), _2)) {
						_immCount = 2; // Mark immutable if it isn't already
						return MakeResult(this, 2, forWList);
					} else {
						return MakeResult(item, item2, forWList);
					}
				} else {
					if (_immCount == MutableFlag)
						_immCount = 1; // Ensure first item is immutable

					return MakeResult(this, 1, forWList);
				}
			} else {
				if (_localCount == 2)
					return MakeResult(item, map(_2), forWList);
				else
					return MakeResult(item, forWList);
			}
		}

		#endregion
	}
}