forked from: HeapTest

/**
 * Copyright pleclech ( http://wonderfl.net/user/pleclech )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/xzl6
 */

// forked from inspirit's HeapTest
// fix insert and pop bug ;)
package {
    import flash.display.AVM1Movie;
    import flash.text.TextField;
    import flash.display.Sprite;
    public class FlashTest extends Sprite {
        
        public static var _txt:TextField;
        
        public function FlashTest() {
            
            _txt = new TextField();
            _txt.width = 300;
            _txt.autoSize = 'left';
            
            addChild(_txt);
            
            var myHeap:Heap1 = new Heap1(10);
            
            p(testHeap(myHeap));
        }
        public static function p(...args):void{
            _txt.appendText(args.join(", "));
        }

        private function dump(heap:Heap1):String{
            var str:String=" [] ";
            for (var i:int=0;i<heap.heap.length;i++) str+=heap.heap[i].val+", ";
            return str;
        }

        private function insert(heap:Heap1, n:Number):String {
            heap.insert(n, n);
            return "\ninsert : "+n;
        }
        private function pop(heap:Heap1):String{
            return "\npop : "+heap.pop();
        }


        public function testHeap(heap:Heap1):String
        {
            var i:uint, j:uint;
            var str:String = '';
            var tmp:HeapNode;
            str+=insert(heap, 34);
            str+=insert(heap, 14);
            str+=insert(heap, 48);
            str+=insert(heap, 8);
            str+=pop(heap);
            str+=pop(heap);
            str+=insert(heap, 50);
            str+=pop(heap);
            str+=pop(heap);
            str+=pop(heap);
            str+=pop(heap);
            return str;
        }
        
    }
}

internal final class Heap1
{
    public var count:uint;
    public var heap:Vector.<HeapNode>;
    
    public function Heap1(size:uint)
    {
        heap = new Vector.<HeapNode>(size+1, true);
        count = 0;
        
        for(var i:int = size; i >= 0; --i)
        {
            heap[i] = new HeapNode();
        }
        heap[0].val=-Number.MAX_VALUE;
    }
    
    public function insert(data:*, val:Number):void
    {
       var i:int=++count; 
       var j:int=i>>1;
       var tmp:HeapNode;
       while( heap[j].val > val) {
           tmp=heap[i];
           heap[i]=heap[j];
           heap[j]=tmp;
           i=j;
           j>>=1;
       }
       heap[ i ].data = data;
       heap[ i ].val = val;
    }
    
    public function pop():HeapNode
    {
        if(count == 0) return null;
        
        var minNode:HeapNode=heap[1];
        
        var lastPos:int=count--;
        var lastNode:HeapNode=heap[lastPos];
        var lastVal:Number=lastNode.val;
        
        var i:int=1;
        var j:int=i<<1;
        
        var tmp:HeapNode;
        
        while(j<=count){
            if (j!=count && heap[j+1].val < heap[j].val) j++;
            if (lastVal<=heap[j].val) break;
            tmp=heap[i];
            heap[i]=heap[j];
            heap[j]=tmp;
            i=j;
            j<<=1;
        }
        
        tmp=heap[i]
        heap[i]=lastNode;
        heap[lastPos]=tmp;
        
        return minNode;
    }
}

internal final class HeapNode
{
    public var data:*;
    public var val:Number;
    public function toString():String{
        return val.toString();
    }
}