quadrant tree test

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

package {
    import flash.display.Sprite;
    import flash.display.Graphics;
	import flash.geom.*;
    import flash.events.*;
    import flash.text.*;
  
	[SWF( width="1024", height="1024" )]

    public class FlashTest extends Sprite {
    		public static var tex : TextField = new TextField();
    		private var space : cSpaceManager;
        private var test : testObject = new testObject();
        public function FlashTest() {
            // write as3 code here..
            var tf : TextFormat = new TextFormat();
            tf.color = 0x01;
            tf.size = 24;
            tex.defaultTextFormat = tf;
            tex.autoSize = TextFieldAutoSize.LEFT;
            addChild( tex );
            addChild( test );
            test.x = parent.stage.stageWidth / 2;
            test.y = parent.stage.stageHeight / 2;

            space = new cSpaceManager( new Rectangle(0,0,1024,1024) );
            
            parent.addEventListener( MouseEvent.MOUSE_UP, this.release );
        }
        public function release( e : MouseEvent ) : void
        {
	        	space.init();
        		test.x = e.stageX;
        		test.y = e.stageY;
        		tex.text = Math.round( test.x ) + ":" + Math.round( test.y ) + "\n";
        		tex.appendText( space.registObject( test ).id + "\n" );
        		
        		drawArea( space.getTree() );
        }
        public function drawArea( tree : Vector.<cSpace> ) : void
        {
        		const g : Graphics = graphics;
        		for( var i : int = 0 ; i < cSpaceManager.DEPTH ; i++ )
        		{
        			var sx : int = 0;
        			var sy : int = 0;
        			var ofs : int = Math.floor( ( Math.pow( 4, i ) - 1 ) / 3 );
        			var par : int = Math.floor( ( Math.pow( 4, i + 1 ) - 1 ) / 3 );
        			for( var j : int = 0 ; j < par ; j++ )
        			{
        			}
        		}
        }
    }
}
import flash.display.*;
import flash.geom.*;
interface iCharacter
{
    function process() : void;
    function draw( v : Vector3D ) : void;
    function getBoundingRect() : Rectangle;
}
class testObject extends Sprite implements iCharacter
{
	public function testObject()
	{
		const g : Graphics = graphics;
        g.clear();
        g.lineStyle( 1, 0x0000ff );
        g.drawCircle( 0, 0, 20 );
	}
	public function process() : void
	{
	}
	public function draw( v : Vector3D ) : void
	{
	}
	public function getBoundingRect() : Rectangle
	{
		return new Rectangle( x - 10, y - 10, 20, 20 );
	}
}
class cSpace
{
	private var parent : cSpace;
	private var child : Vector.<cSpace>;
	private var object : Vector.<iCharacter>;


	public function cSpace( p : cSpace = null )
	{
		parent = p;
		child = new Vector.<cSpace>();
		object = new Vector.<iCharacter>();
	}
	public function addChild( c : cSpace ) : void
	{
		child.push( c );
	}
	public function addObject( o : iCharacter ) : void
	{
		object.push( o );
	}
}

class cSpaceManager
{
//	public static const DEPTH : int = 7;
	public static const DEPTH : int = 2;
	public static const PARTITION_NUMBER : int = Math.pow( 2, DEPTH );

	private var tree : Vector.<cSpace>;
	private var space : Rectangle;
	private var baseLength : int;

	public function cSpaceManager( s : Rectangle = null )
	{
		space = s;
		tree = new Vector.<cSpace>();
		baseLength = space.width / PARTITION_NUMBER;
		init();
	}
	public function init() : void
	{
		var max : int = Math.pow( 4, DEPTH + 1 ) / 3;
		for( var i : int = 0 ; i < max ; i++ )
		{
			tree.push( new cSpace() );
		}
	}
	private function shift( n : int ) : int
	{
		n = ( n | n << 8 ) & 0x00ff00ff;
		n = ( n | n << 4 ) & 0x0f0f0f0f;
		n = ( n | n << 2 ) & 0x33333333;
		return ( n | n << 1 ) & 0x55555555;
	}
	private function getPartitionedID( xx : int, yy : int ) : int
	{
		return ( shift( xx ) | ( shift( yy ) << 1 ) );
	}
	public function getSpaceID( lx : int, ly : int, rx : int, ry : int ) : Object
	{
		var idb : int = getPartitionedID( rx, ry );
		var id : int = getPartitionedID( lx, ly ) ^ idb;
		var result : int = 0;
		while( id > 0 )
		{
			result += 2;
			id >>= 2;
		}
		return { "level" : DEPTH - Math.floor(result / 2), "id" : ( idb >> result ) };
	}
	public function registObject( o : iCharacter ) : Object
	{
		const r : Rectangle = o.getBoundingRect();
		var re : Object = getSpaceID( r.left / baseLength, r.top / baseLength, r.right / baseLength, r.bottom / baseLength );
		tree[ Math.floor(( Math.pow( 4, re.level ) - 1 ) / 3) + re.id ].addObject( o );
		FlashTest.tex.appendText("depth:" + re.level + "\n");
		FlashTest.tex.appendText("index:" + Math.floor(( Math.pow( re.level, 4 ) - 1 ) / 3 + re.id) + "\n");
		return re;
	}
	
	public function getTree() : Vector.<cSpace>
	{
		return tree;
	}
}