<?xml version="1.0" encoding="utf-8"?>
<!--
/* 
 * $Id: PixelBenderSort.mxml 71 2008-11-17 06:51:20Z danielr $
 * 
 * Copyright (c) 2008 Daniel Rinehart
 * http://danielr.neophi.com/
 * 
 * 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.
 */
-->
<FxApplication xmlns="http://ns.adobe.com/mxml/2009" creationComplete="setup();" viewSourceURL="srcview/index.html">
    <Script>
        <![CDATA[
            import mx.controls.dataGridClasses.DataGridColumn;
            import mx.collections.ArrayCollection;
            [Embed("MergeExchangeSort.pbj", mimeType="application/octet-stream")]
            private var sorter:Class;

            // Compare to right
            private static const RIGHT:uint = 0xFF0000;
            // Compare to left
            private static const LEFT:uint = 0x00FF00;
            // Number of special x values
            private static const X_OFFSET:int = 1;
            // Number of special y values
            private static const Y_OFFSET:int = 1;
            // Number of elements
            private static const N:int = 16;
            
            // Holds the bookkeeping information
            private var bookkeeper:BitmapData;
            // Current data
            private var current:BitmapData;
            // How many times have we run the calculation?
            private var generationCount:int;

            [Bindable]
            // Are we currently running a calculation?
            private var running:Boolean;
                        
            // Calculate how many steps we need to run in order to sort
            // an array of n elements
            private function steps(n:int):int
            {
                var temp:Number = Math.ceil(Math.log(n)/Math.log(2)); 
                var result:Number = temp * (temp + 1) * 0.5;       
                return int(result);
            }

            // Create a bitmap that is sized correctly for n elements
            private function createBitmapData(n:int):BitmapData
            {
                // make it one wider for bookkeeping and one taller for pipelining
                var bitmapData:BitmapData = new BitmapData(n + X_OFFSET, steps(n) + Y_OFFSET, false, 0x000000);
                return bitmapData;
            }
            
            // Create a bitmap with all of the bookkeeping data in it 
            private function createBookkeeper(n:int):BitmapData
            {
                var bitmapData:BitmapData = createBitmapData(n);
                bitmapData.lock();
                var step:int = -1;
                
                // M1. [Initialize p.]
                var t:int = Math.ceil(Math.log(n)/Math.log(2));
                var p:int = Math.pow(2, t - 1);
                do
                {
                    // M2. [Initialize q, r, d.]
                    var q:int = Math.pow(2, t - 1);
                    var r:int = 0;
                    var d:int = p;
                    var loopOnQ:Boolean = true;
                    do
                    {
                        // Pass along the value for d
                        step++;                        
                        bitmapData.setPixel(0, step + Y_OFFSET, d);
                        
                        // M3. [Loop on i.]
                        for (var i:int = 0; i < n - d; i++)
                        {
                            if ((i & p) == r)
                            {
                                // M4. [Compare/exchange R_(i+1):R_(i+d+1)]
                                // Store the fact that we need to make this comparison
                                bitmapData.setPixel(X_OFFSET + i, step + Y_OFFSET, RIGHT);
                                bitmapData.setPixel(X_OFFSET + i + d, step + Y_OFFSET, LEFT);
                            }
                        }
                        // M5. [Loop on q.]
                        if (q != p)
                        {
                            d = q - p;
                            q = q / 2;
                            r = p;        
                        }
                        else
                        {
                            loopOnQ = false;
                        }
                    }
                    while (loopOnQ);
                    
                    // M6. [Loop on p.]
                    p = Math.floor(p / 2);
                }
                while (p > 0);
                
                bitmapData.unlock();
                return bitmapData;      
            }
                
            // Generate a row of randomized data in the bitmap
            private function randomizedData(bitmapData:BitmapData):void
            {
                bitmapData.lock();
                for (var i:int = X_OFFSET; i < bitmapData.width; i++)
                {
                    var temp:uint = Math.random() * 0xFFFF;
                    bitmapData.setPixel(i, 0, temp);
                }
                bitmapData.unlock();
            } 

            // Generate the next step in the pipeline
            private function nextGeneration():void
            {
                if ((running) || (current == null))
                {
                    return;
                }
                running = true;
                var shader:Shader = new Shader(new sorter() as ByteArray);
                shader.data.src.input = current;
                shader.data.book.input = bookkeeper;
                var result:BitmapData = new BitmapData(current.width, current.height);
                var shaderJob:ShaderJob = new ShaderJob(shader, result, current.width, current.height);
                shaderJob.addEventListener(ShaderEvent.COMPLETE, handleShaderDone);
                shaderJob.start();
            }
            
            // Last calculation was done
            private function handleShaderDone(shaderEvent:ShaderEvent):void
            {
                current = shaderEvent.bitmapData;
                generationCount++;
                running = false;
                if (pipeline.selected)
                {
                    randomizedData(current);
                }
                dumpData(current);
                if (automatic.selected)
                {
                    nextGeneration();
                }
            }
            
            // Get some data to start us off
            private function setup():void
            {
                bookkeeper = createBookkeeper(N);
                current = createBitmapData(N);
                randomizedData(current);
                var columns:Array = new Array();
                var dgc:DataGridColumn = new DataGridColumn();
                dgc.dataField = "step";
                columns.push(dgc);
                for (var i:int = 1; i <= N; i++)
                {
                    dgc = new DataGridColumn();
                    dgc.dataField = String(i);
                    columns.push(dgc);
                }
                currentData.columns = columns;
                dumpData(current);
            }
            
            // Report the data back to the user
            private function dumpData(bitmapData:BitmapData):void
            {
                var data:ArrayCollection = new ArrayCollection();
                for (var y:int = 0; y < bitmapData.height; y++)
                {
                    var row:Object = new Object();
                    row.step = y;
                    for (var x:int = X_OFFSET; x < bitmapData.width; x++)
                    {
                        row[x] = bitmapData.getPixel(x, y);
                    }
                    data.addItem(row);
                }
                currentData.dataProvider = data;
                for (var i:int = X_OFFSET; i < bitmapData.width - 1; i++)
                {
                    if (bitmapData.getPixel(i, bitmapData.height -1) > bitmapData.getPixel(i + 1, bitmapData.height -1))
                    {
                        throw new Error("Compare error");
                    }
                }
            }   
        ]]>
    </Script>
    <layout>
        <VerticalLayout/>
    </layout>
    <FxContainer>
        <layout>
            <HorizontalLayout/>
        </layout>
        <FxButton label="Next Step" click="nextGeneration();" enabled="{!running}"/>
        <FxCheckBox id="pipeline" label="Pipeline"/>
        <FxCheckBox id="automatic" label="Automatic Stepping" change="nextGeneration();"/>        
    </FxContainer>
    <DataGrid id="currentData" width="1000" sortableColumns="false" height="400"/>
</FxApplication>