The List Trifecta, Part 1

namespace Loyc.Collections.Impl
{
	using System;
	using System.Collections.Generic;
	using System.Linq;
	using System.Text;
	using System.Diagnostics;

	[Serializable]
	public abstract class AListInnerBase<K, T> : AListNode<K, T>
	{
		public const int DefaultMaxNodeSize = 16;

		protected struct Entry
		{
			// Normally this is the base index of the items in Node (the first entry 
			// uses Index differently; see documentation of _children)
			public uint Index;
			// Child node
			public AListNode<K, T> Node;
		}

		/// <summary>List of child nodes. Empty children are null.</summary>
		/// <remarks>
		/// *** TODO ***: don't increase _children size by 4. Increase it exponentially
		/// </remarks>
		protected Entry[] _children;

		#region Constructors

		protected AListInnerBase(AListInnerBase<K, T> frozen)
		{
			_children = InternalList.CopyToNewArray(frozen._children);
			_childCount = frozen._childCount;
			_maxNodeSize = frozen._maxNodeSize;
			_isFrozen = false;

			MarkChildrenFrozen();
			AssertValid();
		}
		private void MarkChildrenFrozen()
		{
			// Inform children that they are frozen
			for (int i = _childCount - 1; i >= 0; i--)
				_children[i].Node.Freeze();
		}

		public AListInnerBase(AListNode<K, T> left, AListNode<K, T> right, int maxNodeSize)
		{
			_children = new Entry[4];
			_childCount = 2;
			_children[0] = new Entry { Node = left, Index = 0 };
			_children[1] = new Entry { Node = right, Index = left.TotalCount };
			_children[2] = new Entry { Index = uint.MaxValue };
			_children[3] = new Entry { Index = uint.MaxValue };
			MaxNodeSize = maxNodeSize;
			AssertValid();
		}

		protected AListInnerBase(AListInnerBase<K,T> original, int localIndex, int localCount, uint baseIndex, int maxNodeSize)
		{
			// round up size to the nearest 4.
			_children = new Entry[(localCount + 3) & ~3];

			int i;
			for (i = 0; i < localCount; i++)
			{
				_children[i] = original._children[localIndex + i];
				_children[i].Index -= baseIndex;
			}
			_childCount = (byte)localCount;
			Debug.Assert(maxNodeSize <= MaxMaxNodeSize);
			MaxNodeSize = maxNodeSize;

			InitEmpties(i);
			AssertValid();
		}

		protected AListInnerBase(AListInnerBase<K, T> original, uint index, uint count, AListBase<K,T> list)
		{
			// This constructor is called by CopySection
			Debug.Assert(count > 0 && count <= original.TotalCount);
			int i0 = original.BinarySearchI(index);
			int iN = original.BinarySearchI(index + count - 1);
			Entry e0 = original._children[i0];
			Entry eN = original._children[iN];
			int localCount = iN - i0 + 1;
			// round up size to the nearest 4.
			_children = new Entry[(localCount + 3) & ~3];
			_isFrozen = false;
			_maxNodeSize = original._maxNodeSize;
			//_userByte = original._userByte;
			_childCount = (byte)localCount;
			InitEmpties(iN-i0+1);

			if (i0 == iN) {
				_children[0].Node = e0.Node.CopySection(index - e0.Index, count, list);
			} else {
				uint adjusted0 = index - e0.Index;
				uint adjustedN = index + count - eN.Index;
				Debug.Assert(adjusted0 <= index && adjustedN < count);
				AListNode<K, T> child0 = e0.Node.CopySection(adjusted0, e0.Node.TotalCount - adjusted0, list);
				AListNode<K, T> childN = eN.Node.CopySection(0, adjustedN, list);

				_children[0].Node = child0;
				_children[iN-i0].Node = childN;
				uint offset = child0.TotalCount;
				for (int i = i0+1; i < iN; i++)
				{
					AListNode<K, T> childI = original._children[i].Node;
					// Freeze child because it will be shared between the original 
					// list and the section being copied
					childI.Freeze();
					_children[i-i0] = new Entry { Node = childI, Index = offset };
					offset += childI.TotalCount;
				}
				_children[iN-i0].Index = offset;
		
				// Finally, if the first/last node is undersized, redistribute items.
				// Note: we can set the 'tob' parameter to null because this
				// constructor is called by CopySection, which creates an 
				// independent AList that does not have an indexer.
				while (_childCount > 1 && _children[0].Node.IsUndersized)
					HandleUndersized(0, null);
				while (_childCount > 1 && _children[_childCount - 1].Node.IsUndersized)
					HandleUndersized(_childCount - 1, null);
			}
			
			AssertValid();
		}

