/*
	Copyright (C) 2006 Christopher E. Miller
	
	This software is provided 'as-is', without any express or implied
	warranty.  In no event will the authors be held liable for any damages
	arising from the use of this software.
	
	Permission is granted to anyone to use this software for any purpose,
	including commercial applications, and to alter it and redistribute it
	freely, subject to the following restrictions:
	
	1. The origin of this software must not be misrepresented; you must not
	   claim that you wrote the original software. If you use this software
	   in a product, an acknowledgment in the product documentation would be
	   appreciated but is not required.
	2. Altered source versions must be plainly marked as such, and must not be
	   misrepresented as being the original software.
	3. This notice may not be removed or altered from any source distribution.
*/


/**
	$(LINK2 http://www.dprogramming.com/_list.php,Linked _list; _list.d 2.1.2).
	This circular linked _list adds the $(I next) and $(I previous) pointers directly into your data structure
	(struct or class) using a $(LINK2 http://www.digitalmars.com/d/mixin.html,mixin) so that no extra
	memory allocations are needed to add items to the _list.
	It is even possible to have more than one linked _list per data structure by making use of mixin identifiers.
	$(BR)$(BR)The documentation file can be compiled to test the below example.
**/

/+++
Example:
---
module people;
private import std.stdio;
private import list;

class Person
{
	mixin List; // Turn the Person class into a linked list.
	
	string name;
	ubyte age;
	
	this(string name, ubyte age)
	{
		this.name = name;
		this.age = age;
	}
}

int main()
{
	Person.ListHead people;
	people ~= new Person("John", 19);
	people ~= new Person("Paul", 31);
	people ~= new Person("George", 44);
	people ~= new Person("Ringo", 41);
	
	foreach(Person p; people.each)
	{
		writefln("Person %s is %d years old", p.name, p.age);
	}
	
	return 0;
}
---
+/
module list;


/+
/// Access for list-modifying members of List.
enum ListAccess
{
	PUBLIC,
	PROTECTED,
	PRIVATE,
	PACKAGE,
}
+/


