From 135699021c2556cefbc582d0a80d20fd2be7d075 Mon Sep 17 00:00:00 2001
From: dsc <david.schoonover@gmail.com>
Date: Fri, 26 Nov 2010 13:16:36 -0800
Subject: [PATCH] Trying out friendly AI. Some code reorganization.

---
 bin/check-css.sh                      |    3 +
 css/reset-old.css                     |    2 +
 css/reset.css                         |   49 +++-
 css/reset.min.css                     |    1 +
 src/Y/y-object.js                     |   10 +-
 src/easel/layer.js                    |  513 +++++++++++++++++++++++++++++
 src/easel/loop/cooldown.js            |   41 +++
 src/easel/loop/eventloop.js           |  122 +++++++
 src/easel/loop/fps.js                 |  101 ++++++
 src/easel/math/line.js                |  141 ++++++++
 src/easel/math/math.js                |   19 +
 src/easel/math/vec.js                 |  133 ++++++++
 src/easel/shape/circle.js             |   23 ++
 src/easel/shape/line.js               |  130 ++++++++
 src/easel/shape/polygon.js            |   63 ++++
 src/easel/shape/rect.js               |   28 ++
 src/easel/shape/shape.js              |   23 ++
 src/easel/util/astar.js               |  140 ++++++++
 src/easel/util/binaryheap.js          |  146 +++++++++
 src/easel/util/graph.js               |   16 +
 src/easel/util/tree/pointquadtree.js  |  580 +++++++++++++++++++++++++++++++++
 src/easel/util/tree/quadtree.js       |  241 ++++++++++++++
 src/easel/util/tree/rbtree.js         |  467 ++++++++++++++++++++++++++
 src/portal/layer.js                   |  513 -----------------------------
 src/portal/loop/cooldown.js           |   41 ---
 src/portal/loop/eventloop.js          |  122 -------
 src/portal/loop/fps.js                |  101 ------
 src/portal/math/line.js               |  141 --------
 src/portal/math/math.js               |   19 -
 src/portal/math/vec.js                |  133 --------
 src/portal/shape/circle.js            |   23 --
 src/portal/shape/line.js              |  130 --------
 src/portal/shape/polygon.js           |   63 ----
 src/portal/shape/rect.js              |   28 --
 src/portal/shape/shape.js             |   23 --
 src/portal/util/astar.js              |  140 --------
 src/portal/util/binaryheap.js         |  146 ---------
 src/portal/util/graph.js              |   16 -
 src/portal/util/tree/pointquadtree.js |  580 ---------------------------------
 src/portal/util/tree/quadtree.js      |  241 --------------
 src/portal/util/tree/rbtree.js        |  467 --------------------------
 src/tanks/game.js                     |    8 +-
 src/tanks/map/level.js                |    1 +
 src/tanks/map/pathmap.js              |    2 +-
 src/tanks/thing/bullet.js             |    2 +-
 src/tanks/ui/config.js                |   60 ----
 src/tanks/ui/main.js                  |    2 +-
 src/tanks/ui/ui-config.js             |   90 +++++
 src/tanks/util/config.js              |   92 +++++-
 tanks.php                             |   36 +-
 test/jsc/bar.js                       |    3 +
 test/jsc/baz.js                       |    2 +
 test/jsc/foo.js                       |    2 +
 test/jsc/jsc.py                       |  198 +++++++++++
 test/jsc/lol.js                       |    1 +
 test/math/index.php                   |    3 -
 test/uki/index.php                    |   79 +++++
 57 files changed, 3479 insertions(+), 3021 deletions(-)
 create mode 100755 bin/check-css.sh
 create mode 100644 css/reset-old.css
 create mode 100644 css/reset.min.css
 create mode 100644 src/easel/layer.js
 create mode 100644 src/easel/loop/cooldown.js
 create mode 100644 src/easel/loop/eventloop.js
 create mode 100644 src/easel/loop/fps.js
 create mode 100644 src/easel/math/line.js
 create mode 100644 src/easel/math/math.js
 create mode 100644 src/easel/math/vec.js
 create mode 100644 src/easel/shape/circle.js
 create mode 100644 src/easel/shape/line.js
 create mode 100644 src/easel/shape/polygon.js
 create mode 100644 src/easel/shape/rect.js
 create mode 100644 src/easel/shape/shape.js
 create mode 100644 src/easel/util/astar.js
 create mode 100644 src/easel/util/binaryheap.js
 create mode 100644 src/easel/util/graph.js
 create mode 100644 src/easel/util/tree/pointquadtree.js
 create mode 100644 src/easel/util/tree/quadtree.js
 create mode 100644 src/easel/util/tree/rbtree.js
 delete mode 100644 src/portal/layer.js
 delete mode 100644 src/portal/loop/cooldown.js
 delete mode 100644 src/portal/loop/eventloop.js
 delete mode 100644 src/portal/loop/fps.js
 delete mode 100644 src/portal/math/line.js
 delete mode 100644 src/portal/math/math.js
 delete mode 100644 src/portal/math/vec.js
 delete mode 100644 src/portal/shape/circle.js
 delete mode 100644 src/portal/shape/line.js
 delete mode 100644 src/portal/shape/polygon.js
 delete mode 100644 src/portal/shape/rect.js
 delete mode 100644 src/portal/shape/shape.js
 delete mode 100644 src/portal/util/astar.js
 delete mode 100644 src/portal/util/binaryheap.js
 delete mode 100644 src/portal/util/graph.js
 delete mode 100644 src/portal/util/tree/pointquadtree.js
 delete mode 100644 src/portal/util/tree/quadtree.js
 delete mode 100644 src/portal/util/tree/rbtree.js
 delete mode 100644 src/tanks/ui/config.js
 create mode 100644 src/tanks/ui/ui-config.js
 create mode 100644 test/jsc/bar.js
 create mode 100644 test/jsc/baz.js
 create mode 100644 test/jsc/foo.js
 create mode 100755 test/jsc/jsc.py
 create mode 100644 test/jsc/lol.js
 create mode 100644 test/uki/index.php
 create mode 100644 test/uki/test-uki.js

