dlinkedlist.as

一个2D基于verlet的Flash物理引擎。它用AS3编写而成。Fisix的目标是应用到游戏等计算量很大的实时应用中。尽管flash比c/c++要慢,很棒的物理引擎

/**
 * DATA STRUCTURES FOR GAME PROGRAMMERS
 * Copyright (c) 2007 Michael Baczynski, http://www.polygonal.de
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
package de.polygonal.ds
{
	import de.polygonal.ds.sort.compare.compareStringCaseInSensitive;
	import de.polygonal.ds.sort.compare.compareStringCaseInSensitiveDesc;
	import de.polygonal.ds.sort.compare.compareStringCaseSensitive;
	import de.polygonal.ds.sort.compare.compareStringCaseSensitiveDesc;
	import de.polygonal.ds.sort.dLinkedInsertionSort;
	import de.polygonal.ds.sort.dLinkedInsertionSortCmp;
	import de.polygonal.ds.sort.dLinkedMergeSort;
	import de.polygonal.ds.sort.dLinkedMergeSortCmp;	
	
	/**
	 * A doubly linked list.
	 * 
	 * <p>A doubly linked list stores a reference to the next
	 * and previous node which makes it possible to traverse
	 * the list in both directions.</p>
	 */
	public class DLinkedList implements Collection
	{
		private var _count:int;
		
		/**
		 * The head node being referenced.
		 */
		public var head:DListNode;
		
		/**
		 * The tail node being referenced.
		 */
		public var tail:DListNode;
		
		/**
		 * Initializes an empty list. You can add initial
		 * items by passing them as a comma-separated list.
		 * 
		 * @param args A list of comma-separated values to append.
		 */
		public function DLinkedList(...args)
		{
			head = tail = null;
			_count = 0;
			
			if (args.length > 0) append.apply(this, args);
		}
		
		/**
		 * Appends items to the list.
		 * 
		 * @param args A list of comma-separated values to append.
		 * @return A DListNode object wrapping the data. If multiple values are
		 *         added, the returned node represents the first argument.
		 */
		public function append(...args):DListNode
		{
			var k:int = args.length;
			
			var node:DListNode = new DListNode(args[0]);
			if (head)
			{
				tail.insertAfter(node);
				tail = tail.next;
			}
			else
				head = tail = node;
			
			if (k > 1)
			{
				var t:DListNode = node;
				for (var i:int = 1; i < k; i++)
				{
					node = new DListNode(args[i]);
					tail.insertAfter(node);
					tail = tail.next;
				}
				_count += k;
				return t;
			}
			
			_count++;
			return node;
		}
		
		/**
		 * Prepends items to the list.
		 * 
		 * @param args A list of one or more comma-separated values to prepend.
		 * @return A DListNode object wrapping the data. If multiple values are
		 *         added, the returned node represents the first argument.
		 */
		public function prepend(...args):DListNode
		{
			var k:int = args.length;
			var node:DListNode = new DListNode(args[int(k - 1)]);
			if (head)
			{
				head.insertBefore(node);
				head = head.prev;
			}
			else
				head = tail = node;
			
			if (k > 1)
			{
				var t:DListNode = node;
				for (var i:int = k - 2; i >= 0; i--)
				{
					node = new DListNode(args[i]);
					head.insertBefore(node);
					head = head.prev;
				}
				_count += k;
				return t;
			}
			
			_count++;
			return node;
		}
		
		/**
		 * Inserts an item after a given iterator or appends it
		 * if the iterator is invalid.
		 * 
		 * @param itr A doubly linked list iterator.
		 * @param obj The data.
		 * @return A doubly linked list node wrapping the data.
		 */
		public function insertAfter(itr:DListIterator, obj:*):DListNode
		{
			if (itr.list != this) return null;
			if (itr.node)
			{
				var node:DListNode = new DListNode(obj);
				itr.node.insertAfter(node);
				
				if (itr.node == tail)
					tail = itr.node.next;
				
				_count++;
				return node;
			}
			else
				return append(obj);
		}
		
		/**
		 * Inserts an item before a given iterator or appends it
		 * if the iterator is invalid.
		 * 
		 * @param itr A doubly linked list iterator.
		 * @param obj The data.
		 * @return A doubly linked list node wrapping the data.
		 */
		public function insertBefore(itr:DListIterator, obj:*):DListNode
		{
			if (itr.list != this) return null;
			if (itr.node)
			{
				var node:DListNode = new DListNode(obj);
				itr.node.insertBefore(node);
				if (itr.node == head)
					head = head.prev;
				
				_count++;
				return node;
			}
			else
				return prepend(obj);
		}
		
		/**
		* Removes the node the iterator is pointing
		* at and moves the iterator to the next node.
		* 
		* @return True if the removal succeeded, otherwise false.
		*/
		public function remove(itr:DListIterator):Boolean
		{
			if (itr.list != this || !itr.node) return false;
			
			var node:DListNode = itr.node;
			
			if (node == head) 
				head = head.next;
			else
			if (node == tail)
				tail = tail.prev;
			
			if (itr.node)
				itr.node = itr.node.next;
			
			if (node.prev) node.prev.next = node.next;
			if (node.next) node.next.prev = node.prev;
			node.next = node.prev = null;
			
			if (head == null) tail = null;
			
			_count--;
			return true;
		}
		
		/**
		 * Removes the head of the list and returns
		 * the head's data or null if the list is empty.
		 * 
		 * @return The data of the removed node.
		 */
		public function removeHead():*
		{
			if (head)
			{
				var obj:* = head.data;
				
				head = head.next;
				
				if (head)
					head.prev = null;
				else
					tail = null;
				
				_count--;
				
				return obj;
			}
			return null;
		}
		
		/**
		 * Removes the tail of the list and returns
		 * the tail's data or null if the list is empty.
		 * 
		 * @return The data of the removed node.
		 */
		public function removeTail():*
		{
			if (tail)
			{
				var obj:* = tail.data;
				
				tail = tail.prev;
				
				if (tail)
					tail.next = null;
				else
					head = null;
				
				_count--;
				
				return obj;
			}
			return null;
		}
		
		/**
		 * Merges the current list with all lists specified in the paramaters.
		 * The list on which the method is called is modified to reflect the changes.
		 * Due to the rearrangement of the node pointers all passed lists become
		 * invalid and should be discarded.
		 * @see #concat
		 * 
		 * @param args  A list of one or more comma-separated DLinkedList objects.
		 */
		public function merge(...args):void
		{
			var a:DLinkedList;
			
			a = args[0];
			if (head)
			{
				tail.next = a.head;
				a.head.prev = tail;
				tail = a.tail;
			}
			else
			{
				head = a.head;
				tail = a.tail;
			}
			
			var k:int = args.length;
			for (var i:int = 1; i < k; i++)
			{
				a = args[i];
				tail.next = a.head;
				a.head.prev = tail;
				tail = a.tail;
				
				_count += a.size;
			}
		}
		
		/**
		 * Concatenates the current list with all lists specified
		 * in the parameters and returns a new linked list.
		 * The list on which the method is called and the passed lists
		 * are left unchanged.
		 * @see #merge
		 * 
		 * @param args A list of one or more comma-separated DLinkedList objects.
		 * @return An copy of the current list which also stores the values from the passed lists.
		 */
		public function concat(...args):DLinkedList
		{
			var c:DLinkedList = new DLinkedList();
			var a:DLinkedList, n:DListNode;
			
			n = head;
			while (n)
			{
				c.append(n.data);
				n = n.next;
			}
			var k:int = args.length;
			for (var i:int = 0; i < k; i++)
			{
				a = args[i];
				n = a.head;
				while (n)
				{
					c.append(n.data);
					n = n.next;
				}
			}
			return c;
		}
		
		/**
		 * Sorts the nodes in the list using the mergesort algorithm.<br/>
		 * See http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html<br/>
		 * 
		 * If the LinkedList.INSERTION_SORT flag is used, the list is sorted using
		 * the insertionsort algorithm instead, which is much faster for nearly sorted lists.<br/>
		 * <ul>
		 * <li>default sort behaviour: mergesort, numeric, ascending</li>
		 * <li>sorting is ascending (for character-strings: a precedes z)</li>
		 * <li>sorting is case-sensitive: Z precedes a</li>
		 * <li>the list is directly modified to reflect the sort order</li>
		 * <li>multiple elements that have identical values are placed consecutively</li>
		 *   in the sorted array in no particular order</li></ul>
		 * 
		 * @param sortOptions
		 * 
		 * You pass an optional comparison function and/or one or more bitflags that determine the
		 * behavior of the sort.<br/>Syntax: DLinkedList.sort(compareFunction, flags)<br/><br/>
		 * <br/>
		 * compareFunction - A comparison function used to determine the sorting
		 *                   order of elements in an array (optional).<br/>
		 *                   It should take two arguments and return a result of
		 *                   -1 if A < B, 0 if A == B and 1 if A > B in the sorted sequence.
		 * <br/><br/>
		 * flags           - One or more numbers or defined constants, separated by the | (bitwise OR) operator,
		 *                   that change the behavior of the sort from the default:<br/>
		 *                   2  or SortOptions.INSERTION_SORT<br/>
		 *                   4  or SortOptions.CHARACTER_STRING<br/>
		 *                   8  or SortOptions.CASEINSENSITIVE<br/>
		 *                   16 or SortOptions.DESCENDING<br/>
		 **/
		public function sort(...sortOptions):void
		{
			if (_count <= 1) return;
			if (sortOptions.length > 0)
			{
				var b:int = 0;
				var cmp:Function = null;
				
				var o:* = sortOptions[0];
				if (o is Function)
				{
					cmp = o;
					if (sortOptions.length > 1)
					{
						o = sortOptions[1];
						if (o is int)
							b = o;
					}
				}
				else
				if (o is int)
					b = o;
				
				if (Boolean(cmp))
				{
					if (b & 2)
						head = dLinkedInsertionSortCmp(head, cmp, b == 18);
					else
						head = dLinkedMergeSortCmp(head, cmp, b == 16);
				}
				else
				{
					if (b & 2)
					{
						if (b & 4)
						{
							if (b == 22)
								head = dLinkedInsertionSortCmp(head, compareStringCaseSensitiveDesc);
							else
							if (b == 14)
								head = dLinkedInsertionSortCmp(head, compareStringCaseInSensitive);
							else
							if (b == 30)
								head = dLinkedInsertionSortCmp(head, compareStringCaseInSensitiveDesc);