package 
{
    import com.adobe.viewsource.ViewSource;
    
    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("#000000", frameRate="60", quality="high", width="800", height="600")]
    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()
        {
            ViewSource.addMenuItem(this, "srcview/index.html"); 
            
            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;
                        }
                    }
                    if (n) {
                        p.next = n;
                        n.prev = p;
                    } else {
                        p.next = null;
                    }
                    //n ? (p.next = n, (n.prev = p)) : p.next = null;
                    if (j == f) {
                        c.prev = null;
                        c.next = j;
                        j.prev = c;
                        f = c;
                    } else {
                        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");
            //*/
            
            
            /*
            time = getTimer();
            
            // Z-SORT
            //
            // Linkedlist Radix sort by Rob Bateman http://www.infiniteturtles.co.uk
            
            var q0:Vector.<Particle3D> = new Vector.<Particle3D>(256, true);
            var q1:Vector.<Particle3D> = new Vector.<Particle3D>(256, true);
            
            var i:int = 0;
            var k:int;
            var f:Particle3D = first;
            var p:Particle3D, c:Particle3D;
            c = f;
            while (c) {
                c.sort = q0[k = (255 & c.z)];
                q0[k] = c;
                c = c.next;
            }
            
            i = 256;
            while (i--) {
                c = q0[i];
                while (c) {
                    p = c.sort;
                    c.sort = q1[k = (65280 & c.z) >> 8];
                    q1[k] = c;
                    c = p;
                }
            }
            
            i = 0;
            k = 0;
            //trace("sorted----");
            while (i < 255) {
                c = q1[i];
                while (c) {
                    output = c.z;
                    //trace(output);
                    c = c.sort;
                }
                i++;
            }
            
            //trace("Linkedlist Radix sort: " + (getTimer() - time));
            resultTf.appendText("Linkedlist Radix sort: "+ (getTimer() - time) + "\n");
            //*/
            
            ///*
            time = getTimer();
            
            // Z-SORT
            //
            // Radix sort by Rob Bateman http://www.infiniteturtles.co.uk
            
            var q0:Vector.<int> = new Vector.<int>(256, true);
            var q1:Vector.<int> = new Vector.<int>(256, true);
            var np0:Vector.<int> = new Vector.<int>(particles.length + 1, true);
            var np1:Vector.<int> = new Vector.<int>(particles.length + 1, true);
            var data:Vector.<int> = new Vector.<int>(particles.length, true);
            var p:Particle3D;
            
            var length:int = particles.length;
            var i:int = 0;
            var j:int = 0;
            var k:int;
            
            while (i < length) {
                p = particles[i];
                np0[int(i+1)] = q0[k = (255 & (data[i] = p.z))];
                q0[k] = int(++i);
            }
            
            i = 256;
            while (i--) {
                j = q0[i];
                while (j) {
                    np1[j] = q1[k = (65280 & data[int(j-1)]) >> 8];
                    j = np0[q1[k] = j];
                }
            }
            
            i = 0;
            k = 0;
            
            while (i < 255) {
                j = q1[int(i++)];
                while (j) {
                    p = particles[int(j-1)];
                    output = p.z;
                    j = np1[j];
                }
            }
            
            //trace("Radix sort: " + (getTimer() - time));
            resultTf.appendText("Radix sort: "+ (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);
            }
        }    
         **/
        
    }
}