LinkRefList.cs

using System;
using UnityEngine;

using System.Collections.Generic;
using System.Diagnostics;
using Debug = UnityEngine.Debug;


namespace P8.Container {

	/**
	 * C#でマシな感じに抽象化したリンクリストの基底クラス。
	 * 標準ライブラリのリンクリストは要素からの逆引きにO(log(n))掛かってしまうが、これはO(1)で引ける。
	 * オーバーヘッドがある分べた書きには敵わないが、それなりに早い。
	 * ただし、同時に複数のリンクリストに登録する事はできない。
	 */
	public class LinkRefList< Elem > : IEnumerable<Elem>
		where Elem : class, LinkRefList<Elem>.IElem
	{
		// ---------------------------- public メンバ --------------------------------

		/** Foreachループ用のEnumerator */
		public struct Enumerator : IEnumerator<Elem> {
			public Elem Current => _cur.body;
			public Enumerator( LinkRefList<Elem> parent ) {
				_parent = parent;
				_cur = null;
				++parent._forLoopCnt;
			}
			public bool MoveNext() {
				// 遅延リリースが予約されているノードはスキップする
				do {
					if ( _cur == null )	_cur = _parent._data;
					else				_cur = _cur.next;
				} while ( _cur != null && _cur.isReservedFree );
				return _cur != null;
			}
			public void Reset() => _cur = null;
			public void Dispose() {
				// foreachループが全て抜けたタイミングで、遅延リリースを実行する
				if ( --_parent._forLoopCnt == 0 ) {
					_parent.releaseAllReserved();
				}
				_parent = null;
			}

			LinkRefList<Elem> _parent;
			Node _cur;
			object System.Collections.IEnumerator.Current => _cur.body;
		}

		/** リストの内容物となるものが実装しなければならないInterface */
		public interface IElem {
			INode linkNode{ get; set; }
		}

		/** ブールの内容物がリンクする対象。プール内のリンクリストで使用しているNodeのinterface */
		public interface INode {
			LinkRefList<Elem> Parent {get;}
			Elem Body {get;}
			INode Next {get;}
			INode Prev {get;}
		}

		public INode data => _data;			//!< データ本体

		public long count {get;private set;} = 0;	//!< 要素数。遅延リリースが予約されているものも含む場合がある

		/** 指定の内容物を、指定の内容物の次に追加する。 */
		public void pushBack( Elem elem, Elem before ) {
			if ( before == null ) { pushFront(elem); return; }
			var bNode = (Node)((IElem)before).linkNode;
			if ( bNode?.parent != this ) throw new ArgumentException( "target's parent is not me" );

			var node = (Node)((IElem)elem).linkNode;
			if ( node == null ) {
				((IElem)elem).linkNode = node = new Node(elem,this);
			} else {
				if ( node.parent != null ) throw new ArgumentException( "target is already inside a list" );
			}
			
			node.prev = bNode;
			node.next = bNode.next;
			bNode.next = node;
			if ( node.next == null )	_last = node;
			else						node.next.prev = node;
			++count;
		}

		/** 指定の内容物を、先頭に追加する。 */
		public void pushFront( Elem elem ) {
			var node = (Node)((IElem)elem).linkNode;
			if ( node == null ) {
				((IElem)elem).linkNode = node = new Node(elem,this);
			} else {
				if ( node.parent != null ) throw new ArgumentException( "target is already inside a list" );
			}
			
			node.next = _data;
			if ( _data == null )	_last = node;
			else					_data.prev = node;
			_data = node;
			++count;
		}

		/** 指定の内容物を、終端に追加する。 */
		public void pushLast( Elem elem ) {
			var node = (Node)((IElem)elem).linkNode;
			if ( node == null ) {
				((IElem)elem).linkNode = node = new Node(elem,this);
			} else {
				if ( node.parent != null ) throw new ArgumentException( "target is already inside a list" );
			}
			
			node.prev = _last;
			if ( _last == null )	_data = node;
			else					_last.next = node;
			_last = node;
			++count;
		}

		/**
		 * 指定の内容物をReleaseする。
		 * for loop中にこれが呼ばれた場合、autoReserveIfInLoopがtrueなら
		 * 自動的にrelease予約処理に切り替える。
		 */
		public bool remove( Elem elem, bool autoReserveIfInLoop = true ) {
			if ( _forLoopCnt != 0 ) {
				if ( autoReserveIfInLoop ) return reserveRelease( elem );
				throw new InvalidOperationException( "release is called in for loop" );
			}

			var node = (Node)((IElem)elem).linkNode;
			if ( node?.parent != this ) throw new ArgumentException( "target's parent is not me" );

			detachNode(node);
			--count;
			return true;
		}

		/** 指定の内容物の遅延Releaseを予約する。ループ中などでも呼ぶことができる */
		public bool reserveRelease( Elem elem ) {
			var node = (Node)((IElem)elem).linkNode;
			if ( node?.parent != this ) throw new ArgumentException( "target's parent is not me" );
			if ( node.isReservedFree ) return false;		// とりあえず多重リリースしても怒らない

			node.isReservedFree = true;
			isReleaseReserved_ = true;
			return true;
		}

		/**
		 * 遅延release指定されたノードをすべてリリースする。
		 * 遅延リリースを予約した場合は、後で必ずこれを呼ぶこと。
		 * foreachで回した場合は、自動的に呼ばれる。
		 */
		public void releaseAllReserved() {
			if ( _forLoopCnt != 0 ) throw new InvalidOperationException( "release is called in for loop" );

			if ( !isReleaseReserved_ ) return;
			isReleaseReserved_ = false;

			for ( var i = _data; i != null; ) {
				if ( i.isReservedFree ) {
					var node = i;
					i = i.next;

					detachNode(node);
					--count;
				} else {
					i = i.next;
				}
			}
		}

		// foreachループ用のEnumerator取得関数
		public Enumerator GetEnumerator() => new Enumerator( this );

		
		// ----------------------- private / protected メンバ --------------------------

		/** リンクリストのノード */
		protected class Node : INode {
			readonly public Elem body;
			public LinkRefList<Elem> parent = null;

			public Node prev = null, next = null;
			public bool isReservedFree = false;

			public Node( Elem body, LinkRefList<Elem> parent ) {
				this.body = body;
				this.parent = parent;
			}

			LinkRefList<Elem> INode.Parent => isReservedFree ? null : parent;
			Elem INode.Body => body;
			INode INode.Next => next;
			INode INode.Prev => prev;
		}

		protected Node _data, _last;		//!< リンクリストの先頭・終端
		int _forLoopCnt = 0;				//!< 現在のforループネスト数。ループ中にリリースが呼ばれないか監視する用
		bool isReleaseReserved_ = false;	//!< 遅延リリースが1つでも予約されたか否か

		/** 指定のノードをリンクリストから取り除く */
		Node detachNode( Node node ) {
			if ( node == _data ) _data = node.next;
			if ( node == _last ) _last = node.prev;
			if ( node.prev != null ) node.prev.next = node.next;
			if ( node.next != null ) node.next.prev = node.prev;
			node.prev = node.next = null;
			node.parent = null;
			node.isReservedFree = false;
			return node;
		}

		IEnumerator<Elem> IEnumerable<Elem>.GetEnumerator() => new Enumerator( this );
		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
		#if UNITY_EDITOR
			// VisualStudioなど、EnumeratorをDisposeしないDebuggerViewでバグらないために、
			// アタッチ中はnullを返すようにする
			if ( System.Diagnostics.Debugger.IsAttached ) return null;
		#endif
			return new Enumerator(this);
		}


		// ----------------------------------------------------------------------------
	}


}