package 
{
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.events.MouseEvent;
	import flash.text.TextField;
	import flash.utils.getTimer;
	
	import project.demo.modifier.particle.Particle3D;
	
	/**
	* @author Simo Santavirta / (jac) EvoFlash (evo.bombsquad.org)
	*/
	[SWF(backgroundColor="#000000", frameRate="60", quality="high", width="1024", height="576")]
	public class ZSortTest extends Sprite
	{
		private var count:int = 100000;
		private var particles:Vector.<Particle3D>;
		private var particleArray:Array;
		private var first:Particle3D;
		
		private var resultTf:TextField;
		
		public function ZSortTest()
		{
			particleArray = new Array();
			particles = new Vector.<Particle3D>(count);
			var l:int = int(count-1);
			for(var i:int = l; i > -1; i--)
			{
				particleArray[i] = particles[i] = new Particle3D();
				particles[i].x = 1//1000 * Math.random();
				particles[i].y = 1//-500 + 1000*Math.random();
				particles[i].z = 50000 - i//-500 + 1000*Math.random();
				particles[i].i = i;
				if(i < l) particles[i].next = particles[int(i+1)];
				if(i < l) particles[int(i+1)].prev = particles[i];
			}
			first = particles[0];
			
			resultTf = new TextField();
			resultTf.textColor = 0xFFFFFF;
			resultTf.width = 1024;
			resultTf.height = 576;
			resultTf.multiline = true;
			resultTf.wordWrap = true;
			resultTf.selectable = true;
			this.addChild(resultTf);
			
			this.addEventListener(Event.ENTER_FRAME, render);
			stage.addEventListener(MouseEvent.CLICK, click);
		}
		
		private function click(event:MouseEvent):void
		{
			this.removeEventListener(Event.ENTER_FRAME, render);
		}
		
		private var time:int;
		private var output:int;
		private function render(event:Event):void
		{
			/*
			time = getTimer();
			
			particles.sort(sort);
			
			for(var i:int = 0; i < count; i++)
			{
				output = particles[i].i;
			}
			
			resultTf.appendText("Vector sort: "+ (getTimer() - time) + "\n");
			//*/
			
			/*
			time = getTimer();
			
			shellSort(particles);
			
			for(var i:int = 0; i < count; i++)
			{
				output = particles[i].i;
			}
			
			//trace("Vector shellShort method: ", (getTimer() - time));
			resultTf.appendText("Vector shellShort method: "+ (getTimer() - time) + "\n");
			//*/
			
			/*
			time = getTimer();
			
			var n:int = count;
			var inc:int = int(n/2 + 0.5);
			var a:Particle3D, b:Particle3D;
			var j:int, i:int;
			var temp:Number;
			while(inc) 
			{
				for(i=inc; i<n; i++) 
				{
					a = particles[i];
					temp = a.z;
					j = i;
					b = particles[int(j - inc)];
					while(j >= inc && b.z > temp) 
					{
						a.z = b.z;
						j = int(j - inc);
					}
					particles[j].z = temp
				}
				inc = int(inc / 2.2 + 0.5);
			}
			
			
			for(i = 0; i < count; i++)
			{
				output = particles[i].i;
			}
			
			//trace("Vector shellShort: ", (getTimer() - time));
			resultTf.appendText("Vector shellShort: "+ (getTimer() - time) + "\n");
			//*/
			
			/*
			time = getTimer();
			
			particleArray.sort(sort);
			
			for(var i:int = 0; i < count; i++)
			{
				output = particleArray[i].i;
			}
			
			//trace("Array sort: ", (getTimer() - time));
			resultTf.appendText("Array sort: "+ (getTimer() - time) + "\n");
			//*/
			
			/*
			time = getTimer();
			
			particleArray.sortOn("z", Array.NUMERIC);
			
			for(var i:int = 0; i < count; i++)
			{
				output = particleArray[i].i;
			}
			
			//trace("Array sortOn: ", (getTimer() - time));
			resultTf.appendText("Array sortOn: "+ (getTimer() - time) + "\n");
			//*/
			
			
			///*
			time = getTimer();
			
			// Z-SORT
			//
			// Insertion sort by Michael Baczynski http://lab.polygonal.de/ 
			// Only slightly modified.
			//
			// (simppafi: I cannot think of any other developer I've learned more then Michael Baczynski.)
			//
			
			// Jedi+Voodoo : 358
			
			var f:Particle3D = first;
			var n:Particle3D, j:Particle3D, p:Particle3D, c:Particle3D;
			c = f.next;
			while(c) 
			{
				n = c.next;
				p = c.prev;
				if (c.z > p.z) 
				{
					j = p;
					while(j.prev) 
					{
						if (c.z > j.prev.z) 
						{
							j = j.prev;
						}else{
							break;
						}
					}
					n ? (p.next = n, (n.prev = p)) : p.next = null;
					(j == f) ? (c.prev = null, (c.next = j), (j.prev = c), (f = c)) : (c.prev = j.prev, (j.prev.next = c), (c.next = j), (j.prev = c));
				}
				c = n;
			}
			
			first = f;
			while(f)
			{
				output = f.i;
				f = f.next;
			}
			
			//trace("Insertion sort + linked list: " + (getTimer() - time));
			resultTf.appendText("Jedi+Voodoo : "+ (getTimer() - time) + "\n");
			//*/
			
		}
		
		/**
		 * Modified code of Tuomas Artman http://www.artman.fi/
		 **/
		final private function sort(a:Particle3D, b:Particle3D):int {
			return (a.z==b.z ? 0 : (a.z < b.z) ? -1 : 1);
		}
		
		/**
		 * Modified from AS3 port of Tuomas Artman http://www.artman.fi/
		 **/
		final private function shellSort(data:Vector.<Particle3D>):void {
			var n:int = data.length;
			var inc:int = int(n/2 + 0.5);
			var a:Particle3D, b:Particle3D;
			var j:int, i:int;
			var temp:Number;
			while(inc) 
			{
				for(i=inc; i<n; i++) 
				{
					a = data[i];
					temp = a.z;
					j = i;
					b = data[int(j - inc)];
					while(j >= inc && b.z > temp) 
					{
						a.z = b.z;
						j = int(j - inc);
					}
					data[j].z = temp
				}
				inc = int(inc / 2.2 + 0.5);
			}
		}    
		
	}
}