slinkedlist.as

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

				else
				{
					if (b & 2)
					{
						if (b & 4)
						{
							if (b == 22)
								head = sLinkedInsertionSortCmp(head, compareStringCaseSensitiveDesc);
							else
							if (b == 14)
								head = sLinkedInsertionSortCmp(head, compareStringCaseInSensitive);
							else
							if (b == 30)
								head = sLinkedInsertionSortCmp(head, compareStringCaseInSensitiveDesc);
							else
								head = sLinkedInsertionSortCmp(head, compareStringCaseSensitive);
						}
						else
							head = sLinkedInsertionSort(head, b == 18);
					}
					else
					{
						if (b & 4)
						{
							if (b == 20)
								head = sLinkedMergeSortCmp(head, compareStringCaseSensitiveDesc);
							else
							if (b == 12)
								head = sLinkedMergeSortCmp(head, compareStringCaseInSensitive);
							else
							if (b == 28)
								head = sLinkedMergeSortCmp(head, compareStringCaseInSensitiveDesc);
							else
								head = sLinkedMergeSortCmp(head, compareStringCaseSensitive);
						}
						else
						if (b & 16)
							head = sLinkedMergeSort(head, true);
					}
				}
			}
			else
				head = sLinkedMergeSort(head);
		}
		
		/**
		 * Searches for an item in the list by using strict equality (===) and returns
		 * and iterator pointing to the node containing the item or null if the
		 * item was not found.
		 * 
		 * @param  obj  The item to search for
		 * @param  from A SListIterator object pointing to the node in the list from which to start searching for the item.  
		 * @return A SListIterator object pointing to the node with the found item or null if no item exists matching the input data
		 *         or the iterator is invalid.
		 */
		public function nodeOf(obj:*, from:SListIterator = null):SListIterator
		{
			if (from != null)
				if (from.list != null)
					return null;
			
			var node:SListNode = (from == null) ? head : from.node;
			while (node)
			{
				if (node.data === obj)
					return new SListIterator(this, node);
				node = node.next;
			}
			return null;
		}
		
		/**
		 * Adds nodes to and removes nodes from the list. This method modifies the list.
		 * 
		 * @param start       A SListIterator object pointing to the node where the insertion or deletion begins. The iterator
		 *                    is updated so it still points to the original node, even if the node now belongs to another list.
		 * @param deleteCount An integer that specifies the number of nodes to be deleted. This number includes
		 *                    the node referenced by the iterator. If no value is specified for the deleteCount parameter,
		 *                    the method deletes all of the nodes from the start start iterator to the tail of the list.
		 *                    If the value is 0, no nodes are deleted.
		 * @param args        Specifies the values to insert into the list, starting at the iterator's node specified by the start parameter.
		 *                    Nodes
		 * 
		 * @param return      A SLinkedList object containing the nodes that were removed from the original list or null if the
		 *                    iterator is invalid.
		 */
		public function splice(start:SListIterator, deleteCount:uint = 0xffffffff, ...args):SLinkedList
		{
			if (start) if (start.list != this) return null;
			
			if (start.node)
			{
				var s:SListNode = start.node;
				var t:SListNode = head;
				while (t.next != s)
					t = t.next;
					
				var c:SLinkedList = new SLinkedList();
				var i:int, k:int;
				
				if (deleteCount == 0xffffffff)
				{
					if (start.node == tail) return c;
					while (start.node)
					{
						c.append(start.node.data);
						start.remove();
					}
					start.list = c;
					start.node = s;
					return c;
				}
				else
				{
					for (i = 0; i < deleteCount; i++)
					{
						if (start.node)
						{
							c.append(start.node.data);
							start.remove();
						}
						else
							break;
					}
				}
				
				k = args.length;
				if (k > 0)
				{
					if (_count == 0)
					{
						for (i = 0; i < k; i++)
							append(args[i]);
					}
					else
					{
						var n:SListNode;
						if (t == null)
						{
							n = prepend(args[0]);
							for (i = 1; i < k; i++)
							{
								n.insertAfter(new SListNode(args[i]));
								if (n == tail) tail = n.next;
								n = n.next;
								_count++;
							}
						}
						else
						{
							n = t;
							for (i = 0; i < k; i++)
							{
								n.insertAfter(new SListNode(args[i]));
								if (n == tail) tail = n.next;
								n = n.next;
								_count++;
							}
						}
					}
					start.node = n;
				}
				else
					start.node = s;
				
				start.list = c;
				return c;
			}
			return null;
		}
		
		/**
		 * Removes and appends the head node to the tail.
		 */
		public function shiftUp():void
		{
			var t:SListNode = head;
			
			if (head.next == tail)
			{
				head = tail;
				
				tail = t;
				tail.next = null;
				
				head.next = tail;
			}
			else
			{
				head = head.next;
				tail.next = t;
				t.next = null;
				tail = t;
			}
		}
		
		/**
		 * Removes and prepends the tail node to the head.
		 */
		public function popDown():void
		{
			var t:SListNode = tail;
			
			if (head.next == tail)
			{
				tail = head;
				head = t;
				
				tail.next = null;
				head.next = tail;
			}
			else
			{
				var node:SListNode = head;
				while (node.next != tail)
					node = node.next;
				
				tail = node;
				tail.next = null;
				
				t.next = head;
				head = t;
			}
		}
		
		/**
		 * Reverses the linked list in place.
		 */
		public function reverse():void
		{
			if (_count == 0) return;
			var a:Array = new Array(_count), i:int = 0;
			var node:SListNode = head;
			while (node)
			{
				a[i++] = node;
				node = node.next;
			}
			
			a.reverse();
			
			node = head = a[0];
			for (i = 1; i < _count ; i++)
				node = node.next = a[i];
			
			node.next = null;
			tail = node;
			a = null;
		}
		
		/**
		 * Converts the node data in the linked list to strings,
		 * inserts the given separator between the elements,
		 * concatenates them, and returns the resulting string.
		 * 
		 * @return A string consisting of the nodes converted to
		 *         strings and separated by the specified parameter. 
		 */
		public function join(sep:*):String
		{
			if (_count == 0) return "";
			var s:String = "";
			var node:SListNode = head;
			while (node.next)
			{
				s += node.data + sep;
				node = node.next;
			}
			s += node.data;
			return s;
		}
		
		/**
		 * Checks if a given item exists.
		 * 
		 * @return True if the item is found, otherwise false.
		 */
		public function contains(obj:*):Boolean
		{
			var node:SListNode = head;
			while (node)
			{
				if (node.data == obj) return true;
				node = node.next;
			}
			return false;
		}
		
		/**
		 * Clears the list by unlinking all nodes
		 * from it. This is important to unlock
		 * the nodes for the garbage collector.
		 */
		public function clear():void
		{
			var node:SListNode = head;
			head = null;
			
			var next:SListNode;
			while (node)
			{
				next = node.next;
				node.next = null;
				node = next;
			}
			_count = 0;
		}
		
		/**
		 * Creates an iterator pointing
		 * to the first node in the list.
		 * 
		 * @returns An iterator object.
		 */
		public function getIterator():Iterator
		{
			return new SListIterator(this, head);
		}
		
		/**
		 * Creates a list iterator pointing
		 * to the first node in the list.
		 * 
		 * @returns A SListIterator object.
		 */
		public function getListIterator():SListIterator
		{
			return new SListIterator(this, head);
		}
		
		/**
		 * The total number of nodes in the list.
		 */
		public function get size():int
		{
			return _count;
		}
		
		/**
		 * Checks if the list is empty.
		 */
		public function isEmpty():Boolean
		{
			return _count == 0;
		}
		
		/**
		 * Converts the linked list into an array.
		 * 
		 * @return An array.
		 */
		public function toArray():Array
		{
			var a:Array = [];
			var node:SListNode = head;
			while (node)
			{
				a.push(node.data);
				node = node.next;
			}
			return a;
		}
		
		/**
		 * Returns a string representing the current object.
		 */
		public function toString():String
		{
			return "[SlinkedList, size=" + size + "]";
		}
		
		/**
		 * Prints out all elements in the list (for debug/demo purposes).
		 */
		public function dump():String
		{
			if (!head)
				return "SLinkedList: (empty)";
			
			var s:String = "SLinkedList: has " + _count + " node" + (_count == 1 ? "" : "s") + "\n|< Head\n";
			
			var itr:SListIterator = getListIterator();
			for (; itr.valid(); itr.forth())
				s += "\t" + itr.data + "\n";
			
			s += "Tail >|";
			
			return s;
		}
	}
}