package
{
    import flash.utils.setTimeout;
    import flash.geom.Vector3D;
    import flash.geom.Matrix3D;
    import flash.text.TextField;
    import flash.utils.getTimer;
    import flash.display.Sprite;

    public class Main extends Sprite
    {
        private var q0:Vector.<ParticleContainer> = new Vector.<ParticleContainer>(256, true);
        private var q1:Vector.<ParticleContainer> = new Vector.<ParticleContainer>(256, true);
        public function Main()
        {
            setTimeout(run, 100);
        }

        private function run():void {
            var tf:TextField = new TextField();
            addChild(tf);
            // Launch your application by right clicking within this class and select: Debug As > FDT SWF Application
            var partCount:uint = 50000;
            var partSize:uint = (3+4);
            var particles:Vector.<Number> = new Vector.<Number>(partCount*partSize);
            var sortedParticles:Vector.<Number> = new Vector.<Number>(partCount*partSize);
            var sortParticles:Vector.<Number> = new Vector.<Number>(partCount*3);
            var k:int, i:int;
            var c:ParticleContainer, p:ParticleContainer;
            var pos:uint;
            var d1:uint = getTimer();
            var firstP:ParticleContainer = new ParticleContainer();
            var curPart:ParticleContainer = firstP;
            // Create particles
            for(i = 0;i<partCount;i++) {
                pos = i*partSize;
                particles[pos++] = Math.random()*1000-500;
                particles[pos++] = Math.random()*1000-500;
                particles[pos++] = Math.random()*1000-500;
                particles[pos++] = 1;
                particles[pos++] = 1;
                particles[pos++] = 1;
                particles[pos++] = 1; // Color RGBA (1,1,1,1)
                curPart.next = new ParticleContainer();
                curPart = curPart.next;
            }
            var d2:uint = getTimer();
            // Rotate particles
            var rotZ:Number = 0.4;
            var rotX:Number = 0.2;
            var rotY:Number = 0.1;
            var rotMat:Matrix3D = new Matrix3D();
            rotMat.appendRotation(rotX, Vector3D.X_AXIS);
            rotMat.appendRotation(rotY, Vector3D.Y_AXIS);
            rotMat.appendRotation(rotZ, Vector3D.Z_AXIS);

            for(i = 0;i<partCount;i++) {
                pos = i*partSize;
                // Copy particle positions for rotation
                sortParticles[i*3+0] = particles[pos];
                sortParticles[i*3+1] = particles[pos+1];
                sortParticles[i*3+2] = particles[pos+2];
            }
            // Transform the vectors for z sorting
            rotMat.transformVectors(sortParticles, sortParticles);

            var d4:uint = getTimer();
            // Now we got the particles transformed to new location, time to sort the real data
            var q0:Vector.<ParticleContainer> = this.q0.concat();
            var q1:Vector.<ParticleContainer> = this.q1.concat();

            curPart = firstP;
            for(i = 0;i<partCount;i++) {
                pos = i*partSize;
                curPart.origIdx = i;
                curPart.z = sortParticles[i*3+2];
                curPart.sort = q0[k = int(255 & -(curPart.z+10000))];
                q0[k] = curPart;
                curPart = curPart.next;
            }

            i = 256;
            while (i--)
            {
                c = q0[i];

                while (c)
                {
                    p = c.sort;
                    c.sort = q1[k = int(65280 & -(c.z+10000)) >> 8];
                    q1[k] = c;
                    c = p;
                }
            }
            var idx:uint = 0;
            while(i++ < 255)
            {
                c = q1[i];
                while(c) {
                    var oldPos:uint = c.origIdx;
                    pos = oldPos*partSize;
                    var newPos:uint = idx*partSize;
                    sortedParticles[newPos++] = particles[pos++];
                    sortedParticles[newPos++] = particles[pos++];
                    sortedParticles[newPos++] = particles[pos++];
                    sortedParticles[newPos++] = particles[pos++];
                    sortedParticles[newPos++] = particles[pos++];
                    sortedParticles[newPos++] = particles[pos++];
                    sortedParticles[newPos++] = particles[pos++];
                    idx++;
                    c = c.sort;
                }
            }
            var d5:uint = getTimer();
            // Particles are now sorted!
            var d3:uint = getTimer();

            tf.text=""+(d5-d2)+":"+(d5-d4);
        }
    }
}