slinkedlist.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.sLinkedInsertionSort;
	import de.polygonal.ds.sort.sLinkedInsertionSortCmp;
	import de.polygonal.ds.sort.sLinkedMergeSort;
	import de.polygonal.ds.sort.sLinkedMergeSortCmp;	
	
	/**
	 * A singly linked list.
	 */
	public class SLinkedList implements Collection
	{
		public static const INSERTION_SORT:int = 1 << 1;
		public static const MERGE_SORT:int     = 1 << 2;
		public static const NUMERIC:int        = 1 << 3;
		public static const DESCENDING:int     = 1 << 4;
		
		private var _count:int;
		
		/**
		 * The head node being referenced.
		 */
		public var head:SListNode;
		
		/**
		 * The tail node being referenced.
		 */
		public var tail:SListNode;
		
		/**
		 * 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 SLinkedList(...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 SListNode object wrapping the data. If multiple values are
		 *         added, the returned node represents the first argument.
		 */
		public function append(...args):SListNode
		{
			var k:int = args.length;
			
			var node:SListNode = new SListNode(args[0]);
			if (head)
			{
				tail.next = node;
				tail = node;
			}
			else
				head = tail = node;
			
			if (k > 1)
			{
				var t:SListNode = node;
				for (var i:int = 1; i < k; i++)
				{
					node = new SListNode(args[i]);
					tail.next = node;
					tail = node;
				}
				_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 SListNode object wrapping the data. If multiple values are
		 *         added, the returned node represents the first argument.
		 */
		public function prepend(...args):SListNode
		{
			var k:int = args.length;
			var node:SListNode = new SListNode(args[int(k - 1)]);
			if (head)
			{
				node.next = head;
				head = node;
			}
			else
				head = tail = node;
			
			if (k > 1)
			{
				var t:SListNode = node;
				for (var i:int = k - 2; i >= 0; i--)
				{
					node = new SListNode(args[i]);
					node.next = head;
					head = node;
				}
				_count += k;
				return t;
			}
			
			_count++;
			return node;
		}
		
		/**
		 * Inserts data after a given iterator or appends it
		 * if the iterator is invalid.
		 * 
		 * @param itr  A singly linked list iterator.
		 * @param obj The data.
		 * @return A singly linked list node wrapping the data.
		 */
		public function insertAfter(itr:SListIterator, obj:*):SListNode
		{
			if (itr.list != this) return null;
			if (itr.node)
			{
				var node:SListNode = new SListNode(obj);
				itr.node.insertAfter(node);
				if (itr.node == tail)
					tail = itr.node.next;
				
				_count++;
				return node;
			}
			else
			{
				return append(obj);
			}
		}
		
		/**
		* Removes the node the iterator is pointing
		* to and move the iterator to the next node.
		* 
		* @return True if the removal succeeded, otherwise false.
		*/
		public function remove(itr:SListIterator):Boolean
		{
			if (itr.list != this || !itr.node) return false;
			
			var node:SListNode = head;
			if (itr.node == head)
			{
				itr.forth();
				
				//inline
				//if (itr.node) itr.node = itr.node.next;
				
				//todo inline
				removeHead();
				return true;
			}
			
			while (node.next != itr.node) node = node.next;
			itr.forth();
			if (node.next == tail) tail = node;
			node.next = itr.node;
			
			_count--;
			return true;
		}
		
		/**
		 * Removes the head of the list and returns
		 * the head's data or null of the list is empty.
		 * 
		 * @return The data of the removed node.
		 */
		public function removeHead():*
		{
			if (head)
			{
				var obj:* = head.data;
				
				if (head == tail)
					head = tail = null;
				else
				{
					var node:SListNode = head;
					
					head = head.next;
					node.next = null;
					if (head == null) 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;
				
				if (head == tail)
					head = tail = null;
				else
				{
					var node:SListNode = head;
					while (node.next != tail)
						node = node.next;
					
					tail = node;
					node.next = 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 SLinkedList objects.
		 */
		public function merge(...args):void
		{
			var c:SLinkedList = new SLinkedList();
			var a:SLinkedList;
			
			a = args[0];
			if (head)
			{
				tail.next = a.head;
				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;
				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 SLinkedList objects.
		 * @return An copy of the current list which also stores the values from the passed lists.
		 */
		public function concat(...args):SLinkedList
		{
			var c:SLinkedList = new SLinkedList();
			var a:SLinkedList, n:SListNode;
			
			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: SLinkedList.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 = sLinkedInsertionSortCmp(head, cmp, b == 18);
					else
						head = sLinkedMergeSortCmp(head, cmp, b == 16);
				}