LinkedList<T>

// System.LinkedList — System.Core (decompiled from Larva HIR)

into namespace System
{
	/// A doubly linked list: adding and removing at either end, or next to a node, costs the same at any size.
	/// `loop (T x in list)` walks it from the first node.
	public class LinkedList<T>
	{
		LinkedListNode<T>? first;
		LinkedListNode<T>? last;
		i32 count;

		[NoInline]
		static NotHere()
		{
			throw new InvalidOperationError("the node is not in this list");
		}

		Owns(LinkedListNode<T> node)
		{
			if (node.List is not LinkedList<T> owner || owner != this)
				NotHere();
		}

		public:
			AddFirst(T value) : LinkedListNode<T>
			{
				LinkedListNode<T> node = new LinkedListNode<T>(value);
				node.Link(this, null, first);
				if (first is LinkedListNode<T> old)
					old.SetPrevious(node);
				else
					last = node;
				first = node;
				count++;
				return node;
			}

			AddLast(T value) : LinkedListNode<T>
			{
				LinkedListNode<T> node = new LinkedListNode<T>(value);
				node.Link(this, last, null);
				if (last is LinkedListNode<T> old)
					old.SetNext(node);
				else
					first = node;
				last = node;
				count++;
				return node;
			}

			/// A new node with `value` just before `node`.
			AddBefore(LinkedListNode<T> node, T value) : LinkedListNode<T>
			{
				Owns(node);
				if (node.Previous is not LinkedListNode<T> before)
					return AddFirst(value);
				LinkedListNode<T> made = new LinkedListNode<T>(value);
				made.Link(this, before, node);
				before.SetNext(made);
				node.SetPrevious(made);
				count++;
				return made;
			}

			/// A new node with `value` just after `node`.
			AddAfter(LinkedListNode<T> node, T value) : LinkedListNode<T>
			{
				Owns(node);
				if (node.Next is not LinkedListNode<T> after)
					return AddLast(value);
				LinkedListNode<T> made = new LinkedListNode<T>(value);
				made.Link(this, node, after);
				node.SetNext(made);
				after.SetPrevious(made);
				count++;
				return made;
			}

			/// Takes `node` out of the list.
			Remove(LinkedListNode<T> node)
			{
				Owns(node);
				LinkedListNode<T>? before = node.Previous;
				LinkedListNode<T>? after = node.Next;
				if (before is LinkedListNode<T> b)
					b.SetNext(after);
				else
					first = after;
				if (after is LinkedListNode<T> a)
					a.SetPrevious(before);
				else
					last = before;
				node.Link(null, null, null);
				count--;
			}

			/// Takes the first node out; its value.
			RemoveFirst() : T
			{
				if (first is LinkedListNode<T> node)
				{
					Remove(node);
					return node.Value;
				}
				throw new InvalidOperationError("the list is empty");
			}

			/// Takes the last node out; its value.
			RemoveLast() : T
			{
				if (last is LinkedListNode<T> node)
				{
					Remove(node);
					return node.Value;
				}
				throw new InvalidOperationError("the list is empty");
			}

			/// The first node whose value `match` accepts (null when none does).
			Find(func<T> : bool match) : LinkedListNode<T>?
			{
				LinkedListNode<T>? at = first;
				loop (at is LinkedListNode<T> node)
				{
					if (match(node.Value))
						return node;
					at = node.Next;
				}
				return null;
			}

			Clear()
			{
				LinkedListNode<T>? at = first;
				loop (at is LinkedListNode<T> node)
				{
					at = node.Next;
					node.Link(null, null, null);
				}
				first = null;
				last = null;
				count = 0;
			}

			/// The values in order, as an array.
			ToArray() : T[]
			{
				T[] items = new T[count];
				i32 i = 0;
				LinkedListNode<T>? at = first;
				loop (at is LinkedListNode<T> node)
				{
					items[i] = node.Value;
					i++;
					at = node.Next;
				}
				return items;
			}

			Iterator() : LinkedListIterator<T> => new LinkedListIterator<T>(first);

			i32 Count
			{
				get => count;
			}

			LinkedListNode<T>? First
			{
				get => first;
			}

			LinkedListNode<T>? Last
			{
				get => last;
			}
	}
}