		#endregion

		private void InitEmpties(int at)
		{
			Debug.Assert(at == LocalCount);
			for (; at < _children.Length; at++) {
				Debug.Assert(_children[at].Node == null);
				_children[at].Index = uint.MaxValue;
			}
		}

		/// <summary>Performs a binary search for an index.</summary>
		/// <remarks>Optimized. Fastest for power-of-two node sizes.</remarks>
		public int BinarySearchI(uint index)
		{
			var children = _children; // might be faster
			Debug.Assert(children.Length < 256);
			
			int i = 2;
			if (children.Length > 4)
			{
				i = 8;
				if (children.Length > 16)
				{
					i = 32;
					if (children.Length > 64)
					{
						i = 128;
						i += ((uint)i < (uint)children.Length && index >= children[i].Index ? 64 : -64);
						i += ((uint)i < (uint)children.Length && index >= children[i].Index ? 32 : -32);
					}
					i += ((uint)i < (uint)children.Length && index >= children[i].Index ? 16 : -16);
					i += ((uint)i < (uint)children.Length && index >= children[i].Index ? 8 : -8);
				}
				i += ((uint)i < (uint)children.Length && index >= children[i].Index ? 4 : -4);
				i += ((uint)i < (uint)children.Length && index >= children[i].Index ? 2 : -2);
			}
			i += ((uint)i < (uint)children.Length && index >= children[i].Index ? 1 : -1);
			if (((uint)i >= (uint)children.Length || index < children[i].Index))
				--i;
			return i;
		}

		protected void PrepareToInsert(int i, IAListTreeObserver<K, T> tob)
		{
			AutoClone(ref _children[i].Node, this, tob);

			if (_children[i].Node.IsFullLeaf)
				TryToShiftAnItemToSiblingOfLeaf(i, tob);
		}
		protected void TryToShiftAnItemToSiblingOfLeaf(int i, IAListTreeObserver<K, T> tob)
		{
			AListNode<K, T> childL, childR;
			
			// Check the left sibling
			if (i > 0 && (childL = _children[i - 1].Node).TakeFromRight(_children[i].Node, tob) != 0)
				_children[i].Index++;
			// Check the right sibling
			else if (i + 1 < _children.Length &&
				(childR = _children[i + 1].Node) != null && childR.TakeFromLeft(_children[i].Node, tob) != 0)
				_children[i + 1].Index--;
		}

		/// <summary>Inserts a slot after _children[i], increasing _childCount and 
		/// replacing [i] and [i+1] with splitLeft and splitRight. Notifies 'tob' 
		/// of the replacement, and checks whether this node itself needs to split.</summary>
		/// <returns>Value of splitLeft to be returned to parent (non-null if splitting)</returns>
		protected AListInnerBase<K, T> HandleChildSplit(int i, AListNode<K, T> splitLeft, ref AListNode<K, T> splitRight, IAListTreeObserver<K, T> tob)
		{
			Debug.Assert(splitLeft != null && splitRight != null);

			if (tob != null) tob.HandleChildReplaced(_children[i].Node, splitLeft, splitRight, this);

			_children[i].Node = splitLeft;

			LLInsert(i + 1, splitRight, 0);
			_children[i + 1].Index = _children[i].Index + splitLeft.TotalCount;
			AssertValid();

			// Does this node need to split too?
			return AutoSplit(out splitRight);
		}

		protected virtual AListInnerBase<K, T> AutoSplit(out AListNode<K, T> splitRight)
		{
			if (_childCount > _maxNodeSize) {
				return SplitAt(LocalCount >> 1, out splitRight);
			} else {
				splitRight = null;
				return null;
			}
		}