/// Mixin for creating circular linked lists.
template List()
{
	alias typeof(this) PType;
	
	protected PType _prev, _next;
	
	final:
	
	/+
	static if(LIST_ACCESS == ListAccess.PUBLIC)
	{
		public: ;
	}
	else static if(LIST_ACCESS == ListAccess.PROTECTED)
	{
		protected: ;
	}
	else static if(LIST_ACCESS == ListAccess.PRIVATE)
	{
		private: ;
	}
	else static if(LIST_ACCESS == ListAccess.PACKAGE)
	{
		package: ;
	}
	+/
	
	
	/// Property: get previous item in the list. null if not belonging to a list.
	public PType prev() // getter
	{
		return _prev;
	}
	
	
	/// Property: get _next item in the list. null if not belonging to a list.
	public PType next() // getter
	{
		return _next;
	}
	
	
	/// Begin a list with this item. Must not already belong to a list. It is not necessary to keep this item as the list head.
	void beginList()
	in
	{
		assert(_prev is null);
		assert(_next is null);
	}
	body
	{
		_prev = this;
		_next = this;
	}
	
	
	private static void _list_add_between(PType add, PType before, PType after)
	in
	{
		assert(add._prev is null);
		assert(add._next is null);
		assert(before._prev !is null);
		assert(before._next !is null);
		assert(after._prev !is null);
		assert(after._next !is null);
	}
	body
	{
		add._prev = before;
		add._next = after;
		after._prev = add;
		before._next = add;
	}
	
	
	/// Property: get whether or not the list is empty.
	public bool listIsEmpty() // getter
	{
		return _prev is null;
	}
	
	
	/// Add an item after this one. item must not already belong to a list.
	void listAdd(PType item)
	{
		_list_add_between(item, this, _next);
	}
	
	
	/// Same as listAdd but will beginList() automatically if needed.
	void listAddSafe(PType item)
	{
		if(listIsEmpty)
			beginList();
		return listAdd(item);
	}
	
	
	/// Add an item before this one. item must not already belong to a list.
	void listAddTail(PType item)
	{
		_list_add_between(item, _prev, this);
	}
	
	
	/// Same as listAddTail but will beginList() automatically if needed.
	void listAddTailSafe(PType item)
	{
		if(listIsEmpty)
			beginList();
		return listAddTail(item);
	}
	
	
	/// Shortcut for listAddTailSafe(item).
	void opCatAssign(PType item)
	{
		listAddTailSafe(item);
	}
	
	
	/// Remove this item from the list. Must belong to a list.
	void listRemove()
	in
	{
		assert(_prev !is null);
		assert(_next !is null);
	}
	body
	{
		_prev._next = _next;
		_next._prev = _prev;
		
		_next = null;
		_prev = null;
	}
	
	
	/// Remove this item from the list. It is safe to call this even if not belonging to a list.
	void unlist()
	{
		if(!_prev)
		{
			assert(_next is null);
			return;
		}
		else if(!_next)
		{
			assert(_prev is null); // Always fails here.
			return;
		}
		
		if(this is _prev)
		{
			assert(this is _next);
			return;
		}
		else if(this is _next)
		{
			assert(this is _prev); // Always fails here.
			return;
		}
		
		listRemove();
	}
	
	
	/// Calls back callback for each item in the list, allowing the item to be removed. Only the item being called back may be removed during filter. Removed items must not be deleted until the end of filter. callback can return false to stop filter early.
	/// Returns: the item started on, one of its next items if removed during filter, or null if all items removed.
	PType filter(bool delegate(PType) callback)
	in
	{
		assert(_prev !is null);
		assert(_next !is null);
	}
	body
	{
		PType start = this;
		PType cur, nxt = this;
		bool bc;
		for(;;)
		{
			cur = nxt;
			nxt = nxt.next;
			bc = callback(cur);
			if(cur.next !is nxt)
			{
				// cur was removed.
				if(cur is start)
				{
					if(!nxt.next)
						return null; // All items removed.
					if(start is nxt)
					{
						// At last one.
						start = nxt;
						break;
					}
					start = nxt;
					if(!bc)
						break;
					continue;
				}
			}
			if(!bc)
				break;
			if(start is nxt)
				break; // At last one.
		}
		return start;
	}
	
	
	private struct ListEach
	{
		private PType start;
		
		
		public int opApply(int delegate(inout PType) dg)
		{
			int result = 0;
			if(start)
			{
				PType cur = start;
				do
				{
					result = dg(cur);
					if(result)
						break;
					cur = cur._next;
				}
				while(cur !is start);
			}
			return result;
		}
		
		
		private struct ListEachBackwards
		{
			private PType start;
			
			
			public int opApply(int delegate(inout PType) dg)
			{
				int result = 0;
				if(start)
				{
					PType cur = start._prev;
					for(;;)
					{
						result = dg(cur);
						if(result)
							break;
						if(cur is start)
							break;
						cur = cur._prev;
					}
				}
				return result;
			}
		}
		
		
		public ListEachBackwards backwards() // getter
		in
		{
			if(start)
			{
				assert(start._prev !is null);
				assert(start._next !is null);
			}
		}
		body
		{
			ListEachBackwards fe;
			fe.start = start;
			return fe;
		}
	}
	
	
	/// Property: get an enumerator for foreach to loop over all items, starting at this one and stopping when all have been encountered.
	/// each.backwards can be used to foreach over all items in reverse order, starting with the previous one and stopping on this as the last one.
	/// List items must not be added or removed during $(LINK2 http://www.digitalmars.com/d/statement.html#foreach , foreach) - use filter for such modifications.
	public ListEach each() // getter
	in
	{
		assert(_prev !is null);
		assert(_next !is null);
	}
	body
	{
		ListEach fe;
		fe.start = this;
		return fe;
	}
	
	
	private struct ListEndless
	{
		private PType start;
		
		
		public int opApply(int delegate(inout PType) dg)
		{
			int result = 0;
			if(start)
			{
				PType cur = start;
				for(;;)
				{
					result = dg(cur);
					if(result)
						break;
					cur = cur._next;
				}
			}
			return result;
		}
		
		
		private struct ListEndlessBackwards
		{
			private PType start;
			
			
			public int opApply(int delegate(inout PType) dg)
			{
				int result = 0;
				if(start)
				{
					PType cur = start._prev;
					for(;;)
					{
						result = dg(cur);
						if(result)
							break;
						cur = cur._prev;
					}
				}
				return result;
			}
		}
		
		
		public ListEndlessBackwards backwards() // getter
		in
		{
			if(start)
			{
				assert(start._prev !is null);
				assert(start._next !is null);
			}
		}
		body
		{
			ListEndlessBackwards fe;
			fe.start = start;
			return fe;
		}
	}
	
	
	/// Property: get an enumerator for foreach to loop over all items, starting at this one and continuously looping until foreach breaks.
	/// endless.backwards can be used to foreach over all items in reverse order, starting with the previous one and continuously looping until foreach breaks.
	/// List items must not be added or removed during $(LINK2 http://www.digitalmars.com/d/statement.html#foreach , foreach) - use filter for such modifications.
	public ListEndless endless() // getter
	in
	{
		assert(_prev !is null);
		assert(_next !is null);
	}
	body
	{
		ListEndless fe;
		fe.start = this;
		return fe;
	}
	
	
	/// Skips n items and returns that item. n may be negative. Skipping wraps around if not enough items.
	public PType listSkip(int n)
	{
		if(n >= 0)
		{
			foreach(PType onitem; endless)
			{
				if(!n)
					return onitem;
				n--;
			}
		}
		else
		{
			assert(n < 0);
			foreach(PType onitem; endless.backwards)
			{
				n++;
				if(!n)
					return onitem;
			}
		}
	}
	
	
	/// Returns the _item if item is part of this list, otherwise returns null.
	public PType listFind(PType item)
	{
		foreach(PType onitem; each)
		{
			if(onitem is item)
				return onitem;
		}
		return null;
	}
	
	
	/// Calls back compare for each item in the list; when compare returns true, listFind returns that item; or listFind returns null if compare never returns true.
	public PType listFind(bool delegate(PType item) compare)
	{
		foreach(PType onitem; each)
		{
			if(compare(onitem))
				return onitem;
		}
		return null;
	}
	
	
	/// Property: get the count of items in the list. This causes the list to be traversed.
	public size_t listLength() // getter
	{
		size_t result = 0;
		foreach(PType onitem; each)
		{
			result++;
		}
		return result;
	}
	
	
	/+
	/// Join this list with another.
	void listJoin(PType otherList)
	{
	}
	+/
	
	
	/// Property: get a ListHead for this item.
	ListHead listHead() // getter
	{
		ListHead result;
		result._head = this;
		return result;
	}
	
	
	/// Designating an item to be the list's head.
	public struct ListHead
	{
		protected PType _head = null;
		
		
		/// Property: get first item, or null if none.
		PType head() // getter
		{
			return _head;
		}
		
		
		/// Property: get last item, or null if none.
		PType tail() // getter
		{
			if(!_head)
				return null;
			return _head.prev;
		}
		
		
		/// Property: get whether or not the list is empty.
		bool isEmpty() // getter
		{
			if(_head)
				assert(!_head.listIsEmpty);
			return _head is null;
		}
		
		
		/// Adds a new item to the list, making a new head.
		void addHead(PType item)
		{
			if(_head)
			{
				_head.prev.listAdd(item);
				_head = item;
			}
			else
			{
				item.beginList();
				_head = item;
			}
		}
		
		
		/// Adds a new item to the list, making a new tail.
		void addTail(PType item)
		{
			if(_head)
			{
				_head.listAddTail(item);
			}
			else
			{
				item.beginList();
				_head = item;
			}
		}
		
		
		/// Shortcut for addTail(item).
		void opCatAssign(PType item)
		{
			addTail(item);
		}
		
		
		/// Properly adjusts the head if the head item is removed.
		void remove(PType item)
		{
			if(!_head)
				return;
			
			if(item is _head)
			{
				_head = item.next;
				item.listRemove();
				if(_head is item)
					_head = null; // Last item being removed.
				return;
			}
			item.listRemove();
		}
		
		
		/// Skip n items and change the head item.
		void skipHead(int n)
		{
			if(_head)
				_head = _head.listSkip(n);
		}
		
		
		/// Aliases for operating on the head item.
		size_t length() // getter
		{
			if(!_head)
				return 0;
			return _head.listLength;
		}
		
		/// ditto
		PType filter(bool delegate(PType) callback)
		{
			if(_head)
				return _head.filter(callback);
			return null;
		}
		
		/// ditto
		ListEach each() // getter
		{
			if(!_head)
			{
				ListEach result;
				return result;
			}
			return _head.each();
		}
		
		/// ditto
		ListEndless endless() // getter
		{
			if(!_head)
			{
				ListEndless result;
				return result;
			}
			return _head.endless();
		}
		
		/// ditto
		PType skip(int n)
		{
			if(!_head)
				return null;
			return _head.listSkip(n);
		}
		
		/// ditto
		PType find(PType item)
		{
			if(!_head)
				return null;
			return _head.listFind(item);
		}
		
		/// ditto
		PType find(bool delegate(PType item) compare)
		{
			if(!_head)
				return null;
			return _head.listFind(compare);
		}
	}
}


