From 424e87c3297347dda781db0738d82ec603441a21 Mon Sep 17 00:00:00 2001 From: dsc Date: Tue, 9 Nov 2010 22:22:01 -0800 Subject: [PATCH] Reorg of packages. --- index.php | 57 +---- src/Y/type.js | 10 +- src/Y/y-core.js | 7 +- src/portal/loop/cooldown.js | 41 +++ src/portal/loop/eventloop.js | 120 +++++++ src/portal/loop/fps.js | 99 ++++++ src/portal/math/vec.js | 44 ++-- src/portal/shape.js | 252 -------------- src/portal/shape/circle.js | 21 ++ src/portal/shape/line.js | 130 ++++++++ src/portal/shape/polygon.js | 63 ++++ src/portal/shape/rect.js | 18 + src/portal/shape/shape.js | 23 ++ src/portal/transform.js | 61 ---- src/portal/util/cooldown.js | 41 --- src/portal/util/eventloop.js | 120 ------- src/portal/util/fps.js | 99 ------ src/portal/util/loc.js | 199 ----------- src/portal/util/pointquadtree.js | 580 --------------------------------- src/portal/util/quadtree.js | 205 ------------ src/portal/util/rbtree.js | 467 -------------------------- src/portal/util/tree/pointquadtree.js | 580 +++++++++++++++++++++++++++++++++ src/portal/util/tree/quadtree.js | 205 ++++++++++++ src/portal/util/tree/rbtree.js | 467 ++++++++++++++++++++++++++ src/tanks/calc.js | 5 + src/tanks/game/level.js | 35 -- src/tanks/game/map.game.js | 158 +++++++++ src/tanks/game/map.js | 158 --------- src/tanks/game/player.js | 108 ------ src/tanks/lttl.js | 35 -- src/tanks/main.js | 39 +++ src/tanks/map/level.js | 35 ++ src/tanks/map/loc.js | 195 +++++++++++ src/tanks/map/pathmap.js | 119 +++++++ src/tanks/ui.js | 91 ----- src/tanks/ui.main.js | 61 ++++ src/tanks/ui/grid.js | 38 +++ src/tanks/ui/player.js | 108 ++++++ src/tanks/util/calc.js | 5 - src/tanks/util/grid.js | 38 --- src/tanks/util/pathmap.js | 119 ------- tanks.php | 86 +++++ test/math/index.php | 34 +-- 43 files changed, 2643 insertions(+), 2733 deletions(-) create mode 100644 src/portal/loop/cooldown.js create mode 100644 src/portal/loop/eventloop.js create mode 100644 src/portal/loop/fps.js delete mode 100644 src/portal/path.js delete mode 100644 src/portal/portal.js delete mode 100644 src/portal/shape.js create mode 100644 src/portal/shape/circle.js create mode 100644 src/portal/shape/line.js create mode 100644 src/portal/shape/polygon.js create mode 100644 src/portal/shape/rect.js create mode 100644 src/portal/shape/shape.js delete mode 100644 src/portal/transform.js delete mode 100644 src/portal/util/cooldown.js delete mode 100644 src/portal/util/eventloop.js delete mode 100644 src/portal/util/fps.js delete mode 100644 src/portal/util/loc.js delete mode 100644 src/portal/util/pointquadtree.js delete mode 100644 src/portal/util/quadtree.js delete mode 100644 src/portal/util/rbtree.js create mode 100644 src/portal/util/tree/pointquadtree.js create mode 100644 src/portal/util/tree/quadtree.js create mode 100644 src/portal/util/tree/rbtree.js create mode 100644 src/tanks/calc.js delete mode 100644 src/tanks/game/level.js create mode 100644 src/tanks/game/map.game.js delete mode 100644 src/tanks/game/map.js delete mode 100644 src/tanks/game/player.js delete mode 100644 src/tanks/lttl.js create mode 100644 src/tanks/main.js create mode 100644 src/tanks/map/level.js create mode 100644 src/tanks/map/loc.js create mode 100644 src/tanks/map/pathmap.js delete mode 100644 src/tanks/ui.js create mode 100644 src/tanks/ui.main.js create mode 100644 src/tanks/ui/grid.js create mode 100644 src/tanks/ui/player.js delete mode 100644 src/tanks/util/calc.js delete mode 100644 src/tanks/util/grid.js delete mode 100644 src/tanks/util/pathmap.js create mode 100644 tanks.php diff --git a/index.php b/index.php index 330dc95..8b6593d 100644 --- a/index.php +++ b/index.php @@ -25,62 +25,7 @@
-\n"; -} - -foreach ($scripts as $s) js($s); -?> +
diff --git a/src/Y/type.js b/src/Y/type.js index c23970c..11d7360 100644 --- a/src/Y/type.js +++ b/src/Y/type.js @@ -15,16 +15,9 @@ function type_of(obj){ } function isFunction(obj) { return type_of(obj) === "function"; } - function isString(obj) { return type_of(obj) === "string"; } - function isNumber(obj) { return type_of(obj) === "number"; } - - -// A crude way of determining if an object is a window -function isWindow( obj ) { - return obj && typeof obj === "object" && "setInterval" in obj; -} +function isWindow( obj ) { return obj && typeof obj === "object" && "setInterval" in obj; } function isPlainObject( obj ){ // Must be an Object. @@ -42,7 +35,6 @@ function isPlainObject( obj ){ // Own properties are enumerated firstly, so to speed up, // if last one is own, then all properties are own. - var key; for ( key in obj ) {} diff --git a/src/Y/y-core.js b/src/Y/y-core.js index dced427..ec51cba 100644 --- a/src/Y/y-core.js +++ b/src/Y/y-core.js @@ -4,9 +4,10 @@ Y.set = dset; Y.attr = dattr; Y.extend = extend; -Y.isFunction = isFunction; -Y.isString = isString; -Y.isNumber = isNumber; +Y.isString = isString; +Y.isNumber = isNumber; +Y.isFunction = isFunction; +Y.isArray = isArray; Y.isPlainObject = isPlainObject; diff --git a/src/portal/loop/cooldown.js b/src/portal/loop/cooldown.js new file mode 100644 index 0000000..5ba12cd --- /dev/null +++ b/src/portal/loop/cooldown.js @@ -0,0 +1,41 @@ +Cooldown = new Y.Class('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/portal/loop/eventloop.js b/src/portal/loop/eventloop.js new file mode 100644 index 0000000..466e822 --- /dev/null +++ b/src/portal/loop/eventloop.js @@ -0,0 +1,120 @@ +(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(){ + 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/portal/loop/fps.js b/src/portal/loop/fps.js new file mode 100644 index 0000000..5dc506a --- /dev/null +++ b/src/portal/loop/fps.js @@ -0,0 +1,99 @@ +FpsSparkline = new Y.Class('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(){ + 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/portal/math/vec.js b/src/portal/math/vec.js index 7ac8e02..76421f6 100644 --- a/src/portal/math/vec.js +++ b/src/portal/math/vec.js @@ -4,14 +4,12 @@ math.Vec = new Y.Class('Vec', [], { init : function init(x, y){ - if ( Array.isArray(x) ) { - y = x[1]; - x = x[0]; - } - this.length = 2; - this.x = this[0] = x; - this.y = this[1] = y; + + if ( x instanceof Array ) { + y = x[1]; x = x[0]; + } + this.setXY(x,y); }, equals : function equals(b){ @@ -22,32 +20,30 @@ math.Vec = new Y.Class('Vec', [], { return new math.Vec(this.x, this.y); }, - scale : function scale(s){ - this.x *= s; - this.y *= s; + setXY : function setXY(x,y){ + this.x = this[0] = x; + this.y = this[1] = y; return this; }, - invert : function invert(){ - this.x = -this.x; - this.y = -this.y; - return this; + add : function add(b){ + return this.setXY(this.x+b.x, this.y+b.y); }, - normalize : function normalize(){ - return this.scale(1 / this.magnitude()); + subtract : function subtract(b){ + return this.setXY(this.x-b.x, this.y-b.y); }, - add : function add(b){ - this.x += b.x; - this.y += b.y; - return this; + scale : function scale(s){ + return this.setXY(this.x*s, this.y*s); }, - subtract : function subtract(b){ - this.x -= b.x; - this.y -= b.y; - return this; + invert : function invert(){ + return this.setXY(-this.x, -this.y); + }, + + normalize : function normalize(){ + return this.scale(1 / this.magnitude()); }, magnitude : function magnitude(){ diff --git a/src/portal/path.js b/src/portal/path.js deleted file mode 100644 index e69de29..0000000 diff --git a/src/portal/portal.js b/src/portal/portal.js deleted file mode 100644 index e69de29..0000000 diff --git a/src/portal/shape.js b/src/portal/shape.js deleted file mode 100644 index 50d3895..0000000 --- a/src/portal/shape.js +++ /dev/null @@ -1,252 +0,0 @@ -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); - }); - } - -}); - - -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('
') - .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, t = this.transform.translate - , line = this.line, p1 = line.p1, p2 = line.p2 - , minW = -t.x, minH = -t.y - , maxW = this.canvasWidth+minW, maxH = this.canvasHeight+minH - ; - - 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) { - 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(69,150,255,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); -}; - - - -Rect = new Y.Class('Rect', Shape, { - _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(); - } - -}); - -Circle = new Y.Class('Circle', Shape, { - _cssClasses : 'portal layer shape circle', - - init : function initCircle(radius){ - Layer.init.call(this); - - var d = radius * 2; - this.radius = this.negBleed.x = this.negBleed.y = radius; - this.width(d).height(d); - // .origin(radius,radius); - }, - - drawShape : function drawShape(ctx){ - var r = this.radius; - ctx.arc(0,0, r, 0, Math.PI*2, false); - ctx.fill(); - ctx.stroke(); - } - -}); - -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/portal/shape/circle.js b/src/portal/shape/circle.js new file mode 100644 index 0000000..10e824f --- /dev/null +++ b/src/portal/shape/circle.js @@ -0,0 +1,21 @@ + +Circle = new Y.Class('Circle', Shape, { + _cssClasses : 'portal layer shape circle', + + init : function initCircle(radius){ + Layer.init.call(this); + + var d = radius * 2; + this.radius = this.negBleed.x = this.negBleed.y = radius; + this.width(d).height(d); + // .origin(radius,radius); + }, + + drawShape : function drawShape(ctx){ + var r = this.radius; + ctx.arc(0,0, r, 0, Math.PI*2, false); + ctx.fill(); + ctx.stroke(); + } + +}); diff --git a/src/portal/shape/line.js b/src/portal/shape/line.js new file mode 100644 index 0000000..fe9ddcd --- /dev/null +++ b/src/portal/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('
') + .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(69,150,255,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/portal/shape/polygon.js b/src/portal/shape/polygon.js new file mode 100644 index 0000000..a2cf377 --- /dev/null +++ b/src/portal/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/portal/shape/rect.js b/src/portal/shape/rect.js new file mode 100644 index 0000000..ef21d2d --- /dev/null +++ b/src/portal/shape/rect.js @@ -0,0 +1,18 @@ + +Rect = new Y.Class('Rect', Shape, { + _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(); + } + +}); diff --git a/src/portal/shape/shape.js b/src/portal/shape/shape.js new file mode 100644 index 0000000..609a74a --- /dev/null +++ b/src/portal/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/portal/transform.js b/src/portal/transform.js deleted file mode 100644 index 6e829f6..0000000 --- a/src/portal/transform.js +++ /dev/null @@ -1,61 +0,0 @@ -Transform = new Y.Class('Transform', { - - scale : function scale(x,y, layer, ctx){ - - }, - - translate : function translate(x,y, layer, ctx){ - - }, - - crop : function crop(){ - - } - -}); - -Transform.Rotation = new Y.Class('Rotation', Transform, { - - init : function initRotation(theta, x,y){ - this.theta = theta; - this.x = x; - this.y = y; - }, - - apply : function applyRotation(layer, ctx){ - ctx = ctx || layer.ctx; - ctx.translate(this.x, this.y); - ctx.rotate(this.theta); - ctx.translate(-this.x, -this.y); - } - -}); - -Transform.Scale = new Y.Class('Scale', Transform, { - - init : function initScale(x,y){ - this.x = x; - this.y = y; - }, - - apply : function apply(layer, ctx){ - ctx = ctx || layer.ctx; - ctx.scale(this.x, this.y); - } - -}); - -Transform.Translate = new Y.Class('Translate', Transform, { - - init : function init(x,y){ - this.x = x; - this.y = y; - }, - - apply : function apply(layer, ctx){ - ctx = ctx || layer.ctx; - ctx.translate(this.x, this.y); - } - -}); - diff --git a/src/portal/util/cooldown.js b/src/portal/util/cooldown.js deleted file mode 100644 index 5ba12cd..0000000 --- a/src/portal/util/cooldown.js +++ /dev/null @@ -1,41 +0,0 @@ -Cooldown = new Y.Class('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/portal/util/eventloop.js b/src/portal/util/eventloop.js deleted file mode 100644 index 466e822..0000000 --- a/src/portal/util/eventloop.js +++ /dev/null @@ -1,120 +0,0 @@ -(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(){ - 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/portal/util/fps.js b/src/portal/util/fps.js deleted file mode 100644 index 5dc506a..0000000 --- a/src/portal/util/fps.js +++ /dev/null @@ -1,99 +0,0 @@ -FpsSparkline = new Y.Class('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(){ - 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/portal/util/loc.js b/src/portal/util/loc.js deleted file mode 100644 index 659a6d8..0000000 --- a/src/portal/util/loc.js +++ /dev/null @@ -1,199 +0,0 @@ -// [x,y] -Loc = new Y.Class('Loc', math.Vec, { - - init : function init(x, y){ - if ( Array.isArray(x) ) { - y = x[1]; - x = x[0]; - } - - this.length = 2; - this.x = this[0] = x; - this.y = this[1] = y; - }, - - set : function set(k, v, def){ - v = (v !== undefined ? v : def); - switch (k) { - case 'x': case 0: - this.x = this[0] = v; break; - case 'y': case 1: - this.y = this[1] = v; break; - default: - this[k] = v; - } - return this; - }, - attr : Y.attr.methodize(), - - clone : function clone(){ - return new Loc(this.x, this.y); - }, - - moveBy : function moveBy(x,y){ - return new Loc(this.x+x, this.y+y); - }, - - moveByAngle : function moveByAngle(theta, v){ - var x = this.x + v*Math.sin(theta) - , y = this.y + v*Math.cos(theta); - return new Loc(x,y); - }, - - moveByDir : function moveByDir(dir, v){ - return this.moveByAngle(Loc.dirToAngle(dir), v); - }, - - toSquare : function toSquare(){ - return Loc.Square.fromLoc(this.x, this.y); - }, - - absolute : function absolute(w,h){ - var x = this.x, y = this.y - return new Loc( Y.isString(x) ? parseFloat(x.slice(0,-1))/100 * w : x - , Y.isString(y) ? parseFloat(y.slice(0,-1))/100 * h : y ); - }, - - toUnits : function toUnits(units){ - units = units || 'px'; - var x = this.x, y = this.y; - return { 'x' : Y.isNumber(x) ? x+units : x - , 'y' : Y.isNumber(y) ? y+units : y }; - }, - - toString : function toString(){ - var x = this.x, y = this.y; - x = Y.isNumber(x) ? x.toFixed(2) : x; - y = Y.isNumber(y) ? y.toFixed(2) : y; - return '('+x+','+y+')'; - } - -}); -Y(Loc).extend({ - UP : 'up', DOWN : 'down', - RIGHT : 'right', LEFT : 'left', - - dirToAngle : function dirToAngle(dir){ - switch (dir) { - case Loc.RIGHT: return 0; - case Loc.UP: return HALF_PI; - case Loc.LEFT: return PI; - case Loc.DOWN: return PI_AND_HALF; - - default: throw new Error("wtf direction is "+dir+"??"); - } - }, - - fromSquare : function fromSquare(col, row){ - return new Loc( - col * REF_SIZE, - row * REF_SIZE ); - }, - - // XXX: Probably wrong for negative locations - centerInSquare : function centerInSquare(v){ - return Math.floor(v/REF_SIZE)*REF_SIZE + REF_SIZE/2; - } - -}); - - -// [x1,y1, x2,y2] -Loc.Rect = new Y.Class('Rect', [], { - init : function init(x1,y1, x2,y2){ - if (x1 instanceof Loc && y1 instanceof Loc) { - y2 = y1.y; x2 = y1.x; - y1 = x1.y; x1 = x1.x; - } - - this.length = 4; - this.x1 = this[0] = this.x = x1; - this.y1 = this[1] = this.y = y1; - this.x2 = this[2] = x2; - this.y2 = this[3] = y2; - - this.width = x2 - x1; - this.height = y2 - y1; - - this.sides = { - top : new math.Line(x1,y1, x2,y1), - bottom : new math.Line(x1,y2, x2,y2), - left : new math.Line(x1,y1, x1,y2), - right : new math.Line(x2,y1, x2,y2) - }; - }, - - set : function set(k, v, def){ - v = (v !== undefined ? v : def); - - switch (k) { - case 'x1': case 0: case 'x': this.x1 = this[0] = this.x = v; break; - case 'y1': case 1: case 'y': this.y1 = this[1] = this.y = v; break; - case 'x2': case 2: this.x2 = this[2] = v; break; - case 'y1': case 3: this.y2 = this[3] = v; break; - - default: this[k] = v; - } - return this; - }, - - attr : Y.attr.methodize(), - - moveTo : function moveTo(x,y){ - return new Loc.Rect(x,y, x+this.width,y+this.height); - }, - - midpoint : function midpoint(){ - return new Loc( this.x1 + this.width /2 - , this.y1 + this.height/2 ); - }, - - clone : function clone(){ - return new Loc.Rect( this.top.clone() - , this.bottom.clone() ); - }, - - contains : function contains(x,y){ - return ( x >= this.x1 && x <= this.x2 && - y >= this.y1 && y <= this.y2 ); - }, - - toString : function toString(){ - return '['+this.top()+' '+this.bottom()+']'; - } - -}); - -Loc.Square = new Y.Class('Square', Loc.Rect, { - init : function init(col, row){ - this.col = col; - this.row = row; - - var x1 = col * REF_SIZE, y1 = row * REF_SIZE - , x2 = x1 + REF_SIZE, y2 = y1 + REF_SIZE - ; - - Loc.Rect.init.call(this, x1,y1, x2,y2); - }, - - clone : function clone(){ - return new Square(this.col, this.row); - }, - - toLoc : function toLoc(){ - return Loc.fromSquare(this.col, this.row); - }, - - toString : function toString(){ - return this.col+'_'+this.row; - } - -}); - -// XXX: Negative grid positions don't round correctly -Loc.Square.fromLoc = function(x, y){ - return new Loc.Square( - Math.floor(x / REF_SIZE), - Math.floor(y / REF_SIZE) ); -}; - diff --git a/src/portal/util/pointquadtree.js b/src/portal/util/pointquadtree.js deleted file mode 100644 index 28d2e16..0000000 --- a/src/portal/util/pointquadtree.js +++ /dev/null @@ -1,580 +0,0 @@ -(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 = new Y.Class('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 = new Y.Class('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 = new Y.Class('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 !( xroot.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/portal/util/quadtree.js b/src/portal/util/quadtree.js deleted file mode 100644 index 47b9fa7..0000000 --- a/src/portal/util/quadtree.js +++ /dev/null @@ -1,205 +0,0 @@ -(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; -} - -var -CAPACITY = 8, -REGION_ID = 0, - -Region = new Y.Class('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+', value='+this.value+')'; - } -}), - -QuadTree = new Y.Class('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 ); - }, - - - 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; - }, - - 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 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/portal/util/rbtree.js b/src/portal/util/rbtree.js deleted file mode 100644 index 1c71b2f..0000000 --- a/src/portal/util/rbtree.js +++ /dev/null @@ -1,467 +0,0 @@ -(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 = new Y.Class('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 - 'max' : function() { - if (this.isEmpty()) return null; - return this._max(this._root).key; - }, - - // the largest key in the subtree rooted at x; null if no such key - _max : function _max(x) { - // assert x !== null; - if (x.right === null) return x; - else return this._max(x.right); - }, - - // the largest key less than or equal to the given key - 'floor' : function(key) { - var x = this._floor(this._root, key); - if (x === null) return null; - else return x.key; - }, - - // the largest key in the subtree rooted at x less than or equal to the given key - _floor : function _floor(x, key) { - if (x === null) return null; - if (key === x.key) return x; - if (key < x.key) return this._floor(x.left, key); - var t = this._floor(x.right, key); - if (t !== null) return t; - else return x; - }, - - // the smallest key greater than or equal to the given key - 'ceiling' : function(key) { - var x = this._ceiling(this._root, key); - if (x === null) return null; - else return x.key; - }, - - // the smallest key in the subtree rooted at x greater than or equal to the given key - _ceiling : function _ceiling(x, key) { - if (x === null) return null; - if (key === x.key) return x; - if (key > x.key) return this._ceiling(x.right, key); - var t = this._ceiling(x.left, key); - if (t !== null) return t; - else return x; - }, - - - // the key of rank i - 'iRank' : function(i) { - if (i < 0 || i >= this.size()) - return null; - var x = this._iRank(this._root, i); - return x.key; - }, - - // the key of rank i in the subtree rooted at x - _iRank : function _iRank(x, i) { - // assert x !== null; - // assert i >= 0 && i < size(x); - var t = size(x.left); - if (t > i) return this._iRank(x.left, i); - else if (t < i) return this._iRank(x.right, i-t-1); - else return x; - }, - - // number of keys less than key - 'rank' : function(key) { - return this._rank(key, this._root); - }, - - // number of keys less than key in the subtree rooted at x - _rank : function _rank(key, x) { - if (x === null) return 0; - if (key < x.key) return this._rank(key, x.left); - else if (key > x.key) return 1 + size(x.left) + this._rank(key, x.right); - else return size(x.left); - }, - - /*********************************************************************** - * Range count and range search. - ***********************************************************************/ - - // the keys between lo and hi, as an Iterable - 'keys' : function(lo, hi) { - var queue = []; - lo = lo || this.min(); - hi = hi || this.max(); - // if (this.isEmpty() || lo > hi) return queue; - this._keys(this._root, queue, lo, hi); - return queue; - }, - - // add the keys between lo and hi in the subtree rooted at x - // to the queue - _keys : function _keys(x, queue, lo, hi) { - if (!x) return; - if (lo < x.key) this._keys(x.left, queue, lo, hi); - if (lo <= x.key && hi >= x.key) queue.push(x.key); - if (hi > x.key) this._keys(x.right, queue, lo, hi); - }, - - // number keys between lo and hi - 'count' : function(lo, hi) { - if (lo > hi) return 0; - if (this.contains(hi)) return this._rank(hi) - this._rank(lo) + 1; - else return this._rank(hi) - this._rank(lo); - }, - - /** - * Visits all pairs in [lo..hi], defaulting to [min..max]. - * Visitor defaults to creating an array of nodes. - */ - 'reduce' : function(fn, acc, lo, hi, context){ - return this._reduce( this._root, fn, acc, - lo || this.min(), hi || this.max(), context || this ); - }, - - _reduce : function _reduce(x, fn, acc, lo, hi, context){ - if (!x) return acc; - if (lo < x.key) acc = this._reduce(x.left, fn, acc, lo, hi, context); - if (lo <= x.key && hi >= x.key) acc = fn.call(context, acc, x.val, x.key, this); - if (hi > x.key) acc = this._reduce(x.right, fn, acc, lo, hi, context); - return acc; - }, - - /** - * Returns a new tree with the same keyset and values - * generated by applying the given function. - */ - 'map' : function(fn, lo, hi, context){ - return this.reduce(function(newTree, v, k, tree){ - newTree.setKey(k, fn.call(this, v, k, tree)); - return newTree; - }, new RedBlackTree(), lo, hi, context); - }, - - /** - * Iterates across keys between [lo..hi]. - */ - 'forEach' : function(fn, lo, hi, context){ - this.reduce(function(acc, v, k, tree){ - fn.call(this, v, k, tree); - }, null, lo, hi, context); - }, - - 'toString' : function(){ - return this.className+"(size="+this.size()+", height="+this.height()+")"; - } - - -}); - -RedBlackTree['RED'] = RED; -RedBlackTree['BLACK'] = BLACK; -RedBlackTree['Node'] = Node; -this['RedBlackTree'] = RedBlackTree; - -})(); diff --git a/src/portal/util/tree/pointquadtree.js b/src/portal/util/tree/pointquadtree.js new file mode 100644 index 0000000..28d2e16 --- /dev/null +++ b/src/portal/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 = new Y.Class('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 = new Y.Class('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 = new Y.Class('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 !( xroot.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: +