		/// <summary>Splits this node into two halves</summary>
		/// <param name="divAt">Index into _children where the right half starts</param>
		/// <param name="right">An AListInner node containing the right children</param>
		/// <returns>An AListInner node containing the left children</returns>
		protected abstract AListInnerBase<K, T> SplitAt(int divAt, out AListNode<K, T> right);

		public override T GetLastItem()
		{
			return _children[LocalCount-1].Node.GetLastItem();
		}

		[Conditional("DEBUG")]
		protected void AssertValid()
		{
			Debug.Assert(_childCount <= _children.Length);
			if (_childCount != 0)
				Debug.Assert(_children[0].Node != null && _children[0].Index == 0);
			else
				Debug.Assert(_children[0].Node == null && _children[0].Index == uint.MaxValue);

			uint @base = 0;
			int i;
			for (i = 1; i < _childCount; i++) {
				Debug.Assert(_children[i].Node != null);
				Debug.Assert(_children[i].Index == (@base += _children[i-1].Node.TotalCount));
			}
			for (; i < _children.Length; i++) {
				Debug.Assert(_children[i].Node == null);
				Debug.Assert(_children[i].Index == uint.MaxValue);
			}
		}

		/// <summary>Inserts a child node into _children at index i (resizing 
		/// _children if necessary), increments _childCount, and adds 
		/// indexAdjustment to _children[j].Index for all j>i (indexAdjustment can
		/// be 0 if i==_childCount).</summary>
		/// <remarks>Derived classes can override to add their own bookkeeping.</remarks>
		protected virtual void LLInsert(int i, AListNode<K, T> child, uint indexAdjustment)
		{
			AutoEnlargeChildren(1);
			for (int j = LocalCount; j > i; j--)
				_children[j] = _children[j - 1]; // insert room
			_children[i].Node = child;
			++_childCount; // increment LocalCount
			if (indexAdjustment != 0)
				AdjustIndexesAfter(i, (int)indexAdjustment);
		}

		protected void AdjustIndexesAfter(int i, int indexAdjustment)
		{
			int lcount = LocalCount;
			for (i++; i < lcount; i++)
				_children[i].Index += (uint)indexAdjustment;
		}

		public AListNode<K, T> Child(int i)
		{
			return _children[i].Node;
		}

		public sealed override int LocalCount
		{
			get {
				return (byte)_childCount;
			}
		}

		protected const int MaxMaxNodeSize = 0xFF;
		protected const uint FrozenBit = 0x8000;

		protected int MaxNodeSize
		{
			get { return _maxNodeSize; }
			set { _maxNodeSize = (byte)value; }
		}

		public sealed override uint TotalCount
		{
			get {
				int lc = LocalCount;
				if (lc == 0)
					return 0;
				Entry e = _children[lc - 1];
				return e.Index + e.Node.TotalCount;
			}
		}

		public sealed override bool IsFullLeaf
		{
			get { return false; }
		}
		public override bool IsUndersized
		{
			get { return (_childCount << 1) < _maxNodeSize; }
		}

		public override T this[uint index]
		{
			get {
				int i = BinarySearchI(index);
				return _children[i].Node[index - _children[i].Index];
			}
		}

		public override void SetAt(uint index, T item, IAListTreeObserver<K, T> tob)
		{
			Debug.Assert(!IsFrozen);
			int i = BinarySearchI(index);
			AutoClone(ref _children[i].Node, this, tob);
			var e = _children[i];
			index -= e.Index;
			e.Node.SetAt(index, item, tob);
		}

		internal uint ChildIndexOffset(int i)
		{
			Debug.Assert(i < _childCount);
			return _children[i].Index;
		}