diff --git a/bin/check-css.sh b/bin/check-css.sh
new file mode 100755
index 0000000..4bc5456
--- /dev/null
+++ b/bin/check-css.sh
@@ -0,0 +1,3 @@
+#!/usr/local/bin/fish
+echo "$_" (dirname "$_")
+# ls -lia ~/dev/lang/css/reset* (dirname $_)/css/reset* | sort
diff --git a/css/reset-old.css b/css/reset-old.css
new file mode 100644
index 0000000..dd5886b
--- /dev/null
+++ b/css/reset-old.css
@@ -0,0 +1,2 @@
+html{color:#000;background:#FFF;}body,div,dl,dt,dd,ul,ol,li,h1,h2,h3,h4,h5,h6,pre,code,form,fieldset,legend,input,textarea,p,blockquote,th,td{margin:0;padding:0;}table{border-collapse:collapse;border-spacing:0;}fieldset,img{border:0;}address,caption,cite,code,dfn,em,strong,th,var{font-style:normal;font-weight:normal;}li{list-style:none;}caption,th{text-align:left;}h1,h2,h3,h4,h5,h6{font-size:100%;font-weight:normal;}q:before,q:after{content:'';}abbr,acronym {border:0;font-variant:normal;}sup {vertical-align:text-top;}sub {vertical-align:text-bottom;}input,textarea,select{font-family:inherit;font-size:inherit;font-weight:inherit;}input,textarea,select{*font-size:100%;}legend{color:#000;}
+h1{font-size:138.5%;}h2{font-size:123.1%;}h3{font-size:108%;}h1,h2,h3{margin:1em 0;}h1,h2,h3,h4,h5,h6,strong{font-weight:bold;}abbr,acronym{border-bottom:1px dotted #000;cursor:help;} em{font-style:italic;}blockquote,ul,ol,dl{margin:1em;}ol,ul,dl{margin-left:2em;}ol li{list-style:decimal outside;}ul li{list-style:disc outside;}dl dd{margin-left:1em;}th,td{padding:.5em;}th{font-weight:bold;text-align:center;}caption{margin-bottom:.5em;text-align:center;}p,fieldset,table,pre{margin-bottom:1em;}input[type=text],input[type=password],textarea{width:12.25em;*width:11.9em;}
\ No newline at end of file
diff --git a/css/reset.css b/css/reset.css
index dd5886b..0fbb22a 100644
--- a/css/reset.css
+++ b/css/reset.css
@@ -1,2 +1,47 @@
-html{color:#000;background:#FFF;}body,div,dl,dt,dd,ul,ol,li,h1,h2,h3,h4,h5,h6,pre,code,form,fieldset,legend,input,textarea,p,blockquote,th,td{margin:0;padding:0;}table{border-collapse:collapse;border-spacing:0;}fieldset,img{border:0;}address,caption,cite,code,dfn,em,strong,th,var{font-style:normal;font-weight:normal;}li{list-style:none;}caption,th{text-align:left;}h1,h2,h3,h4,h5,h6{font-size:100%;font-weight:normal;}q:before,q:after{content:'';}abbr,acronym {border:0;font-variant:normal;}sup {vertical-align:text-top;}sub {vertical-align:text-bottom;}input,textarea,select{font-family:inherit;font-size:inherit;font-weight:inherit;}input,textarea,select{*font-size:100%;}legend{color:#000;}
-h1{font-size:138.5%;}h2{font-size:123.1%;}h3{font-size:108%;}h1,h2,h3{margin:1em 0;}h1,h2,h3,h4,h5,h6,strong{font-weight:bold;}abbr,acronym{border-bottom:1px dotted #000;cursor:help;} em{font-style:italic;}blockquote,ul,ol,dl{margin:1em;}ol,ul,dl{margin-left:2em;}ol li{list-style:decimal outside;}ul li{list-style:disc outside;}dl dd{margin-left:1em;}th,td{padding:.5em;}th{font-weight:bold;text-align:center;}caption{margin-bottom:.5em;text-align:center;}p,fieldset,table,pre{margin-bottom:1em;}input[type=text],input[type=password],textarea{width:12.25em;*width:11.9em;}
\ No newline at end of file
+html { color:#000; background:#fff; width:100%; height:100%; }
+body { position:absolute; width:100%; top:0; left:0; }
+html,body,div,
+	dl,dt,dd,ul,ol,li,
+	h1,h2,h3,h4,h5,h6,
+	pre,code,
+	form,fieldset,legend,input,button,textarea,
+	p,blockquote,
+	th,td { margin:0; padding:0; }
+
+address,caption,cite,code,dfn,em,strong,th,var,optgroup { font-style:inherit; font-weight:inherit; }
+fieldset,img { border:0; }
+caption,th { text-align:left; }
+caption { margin-bottom:.5em; text-align:center; }
+
+h1,h2,h3,h4,h5,h6 { font-size:100%; font-weight:normal; }
+h1,h2,h3,h4,h5,h6,strong { font-weight:bold; }
+h1 { font-size:138.5%; }
+h2 { font-size:123.1%; }
+h3 { font-size:108%; }
+h1,h2,h3 { margin:0.5em 0 1em; }
+
+q:before,q:after { content:''; }
+del,ins { text-decoration:none; }
+abbr,acronym { border:0; font-variant:normal; border-bottom:1px dotted #000; cursor:help; }
+sup, sub { vertical-align:baseline; }
+em { font-style:italic; }
+
+input,button,textarea,select,optgroup,option { font-family:inherit; font-size:inherit; font-style:inherit; font-weight:inherit; }
+input,button,textarea,select { *font-size:100%; }
+input[type=text],input[type=password],textarea { width:12.25em; *width:11.9em; }
+legend { color:#000; }
+
+ul,ol,dl,blockquote { margin:1em; }
+ol,ul,dl { margin-left:2em; }
+li { list-style:none; }
+ol li { list-style:decimal outside; }
+ul li { list-style:disc outside; }
+dl dd { margin-left:1em; }
+
+table { border-collapse:collapse; border-spacing:0; }
+th,td { padding:.5em; }
+th { font-weight:bold; text-align:center; }
+p,fieldset,table,pre { margin-bottom:1em; }
+
+.clearer { clear:both !important; float:none !important; margin:0 !important; padding:0 !important; }
+.rounded { border-radius:1em; -moz-border-radius:1em; -webkit-border-radius:1em; }
\ No newline at end of file
diff --git a/css/reset.min.css b/css/reset.min.css
new file mode 100644
index 0000000..3c93c02
--- /dev/null
+++ b/css/reset.min.css
@@ -0,0 +1 @@
+html{color:#000;background:#fff;width:100%;height:100%;}body{position:absolute;width:100%;top:0;left:0;}html,body,div,dl,dt,dd,ul,ol,li,h1,h2,h3,h4,h5,h6,pre,code,form,fieldset,legend,input,button,textarea,p,blockquote,th,td{margin:0;padding:0;}address,caption,cite,code,dfn,em,strong,th,var,optgroup{font-style:inherit;font-weight:inherit;}fieldset,img{border:0;}caption,th{text-align:left;}caption{margin-bottom:.5em;text-align:center;}h1,h2,h3,h4,h5,h6{font-size:100%;font-weight:normal;}h1,h2,h3,h4,h5,h6,strong{font-weight:bold;}h1{font-size:138.5%;}h2{font-size:123.1%;}h3{font-size:108%;}h1,h2,h3{margin:.5em 0 1em;}q:before,q:after{content:'';}del,ins{text-decoration:none;}abbr,acronym{border:0;font-variant:normal;border-bottom:1px dotted #000;cursor:help;}sup,sub{vertical-align:baseline;}em{font-style:italic;}input,button,textarea,select,optgroup,option{font-family:inherit;font-size:inherit;font-style:inherit;font-weight:inherit;}input,button,textarea,select{*font-size:100%;}input[type=text],input[type=password],textarea{width:12.25em;*width:11.9em;}legend{color:#000;}ul,ol,dl,blockquote{margin:1em;}ol,ul,dl{margin-left:2em;}li{list-style:none;}ol li{list-style:decimal outside;}ul li{list-style:disc outside;}dl dd{margin-left:1em;}table{border-collapse:collapse;border-spacing:0;}th,td{padding:.5em;}th{font-weight:bold;text-align:center;}p,fieldset,table,pre{margin-bottom:1em;}.clearer{clear:both!important;float:none!important;margin:0!important;padding:0!important;}.rounded{border-radius:1em;-moz-border-radius:1em;-webkit-border-radius:1em;}
\ No newline at end of file
diff --git a/src/Y/y-object.js b/src/Y/y-object.js
index b286350..2d6b497 100644
--- a/src/Y/y-object.js
+++ b/src/Y/y-object.js
@@ -27,12 +27,13 @@ YCollection.subclass('YObject', {
     /**
      * Searches a heirarchical object for a given subkey specified in dotted-property syntax.
      * @param {Array|String} chain The property-chain to lookup.
+     * @param {Any} [def] Default value should the key be `undefined`.
      * @param {Boolean} [meta] If supplied return an object of the form
       *         `{ key: Qualified key name, obj: Parent object of key, value: Value at obj[key] }` 
       *     if chain is found (and `undefined` otherwise).
-     * @return {Any} The value at the path, or `undefined`.
+     * @return {Any} The value at the path, or `def` if `undefined`, otherwise `undefined`.
      */
-    getNested : function getNested(chain, meta){
+    getNested : function getNested(chain, def, meta){
         if ( !isArray(chain) )
             chain = chain.toString().split('.');
         
@@ -48,7 +49,10 @@ YCollection.subclass('YObject', {
                 };
         }, { value:this._o });
         
-        return (ret && !meta ? ret.value : ret);
+        if (ret !== undefined)
+            return (meta ? ret : ret.value);
+        else
+            return (meta ? { value:def } : def);
     },
     
     /**
diff --git a/src/easel/layer.js b/src/easel/layer.js
new file mode 100644
index 0000000..b6cd536
--- /dev/null
+++ b/src/easel/layer.js
@@ -0,0 +1,513 @@
+(function($, undefined){
+
+var CONTEXT_ATTRS = Y([
+    'globalAlpha', 'globalCompositeOperation',
+    'strokeStyle', 'fillStyle',
+    'lineWidth', 'lineCap', 'lineJoin', 'miterLimit',
+    'shadowOffsetX', 'shadowOffsetY', 'shadowBlur', 'shadowColor'
+]);
+
+
+
+Layer = Y.subclass('Layer', {
+    _cssClasses : 'portal layer',
+    
+    canvas   : null,
+    
+    parent   : null,
+    children : null,
+    
+    ctx      : null,
+    dirty    : true,
+    
+    canvasWidth : 0,    layerWidth  : 0,
+    canvasHeight : 0,   layerHeight : 0,
+    
+    x: 0, y: 0, loc : null, // Position relative to parent
+    
+    // Bleeds are marks outside the declared layer-size
+    negBleed : null, // Loc
+    posBleed : null, // Loc
+    
+    // Transforms
+    transform : null, // Object
+    useCanvasScaling : false, // default to CSS3 scaling
+    
+    
+    /// Setup ///
+    
+    init : function init(){
+        this.children = new Y.YArray();
+        
+        this.loc      = new Loc(0,0);
+        this.negBleed = new Loc(0,0);
+        this.posBleed = new Loc(0,0);
+        
+        this.boundingBox = new Loc.BoundingBox(0,0, 0,0);
+        
+        this.transform = {
+            origin    : new Loc('50%','50%'), // rotational origin
+            rotate    : 0,
+            scale     : new Loc(1.0,1.0),
+            translate : new Loc(0,0) // translates canvas
+        };
+        
+        this.canvas = jQuery('<canvas />');
+        this.ctx = this.canvas[0].getContext('2d');
+        
+        this.layer = jQuery('<div/>')
+            .addClass(this._cssClasses)
+            .append(this.canvas);
+        
+        this.layer[0].layer =
+        this.canvas[0].layer = this;
+    },
+    
+    /// Scene Graph Heirarchy ///
+    
+    /** @param {Layer} child */
+    append : function append(child){
+        new Y(arguments).invoke('appendTo', this);
+        return this;
+    },
+    
+    /** @param {Layer} parent */
+    appendTo : function appendTo(parent){
+        if (!parent) return this;
+        
+        // Always ensure we detach from the DOM and redraw this node
+        this.remove();
+        this.dirty = true;
+        
+        // Layer? Add self as new child, fix DOM
+        if ( parent instanceof Layer ){
+            this.parent = parent;
+            parent.children.push(this);
+            parent.layer.append(this.layer);
+            
+        // Otherwise: Attach to a DOM node as a new root layer node, leave parent null
+        } else
+            $(parent).append(this.layer);
+        
+        return this;
+    },
+    
+    /**
+     * Removes this layer from its parent and the DOM.
+     */
+    remove : function remove(){
+        if (this.parent)
+            this.parent.children.remove(this);
+        this.parent = null;
+        this.layer.remove();
+    },
+    
+    /**
+     * Clears this layer and destroys all children.
+     */
+    empty : function empty(ctx){
+        this.children.invoke('remove');
+        this.clear();
+        return this;
+    },
+    
+    /**
+     * @returns The root of the scene graph.
+     */
+    root : function root(){
+        if (this.parent)
+            return this.parent.root();
+        else
+            return this;
+    },
+    
+    
+    
+    
+    
+    /// Attributes ///
+    
+    
+    attr : function attr(key, value, def){
+        if (!key) return this;
+        
+        if ( Y.isPlainObject(key) ) {
+            for (var k in key)
+                this.attr(k, key[k]);
+            return this;
+            
+        // } else if ( CONTEXT_ATTRS.has(key) ) {
+        //     var r = Y.attr(this.ctx, key, value, def);
+        //     
+        //     if (r === this.ctx) {
+        //         // This implies we set a property
+        //         this.dirty = true;
+        //         return this;
+        //     } else
+        //         return r;
+        //     
+        } else
+            return Y.op.attr(this, key, value, def);
+    },
+    
+    /**
+     * Changes the layer's width and then updates the canvas.
+     */
+    width : function width(w){
+        if (w === undefined)
+            return this.layerWidth;
+        
+        this.layerWidth = w;
+        this.boundingBox = this.boundingBox.resize(w, this.layerHeight);
+        
+        var nb = this.negBleed.x
+        ,   v  = this.canvasWidth = Math.ceil(w + nb + this.posBleed.x);
+        this.layer.width(w).css('margin-left', (-nb)+'px')
+        this.canvas.width(v);
+        // this.canvas.css({
+        //     'width' : v+'px',
+        //     'margin-left' : (-nb)+'px'
+        // });
+        this.canvas[0].width = v;
+        
+        
+        return this;
+    },
+    
+    height : function height(h){
+        if (h === undefined)
+            return this.layerHeight;
+        
+        this.layerHeight = h;
+        this.boundingBox = this.boundingBox.resize(this.layerWidth, h);
+        
+        var nb = this.negBleed.y
+        ,   v  = this.canvasHeight = Math.ceil(h + nb + this.posBleed.y);
+        this.layer.height(h).css('margin-top', (-nb)+'px')
+        this.canvas.height(v);
+        // this.canvas.css({
+        //     'height' : v+'px',
+        //     'margin-top' : (-nb)+'px'
+        // });
+        this.canvas[0].height = v;
+        
+        return this;
+    },
+    
+    /**
+     * position() -> object 
+     * Gets position of the layer relative to the parent.
+     */
+    /**
+     * position(top, left) -> this
+     * Sets the position of this node, and then returns it.
+     * @param {Number|String|undefined} top If omitted, this method must be invoked with `undefined` as the first argument.
+     * @param {Number|String|undefined} left
+     */
+    /**
+     * position(pos) -> this
+     * Sets the position of this node, and then returns it.
+     * @param {Object} pos An object with "top" and/or "left" properties as in `position(top, left)`.
+     */
+    position : function position(left, top){
+        if (top === undefined && left === undefined)
+            return this.layer.position();
+        
+        if (top && Y.isPlainObject(top))
+            var pos = top;
+        else
+            var pos = { 'top': top, 'left':left };
+        
+        // if (pos.left !== undefined)  pos.left -= this.offsetX;
+        // if (pos.top  !== undefined)  pos.top  -= this.offsetY;
+        
+        this.boundingBox = this.boundingBox.add(pos.left,pos.top);
+        this.loc = this.boundingBox.p1;
+        this.css(pos);
+        return this;
+    },
+    
+    stroke : function stroke(style, width){
+        if (style === undefined && width === undefined)
+            return this.strokeStyle;
+        
+        if (width !== undefined)
+            this.lineWidth = width;
+        
+        this.dirty = true;
+        this.strokeStyle = style;
+        return this;
+    },
+    
+    fill : function fill(style){
+        if (style === undefined)
+            return this.fillStyle;
+        
+        this.dirty = true;
+        this.fillStyle = style;
+        return this;
+    },
+    
+    hide : makeDelegate('hide'),
+    show : makeDelegate('show'),
+    
+    /** CSS properties */
+    css : makeDelegate('css'),
+    
+    /** Position relative to document. */
+    offset : makeDelegate('offset'),
+    
+    
+    
+    /// Transformations ///
+    
+    /**
+     * Gets and sets the transformation origin.
+     */
+    origin : function origin(x,y){
+        var o = this.transform.origin;
+        if (arguments.length === 0)
+            return o.absolute(this.layerWidth, this.layerHeight);
+        
+        o.x = x;
+        o.y = y;
+        return this._applyTransforms();
+    },
+    
+    /**
+     * Rotates this layer by r radians.
+     */
+    rotate : function rotate(r){
+        var t = this.transform;
+        if (r === undefined)
+            return t.rotate;
+        
+        t.rotate = r;
+        return this._applyTransforms();
+    },
+    
+    /**
+     * Scales this layer by (sx,sy), and then applies scaling relatively
+     * to all sublayers (preserving knowledge of their individual scaling).
+     */
+    scale : function scale(sx,sy){
+        var o = this.transform.scale;
+        if (arguments.length === 0)
+            return o.absolute(this.layerWidth, this.layerHeight);
+        
+        o.x = sx;
+        o.y = sy;
+        this.dirty = true;
+        return this._applyTransforms();
+    },
+    
+    /**
+     * Translates draw calls by (x,y) within this layer only. This allows you to
+     * functionally move the coordinate system of the layer.
+     */
+    translate : function translate(x,y){
+        var o = this.transform.translate;
+        if (arguments.length === 0)
+            return o.absolute(this.layerWidth, this.layerHeight);
+        
+        o.x = x;
+        o.y = y;
+        this.dirty = true;
+        return this;
+    },
+    
+    _applyTransforms : function _applyTransforms(){
+        var t = this.transform, tfns = [];
+        
+        if (t.rotate !== 0)
+            tfns.push('rotate('+t.rotate+'rad)');
+        
+        if (!this.useCanvasScaling && (t.scale.x !== 1 || t.scale.y !== 1))
+            tfns.push('scale('+t.scale.x+','+t.scale.y+')');
+        
+        var trans = (tfns.length ? tfns.join(' ') : 'none')
+        ,   o = t.origin.toUnits()
+        ,   origin = o.x+' '+o.y ;
+        this.layer.css(
+            ['', '-moz-', '-webkit-'].reduce(
+                function(values, prefix){
+                    values[prefix+'transform'] = trans;
+                    values[prefix+'transform-origin'] = origin;
+                    return values;
+                }, {}) );
+        return this;
+    },
+    
+    
+    
+    
+    
+    
+    
+    /// Iterators ///
+    
+    invoke : function invoke(name){
+        var args = Y(arguments,1);
+        // this[name].apply(this, args);
+        // this.children.invoke.apply(this.children, ['invoke', name].concat(args));
+        return this._invoke(name, args);
+    },
+    _invoke : function _invoke(name, args){
+        this[name].apply(this, args);
+        this.children.invoke('_invoke', name, args);
+        return this;
+    },
+    
+    setAll : function setAll(k,v){
+        this[k] = v;
+        this.children.invoke('setAll', k,v);
+        return this;
+    },
+    
+    /**
+     * Reduce "up", across this and parents, inner to outer:
+     *      acc = fn.call(context || node, acc, node)
+     */
+    reduceup : function reduceup(acc, fn, context){
+        // if ( Y.isFunction(fn) )
+        //     acc = fn.call(context || this, acc, this);
+        // else
+        //     acc = this[fn].call(context || this, acc, this);
+        acc = fn.call(context || this, acc, this);
+        return ( this.parent ? this.parent.reduceup(acc, fn, context) : acc );
+    },
+    
+    /**
+     * Reduce "down", across this and children, depth-first:
+     *      acc = fn.call(context || node, acc, node)
+     */
+    reduce : function reduce(acc, fn, context){
+        acc = fn.call(context || this, acc, this);
+        return this.children.reduce(acc, fn, context);
+    },
+    
+    
+    
+    
+    
+    
+    /// Drawing Functions ///
+    
+    /**
+     * @param {CanvasDrawingContext2D} [ctx=this.ctx] Forces context to use rather than the layer's own.
+     * @param {Boolean} [force=false] Forces redraw.
+     */
+    draw : function draw(ctx, force){
+        if ( this.dirty || force ){
+            var _ctx = ctx || this.ctx;
+            this._openPath(_ctx);
+            this.drawShape(_ctx);
+            this._closePath(_ctx);
+        }
+        
+        this.dirty = false;
+        this.children.invoke('draw', ctx, force);
+        return this;
+    },
+    
+    _openPath : function _openPath(ctx){
+        var self = this
+        ,   alwaysClear = this.alwaysClear
+        ,   neg = this.negBleed
+        ,   t = this.transform
+        ,   w = this.canvasWidth, h = this.canvasHeight ;
+        
+        ctx.beginPath();
+        ctx.setTransform(1,0,0,1,0,0);
+        ctx.clearRect(-w,-h, 2*w,2*h);
+        
+        if (this.useCanvasScaling && (t.scale.x !== 1 || t.scale.y !== 1))
+            ctx.scale(t.scale.x,t.scale.y);
+        
+        ctx.translate(neg.x, neg.y);
+        ctx.translate(t.translate.x, t.translate.y);
+        
+        // Set context attributes
+        CONTEXT_ATTRS.forEach(function(name){
+            if (self[name] !== undefined)
+                ctx[name] = self[name];
+            else if (alwaysClear)
+                delete ctx[name];
+        });
+        
+        return this;
+    },
+    
+    /** To be implemented by subclasses. */
+    drawShape : function drawShape(ctx){ return this; },
+    
+    _closePath : function _closePath(ctx){
+        ctx.closePath();
+        return this;
+    },
+    
+    /**
+     * Clears this layer and all children.
+     */
+    clear : function clear(ctx){
+        var w = this.canvas.width()
+        ,   h = this.canvas.height();
+        ctx = ctx || this.ctx;
+        ctx.beginPath();
+        ctx.setTransform(1,0,0,1,0,0);
+        ctx.clearRect(-w,-h, 2*w,2*h);
+        ctx.closePath();
+        this.children.invoke('clear');
+        return this;
+    },
+    
+    // for debugging
+    point : function point(x,y, color){
+        var ctx = this.ctx;
+        // this._openPath(ctx);
+        
+        var r = 2;
+        ctx.beginPath();
+        ctx.arc(x,y, r, 0, Math.PI*2, false);
+        ctx.fillStyle = color || '#FFFFFF';
+        ctx.fill();
+        ctx.closePath();
+        
+        // this._closePath(ctx);
+        return this;
+    },
+    
+    
+    
+    /// Misc ///
+    toString : function toString(){
+        var pos = (this.layer ? this.position() : {top:NaN, left:NaN});
+        return this.className+'['+pos.left+','+pos.top+']( children='+this.children.size()+' )';
+    }
+});
+
+function makeDelegate(name, dirties, prop){
+    prop = prop || 'layer';
+    return function(){
+        if (dirties && arguments.length)
+            this.dirty = true;
+        
+        var target = this[prop]
+        ,   result = target[name].apply(target, arguments);
+        
+        return (result !== target ? result : this);
+    };
+}
+
+// Install CSS styles
+$(function(){
+    $('<style />')
+        .text([
+            '.portal.layer { position:absolute; z-index:1; top:0; left:0; line-height:0; }',
+            // '.portal.layer { outline:1px solid #000000; }',
+            '.portal.layer canvas { z-index:0; }'
+        ].join('\n'))
+        .appendTo('head');
+});
+
+})(jQuery);
diff --git a/src/easel/loop/cooldown.js b/src/easel/loop/cooldown.js
new file mode 100644
index 0000000..1a61a37
--- /dev/null
+++ b/src/easel/loop/cooldown.js
@@ -0,0 +1,41 @@
+Cooldown = Y.subclass('Cooldown', {
+    'init' : function(cooldown, isReady){
+        this.cooldown = cooldown; // ms
+        this.ready    = isReady || true;
+        this.last     = new Date().getTime();
+    },
+    
+    'activate' : function(now){
+        now = now || new Date().getTime();
+        if ( this.ready ) {
+            this.ready = false;
+            this.last  = now;
+            return true;
+        }
+        return false;
+    },
+    
+    'update' : function(now){
+        if (this.ready) return true;
+        
+        now = now || new Date().getTime();
+        if ( (this.last+this.cooldown) <= now )
+            this.ready = true;
+        
+        return this.ready;
+    },
+    
+    'setCooldown' : function(cooldown, now){
+        this.cooldown = cooldown;
+        return this.update(now);
+    },
+    
+    'ratio' : function(now){
+        now = now || new Date().getTime();
+        if ( this.update(now) )
+            return 1.0;
+        else
+            return now / (this.last+this.cooldown);
+    }
+    
+});
diff --git a/src/easel/loop/eventloop.js b/src/easel/loop/eventloop.js
new file mode 100644
index 0000000..84b8325
--- /dev/null
+++ b/src/easel/loop/eventloop.js
@@ -0,0 +1,122 @@
+(function(){
+
+function add(a,b){ return a+b; }
+
+function decorate(delegate){
+    if (!delegate) return;
+    Y.event.Emitter.prototype.decorate.call(this, delegate);
+    'start stop reset'.split(' ').forEach(function(k){
+        delegate[k] = methods[k].bind(this);
+    }, this);
+    return delegate;
+}
+
+var
+MIN_TICK_INTERVAL = 0, // ms
+NUM_SAMPLES = 33,
+
+methods = {
+    // framerate : 0, // Target framerate
+    // frametime : 0, // 1000 / framerate
+    // samples   : NUM_SAMPLES, // Number of frames to track for effective fps
+    // 
+    // now       : 0, // Last tick time (ms)
+    // fps       : 0, // Effective framerate
+    // ticks     : 0, // Number of ticks since start
+    // 
+    // timer     : null,
+    // running   : false,
+    // times     : null, // Last `samples` frame durations
+    
+    
+    init : function init(target, framerate, samples){
+        Y.event.Emitter.init.call(this, target);
+        decorate.call(this, target);
+        this.tick = this.tick.bind(this);
+        this.decorate = decorate.bind(this);
+        
+        this.framerate = framerate;
+        this.targetTime = 1000 / framerate;
+        this.samples = samples || NUM_SAMPLES;
+        
+        this.reset();
+    },
+    
+    reset : function reset(){
+        this.stop();
+        this.elapsedAtStop = 0;
+        this.ticks = 0;
+        this.times = [];
+        this.realtimes = [];
+    },
+    
+    start : function start(){
+        if (this.running) return;
+        
+        this.running = true;
+        this.now = new Date().getTime() - (this.elapsedAtStop || this.targetTime);
+        this.fire('start');
+        
+        if (this.elapsedAtStop > 0)
+            this.sleepMinus(this.elapsedAtStop);
+        else
+            this.tick();
+        this.elapsedAtStop = 0;
+    },
+    
+    stop : function stop(){
+        if (!this.running) return;
+        
+        clearTimeout(this.timer);
+        this.elapsedAtStop = Math.min(this.targetTime, new Date().getTime() - this.now);
+        this.timer = null;
+        this.running = false;
+        this.fire('stop');
+    },
+    
+    sleepMinus : function sleepMinus(tFrame){
+        if (this.timer !== null) return;
+        
+        var tickInt = Math.max(MIN_TICK_INTERVAL, this.targetTime - tFrame);
+        this.timer = setTimeout(this.tick, tickInt);
+    },
+    
+    tick : function tick(){
+        if (!this.running) return;
+        
+        var lastTick = this.now;
+        this.now     = new Date().getTime();
+        this.elapsed = this.now - lastTick;
+        
+        clearTimeout(this.timer);
+        this.timer = null;
+        
+        this.fire('tick', this, {
+            now     : this.now,
+            elapsed : this.elapsed,
+            ticks   : ++this.ticks
+        });
+        
+        var tFrame = this.tFrame = new Date().getTime() - this.now;
+        this.sleepMinus(tFrame);
+        
+        this.realtimes.push(tFrame);
+        this.times.push(Math.max(tFrame, this.targetTime));
+        if (this.times.length > this.samples){
+            this.times.shift();
+            this.realtimes.shift();
+        }
+    },
+    
+    fps : function fps(){
+        return 1000 / (this.times.reduce(Y.op.add,0) / this.times.length);
+    },
+    
+    frametime : function frametime(){
+        return (this.realtimes.reduce(Y.op.add,0) / this.realtimes.length);
+    }
+    
+};
+this.EventLoop = new Y.Class('EventLoop', Y.event.Emitter, methods);
+
+})();
diff --git a/src/easel/loop/fps.js b/src/easel/loop/fps.js
new file mode 100644
index 0000000..9038237
--- /dev/null
+++ b/src/easel/loop/fps.js
@@ -0,0 +1,101 @@
+FpsSparkline = Y.subclass('FpsSparkline', {
+    
+    init : function init(loop, el, w,h, maxBuffer, interval){
+        this.buffer    = [];
+        
+        this.el        = el;
+        this.width     = w !== undefined ? w : 'auto';
+        this.height    = h !== undefined ? h : 'auto';
+        
+        // Wrap tick function to extract data
+        this.loop      = loop;
+        this.loopTick  = loop.tick;
+        loop.tick      = this.tickTime.bind(this);
+        
+        // Aggregation counters
+        this.ticks     = 0;
+        this.tickSum   = 0;
+        
+        this.maxBuffer = maxBuffer || 0; // intervals to show
+        this.interval  = interval  || loop.framerate; // ticks to aggregate into an interval
+        
+        $(this.setup.bind(this));
+    },
+    
+    setup : function setup(){
+        this.el = $(this.el);
+        
+        var w = this.el.parent().width();
+        if (this.width === 0)
+            this.width = w+'px';
+        if (this.height === 0)
+            this.height = this.el.height()+'px';
+        if (this.maxBuffer === 0)
+            this.maxBuffer = Math.floor(w / 3);
+    },
+    
+    tickTime : function tickTime(){
+        if (!this.loop.running) return;
+        
+        var loop = this.loop
+        ,   buf  = this.buffer
+        ;
+        this.loopTick.call(loop);
+        
+        this.ticks++;
+        this.tickSum += loop.tFrame;
+        
+        if (this.ticks >= this.interval) {
+            buf.push( this.tickSum/this.ticks );
+            this.tickSum = this.ticks = 0;
+            if (buf.length > this.maxBuffer) buf.shift();
+        }
+    },
+    
+    /**
+     * Draws average render time across interval frames
+     */
+    drawTimes : function drawTimes(){
+        var buf = this.buffer
+        ,   max = this.maxBuffer
+        ,   diff = max - buf.length
+        ;
+        
+        if (!buf.length) return;
+        
+        if (diff > 0) {
+            buf = buf.slice(0);
+            while (diff-- > 0) buf.push(null);
+        }
+        
+        this.el
+            .sparkline( buf,
+                { type             : 'line'
+                
+                , width            : this.width
+                , height           : this.height
+                
+                , lineColor        : '#2F2F2F'
+                , fillColor        : '#2F2F2F'
+                , spotColor        : false
+                , minSpotColor     : '#83BB32'
+                , maxSpotColor     : '#AF2A31'
+                
+                // , chartRangeMin    : 0
+                // , chartRangeMax    : 100
+                // , normalRangeColor : '#7F7F7F'
+                // , normalRangeMin   : 0
+                // , normalRangeMax   : this.loop.frametime
+                });
+    },
+    
+    /**
+     * Draws average FPS over interval.
+     */
+    drawFps : function drawFps(){
+        
+    }
+    
+    
+});
+
diff --git a/src/easel/math/line.js b/src/easel/math/line.js
new file mode 100644
index 0000000..3224e41
--- /dev/null
+++ b/src/easel/math/line.js
@@ -0,0 +1,141 @@
+(function(){
+
+var
+Vec = math.Vec,
+HALF_PI = Math.PI/2,
+SIN_HALF_PI = Math.sin(HALF_PI),
+COS_HALF_PI = Math.cos(HALF_PI);
+
+
+/**
+ * A line in the cartesian plane.
+ */
+math.Line = math.Vec.subclass('Line', {
+    
+    init : function initLine(x1,y1, x2,y2, tdist){
+        this.x1 = x1; this.y1 = y1;
+        this.x2 = x2; this.y2 = y2;
+        
+        var x0 = x2-x1
+        ,   y0 = y2-y1
+        
+        ,    m = this.slope  =  y0/x0
+        ,   yi = this.yint   = -x1*m + y1
+        ,   xi = this.xint   = -y1/m + x1
+        ;
+        math.Vec.init.call(this, x0,y0);
+        
+        this.p1 = new math.Vec(x1,y1);
+        this.p2 = new math.Vec(x2,y2);
+        
+        this.theta = Math.atan2(y0, x0);
+        this._cos  = Math.cos(this.theta);
+        this._sin  = Math.sin(this.theta);
+        
+        this.setTScale(tdist);
+    },
+    
+    clone : function clone(){
+        return new math.Line(this.x1,this.y1, this.x2,this.y2, this.tdist);
+    },
+    
+    
+    
+    setTScale : function setTScale(tdist){
+        if (tdist) {
+            this.tdist = tdist;
+            this.pa = tdist * this._cos;
+            this.pb = tdist * this._sin;
+        } else {
+            this.tdist = this.y / this._sin;
+            this.pa = this.x;
+            this.pb = this.y;
+        }
+        return this;
+    },
+    
+    parametric : function parametric(t){
+        return new math.Vec( this.x1 + t*this.pa ,
+                             this.y1 + t*this.pb );
+    },
+    
+    iparametric : function iparametric(x,y){
+        return new math.Vec( (x-this.x1)/this.pa ,
+                             (y-this.y1)/this.pa );
+    },
+    
+    pointAtX : function pointAtX(x){ return new math.Vec(x, this.calcY(x)); },
+    pointAtY : function pointAtY(y){ return new math.Vec(this.calcX(y), y); },
+    calcY : function calcY(x){ return (x !== this.xint ? x*this.slope + this.yint : 0); },
+    calcX : function calcX(y){ return (y !== this.yint ? y/this.slope + this.xint : 0); },
+    
+    near : function near(x,y){
+        if ( !isFinite(this.slope) )
+            return this.pointAtY(y);
+        else
+            return this.pointAtX(x);
+    },
+    
+    
+    
+    equals : function equals(line){
+        return ( this.slope === line.slope
+            && this.x1 === line.x1 && this.y1 === line.y1
+            && this.x2 === line.x2 && this.y2 === line.y2 );
+    },
+    
+    intersects : function intersects(x,y){
+        var o = x;
+        if (o instanceof math.Line)
+            return this.slope !== o.slope || this.equals(o);
+        
+        if (o instanceof math.Vec) {
+            x = o.x;
+            y = o.y;
+        }
+        return this.calcY(x) === y;
+    },
+    
+    isWithin : function isWithin(pt, w,h){
+        if ( !Y.isNumber(w) ){
+            h = w.height; w = w.width;
+        }
+        var dw = Math.abs(this.calcX(pt.y) - pt.x)
+        ,   dh = Math.abs(this.calcY(pt.x) - pt.y) ;
+        return dw <= w || dh <= h ;
+    },
+    
+    
+    
+    vec : function vec(){
+        return new math.Vec(this.x, this.y); // reset to vector from origin
+    },
+    
+    base : function base(){
+        if (!this._base)
+            this._base = new math.Line(0,0, this.x,this.y);
+        return this._base;
+    },
+    
+    tangent : function tangent(at){
+        var slope = this.slope;
+        
+        if ( slope === 0 )
+            return new math.Line(at.x,at.y, at.x,at.y+1, this.tdist);
+        
+        if ( !isFinite(slope) )
+            return new math.Line(at.x,at.y, at.x+1,at.y, this.tdist);
+        
+        var x1 = at.x, y1 = at.y
+        ,   x2 = at.x - at.y + (at.y !== this.y1 ? this.y1 : this.y2)
+        ,   y2 = at.y + at.x - (at.x !== this.x1 ? this.x1 : this.x2) ;
+        return new math.Line(x1,y1, x2,y2, this.tdist);
+    },
+    
+    toString : function toString(){
+        return '['+this.p1+', '+this.p2+', slope='+this.slope.toFixed(3)+']';
+    }
+    
+});
+
+})();
\ No newline at end of file
diff --git a/src/easel/math/math.js b/src/easel/math/math.js
new file mode 100644
index 0000000..882cdbb
--- /dev/null
+++ b/src/easel/math/math.js
@@ -0,0 +1,19 @@
+math = {
+    clamp : function clamp(value, min, max) {
+      return Math.min(Math.max(value, min), max);
+    },
+    
+    lerp : function lerp(x, a, b) {
+        return a + x*(b - a);
+    },
+    
+    reflect : function reflect(v, line){
+        var dot   = math.Vec.dot
+        ,   basev = math.Vec.difference(v, line.p1);
+        return line.vec()
+            .scale(2 * dot(basev,line) / dot(line,line))
+            .subtract(basev)
+            .add(line.p1);
+    }
+    
+};
\ No newline at end of file
diff --git a/src/easel/math/vec.js b/src/easel/math/vec.js
new file mode 100644
index 0000000..d0035a0
--- /dev/null
+++ b/src/easel/math/vec.js
@@ -0,0 +1,133 @@
+/**
+ * A 2-dimensional vector.
+ */
+math.Vec = new Y.Class('Vec', [], {
+    
+    init : function init(x, y){
+        this.length = 2;
+        
+        if ( x instanceof Array ) {
+            y = x[1]; x = x[0];
+        }
+        this.setXY(x,y);
+    },
+    
+    equals : function equals(b){
+        return (this.x === b.x) && (this.y === b.y);
+    },
+    
+    clone : function clone(){
+        return new math.Vec(this.x, this.y);
+    },
+    
+    setXY : function setXY(x,y){
+        this.x = this[0] = x;
+        this.y = this[1] = y;
+        return this;
+    },
+    
+    add : function add(x,y){
+        if ( x instanceof Array ) {
+            y = x[1]; x = x[0];
+        }
+        return this.setXY(this.x+x, this.y+y);
+    },
+    
+    subtract : function subtract(x,y){
+        if ( x instanceof Array ) {
+            y = x[1]; x = x[0];
+        }
+        return this.setXY(this.x-x, this.y-y);
+    },
+    
+    scale : function scale(s){
+        return this.setXY(this.x*s, this.y*s);
+    },
+    
+    invert : function invert(){
+        return this.setXY(-this.x, -this.y);
+    },
+    
+    normalize : function normalize(){
+        return this.scale(1 / this.magnitude());
+    },
+    
+    magnitude : function magnitude(){
+        return Math.sqrt(this.x*this.x + this.y*this.y);
+    },
+    
+    sqMagnitude : function sqMagnitude(){
+        return this.x*this.x + this.y*this.y;
+    },
+    
+    dot : function dot(b){
+        return this.x*b.x + this.y*b.y;
+    },
+    
+    manhattan: function manhattan(x2,y2) {
+        if (x2 instanceof math.Vec) {
+            y2 = x2.y; x2 = x2.x;
+        }
+        var d1 = Math.abs(x2 - this.x)
+        ,   d2 = Math.abs(y2 - this.y) ;
+        return d1 + d2;
+    },
+    
+    rotate : function rotate(theta){
+        var sin = Math.sin(theta)
+        ,   cos = Math.cos(theta)
+        ,   x = this.x, y = this.y ;
+        return this.setXY(x*cos - y*sin, x*sin + y*cos);
+    },
+    
+    toString : function toString(){
+        var p = 2, x = this.x, y = this.y;
+        x = ((x % 1 !== 0) ? x.toFixed(p) : x);
+        y = ((y % 1 !== 0) ? y.toFixed(p) : y);
+        return '('+x+', '+y+')';
+    }
+    
+});
+
+Y.extend(math.Vec, {
+    sum : function sum(a, b) {
+        return new math.Vec(a.x+b.x, a.y+b.y);
+    },
+    
+    difference : function difference(a, b) {
+        return new math.Vec(a.x-b.x, a.y-b.y);
+    },
+    
+    dot : function dot(a, b) {
+        return a.x*b.x + a.y*b.y;
+    },
+    
+    lerp : function lerp(x, a, b) {
+        return new math.Vec( math.lerp(a.x, b.x, x),
+                             math.lerp(a.y, b.y, x)  );
+    },
+    
+    // manhattan: function manhattan(p1, p2) {
+    //     var d1 = Math.abs(p2.x - p1.x)
+    //     ,   d2 = Math.abs(p2.y - p1.y) ;
+    //     return d1 + d2;
+    // },
+    
+    // manhattan4: function manhattan4(x1,y1, x2,y2) {
+    //     var d1 = Math.abs(x2 - x1)
+    //     ,   d2 = Math.abs(y2 - y1) ;
+    //     return d1 + d2;
+    // },
+    
+    manhattan: function manhattan(x1,y1, x2,y2) {
+        if (x1 instanceof Array && y1 instanceof Array) {
+            y2 = y1[1]; x2 = y1[0];
+            y1 = x1[1]; x1 = x1[0];
+        }
+        var d1 = Math.abs(x2 - x1)
+        ,   d2 = Math.abs(y2 - y1) ;
+        return d1 + d2;
+    },
+    
+    
+});
diff --git a/src/easel/shape/circle.js b/src/easel/shape/circle.js
new file mode 100644
index 0000000..16c9c6a
--- /dev/null
+++ b/src/easel/shape/circle.js
@@ -0,0 +1,23 @@
+
+Circle = new Y.Class('Circle', Shape, {
+    _cssClasses : 'portal layer shape circle',
+    
+    init : function initCircle(radius, centerTL){
+        Layer.init.call(this);
+        
+        var d = radius * 2;
+        this.radius = radius;
+        if (!centerTL)
+            this.negBleed.x = this.negBleed.y = radius;
+        this.width(d).height(d);
+            // .origin(radius,radius);
+    },
+    
+    drawShape : function drawShape(ctx){
+        var r  = this.radius, nb = this.negBleed;
+        ctx.arc(r-nb.x,r-nb.y, r, 0, Math.PI*2, false);
+        ctx.fill();
+        ctx.stroke();
+    }
+    
+});
diff --git a/src/easel/shape/line.js b/src/easel/shape/line.js
new file mode 100644
index 0000000..504037a
--- /dev/null
+++ b/src/easel/shape/line.js
@@ -0,0 +1,130 @@
+
+Line = new Y.Class('Line', Shape, {
+    _cssClasses : 'portal layer shape line',
+    
+    useCanvasScaling : true,
+    fillStyle   : 'transparent',
+    strokeStyle : "#000000",
+    lineWidth   : 1,
+    
+    drawDefinitionPoints : false,
+    invertY : false,
+    
+    
+    init : function initLine(x,y){
+        Layer.init.call(this);
+        
+        this.sublayer = jQuery('<div style="overflow:hidden" />')
+            .append(this.canvas)
+            .appendTo(this.layer);
+        
+        this.x2 = x; this.y2 = y;
+        this.position(0,0);
+    },
+    
+    position : function position(left, top){
+        if (top === undefined && left === undefined)
+            return this.line.p1;
+        
+        var pos = Y.isPlainObject(top) ? top : {'top':top, 'left':left};
+        
+        this.x1 = pos.left; this.x2 += this.x1;
+        this.y1 = pos.top;  this.y2 += this.y1;
+        
+        this.line = new math.Line(this.x1,this.y1, this.x2,this.y2, (this.line||{}).tdist);
+        
+        return this;
+    },
+    
+    origin : function origin(x,y){
+        var o = this.transform.origin;
+        if (arguments.length === 0)
+            return o.absolute(this.layerWidth, this.layerHeight);
+        
+        o.x = x;
+        o.y = y;
+        this.ctx.translate(x,y);
+        this.dirty = true;
+        return this._applyTransforms();
+    },
+    
+    appendTo : function appendTo(parent){
+        var r = Layer.prototype.appendTo.call(this, parent);
+        this._fixSize();
+        return r;
+    },
+    
+    _fixSize : function _fixSize(){
+        var p  = this.parent
+        ,   pw = p.canvasWidth,    ph = p.canvasHeight
+        ,   w  = this.canvasWidth, h  = this.canvasHeight
+        ;
+        
+        if (w !== pw) {
+            this.width(pw);
+            this.sublayer.width(pw);
+        }
+        if (h !== ph) {
+            this.height(ph);
+            this.sublayer.height(ph);
+        }
+        return this;
+    },
+    
+    drawShape : function drawShape(ctx){
+        this._fixSize();
+        var x1,y1, x2,y2
+        ,   line = this.line, p1 = line.p1, p2 = line.p2
+        ,   t = this.transform.translate
+        ,   minW = -t.x, minH = -t.y
+        ,   maxW = this.canvasWidth+minW, maxH = this.canvasHeight+minH
+        ;
+        
+        // We need endpoints at the edges of the viewport to draw the full line.
+        x1 = minW; y1 = line.calcY(x1);
+        if (isNaN(y1) || !isFinite(y1)) {
+            y1 = minH; x1 = line.calcX(y1);
+        }
+        
+        x2 = maxW; y2 = line.calcY(x2);
+        if (isNaN(y2) || !isFinite(y2)) {
+            y2 = maxH; x2 = line.calcX(y2);
+        }
+        
+        if (this.invertY){
+            y1 = -y1;
+            y2 = -y2;
+        }
+        
+        // try {
+            ctx.moveTo(x1,y1);
+            ctx.lineTo(x2,y2);
+            ctx.stroke();
+            ctx.closePath();
+        // } catch(e) {
+        //     if (window.console) {
+        //         console.error(this+'.drawShape()');
+        //         console.log('  points:', x1,y1, ' ', x2,y2);
+        //         console.log('  bounds:', minW,minH, ' ', maxW,maxH);
+        //         console.log('  ::', this, line);
+        //     }
+        // }
+        
+        // Show definition points
+        if ( this.drawDefinitionPoints ) {
+            this.point(p1.x,p1.y, 'rgba(46,98,201,  0.4)');
+            this.point(p2.x,p2.y, 'rgba(69,150,255, 0.4)');
+        }
+    },
+    
+    
+    toString : function toString(){
+        return this.className+'['+this.x1+','+this.y1+', '+this.x2+','+this.y2+']';
+    }
+    
+    
+});
+Line.fromPoints = function fromPoints(x1,y1, x2,y2){
+    return new Line(x2-x1, y2-y1).position(x1,y1);
+};
+
diff --git a/src/easel/shape/polygon.js b/src/easel/shape/polygon.js
new file mode 100644
index 0000000..a2cf377
--- /dev/null
+++ b/src/easel/shape/polygon.js
@@ -0,0 +1,63 @@
+
+Polygon = new Y.Class('Polygon', Shape, {
+    _cssClasses : 'portal layer shape polygon',
+    
+    /**
+     * Expects two arrays of coordinate-halfs, which could be zipped
+     * together to make the numbered coordinates.
+     * x0 and y0 will always be 0.
+     */
+    init : function initPolygon(xs, ys){
+        Layer.init.call(this);
+        
+        var xs = this._calcDimension('x', xs)
+        ,   ys = this._calcDimension('y', ys)
+        ,   w  = Math.max.apply(Math, xs)
+        ,   h  = Math.max.apply(Math, ys)
+        ;
+        
+        this.points = Y(xs).zip(ys).map(Loc.instantiate, Loc);
+        this.width(w)
+            .height(h);
+            // .origin(w/2, h/2);
+    },
+    
+    drawShape : function drawShape(ctx){
+        this.points.forEach(function(loc, i){
+            ctx.lineTo(loc.x, loc.y);
+        });
+        ctx.fill();
+    }
+});
+
+
+Triangle = new Y.Class('Triangle', Polygon, {
+    _cssClasses : 'portal layer shape polygon triangle',
+    
+    init : function initTriangle(x1,y1, x2,y2){
+        Polygon.init.call(this, [x1,x2], [y1,y2]);
+    },
+    
+    circumcenter : function circumcenter(){
+        var offX = this.offsetX, offY = this.offsetY
+        ,   x1 = this.x1 - offX, y1 = -1 * (this.y1 - offY) // remember, DOM is Y-inverted
+        ,   x2 = this.x2 - offX, y2 = -1 * (this.y2 - offY) // which affects the signs
+        
+        ,   D = 2 * (x1*y2 - y1*x2)
+        ,   B = Math.pow(x1,2) + Math.pow(y1,2)
+        ,   C = Math.pow(x2,2) + Math.pow(y2,2)
+        ;
+        return { 'x' : offX + (y2*B - y1*C)/D
+               , 'y' : offY + (x1*C - x2*B)/D * -1 // fix inverted Y-axis
+               };
+    },
+});
+
+Quad = new Y.Class('Quad', Polygon, {
+    _cssClasses : 'portal layer shape polygon quad',
+    
+    init : function initQuad(x1,y1, x2,y2, x3,y3){
+        Polygon.init.call(this, [x1,x2,x3], [y1,y2,y3]);
+    }
+    
+});
diff --git a/src/easel/shape/rect.js b/src/easel/shape/rect.js
new file mode 100644
index 0000000..ea8ca8c
--- /dev/null
+++ b/src/easel/shape/rect.js
@@ -0,0 +1,28 @@
+
+Rect = Shape.subclass('Rect', {
+    _cssClasses : 'portal layer shape rect',
+    
+    init : function initRect(w,h){
+        Layer.init.call(this);
+        
+        this.width(w)
+            .height(h);
+            // .origin(w/2, h/2);
+    },
+    
+    drawShape : function drawShape(ctx){
+        ctx.rect(0,0, this.canvasWidth,this.canvasHeight);
+        ctx.fill();
+    },
+    
+    toString : function(){
+        var loc = this.loc
+        ,   x1 = loc.x, y1 = loc.y
+        ,   x2 = x1+this.layerWidth, y2 = y1 + this.layerHeight;
+        return this.className+'['+x1+','+y1+', '+x2+','+y2+'](w='+this.layerWidth+', h='+this.layerHeight+')';
+    }
+    
+});
+Rect.fromPoints = function(x1,y1, x2,y2){
+    return new Rect(x2-x1, y2-y1).position(x1,y1);
+};
\ No newline at end of file
diff --git a/src/easel/shape/shape.js b/src/easel/shape/shape.js
new file mode 100644
index 0000000..609a74a
--- /dev/null
+++ b/src/easel/shape/shape.js
@@ -0,0 +1,23 @@
+Shape = new Y.Class('Shape', Layer, {
+    _cssClasses : 'portal layer shape',
+    fillStyle   : 'rgba(231,48,117, 1)',
+    strokeStyle : 'transparent',
+    lineWidth   : 0,
+    
+    _calcDimension : function _calcDimension(which, values){
+        values.unshift(0);
+        var self = this
+        ,   neg = -1 * Math.min.apply(Math, values)
+        // ,   pos = Math.min(0, Math.max.apply(Max, values) - max)
+        ;
+        
+        self.negBleed.attr(which, neg);
+        // self.posBleed.attr(which, pos);
+        
+        return values.map(function(v, i){
+                return (self[which+i] = v);
+            });
+    }
+    
+});
+
diff --git a/src/easel/util/astar.js b/src/easel/util/astar.js
new file mode 100644
index 0000000..78f89ed
--- /dev/null
+++ b/src/easel/util/astar.js
@@ -0,0 +1,140 @@
+/*  astar.js http://github.com/bgrins/javascript-astar
+    MIT License
+    
+    Implements the astar search algorithm in javascript using a binary heap
+    **Requires graph.js**
+
+    Example Usage:
+        var graph = new Graph([
+            [0,0,0,0],
+            [1,0,0,1],
+            [1,1,0,0]
+        ]);
+        var start = graph.nodes[0][0];
+        var end = graph.nodes[1][2];
+        astar.search(graph.nodes, start, end);
+*/
+
+var astar = {
+    
+    init: function initAStar(grid) {
+        // var copy = [];
+        for(var x = 0, xl = grid.length; x < xl; x++) {
+            var yl = grid[x].length;
+            // copy[x] = new Array(yl);
+            for(var y = 0; y < yl; y++) {
+                // var node = grid[x][y].clone();
+                var node = grid[x][y];
+                node.f = 0;
+                node.g = 0;
+                node.h = 0;
+                node.visited = false;
+                node.closed = false;
+                node.parent = null;
+                // copy[x][y] = node;
+            }
+        }
+        // return copy;
+    },
+    
+    search: function search(grid, start, end, heuristic, ignore) {
+        astar.init(grid);
+        heuristic = heuristic || astar.manhattan;
+        
+        ignore = ignore || [];
+        ignore.push(start.value);
+        ignore.push(end.value);
+        
+        var open = new BinaryHeap('f');
+        open.push(start);
+        
+        while( open.length > 0 ) {
+            
+            // Grab the lowest f(x) to process next.  Heap keeps this sorted for us.
+            var current = open.pop();
+            
+            // End case -- result has been found, return the traced path
+            if(current === end) {
+                var path = []
+                ,   node = current;
+                while( node.parent ) {
+                    path.push( node.clone() );
+                    node = node.parent;
+                }
+                return path.reverse();
+            }
+            
+            // Normal case -- move current from open to closed, process each of its neighbors
+            current.closed = true;
+            
+            var neighbors = astar.neighbors(grid, current);
+            for(var i=0, il = neighbors.length; i < il; i++) {
+                var neighbor = neighbors[i];
+                
+                // blocker
+                if( neighbor.closed || (neighbor.blocked && ignore.indexOf(neighbor.value) === -1) )
+                    continue;
+                
+                // g score is the shortest distance from start to current node, we need to check if
+                //   the path we have arrived at this neighbor is the shortest one we have seen yet.
+                // We define the distance from a node to it's neighbor as 1, but this could be variable for weighted paths.
+                var g = current.g + 1;
+                
+                if( !neighbor.visited || g < neighbor.g ) {
+                    
+                    // Found an optimal (so far) path to this node.  Take score for node to see how good it is.
+                    neighbor.parent = current;
+                    neighbor.h = neighbor.h || heuristic(neighbor, end);
+                    neighbor.g = g;
+                    neighbor.f = g + neighbor.h;
+                    
+                    // New? Add to the set of nodes to process
+                    if ( !neighbor.visited ) {
+                        neighbor.visited = true;
+                        open.push(neighbor);
+                    
+                    // Seen, but since it has been rescored we need to reorder it in the heap
+                    } else
+                        open.rescore(neighbor);
+                }
+            }
+        }
+        
+        // No result was found -- empty array signifies failure to find path
+        return [];
+    },
+    
+    manhattan: function manhattan(p1, p2) {
+        // See list of heuristics: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
+        var d1 = Math.abs(p2.x - p1.x)
+        ,   d2 = Math.abs(p2.y - p1.y) ;
+        return d1 + d2;
+    },
+    
+    manhattan4: function manhattan(x1,y1, x2,y2) {
+        // See list of heuristics: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
+        var d1 = Math.abs(x2 - x1)
+        ,   d2 = Math.abs(y2 - y1) ;
+        return d1 + d2;
+    },
+    
+    neighbors: function neighbors(grid, node) {
+        var ret = [];
+        var x = node.x;
+        var y = node.y;
+        
+        if(grid[x-1] && grid[x-1][y]) {
+            ret.push(grid[x-1][y]);
+        }
+        if(grid[x+1] && grid[x+1][y]) {
+            ret.push(grid[x+1][y]);
+        }
+        if(grid[x] && grid[x][y-1]) {
+            ret.push(grid[x][y-1]);
+        }
+        if(grid[x] && grid[x][y+1]) {
+            ret.push(grid[x][y+1]);
+        }
+        return ret;
+    }
+};
diff --git a/src/easel/util/binaryheap.js b/src/easel/util/binaryheap.js
new file mode 100644
index 0000000..cfecb3a
--- /dev/null
+++ b/src/easel/util/binaryheap.js
@@ -0,0 +1,146 @@
+(function(){
+
+function BinaryHeap(score){
+    if (typeof score === 'string')
+        this.key = score;
+    else
+        this.score = score;
+}
+
+var AP = Array.prototype
+,   proto = BinaryHeap.prototype = []
+,   methods = {
+    
+    _push : AP.push,
+    _pop: AP.pop,
+    
+    // Replaced by score function if supplied
+    score : function score(el){
+        return el[this.key];
+    },
+    
+    push: function(el) {
+        // Add the new element to the end of the array.
+        this._push(el);
+        
+        // Allow it to sink down.
+        this.heapDown(this.length-1);
+        
+        return this;
+    },
+    
+    pop: function() {
+        // Store the first element so we can return it later.
+        var result = this[0]
+        
+        // Get the element at the end of the array.
+        ,   end = this._pop();
+        
+        // If there are any elements left, put the end element at the
+        // start, and let it bubble up.
+        if ( this.length > 0 ) {
+            this[0] = end;
+            this.heapUp(0);
+        }
+        return result;
+    },
+    
+    remove: function(node) {
+        var key = this.key
+        ,   i = this.indexOf(node)
+        
+        // When it is found, the process seen in 'pop' is repeated
+        // to fill up the hole.
+        ,   end = this._pop();
+        
+        if ( i !== this.length-1 ) {
+            this[i] = end;
+            var endScore  = (key ? end[key] : this.score(end))
+            ,   nodeScore = (key ? node[key] : this.score(node)) ;
+            if ( endScore < nodeScore )
+                this.heapDown(i);
+            else
+                this.heapUp(i);
+        }
+        return this;
+    },
+    
+    rescore: function(node) {
+        this.heapDown(this.indexOf(node));
+        return this;
+    },
+    
+    heapDown: function(n) {
+        var key = this.key
+        ,   el = this[n]
+        ,   elScore = (key ? el[key] : this.score(el))
+        ;
+        
+        // When at 0, an element can not sink any further.
+        while ( n > 0 ) {
+            
+            // Compute the parent element's index and score
+            var parentN = ((n + 1) >> 1) - 1
+            ,   parent = this[parentN]
+            ,   parentScore = (key ? parent[key] : this.score(parent))
+            ;
+            
+            // Swap the elements if the parent is greater
+            if ( elScore < parentScore ) {
+                this[parentN] = el;
+                this[n] = parent;
+                
+                // Update 'n' to continue at the new position.
+                n = parentN;
+            
+            // Found a parent that is less, no need to sink any further.
+            } else break;
+        }
+    },
+    
+    heapUp: function(n) {
+        var key     = this.key
+        ,   len     = this.length
+        ,   el      = this[n]
+        ,   elScore = this.score(el)
+        ;
+        
+        while( true ) {
+            var child2N = (n+1) << 1    // Compute children
+            ,   child1N = child2N - 1
+            ,   swap    = null          // Swap index
+            ;
+            
+            if ( child1N < len ) {
+                var child1 = this[child1N]
+                ,   child1Score = (key ? child1[key] : this.score(child1))
+                ;
+                if (child1Score < elScore)
+                    swap = child1N;
+            }
+            
+            if ( child2N < len ) {
+                var child2 = this[child2N]
+                ,   child2Score = (key ? child2[key] : this.score(child2))
+                ;
+                if (child2Score < (swap === null ? elScore : child1Score))
+                    swap = child2N;
+            }
+            
+            // Perform swap if necessary
+            if ( swap !== null ) {
+                this[n] = this[swap];
+                this[swap] = el;
+                n = swap;
+                
+            } else break;
+        }
+    }
+};
+
+// Add methods to prototype
+for (var k in methods) proto[k] = methods[k];
+
+this.BinaryHeap = BinaryHeap;
+
+})();
\ No newline at end of file
diff --git a/src/easel/util/graph.js b/src/easel/util/graph.js
new file mode 100644
index 0000000..e85dc73
--- /dev/null
+++ b/src/easel/util/graph.js
@@ -0,0 +1,16 @@
+function Graph(grid) {
+    this.grid = grid;
+    this.nodes = [];
+    
+    for (var x = 0; x < grid.length; x++) {
+        var row = grid[x];
+        this.nodes[x] = [];
+        for (var y = 0; y < row.length; y++) {
+            var n = new math.Vec(x,y);
+            n.blocked = !!row[y];
+            this.nodes[x].push(n);
+        }
+    }
+}
+
+
diff --git a/src/easel/util/tree/pointquadtree.js b/src/easel/util/tree/pointquadtree.js
new file mode 100644
index 0000000..38b7222
--- /dev/null
+++ b/src/easel/util/tree/pointquadtree.js
@@ -0,0 +1,580 @@
+(function(){
+
+var
+cellId = 0,
+NodeType = {
+    EMPTY    : 0,
+    LEAF     : 1,
+    POINTER  : 2,
+    toString : function toString(type){
+        switch (type) {
+            case NodeType.EMPTY:    return "Empty";
+            case NodeType.LEAF:     return "Leaf";
+            case NodeType.POINTER:  return "Pointer";
+        }
+    }
+},
+RangeCellType = {
+    TOP    : 2,
+    LEFT   : 4,
+    BOTTOM : 8,
+    RIGHT  : 16
+},
+LeafType = {
+    POINT    : 0,
+    RANGE    : 1,
+    RANGE_TL : 1 | RangeCellType.TOP    | RangeCellType.LEFT,
+    RANGE_TR : 1 | RangeCellType.TOP    | RangeCellType.RIGHT,
+    RANGE_BL : 1 | RangeCellType.BOTTOM | RangeCellType.LEFT,
+    RANGE_BR : 1 | RangeCellType.BOTTOM | RangeCellType.RIGHT,
+    toString : function toString(type){
+        switch (type) {
+            case LeafType.POINT:    return "Point";
+            case LeafType.RANGE:    return "Range";
+            case LeafType.RANGE_TL: return "RangeTL";
+            case LeafType.RANGE_TR: return "RangeTR";
+            case LeafType.RANGE_BL: return "RangeBL";
+            case LeafType.RANGE_BR: return "RangeBR";
+        }
+    }
+},
+
+Node = Y.subclass('Node', {
+    init : function Node(x, y, w, h, parent) {
+        this.w = w;
+        this.h = h;
+        this.x1 = this.x = x;
+        this.y1 = this.y = y;
+        this.x2 = x+w;
+        this.y2 = y+h;
+        this.parent = parent || null;
+    },
+    type  : NodeType.EMPTY,
+    nw    : null,
+    ne    : null,
+    sw    : null,
+    se    : null,
+    value : null,
+    
+    reduce : function reduce(fn, acc, context){
+        context = context || this;
+        if (this.nw) acc = fn.call(context, acc, this.nw, 'nw', this);
+        if (this.ne) acc = fn.call(context, acc, this.ne, 'ne', this);
+        if (this.sw) acc = fn.call(context, acc, this.sw, 'sw', this);
+        if (this.se) acc = fn.call(context, acc, this.se, 'se', this);
+        return acc;
+    },
+    
+    toString : function toString(){
+        return (NodeType.toString(this.type)+'( '+
+            'x='+this.x+',y='+this.y+', '+
+            'w='+this.w+',h='+this.h+
+        ' )');
+    }
+}),
+
+Range = new Y.Class('Range', Y.YCollection, {
+    init : function init(tree, x1,y1, x2,y2, value){
+        this.x1 = this.x = x1;
+        this.y1 = this.y = y1;
+        this.x2 = x2;
+        this.y2 = y2;
+        this.w = x2-x1;
+        this.h = y2-y1;
+        this.value = value;
+        this._o = this.cells = {};
+        
+        this.tree = tree;
+        tree._ranges.push(this);
+    },
+    
+    contains : function contains(x,y){
+        return (this.x1 <= x && x <= this.x2)
+            && (this.y1 <= y && y <= this.y2);
+    },
+    
+    containsRange : function containsRange(x1,y1, x2,y2){
+        var sm_x = Math.min(x1,x2), lg_x = Math.max(x1,x2)
+        ,   sm_y = Math.min(y1,y2), lg_y = Math.max(y1,y2);
+        return !( sm_x > this.x2 || sm_y > this.y2
+               || lg_x < this.x1 || lg_y < this.y1 );
+    },
+    
+    getCell : function getCell(x1,y1, x2,y2){
+        var cell =  new RangeCell(cellId++, x1,y1, x2,y2, this);
+        this.cells[cell.id] = cell;
+        return cell;
+    },
+    
+    removeCell : function removeCell(cell){
+        delete this.cells[cell.id];
+    },
+    
+    removeAll : function removeAll(){
+        var tree = this.tree;
+        this.forEach(function(cell){
+            this.removeCell(cell);
+            var cellNode = tree.closest(cell.x,cell.y);
+            if (cellNode) tree._remove(cellNode, true);
+        }, this);
+        tree._ranges.remove(this);
+    },
+    
+    reduce : function reduce(fn, acc, context){
+        context = context || this;
+        return Y(this.cells).clone().reduce(fn, acc, context);
+    },
+    
+    toString : function toString(){
+        return 'Range('+this.x1+','+this.y1+', '+this.x2+','+this.y2+', value='+this.value+')'
+    }
+}),
+
+Leaf = Y.subclass('Leaf', {
+    toString : function toString(){
+        return LeafType.toString(this.type)+'('+this.x+','+this.y+', value='+this.value+')';
+    }
+}),
+Point = new Y.Class('Point', Leaf, {
+    init : function Point(x,y, value) {
+        this.x = x;
+        this.y = y;
+        this.value = (value !== undefined ? value : null);
+        this.type  = LeafType.POINT;
+    }
+}),
+RangeCell = new Y.Class('RangeCell', Leaf, {
+    init : function init(id, x1,y1, x2,y2, owner) {
+        this.id = id;
+        this.x1 = this.x = x1;
+        this.y1 = this.y = y1;
+        this.x2 = x2;
+        this.y2 = y2;
+        this.w = x2-x1;
+        this.h = y2-y1;
+        this.type  = RangeCellType.RANGE;
+        this.owner = owner;
+        this.value = owner.value;
+    },
+    
+    containsRange : function containsRange(x1,y1, x2,y2){
+        var sm_x = Math.min(x1,x2), lg_x = Math.max(x1,x2)
+        ,   sm_y = Math.min(y1,y2), lg_y = Math.max(y1,y2);
+        return !( sm_x > this.x2 || sm_y > this.y2
+               || lg_x < this.x1 || lg_y < this.y1 );
+    },
+    
+    calc : function calc(node){
+        var r = this, t = LeafType.RANGE;
+        
+        if (node.x2 > r.x2)
+            t = t | RangeCellType.RIGHT;
+        else if (node.x1 <= r.x1) {
+            t = t | RangeCellType.LEFT;
+            r.x2 = node.x2;
+            r.w = r.x2 - r.x1;
+        }
+        
+        if (node.y2 > r.y2)
+            t = t | RangeCellType.BOTTOM;
+        else if (node.y1 <= r.y1) {
+            t = t | RangeCellType.TOP;
+            r.y2 = node.y2;
+            r.h = r.y2 - r.y1;
+        }
+        
+        this.type = t;
+    },
+    
+    removeRange : function removeRange(){
+        this.owner.removeAll();
+    }
+}),
+
+PointQuadTree = Y.subclass('PointQuadTree', {
+    'init' : function(minX,minY, maxX,maxY) {
+        this.x1 = this.x = minX;
+        this.y1 = this.y = minY;
+        this.x2 = maxX;
+        this.y2 = maxY;
+        this.width  = maxX-minX;
+        this.height = maxY-minY;
+        this.clear();
+    },
+    _root : null,
+    count : 0,
+    _ranges : null,
+    
+    inBounds : function inBounds(x,y){
+        var root = this._root;
+        return !( x<root.x1 || y<root.y1 || x>root.x2 || y>root.y2 );
+    },
+    
+    _inSubrange : function _inSubrange(x1,y1, x2,y2){
+        if (arguments.length === 4)
+            return this._ranges.invoke('containsRange', x1,y1, x2,y2).any();
+        else
+            return this._ranges.invoke('contains', x1,y1).any();
+    },
+    
+    // XXX: Hm. Should this be contains ALL or contains ANY for the range query?
+    contains : function contains(x1,y1, x2,y2){
+        if (arguments.length === 4)
+            return this._inSubrange(x1,y1, x2,y2);
+        else
+            return this._inSubrange(x1,y1) || this.get(x1,y1) !== null;
+    },
+    
+    isEmpty : function isEmpty(){
+        return this._root.type == NodeType.EMPTY;
+    },
+    
+    clear : function clear(){
+        this._root = new Node(this.x1,this.y1, this.width,this.height);
+        this._ranges = Y([]);
+        this.count = 0;
+    },
+    
+    get : function get(x,y, def){
+        var node = this.closest(x,y);
+        if (node && node.value.x === x && node.value.y === y)
+            return node.value.value;
+        else
+            return def;
+    },
+    
+    set : function set(x,y, value){
+        if ( !this.inBounds(x,y) )
+            throw new Error('Out of bounds: ('+x+', '+y+')');
+        if ( this._inSubrange(x,y) )
+            throw new Error('Cannot place point in existing subrange!');
+        
+        this._insert(this._root, new Point(x,y, value), 1);
+    },
+    
+    addRange : function addRange(x1,y1, x2,y2, value){
+        if ( !this.inBounds(x1,y1) )
+            throw new Error('Out of bounds: ('+x1+', '+y1+')');
+        if ( !this.inBounds(x2,y2) )
+            throw new Error('Out of bounds: ('+x2+', '+y2+')');
+        if ( this._inSubrange(x1,y1, x2,y2) )
+            throw new Error('Cannot overlap subrange!');
+        
+        var points = this.find(x1,y1, x2,y2);
+        if (points.length)
+            throw new Error('Cannot add range where points exist: ['+points.join(', ')+']');
+        
+        var sm_x = Math.min(x1,x2), lg_x = Math.max(x1,x2)
+        ,   sm_y = Math.min(y1,y2), lg_y = Math.max(y1,y2);
+        return this._addRangeUnsafe(sm_x,sm_y, lg_x,lg_y, value)
+    },
+    
+    _addRangeUnsafe : function _addRangeUnsafe(x1,y1, x2,y2, value){
+        var range = new Range(this, x1,y1, x2,y2, value);
+        this._addRange(x1,y1, x2,y2, range);
+        return range;
+    },
+    
+    _addRange : function _addRange(x1,y1, x2,y2, range){
+        if (x1 === x2 || y1 === y2) return;
+        
+        var r = range.getCell(x1,y1, x2,y2)
+        ,   n = this._insert(this._root, r)
+        ;
+        
+        // Horizontal recursion?
+        if (n.x2 < x2) this._addRange(n.x2,y1, x2,y2, range);
+        
+        // Vertical recursion?
+        if (n.y2 < y2) this._addRange(x1,n.y2, x2,y2, range);
+        
+        r.calc(n);
+        if ( (n.x1 < x1 && n.x2 > x2) || (n.y1 < y1 && n.y2 > y2) )
+            this._split(n);
+        
+        return n;
+    },
+    
+    remove : function remove(x,y){
+        var self = this
+        ,   node = this.closest(x,y)
+        ,   leaf = node && node.value;
+        if (leaf && leaf.x == x && leaf.y == y) {
+            return this._remove(node);
+        } else
+            return null;
+    },
+    
+    _removeClosest : function _removeClosest(x,y){
+        var node = this.closest(x,y);
+        if (node && node.type === NodeType.LEAF)
+            return this._remove(node);
+        else
+            return null;
+    },
+    
+    _remove : function _remove(node, range){
+        var leaf = node.value;
+        node.value = null;
+        node.type = NodeType.EMPTY;
+        if (!range) {
+            this.count--;
+            if (leaf && (leaf.type & LeafType.RANGE))
+                leaf.owner.removeAll();
+        }
+        this._balance(node);
+        return leaf ? leaf.value : leaf;
+    },
+    
+    find : function find(x1,y1, x2,y2, fn, acc, context){
+        var self = this
+        ,   cxt  = context || self
+        ,   sm_x = Math.min(x1,x2), lg_x = Math.max(x1,x2)
+        ,   sm_y = Math.min(y1,y2), lg_y = Math.max(y1,y2)
+        ;
+        
+        if (!fn) {
+            acc = [];
+            fn = function(acc, v, k){ acc.push(v); return acc; };
+        }
+        
+        function collect(acc, node) {
+            var np = node.value
+            ,   nx1=node.x,     ny1=node.y
+            ,   nx2=nx1+node.w, ny2=ny1+node.h ;
+            
+            if ( node.type === NodeType.EMPTY
+                 || nx2 < sm_x || ny2 < sm_y
+                 || nx1 > lg_x || ny1 > lg_y )
+                    return acc;
+            
+            if ( np && np.value !== null && (
+                   (np.type & LeafType.RANGE && np.containsRange(x1,y1, x2,y2)) ||
+                   (np.x >= sm_x && np.x <= lg_x && np.y >= sm_y && np.y <= lg_y) ) )
+                    acc = fn(acc, np.value, np, cxt);
+            
+            return node.reduce(collect, acc, self);
+        }
+        
+        return collect(acc, this._root);
+    },
+    
+    closest : function closest(x,y){
+        if ( !this.inBounds(x,y) )
+            return null;
+        return this._closest(x,y, this._root);
+    },
+    
+    _closest : function _closest(x,y, node){
+        if ( !(node && this.inBounds(x,y)) )
+            return null;
+        
+        switch (node.type) {
+            case NodeType.EMPTY:
+                return null;
+            
+            case NodeType.LEAF:
+                return node;
+            
+            case NodeType.POINTER:
+                return this._closest(x,y, this._getQuadrantForPoint(node, x,y));
+            
+            default:
+                throw new Error('Invalid type');
+        }
+    },
+    
+    _getQuadrantForPoint : function _getQuadrantForPoint(parent, x,y){
+        var mx = parent.x + parent.w/2;
+        var my = parent.y + parent.h/2;
+        if (x < mx) {
+            return y < my ? parent.nw : parent.sw;
+        } else {
+            return y < my ? parent.ne : parent.se;
+        }
+    },
+    
+    _insert : function _insert(parent, value, isNew){
+        switch (parent.type) {
+            case NodeType.EMPTY:
+                this._setPointForNode(parent, value);
+                if (isNew) this.count++;
+                return parent;
+            
+            case NodeType.LEAF:
+                if (parent.value.x === value.x && parent.value.y === value.y) {
+                    this._setPointForNode(parent, value);
+                    return parent;
+                } else {
+                    this._split(parent);
+                    return this._insert(parent, value);
+                }
+            
+            case NodeType.POINTER:
+                return this._insert(
+                        this._getQuadrantForPoint(parent, value.x, value.y), value);
+            
+            default:
+                throw new Error('Invalid type in parent');
+        }
+    },
+    
+    _setPointForNode : function _setPointForNode(node, value){
+        if (node.type == NodeType.POINTER)
+            throw new Error('Can not set value for node of type POINTER');
+        node.type = NodeType.LEAF;
+        node.value = value;
+    },
+    
+    _split : function _split(node){
+        var v = node.value;
+        node.value = null;
+        node.type = NodeType.POINTER;
+        
+        var x = node.x;
+        var y = node.y;
+        var hw = node.w / 2;
+        var hh = node.h / 2;
+        
+        node.nw = new Node(x,    y,    hw, hh, node);
+        node.ne = new Node(x+hw, y,    hw, hh, node);
+        node.sw = new Node(x,    y+hh, hw, hh, node);
+        node.se = new Node(x+hw, y+hh, hw, hh, node);
+        
+        if (v.type & LeafType.RANGE) {
+            v.owner.removeCell(v);
+            this._addRange(v.x1,v.y1, v.x2,v.y2, v.owner);
+        } else
+            this._insert(node, v);
+    },
+    
+    // TODO: beautify
+    _balance : function _balance(node){
+        switch (node.type) {
+            case NodeType.EMPTY:
+            case NodeType.LEAF:
+                if (node.parent) {
+                    this._balance(node.parent);
+                }
+                break;
+            
+            case NodeType.POINTER:
+                var nw = node.nw, ne = node.ne, sw = node.sw, se = node.se;
+                var firstLeaf = null;
+                
+                // Look for the first non-empty child, if there is more than one then we
+                // break as this node can't be balanced.
+                if (nw.type != NodeType.EMPTY) {
+                    firstLeaf = nw;
+                }
+                if (ne.type != NodeType.EMPTY) {
+                    if (firstLeaf) {
+                        break;
+                    }
+                    firstLeaf = ne;
+                }
+                if (sw.type != NodeType.EMPTY) {
+                    if (firstLeaf) {
+                        break;
+                    }
+                    firstLeaf = sw;
+                }
+                if (se.type != NodeType.EMPTY) {
+                    if (firstLeaf) {
+                        break;
+                    }
+                    firstLeaf = se;
+                }
+                
+                if (!firstLeaf) {
+                    // All child nodes are empty: so make this node empty.
+                    node.type = NodeType.EMPTY;
+                    node.nw = node.ne = node.sw = node.se = null;
+                    
+                } else if (firstLeaf.type == NodeType.POINTER) {
+                    // Only child was a pointer, therefore we can't rebalance.
+                    break;
+                    
+                } else {
+                    // Only child was a leaf: so update node's value and make it a leaf.
+                    node.type = NodeType.LEAF;
+                    node.nw = node.ne = node.sw = node.se = null;
+                    node.value = firstLeaf.value;
+                }
+                
+                // Try and balance the parent as well.
+                if (node.parent) {
+                    this._balance(node.parent);
+                }
+                
+                break;
+        }
+    },
+    
+    getKeys : function getKeys(){
+        var arr = [];
+        this._traverse(this._root, function(node) {
+            arr.push({ 'x':node.value.x, 'y':node.value.y });
+        });
+        return arr;
+    },
+    
+    getValues : function getValues(){
+        var arr = [];
+        this._traverse(this._root, function(node) {
+            // Must have a value because it's a leaf.
+            arr.push(node.value.value);
+        });
+        return arr;
+    },
+    
+    forEach : function forEach(fn, context){
+        this._traverse(this._root, function(node) {
+            var coord = { 'x':node.value.x, 'y':node.value.y };
+            fn.call(context || this, node.value.value, coord, this);
+        });
+    },
+    
+    clone : function clone(){
+        var x1 = this._root.x;
+        var y1 = this._root.y;
+        var x2 = x1 + this._root.w;
+        var y2 = y1 + this._root.h;
+        var clone = new PointQuadTree(x1, y1, x2, y2);
+        // This is inefficient as the clone needs to recalculate the structure of the
+        // tree, even though we know it already.    But this is easier and can be
+        // optimized when/if needed.
+        this._traverse(this._root, function(node) {
+            clone.set(node.value.x, node.value.y, node.value.value);
+        });
+        return clone;
+    },
+    
+    _traverse : function _traverse(node, fn){
+        switch (node.type) {
+            case NodeType.LEAF:
+                fn.call(this, node);
+                break;
+            
+            case NodeType.POINTER:
+                this._traverse(node.ne, fn);
+                this._traverse(node.se, fn);
+                this._traverse(node.sw, fn);
+                this._traverse(node.nw, fn);
+                break;
+        }
+    }
+    
+});
+
+this.PointQuadTree = PointQuadTree;
+PointQuadTree.NodeType = NodeType;
+PointQuadTree.LeafType = LeafType;
+PointQuadTree.RangeCellType = RangeCellType;
+PointQuadTree.Node = Node;
+PointQuadTree.Range = Range;
+PointQuadTree.Leaf = Leaf;
+PointQuadTree.Point = Point;
+PointQuadTree.RangeCell = RangeCell;
+
+})();
\ No newline at end of file
diff --git a/src/easel/util/tree/quadtree.js b/src/easel/util/tree/quadtree.js
new file mode 100644
index 0000000..5f92556
--- /dev/null
+++ b/src/easel/util/tree/quadtree.js
@@ -0,0 +1,241 @@
+(function(){
+
+function Rect(x1,y1, x2,y2){
+    var sm_x = Math.min(x1,x2), lg_x = Math.max(x1,x2)
+    ,   sm_y = Math.min(y1,y2), lg_y = Math.max(y1,y2);
+    this.x1 = this.x = sm_x;
+    this.y1 = this.y = sm_y;
+    this.x2 = lg_x;
+    this.y2 = lg_y;
+    this.width  = lg_x-sm_x;
+    this.height = lg_y-sm_y;
+}
+function rectToString(o){
+    var p = 2
+    ,   x1 = o.x1, y1 = o.y1
+    ,   x2 = o.x2, y2 = o.y2 ;
+    x1 = ((x1 % 1 !== 0) ? x1.toFixed(p) : x1);
+    y1 = ((y1 % 1 !== 0) ? y1.toFixed(p) : y1);
+    x2 = ((x2 % 1 !== 0) ? x2.toFixed(p) : x2);
+    y2 = ((y2 % 1 !== 0) ? y2.toFixed(p) : y2);
+    return '['+x1+','+y1+', '+x2+','+y2+']';
+}
+
+var
+CAPACITY  = 8,
+REGION_ID = 0,
+
+Region = Y.subclass('Region', {
+    init : function init(x1,y1, x2,y2, value){
+        Rect.call(this, x1,y1, x2,y2);
+        this.id = REGION_ID++;
+        this.value = value;
+    },
+    
+    // Expects caller will have ordered x1 < x2, y1 < y2
+    overlaps : function overlaps(x1,y1, x2,y2){
+        return !( x1 >  this.x2 || y1 >  this.y2
+               || x2 <= this.x1 || y2 <= this.y1 );
+    },
+    
+    toString : function toString(){
+        return this.className+'(id='+this.id+', rect='+rectToString(this)+', value='+this.value+')';
+    }
+}),
+
+QuadTree = Y.subclass('QuadTree', {
+    depth    : 0,
+    parent   : null,
+    regions  : [],
+    overflow : false,
+    
+    children : Y([]),
+    nw : null, ne : null,
+    sw : null, se : null,
+    
+    
+    init : function init(x1,y1, x2,y2, capacity, parent) {
+        Rect.call(this, x1,y1, x2,y2);
+        this.capacity = capacity || CAPACITY;
+        this.parent   = parent   || null;
+        if (parent) this.depth = parent.depth + 1;
+        this.clear();
+    },
+    
+    // Expects caller will have ordered x1 < x2, y1 < y2
+    overlaps : function overlaps(x1,y1, x2,y2){
+        return !( x1 >  this.x2 || y1 >  this.y2
+               || x2 <= this.x1 || y2 <= this.y1 );
+    },
+    
+    
+    // TODO: Add optional filter
+    get : function get(x1,y1, x2,y2){
+        return this.collect(x1,y1, x2,y2, this._get, { vals:Y([]) }, this).vals;
+    },
+    
+    _get : function _get(acc, value, region){
+        if ( !acc[region.id] ) {
+            acc[region.id] = region;
+            acc.vals.push(value);
+        }
+        return acc;
+    },
+    
+    // XXX: Since this is by far the most commonly called function, it'd be good to
+    // collapse the recursion and reduce the number of function-calls. But it's not a
+    // bottleneck yet, so we'll wait.
+    // _get : function _get(_x1,_y1, _x2,_y2, values){
+    //     var self = this
+    //     ,   cxt = context || self
+    //     ,   x1 = Math.min(_x1,_x2), x2 = Math.max(_x1,_x2)
+    //     ,   y1 = Math.min(_y1,_y2), y2 = Math.max(_y1,_y2) ;
+    //     
+    //     if ( !self.overlaps(x1,y1, x2,y2) )
+    //         return acc;
+    //     
+    //     // Implies this is a leaf: check its values
+    //     if ( self.regions ) acc = fn.call(cxt, acc, self.regions, self, self);
+    //     
+    //     // Recurse into any children -- Note we do not place this in an else-block,
+    //     // as mutation during the above call might cause the tree to split.
+    //     if (self.nw) acc = self.nw.leaves(x1,y1, x2,y2, fn, acc, context);
+    //     if (self.ne) acc = self.ne.leaves(x1,y1, x2,y2, fn, acc, context);
+    //     if (self.sw) acc = self.sw.leaves(x1,y1, x2,y2, fn, acc, context);
+    //     if (self.se) acc = self.se.leaves(x1,y1, x2,y2, fn, acc, context);
+    //     
+    //     return acc;
+    // },
+    
+    set : function set(x1,y1, x2,y2, value){
+        return this._set(new Region(x1,y1, x2,y2, value));
+    },
+    
+    _set : function _set(r){
+        return this.leaves(r.x1,r.y1, r.x2,r.y2, function(acc, regions, tree){
+            if ( regions.length < tree.capacity || tree.overflow )
+                regions.push(r);
+            else
+                // Splitting transforms this into an internal node, and
+                // causes leaves() to continue us down into the next level.
+                tree._split();
+            return r;
+        });
+    },
+    
+    remove : function remove(region){
+        var trees =
+            this.leaves(
+                region.x1,region.y1, region.x2,region.y2,
+                function(trees, regions, tree){
+                    Y(regions).remove(region);
+                    
+                    if ( !trees[tree.depth] )
+                        trees[tree.depth] = [];
+                    trees[tree.depth].push();
+                    
+                    return trees;
+                }, []);
+        
+        Y(trees.pop()).invoke('_balance');
+        
+        return region;
+    },
+    
+    removeAll : function removeAll(x1,y1, x2,y2){
+        this.leaves(x1,y1, x2,y2, function(_, regions, tree){
+            tree.clear();
+        });
+    },
+    
+    leaves : function leaves(x1,y1, x2,y2, fn, acc, context){
+        var self = this
+        ,   cxt = context || self
+        ,   _x1 = Math.min(x1,x2), _x2 = Math.max(x1,x2)
+        ,   _y1 = Math.min(y1,y2), _y2 = Math.max(y1,y2) ;
+        
+        if ( !self.overlaps(_x1,_y1, _x2,_y2) )
+            return acc;
+        
+        // Implies this is a leaf: check its values
+        if ( self.regions ) acc = fn.call(cxt, acc, self.regions, self, self);
+        
+        // Recurse into any children -- Note we do not place this in an else-block,
+        // as mutation during the above call might cause the tree to split.
+        if (self.nw) acc = self.nw.leaves(_x1,_y1, _x2,_y2, fn, acc, context);
+        if (self.ne) acc = self.ne.leaves(_x1,_y1, _x2,_y2, fn, acc, context);
+        if (self.sw) acc = self.sw.leaves(_x1,_y1, _x2,_y2, fn, acc, context);
+        if (self.se) acc = self.se.leaves(_x1,_y1, _x2,_y2, fn, acc, context);
+        
+        return acc;
+    },
+    
+    collect : function collect(x1,y1, x2,y2, fn, acc, context){ // XXX: unique=false, limit=Infinity, depth=Infinity
+        var _x1 = Math.min(x1,x2), _x2 = Math.max(x1,x2)
+        ,   _y1 = Math.min(y1,y2), _y2 = Math.max(y1,y2);
+        return this.leaves(
+            _x1,_y1, _x2,_y2,
+            function(acc, rs, tree){
+                for (var i=0, L=rs.length, r=rs[i]; i<L; r=rs[++i])
+                    if ( r.overlaps(_x1,_y1, _x2,_y2) )
+                        acc = fn.call(this, acc, r.value, r, tree);
+                return acc;
+            },
+            acc,
+            context );
+    },
+    
+    reduce : function reduce(fn, acc, context){
+        return this.collect(this.x1,this.y1, this.x2,this.y2, fn, acc, context);
+    },
+    
+    clear : function clear(){
+        this.overflow = false;
+        this.regions  = [];
+        this.children = null;
+        this.nw = this.ne = this.sw = this.se = null;
+    },
+    
+    _split : function _split(){
+        if (this.overflow) return;
+        
+        var regions = this.regions
+        ,   cap = this.capacity
+        ,   hw  = this.width  / 2
+        ,   hh  = this.height / 2
+        ,   x1  = this.x1, hx = x1+hw, x2 = this.x2
+        ,   y1  = this.y1, hy = y1+hh, y2 = this.y2 ;
+        
+        this.regions = null;
+        var nw = this.nw = new QuadTree(x1,y1, hx,hy, cap, this)
+        ,   ne = this.ne = new QuadTree(hx,y1, x2,hy, cap, this)
+        ,   sw = this.sw = new QuadTree(x1,hy, hx,y2, cap, this)
+        ,   se = this.se = new QuadTree(hx,hy, x2,y2, cap, this)
+        ,   children = this.children = Y([nw, ne, sw, se]) ;
+        
+        regions.forEach(this._set, this);
+        
+        // If any children are still at max capacity, undo and set the overflow flag
+        if ( Math.max.apply(Math, children.pluck('regions').pluck('length').end()) > cap ){
+            this.clear();
+            this.overflow = true;
+            this.regions  = regions;
+        }
+    },
+    
+    _balance : function _balance(){
+        
+    },
+    
+    toString : function toString(){
+        var indent = '', d = this.depth+1;
+        while ( d-- > 0 ) indent += '\t';
+        return this.className+'('+this.x1+','+this.y1+', '+this.x2+','+this.y2+(this.regions ? ', regions='+this.regions.length : 0)+') '+
+            (this.children ? '\n'+indent+this.children.end().join('\n'+indent) : '');
+    }
+});
+
+QuadTree['Region'] = Region;
+this['QuadTree'] = QuadTree;
+
+})();
diff --git a/src/easel/util/tree/rbtree.js b/src/easel/util/tree/rbtree.js
new file mode 100644
index 0000000..a5cb4e1
--- /dev/null
+++ b/src/easel/util/tree/rbtree.js
@@ -0,0 +1,467 @@
+(function(){
+var RED        = "Red"
+,   BLACK      = "Black"
+,   FLIP_COLOR = {};
+FLIP_COLOR[RED]   = BLACK;
+FLIP_COLOR[BLACK] = RED;
+
+
+function isRed(n)   { return n && (n.color == RED); }
+function isBlack(n) { return n && (n.color == BLACK); }
+function size(n)    { return (n && n.N) || 0; }
+
+
+function Node(key, val, color, N) {
+    this.key   = key;
+    this.val   = val;
+    this.color = color;
+    this.N     = N;
+    this.left  = null;
+    this.right = null;
+}
+Node.prototype.toString = function(){
+    var S = (this.color === RED ? '[' : '(')
+    ,   E = (this.color === RED ? ']' : ')');
+    return S+this.key+' '+this.val+E;
+};
+
+var
+RedBlackTree = Y.subclass('RedBlackTree', {
+    init : function init(key, value){
+        if (this.key !== undefined)
+            this.setKey(key, value);
+    },
+    
+    _root : null,
+
+   /*************************************************************************
+    *  Size methods
+    *************************************************************************/
+
+    // return number of key-value pairs in this symbol table
+    'size' : function() { return size(this._root); },
+
+    // is this symbol table empty?
+    'isEmpty' : function() {
+        return this._root === null;
+    },
+
+   /*************************************************************************
+    *  Standard BST search
+    *************************************************************************/
+
+    // value associated with the given key; null if no such key
+    'getKey' : function(key) {
+        return this._getKey(this._root, key);
+    },
+
+    // value associated with the given key in subtree rooted at x; null if no such key
+    _getKey : function _getKey(x, key) {
+        while (x !== null) {
+            if      (key < x.key) x = x.left;
+            else if (key > x.key) x = x.right;
+            else                  return x.val;
+        }
+        return null;
+    },
+
+    // is there a key-value pair with the given key?
+    'contains' : function(key) {
+        return (this.getKey(key) !== null);
+    },
+
+    // is there a key-value pair with the given key in the subtree rooted at x?
+    _contains : function _contains(x, Key) {
+        return (this._getKey(x, key) !== null);
+    },
+
+   /*************************************************************************
+    *  Red-black insertion
+    *************************************************************************/
+
+    // insert the key-value pair; overwrite the old value with the new value
+    // if the key is already present
+    'setKey' : function(key, val) {
+        if (key === undefined) throw new Exception("Key cannot be undefined!");
+        this._root = this._setKey(this._root, key, val);
+        this._root.color = BLACK;
+        // assert isRedBlackBST();
+    },
+
+    // insert the key-value pair in the subtree rooted at h
+    _setKey : function _setKey(h, key, val) {
+        if (h === null) return new Node(key, val, RED, 1);
+        
+        if      (key < h.key) h.left  = this._setKey(h.left,  key, val);
+        else if (key > h.key) h.right = this._setKey(h.right, key, val);
+        else                  h.val   = val;
+        
+        return this._balance(h);
+    },
+
+    // remove the key-value pair with the given key
+    'remove' : function(key) {
+        if (!this.contains(key)) {
+            System.err.println("symbol table does not contain " + key);
+            return;
+        }
+
+        // if both children of this._root are black, set this._root to red
+        if (!isRed(this._root.left) && !isRed(this._root.right))
+            this._root.color = RED;
+
+        this._root = this._remove(this._root, key);
+        if (!this.isEmpty()) this._root.color = BLACK;
+        // assert isRedBlackBST();
+    },
+
+    // remove the key-value pair with the given key rooted at h
+    _remove : function _remove(h, key) {
+        // assert this.contains(h, key);
+
+        if (key < h.key)  {
+            if (!isRed(h.left) && !isRed(h.left.left))
+                h = this._moveRedLeft(h);
+            h.left =  this._remove(h.left, key);
+        } else {
+            if (isRed(h.left))
+                h = this._rotateRight(h);
+            if (key === h.key && (h.right === null))
+                return null;
+            if (!isRed(h.right) && !isRed(h.right.left))
+                h = this._moveRedRight(h);
+            if (key === h.key) {
+                h.val = this._getKey(h.right, this._min(h.right).key);
+                h.key = this._min(h.right).key;
+                h.right = this._removeMin(h.right);
+            }
+            else h.right = this._remove(h.right, key);
+        }
+        return this._balance(h);
+    },
+    
+    // remove the key-value pair with the minimum key
+    _removeMin : function _removeMin(h) {
+        if (h) {
+            if (h.left === null)
+                return null;
+
+            if (!isRed(h.left) && !isRed(h.left.left))
+                h = this._moveRedLeft(h);
+
+            h.left = this._removeMin(h.left);
+            return this._balance(h);
+            
+        } else {
+            if (this.isEmpty()) throw new Exception("BST underflow");
+
+            // if both children of root are black, set root to red
+            if (!isRed(this._root.left) && !isRed(this._root.right))
+                this._root.color = RED;
+
+            this._root = this._removeMin(this._root);
+            if (!this.isEmpty()) this._root.color = BLACK;
+            // assert isRedBlackBST();
+        }
+    },
+
+    // remove the key-value pair with the maximum key
+    _removeMax : function _removeMax(h){
+        if (h) {
+            if (isRed(h.left))
+                h = this._rotateRight(h);
+
+            if (h.right === null)
+                return null;
+
+            if (!isRed(h.right) && !isRed(h.right.left))
+                h = this._moveRedRight(h);
+
+            h.right = this._removeMax(h.right);
+
+            return this._balance(h);
+            
+        } else {
+            if (this.isEmpty()) throw new Exception("BST underflow");
+
+            // if both children of root are black, set root to red
+            if (!isRed(this._root.left) && !isRed(this._root.right))
+                this._root.color = RED;
+
+            this._root = this._removeMax(this._root);
+            if (!this.isEmpty()) this._root.color = BLACK;
+            // assert isRedBlackBST();
+        }
+    },
+
+   /*************************************************************************
+    *  red-black tree helper functions
+    *************************************************************************/
+
+    // make a left-leaning link lean to the right
+    _rotateRight : function _rotateRight(h) {
+        // assert (h !== null) && isRed(h.left);
+        var x = h.left;
+        h.left = x.right;
+        x.right = h;
+        x.color = x.right.color;
+        x.right.color = RED;
+        x.N = h.N;
+        h.N = size(h.left) + size(h.right) + 1;
+        return x;
+    },
+
+    // make a right-leaning link lean to the left
+    _rotateLeft : function _rotateLeft(h) {
+        // assert (h !== null) && isRed(h.right);
+        var x = h.right;
+        h.right = x.left;
+        x.left = h;
+        x.color = x.left.color;
+        x.left.color = RED;
+        x.N = h.N;
+        h.N = size(h.left) + size(h.right) + 1;
+        return x;
+    },
+
+    // flip the colors of a node and its two children
+    _flipColors : function _flipColors(h) {
+        // h must have opposite color of its two children
+        // assert (h !== null) && (h.left !== null) && (h.right !== null);
+        // assert (!isRed(h) &&  isRed(h.left) &&  isRed(h.right)) ||
+        //         (isRed(h) && !isRed(h.left) && !isRed(h.right));
+        h.color       = FLIP_COLOR[h.color];
+        h.left.color  = FLIP_COLOR[h.left.color];
+        h.right.color = FLIP_COLOR[h.right.color];
+    },
+
+    // Assuming that h is red and both h.left and h.left.left
+    // are black, make h.left or one of its children red.
+    _moveRedLeft : function _moveRedLeft(h) {
+        // assert (h !== null);
+        // assert isRed(h) && !isRed(h.left) && !isRed(h.left.left);
+
+        this._flipColors(h);
+        if (isRed(h.right.left)) {
+            h.right = this._rotateRight(h.right);
+            h = this._rotateLeft(h);
+            // this._flipColors(h);
+        }
+        return h;
+    },
+
+    // Assuming that h is red and both h.right and h.right.left
+    // are black, make h.right or one of its children red.
+    _moveRedRight : function _moveRedRight(h) {
+        // assert (h !== null);
+        // assert isRed(h) && !isRed(h.right) && !isRed(h.right.left);
+        this._flipColors(h);
+        if (isRed(h.left.left)) {
+            h = this._rotateRight(h);
+            // this._flipColors(h);
+        }
+        return h;
+    },
+
+    // restore red-black tree invariant
+    _balance : function _balance(h) {
+        // assert (h !== null);
+        if (h === null)
+            throw new Exception("wtf balance a null node?");
+        
+        if (isRed(h.right))                      h = this._rotateLeft(h);
+        if (isRed(h.left) && isRed(h.left.left)) h = this._rotateRight(h);
+        if (isRed(h.left) && isRed(h.right))     this._flipColors(h);
+
+        h.N = size(h.left) + size(h.right) + 1;
+        return h;
+    },
+
+
+   /*************************************************************************
+    *  Utility functions
+    *************************************************************************/
+
+    // height of tree; 0 if empty
+    'height' : function() { return this._height(this._root); },
+    _height : function _height(x) {
+        if (x === null) return 0;
+        return 1 + Math.max(this._height(x.left), this._height(x.right));
+    },
+
+   /*************************************************************************
+    *  Ordered symbol table methods.
+    *************************************************************************/
+
+    // the smallest key; null if no such key
+    'min' : function() {
+        if (this.isEmpty()) return null;
+        return this._min(this._root).key;
+    },
+
+    // the smallest key in subtree rooted at x; null if no such key
+    _min : function _min(x) {
+        // assert x !== null;
+        if (x.left === null) return x;
+        else                 return this._min(x.left);
+    },
+
+    // the largest key; null if no such key