template ListNames(alias FromScope)
{
	alias FromScope.listIsEmpty isEmpty;
	alias FromScope.listAdd add;
	alias FromScope.listAddSafe addSafe;
	alias FromScope.listAddTail addTail;
	alias FromScope.listAddTailSafe addTailSafe;
	alias FromScope.listRemove remove;
	alias FromScope.listSkip skip;
	alias FromScope.listFind find;
	alias FromScope.listLength length;
}


/// Mixin for friendlier List names. Can also take a mixin identifier as an argument.
template ListNames()
{
	mixin ListNames!(typeof(this));
}


unittest
{
	class Foo
	{
		mixin List;
		
		int foo;
		
		this(int foo)
		{
			this.foo = foo;
		}
	}
	
	Foo foo;
	size_t iw;
	
	foo = new Foo(0);
	//foo.beginList();
	foo ~= new Foo(1);
	foo ~= new Foo(2);
	foo ~= new Foo(3);
	foo ~= new Foo(4);
	
	assert(foo.listLength == 5);
	
	iw = 0;
	foreach(Foo f; foo.each)
	{
		assert(f.foo == iw);
		iw++;
	}
	foreach(Foo f; foo.each.backwards)
	{
		iw--;
		assert(f.foo == iw);
	}
	
	foo = foo.listFind(delegate bool(Foo f) { return f.foo == 2; });
	assert(foo !is null);
	
	foo.next.listRemove(); // Remove Foo(3), next after 2 found above.
	assert(foo.listLength == 4);
	
	foo = foo.listFind(delegate bool(Foo f) { return f.foo == 0; });
	assert(foo !is null);
	
	// Make sure Foo(3) is not there.
	iw = 0;
	foreach(Foo f; foo.each)
	{
		assert(f.foo != 3);
		assert(f.foo == iw);
		iw++;
		if(iw == 3)
			iw++;
	}
	
	iw = 0;
	foreach(Foo f; foo.endless)
	{
		if(++iw == 200)
			break;
	}
	assert(200 == iw);
	
	iw = 0;
	foreach(Foo f; foo.endless.backwards)
	{
		if(++iw == 200)
			break;
	}
	assert(200 == iw);
	
	assert(!foo.foo);
	foo ~= new Foo(5);
	assert(foo.listSkip(0).foo == 0);
	assert(foo.listSkip(1).foo == 1);
	assert(foo.listSkip(2).foo == 2);
	assert(foo.listSkip(3).foo == 4);
	assert(foo.listSkip(4).foo == 5);
	assert(foo.listSkip(5).foo == 0);
	assert(foo.listSkip(-1).foo == 5);
	assert(foo.listSkip(-2).foo == 4);
	assert(foo.listSkip(-3).foo == 2);
	assert(foo.listSkip(-4).foo == 1);
	assert(foo.listSkip(-5).foo == 0);
	assert(foo.listSkip(-6).foo == 5);
	
	iw = 0;
	foo = foo.filter(
		delegate bool(Foo f)
		{
			iw++;
			return true; // Continue.
		});
	assert(iw == 5 && foo.listLength == 5);
	
	iw = 0;
	foo = foo.filter(
		delegate bool(Foo f)
		{
			if(f.foo == 2)
			{
				f.listRemove();
				return true; // Continue.
			}
			iw++;
			return true; // Continue.
		});
	assert(iw == 4 && foo.listLength == 4);
	
	iw = 0;
	foo = foo.filter(
		delegate bool(Foo f)
		{
			if(!f.foo)
			{
				f.listRemove();
				return true; // Continue.
			}
			iw++;
			return true; // Continue.
		});
	assert(iw == 3 && foo.listLength == 3);
	assert(foo.foo == 1);
	
	iw = 0;
	foo = foo.filter(
		delegate bool(Foo f)
		{
			if(f.foo == 5)
			{
				f.listRemove();
				return true; // Continue.
			}
			iw++;
			return true; // Continue.
		});
	assert(iw == 2);
	assert(foo.listLength == 2);
	
	foo = foo.filter(
		delegate bool(Foo f)
		{
			f.listRemove();
			return true; // Continue.
		});
	assert(!foo);
}