		public override bool RemoveAt(uint index, uint count, IAListTreeObserver<K, T> tob)
		{
			Debug.Assert(!IsFrozen);
			AssertValid();
			Debug.Assert(index + count <= TotalCount && (int)(count|index) >= 0);
			bool undersizedOrAggChg = false;
			
			while (count != 0)
			{
				int i = BinarySearchI(index + count - 1);
				var e = _children[i];

				uint adjustedCount = count;
				uint adjustedIndex = index - e.Index;
				if (index <= e.Index)
				{
					adjustedCount = count + index - e.Index;
					adjustedIndex = 0;
					if (adjustedCount == e.Node.TotalCount && tob == null)
						e.Node = null; // check below
				}

				if (e.Node == null) {
					// The child will be empty after the remove operation, so we
					// can simply delete it without looking at it. This is not
					// required for correctness, but we do this optimization so 
					// that RemoveSection() runs in O(log N) time.
					Debug.Assert(tob == null);
					undersizedOrAggChg |= LLDelete(i, true);
					if (!undersizedOrAggChg && IsUndersized)
						undersizedOrAggChg = true;
				} else {
					if (AutoClone(ref e.Node, this, tob))
						_children[i].Node = e.Node;
					bool result = e.Node.RemoveAt(adjustedIndex, adjustedCount, tob);

					AdjustIndexesAfter(i, -(int)adjustedCount);
					if (result)
						undersizedOrAggChg |= HandleUndersizedOrAggregateChanged(i, tob);
				}
				AssertValid();
				count -= adjustedCount;
			}
			return undersizedOrAggChg;
		}

		internal AListInnerBase<K, T> HandleChildCloned(int i, AListNode<K, T> childClone, IAListTreeObserver<K, T> tob)
		{
			Debug.Assert(childClone.LocalCount == _children[i].Node.LocalCount);
			Debug.Assert(childClone.TotalCount == _children[i].Node.TotalCount);
			if (tob != null) tob.HandleChildReplaced(_children[i].Node, childClone, null, this);

			var self = this;
			if (IsFrozen)
				self = (AListInnerBase<K, T>) DetachedClone();
			self._children[i].Node = childClone;
			return self != this ? self : null;
		}

		protected virtual bool HandleUndersizedOrAggregateChanged(int i, IAListTreeObserver<K, T> tob)
		{
			if (_children[i].Node.IsUndersized)
				return HandleUndersized(i, tob);
			return false;
		}

		/// <summary>
		/// This is called by RemoveAt(), DoSingleOperation() for B+ trees, or by
		/// the constructor called by CopySection(), when child [i] drops below its 
		/// normal size range. We'll either distribute the child's items to its 
		/// siblings, or transfer ONE item from a sibling to increase the node's 
		/// size.
		/// </summary>
		/// <param name="i">Index of undersized child</param>
		/// <param name="tob">Observer to notify about node movements</param>
		/// <returns>True iff this node has become undersized.</returns>
		protected virtual bool HandleUndersized(int i, IAListTreeObserver<K, T> tob)
		{
			AListNode<K, T> node = _children[i].Node;
			Debug.Assert(!node.IsFrozen);

			// Examine the fullness of the siblings of e.Node.
			uint ui = (uint)i;
			AListNode<K, T> left = null, right = null;
			int leftCap = 0, rightCap = 0;
			if (ui-1u < (uint)_children.Length) {
				AutoClone(ref _children[ui-1u].Node, this, tob);
				left = _children[ui-1u].Node;
				leftCap = left.CapacityLeft;
			}
			if (ui + 1u < (uint)LocalCount) {
				AutoClone(ref _children[ui+1u].Node, this, tob);
				right = _children[ui+1u].Node;
				rightCap = right.CapacityLeft;
			}

			// If the siblings have enough capacity...
			if (leftCap + rightCap >= node.LocalCount)
			{
				// Unload data from 'node' into its siblings
				int oldRightCap = rightCap;
				uint rightAdjustment = 0, a;
				while (node.LocalCount > 0)
					if (leftCap >= rightCap) {
						Verify(left.TakeFromRight(node, tob) != 0);
						leftCap--;
					} else {
						Verify((a = right.TakeFromLeft(node, tob)) != 0);
						rightAdjustment += a;
						rightCap--;
					}
					
				if (rightAdjustment != 0) // if rightAdjustment==0, _children[i+1] might not exist
					_children[i+1].Index -= rightAdjustment;

				if (tob != null) tob.NodeRemoved(node, this);
				LLDelete(i, false);
				// Return true if this node has become undersized.
				return IsUndersized;
			}
			else if (left != null || right != null)
			{	// Transfer an element from the fullest sibling so that 'node'
				// is no longer undersized.
				if (left == null)
					leftCap = int.MaxValue;
				if (right == null)
					rightCap = int.MaxValue;
				if (leftCap < rightCap) {
					Debug.Assert(i > 0);
					uint amt = node.TakeFromLeft(left, tob);
					Debug.Assert(amt > 0);
					_children[i].Index -= amt;
				} else {
					uint amt = node.TakeFromRight(right, tob);
					Debug.Assert(amt > 0);
					_children[i+1].Index += amt;
				}
			}
			return false;
		}

		/// <summary>Deletes the child _children[i], shifting all entries afterward 
		/// to the left, and decrements _childCount. If adjustIndexesAfterI is true,
		/// the values of _children[j].Index where j>i are decreased appropriately.</summary>
		/// <returns>True if the aggregate value of this node may have changed (organized lists only)</returns>
		/// <remarks>Derived classes can override to add their own bookkeeping.</remarks>
		protected virtual bool LLDelete(int i, bool adjustIndexesAfterI)
		{
			int newCCount = LocalCount - 1;
			if (i < newCCount) {
				if (adjustIndexesAfterI)
				{
					uint indexAdjustment = _children[i + 1].Index - _children[i].Index;
					AdjustIndexesAfter(i, -(int)indexAdjustment);
				}
				for (int j = i; j < newCCount; j++)
					_children[j] = _children[j + 1];
			}
			_children[newCCount] = new Entry { Node = null, Index = uint.MaxValue };
			_childCount--;
			return false;
		}

		internal override uint TakeFromRight(AListNode<K, T> sibling, IAListTreeObserver<K, T> tob)
		{
			var right = (AListInnerBase<K, T>)sibling;
			if (IsFrozen || right.IsFrozen)
				return 0;
			uint oldTotal = TotalCount;
			int oldLocal = LocalCount;
			var child = right.Child(0);
			LLInsert(oldLocal, child, 0);
			Debug.Assert(oldLocal > 0);
			_children[oldLocal].Index = oldTotal;
			right.LLDelete(0, true);
			AssertValid();
			right.AssertValid();
			if (tob != null) tob.NodeMoved(child, right, this);
			return child.TotalCount;
		}

		internal override uint TakeFromLeft(AListNode<K, T> sibling, IAListTreeObserver<K, T> tob)
		{
			Debug.Assert(!IsFrozen);
			var left = (AListInnerBase<K, T>)sibling;
			if (IsFrozen || left.IsFrozen)
				return 0;
			var child = left.Child(left.LocalCount - 1);
			LLInsert(0, child, child.TotalCount);
			left.LLDelete(left.LocalCount - 1, false);
			AssertValid();
			left.AssertValid();
			if (tob != null) tob.NodeMoved(child, left, this);
			return child.TotalCount;
		}

		public override void Freeze()
		{
			_isFrozen = true;
		}

		public override int CapacityLeft { get { return MaxNodeSize - LocalCount; } }

		public void AutoEnlargeChildren(int more)
		{
			if (_childCount + more > _children.Length)
			{
				int newCapacity = InternalList.NextLargerSize(_childCount + more - 1, _maxNodeSize);
				_children = InternalList.CopyToNewArray(_children, _childCount, newCapacity);
				InitEmpties(_childCount);
			}
		}

		public uint BaseIndexOf(AListNode<K, T> child)
		{
			int i = IndexOf(child);
			if (i <= 0)
				return (uint)i;
			return _children[i].Index;
		}
		public int IndexOf(AListNode<K, T> child)
		{
			for (int i = 0; i < _children.Length; i++)
				if (_children[i].Node == child)
					return i;
			return -1;
		}

		public override int ImmutableCount()
		{
			if (IsFrozen)
				return (int)TotalCount;
			int ic = 0;
			for (int i = 0; i < _childCount; i++)
				ic += Child(i).ImmutableCount();
			return ic;
		}
	}
}