requirebin sketch

index.js

// Welcome! require() some modules from npm (like you were using browserify)
// and then hit Run Code to run your code on the right side.
// Modules get downloaded from browserify-cdn and bundled in your browser.
/*
var tree = require("segment-tree").zeros(10)

tree.set(1, 10)
tree.set(2, 5)
tree.set(6, 8)
tree.set(11, 14)

console.log(tree.length)
console.log(tree.pointers)
console.log(tree.values)
*/


var intervals = require('interval-query');

var tree = new intervals.SegmentTree;

//tree.pushInterval(1, 5);
//tree.pushInterval(2, 7);
//tree.pushInterval(3, 6);

tree.pushInterval(1, 10);
tree.pushInterval(2, 5)
tree.pushInterval(6, 8)
tree.pushInterval(11, 14)

tree.buildTree();
console.log(tree.queryOverlap());
tree.printTreeTopDown();

var IntervalTree = require('interval-tree2');
var itree = new IntervalTree(300); 

itree.add(22, 56,  'foo'); // 'foo' is the id of the interval data
itree.add(44, 199, 'bar'); // 'bar' is the id of the interval data
itree.add(1, 38); // id is automatically set when not given


var intervals2 = itree.rangeSearch(22, 199);
console.log(intervals2);

minified.js

setTimeout(function(){require=function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s}({1:[function(require,module,exports){module.exports.Interval=Interval;module.exports.IntervalStack=IntervalStack;function Interval(from,to){this.id=++Interval.prototype.id;this.from=from;this.to=to}Interval.prototype.id=0;Interval.const=Interval.prototype;Interval.prototype.SUBSET=1;Interval.prototype.DISJOINT=2;Interval.prototype.INTERSECT_OR_SUPERSET=3;Interval.prototype.compareTo=function(other){if(other.from>this.to||other.to<this.from)return this.DISJOINT;if(other.from<=this.from&&other.to>=this.to)return this.SUBSET;return this.INTERSECT_OR_SUPERSET};Interval.prototype.disjointIncl=function(other){if(other.from>this.to||other.to<this.from)return this.DISJOINT};Interval.prototype.disjointExcl=function(other){if(other.from>=this.to||other.to<=this.from)return this.DISJOINT};function IntervalStack(intervals,queryIntervalFn){this._intervals=intervals;this._queryInterval=queryIntervalFn}IntervalStack.prototype=function(){return{constructor:IntervalStack,pushInterval:pushInterval,pushArray:pushArray,clearIntervalStack:clearIntervalStack,queryPoint:queryPoint,queryPointArray:queryPointArray,queryInterval:queryInterval,queryIntervalArray:queryIntervalArray}}();function _validateInterval(from,to){if(typeof from!=="number"||typeof to!=="number")throw{name:"InvalidInterval",message:"endpoints of interval must be of type number"};if(from>to)throw{name:"InvalidInterval",message:"("+from+","+to+")"+" a > b"}}function _validateIntervalArray(from,to){if(!(from instanceof Array&&to instanceof Array))throw{name:"InvalidParameter",message:"function pushArray: parameters must be arrays"};if(from.length!==to.length)throw{name:"InvalidParameter",message:"function pushArray: arrays must have same length"};for(var i=0;i<from.length;i++){_validateInterval(from[i],to[i])}}function _validatePoint(point){if(typeof point!=="number")throw{name:"InvalidParameter",message:"parameter must be a number"}}function _validatePointArray(points){if(!(points instanceof Array))throw{name:"InvalidParameter",message:"parameter must be an array"};for(var i=0;i<points.length;i++){if(typeof points[i]!=="number")throw{name:"InvalidParameter",message:"array must consist only of numbers"}}}function pushInterval(from,to){_validateInterval(from,to);this._intervals.push(new Interval(from,to))}function pushArray(from,to,validate){var val=validate!==undefined?validate:true;if(val)_validateIntervalArray(from,to);for(var i=0;i<from.length;i++){this._intervals.push(new Interval(from[i],to[i]))}}function clearIntervalStack(){this._intervals.length=0;Interval.prototype.id=0}function queryPoint(point,resultFn){_validatePoint(point);return this.queryPointArray([point],resultFn)}function queryPointArray(points,resultFn,validate){var val=validate!==undefined?validate:true;if(val)_validatePointArray(points);var intervalArray=points.map(function(item){return new Interval(item,item)});return this._queryInterval(intervalArray,resultFn)}function queryInterval(from,to,options){_validateInterval(from,to);return this.queryIntervalArray([from],[to],options)}function queryIntervalArray(from,to,options){var intervalArray=[];var val=options!==undefined&&options.validate!==undefined?options.validate:true;var resFn=options!==undefined&&options.resultFn!==undefined?options.resultFn:undefined;var disjointFn=options!==undefined&&options.endpoints===false?Interval.prototype.disjointExcl:Interval.prototype.disjointIncl;if(val)_validateIntervalArray(from,to);for(var i=0;i<from.length;i++){intervalArray.push(new Interval(from[i],to[i]))}return this._queryInterval(intervalArray,resFn,disjointFn)}},{}],2:[function(require,module,exports){var intervals=require("./intervals");function Node(from,to){this.left=null;this.right=null;this.segment=new intervals.Interval(from,to);this.intervals=[]}var root=null;var _intervals=[];function SegmentTree(){if(!(this instanceof SegmentTree))return new SegmentTree;intervals.IntervalStack.call(this,_intervals,_queryInterval)}SegmentTree.prototype=new intervals.IntervalStack(_intervals,_queryInterval);SegmentTree.prototype.constructor=SegmentTree;SegmentTree.prototype.buildTree=buildTree;SegmentTree.prototype.printTree=printTree;SegmentTree.prototype.printTreeTopDown=printTreeTopDown;SegmentTree.prototype.queryOverlap=queryOverlap;module.exports.SegmentTree=SegmentTree;function _endpointArray(){var endpoints=[];endpoints.push(-Infinity);endpoints.push(Infinity);_intervals.forEach(function(item){endpoints.push(item.from);endpoints.push(item.to)});return _sortAndDeDup(endpoints,function(a,b){return a-b})}function _sortAndDeDup(unordered,compFn){var result=[];var prev;unordered.sort(compFn).forEach(function(item){var equal=compFn!==undefined&&prev!==undefined?compFn(prev,item)===0:prev===item;if(!equal){result.push(item);prev=item}});return result}function _insertElements(pointArray){var node;if(pointArray.length===2){node=new Node(pointArray[0],pointArray[1]);if(pointArray[1]!==Infinity){node.left=new Node(pointArray[0],pointArray[1]);node.right=new Node(pointArray[1],pointArray[1])}}else{node=new Node(pointArray[0],pointArray[pointArray.length-1]);var center=Math.floor(pointArray.length/2);node.left=_insertElements(pointArray.slice(0,center+1));node.right=_insertElements(pointArray.slice(center))}return node}function _insertInterval(node,interval){switch(node.segment.compareTo(interval)){case intervals.Interval.const.SUBSET:node.intervals.push(interval);break;case intervals.Interval.const.INTERSECT_OR_SUPERSET:if(node.left)_insertInterval(node.left,interval);if(node.right)_insertInterval(node.right,interval);break;case intervals.Interval.const.DISJOINT:break}}function _traverseTree(node,enterFn,leaveFn){if(node===null)return;if(enterFn!==undefined)enterFn(node);_traverseTree(node.right,enterFn,leaveFn);_traverseTree(node.left,enterFn,leaveFn);if(leaveFn!==undefined)leaveFn(node)}function _tree2Array(node,level,array){if(node===null)return;if(level===undefined)level=-1;if(array===undefined)array=[];level++;if(!array[level])array[level]=[];array[level].push(node);_tree2Array(node.right,level,array);_tree2Array(node.left,level,array);return array}function _query(node,queryIntervals,hits,disjointFn){if(node===null)return;var notDisjoint=[];queryIntervals.forEach(function(queryInterval){if(disjointFn.call(node.segment,queryInterval)!==intervals.Interval.const.DISJOINT){node.intervals.forEach(function(interval){hits[interval.id]=interval});notDisjoint.push(queryInterval)}});if(notDisjoint.length!==0){_query(node.right,notDisjoint,hits,disjointFn);_query(node.left,notDisjoint,hits,disjointFn)}}function _queryInterval(intervalArray,resultFn,disjointFn){var hits={};if(disjointFn===undefined)disjointFn=intervals.Interval.prototype.disjointIncl;_query(root,intervalArray,hits,disjointFn);var intervalArray=Object.keys(hits).map(function(key){return hits[key]});if(resultFn!==undefined&&typeof resultFn==="function")resultFn(intervalArray);return intervalArray.length}function _exchangeOverlap(intervals,superiorIntervals){for(var i=0;i<superiorIntervals.length;i++){var superiorInterval=superiorIntervals[i];for(var j=0;j<intervals.length;j++){intervals[j].overlap[superiorInterval.id]=superiorInterval;superiorInterval.overlap[intervals[j].id]=intervals[j]}}for(var i=0;i<intervals.length;i++){for(var j=i+1;j<intervals.length;j++){intervals[i].overlap[intervals[j].id]=intervals[j];intervals[j].overlap[intervals[i].id]=intervals[i]}}}function _queryOverlap(node,topOverlap){if(node===null)return;var localTopOvrlp;if(node.intervals.length!==0){_exchangeOverlap(node.intervals,topOverlap);localTopOvrlp=topOverlap.concat(node.intervals)}else{localTopOvrlp=topOverlap}_queryOverlap(node.left,localTopOvrlp);_queryOverlap(node.right,localTopOvrlp)}function buildTree(){if(_intervals.length===0)throw{name:"BuildTreeError",message:"interval stack is empty"};root=_insertElements(_endpointArray());_intervals.forEach(function(item){_insertInterval(root,item)})}function printTree(){_traverseTree(root,function(node){console.log("\nSegment: (%d,%d)",node.segment.from,node.segment.to);node.intervals.forEach(function(item,pos){console.log("Interval %d: (%d,%d)",pos,item.from,item.to)})})}function printTreeTopDown(){_tree2Array(root).forEach(function(item,pos){console.log("Level %d:",pos);item.forEach(function(item,pos){console.log("Segment %d: (%d,%d)",pos,item.segment.from,item.segment.to);item.intervals.forEach(function(item,pos){console.log("  Interval %d: (%d,%d)",pos,item.from,item.to)})})})}function queryOverlap(){_intervals.forEach(function(interval){interval.overlap={}});_queryOverlap(root,[]);_intervals.forEach(function(interval){interval.overlap=Object.keys(interval.overlap)});return _intervals}},{"./intervals":1}],3:[function(require,module,exports){var intervals=require("./intervals");var _intervals=[];function Sequential(){if(!(this instanceof Sequential))return new Sequential;intervals.IntervalStack.call(this,_intervals,_queryInterval)}Sequential.prototype=new intervals.IntervalStack(_intervals,_queryInterval);Sequential.prototype.constructor=Sequential;Sequential.prototype.queryOverlap=queryOverlap;module.exports.Sequential=Sequential;function _query(queryIntervals,hits,disjointFn){queryIntervals.forEach(function(queryInterval){_intervals.forEach(function(interval){if(disjointFn.call(interval,queryInterval)!==intervals.Interval.const.DISJOINT){hits[interval.id]=interval}})})}function _queryInterval(intervalArray,resultFn,disjointFn){var hits={};if(disjointFn===undefined)disjointFn=intervals.Interval.prototype.disjointIncl;_query(intervalArray,hits,disjointFn);var intervalArray=Object.keys(hits).map(function(key){return hits[key]});if(resultFn!==undefined&&typeof resultFn==="function")resultFn(intervalArray);return intervalArray.length}function _queryOverlap(disjointFn){for(var i=0;i<_intervals.length;i++){for(var h=i+1;h<_intervals.length;h++){if(disjointFn.call(_intervals[i],_intervals[h])!==intervals.Interval.const.DISJOINT){_intervals[i].overlap.push(_intervals[h].id.toString());_intervals[h].overlap.push(_intervals[i].id.toString())}}}}function queryOverlap(){_intervals.forEach(function(interval){interval.overlap=[]});_queryOverlap(intervals.Interval.prototype.disjointIncl);return _intervals}},{"./intervals":1}],"interval-query":[function(require,module,exports){var segment=require("./lib/segment-tree");var sequential=require("./lib/sequential");module.exports.SegmentTree=segment.SegmentTree;module.exports.Sequential=sequential.Sequential},{"./lib/segment-tree":2,"./lib/sequential":3}]},{},[]);require=function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s}({1:[function(require,module,exports){var Interval,IntervalTree,Node,Point,SortedList,Util;SortedList=require("./sorted-list");Node=require("./node");Point=require("./point");Interval=require("./interval");Util=require("./util");IntervalTree=function(){function IntervalTree(center){Util.assertNumber(center,"IntervalTree: center");this.nodesByCenter={};this.root=this.createNode(center);this.intervalsById={};this.nodesById={};this.pointTree=new SortedList("val");this.idCandidate=0}IntervalTree.prototype.add=function(start,end,id){var interval;if(this.intervalsById[id]!=null){throw new Error("id "+id+" is already registered.")}if(id==null){while(this.intervalsById[this.idCandidate]!=null){this.idCandidate++}id=this.idCandidate}Util.assertNumber(start,"1st argument of IntervalTree#add()");Util.assertNumber(end,"2nd argument of IntervalTree#add()");if(start>=end){Util.assertOrder(start,end,"start","end")}interval=new Interval(start,end,id);this.pointTree.insert(new Point(interval.start,id));this.pointTree.insert(new Point(interval.end,id));this.intervalsById[id]=interval;return this.insert(interval,this.root)};IntervalTree.prototype.search=function(val1,val2){Util.assertNumber(val1,"1st argument at IntervalTree#search()");if(val2==null){return this.pointSearch(val1)}else{Util.assertNumber(val2,"2nd argument at IntervalTree#search()");Util.assertOrder(val1,val2,"1st argument","2nd argument","IntervalTree#search()");return this.rangeSearch(val1,val2)}};IntervalTree.prototype.remove=function(id){var interval,node;interval=this.intervalsById[id];if(interval==null){return}node=this.nodesById[id];node.remove(interval);delete this.nodesById[id];return delete this.intervalsById[id]};IntervalTree.prototype.pointSearch=function(val,node,results){if(node==null){node=this.root}if(results==null){results=[]}Util.assertNumber(val,"1st argument of IntervalTree#pointSearch()");if(val<node.center){results=results.concat(node.startPointSearch(val));if(node.left!=null){return this.pointSearch(val,node.left,results)}else{return results}}if(val>node.center){results=results.concat(node.endPointSearch(val));if(node.right!=null){return this.pointSearch(val,node.right,results)}else{return results}}return results.concat(node.getAllIntervals())};IntervalTree.prototype.rangeSearch=function(start,end){var firstPos,i,id,interval,j,lastPos,len,len1,point,ref,ref1,resultsById;Util.assertNumber(start,"1st argument at IntervalTree#rangeSearch()");Util.assertNumber(end,"2nd argument at IntervalTree#rangeSearch()");Util.assertOrder(start,end,"1st argument","2nd argument","IntervalTree#rangeSearch()");resultsById={};ref=this.pointSearch(start);for(i=0,len=ref.length;i<len;i++){interval=ref[i];resultsById[interval.id]=interval}firstPos=this.pointTree.firstPositionOf(new Point(start));lastPos=this.pointTree.lastPositionOf(new Point(end));ref1=this.pointTree.slice(firstPos,lastPos+1);for(j=0,len1=ref1.length;j<len1;j++){point=ref1[j];resultsById[point.id]=this.intervalsById[point.id]}return function(){var results1;results1=[];for(id in resultsById){interval=resultsById[id];results1.push(interval)}return results1}()};IntervalTree.prototype.insert=function(interval,node){if(interval.end<node.center){if(node.left==null){node.left=this.createNode(interval.end)}return this.insert(interval,node.left)}if(node.center<interval.start){if(node.right==null){node.right=this.createNode(interval.start)}return this.insert(interval,node.right)}node.insert(interval);this.nodesById[interval.id]=node;return interval};IntervalTree.prototype.createNode=function(center){var node;node=new Node(center);this.nodesByCenter[center]=node;return node};return IntervalTree}();module.exports=IntervalTree},{"./interval":2,"./node":3,"./point":4,"./sorted-list":5,"./util":6}],2:[function(require,module,exports){var Interval;Interval=function(){function Interval(start,end,id){this.start=start;this.end=end;this.id=id}Interval.prototype.center=function(){return(this.start+this.end)/2};return Interval}();module.exports=Interval},{}],3:[function(require,module,exports){var Node,SortedList;SortedList=require("./sorted-list");Node=function(){function Node(center){this.center=center;this.left=null;this.right=null;this.starts=new SortedList("start");this.ends=new SortedList("end")}Node.prototype.count=function(){return this.starts.length};Node.prototype.insert=function(interval){this.starts.insert(interval);return this.ends.insert(interval)};Node.prototype.startPointSearch=function(val){var index;index=this.starts.lastPositionOf({start:val});return this.starts.slice(0,index+1)};Node.prototype.endPointSearch=function(val){var index;index=this.ends.firstPositionOf({end:val});return this.ends.slice(index)};Node.prototype.getAllIntervals=function(){return this.starts.toArray()};Node.prototype.remove=function(interval){this.removeFromList(interval,this.starts);return this.removeFromList(interval,this.ends)};Node.prototype.removeFromList=function(interval,list){var candidate,firstPos,i,idx,ref,ref1,results;firstPos=list.firstPositionOf(interval);results=[];for(idx=i=ref=firstPos,ref1=list.length;ref<=ref1?i<ref1:i>ref1;idx=ref<=ref1?++i:--i){candidate=list[idx];if(candidate.id===interval.id){list.remove(idx);break}else{results.push(void 0)}}return results};return Node}();module.exports=Node},{"./sorted-list":5}],4:[function(require,module,exports){var Point;Point=function(){function Point(val,id){this.val=val;this.id=id}return Point}();module.exports=Point},{}],5:[function(require,module,exports){var SortedList,extend=function(child,parent){for(var key in parent){if(hasProp.call(parent,key))child[key]=parent[key]}function ctor(){this.constructor=child}ctor.prototype=parent.prototype;child.prototype=new ctor;child.__super__=parent.prototype;return child},hasProp={}.hasOwnProperty;SortedList=function(superClass){extend(SortedList,superClass);function SortedList(compareKey){this.compareKey=compareKey}SortedList.prototype.insert=function(val){var pos;pos=this.bsearch(val);this.splice(pos+1,0,val);return pos+1};SortedList.prototype.remove=function(pos){this.splice(pos,1);return this};SortedList.prototype.max=function(){var ref;return(ref=this[this.length-1])!=null?ref[this.compareKey]:void 0};SortedList.prototype.min=function(){var ref;return(ref=this[0])!=null?ref[this.compareKey]:void 0};SortedList.prototype.bsearch=function(val){var comp,epos,mpos,mval,spos;if(!this.length){return-1}mpos=null;mval=null;spos=0;epos=this.length;while(epos-spos>1){mpos=Math.floor((spos+epos)/2);mval=this[mpos];comp=this.compare(val,mval);if(comp===0){return mpos}if(comp>0){spos=mpos}else{epos=mpos}}if(spos===0&&this.compare(this[0],val)>0){return-1}else{return spos}};SortedList.prototype.firstPositionOf=function(val){var index,num,ref;index=this.bsearch(val);if(index===-1){return-1}num=val[this.compareKey];if(num===((ref=this[index])!=null?ref[this.compareKey]:void 0)){while(true){if(index<=0){break}if(this[index-1][this.compareKey]<num){break}index--}}else{index++}return index};SortedList.prototype.lastPositionOf=function(val){var index,num;index=this.bsearch(val);if(index===-1){return-1}num=val[this.compareKey];if(index===this.length-1&&num>this.max()){return index+1}while(true){if(index+1>=this.length){break}if(this[index+1][this.compareKey]>num){break}index++}return index};SortedList.prototype.toArray=function(){return this.slice()};SortedList.prototype.compare=function(a,b){var c;if(a==null){return-1}if(b==null){return 1}c=a[this.compareKey]-b[this.compareKey];if(c>0){return 1}else if(c===0){return 0}else{return-1}};return SortedList}(Array);module.exports=SortedList},{}],6:[function(require,module,exports){var Util;Util=function(){function Util(){}Util.assertNumber=function(val,desc){if(val==null){throw new Error(desc+" is required.")}if(typeof val!=="number"){throw new Error(desc+" must be a number.")}};Util.assertOrder=function(start,end,startName,endName,desc){if(start>=end){throw new Error(desc+": "+startName+"("+start+") must be smaller than "+endName+"("+end+").")}};return Util}();module.exports=Util},{}],"interval-tree2":[function(require,module,exports){module.exports=require("./dist/lib/interval-tree")},{"./dist/lib/interval-tree":1}]},{},[]);var intervals=require("interval-query");var tree=new intervals.SegmentTree;tree.pushInterval(1,10);tree.pushInterval(2,5);tree.pushInterval(6,8);tree.pushInterval(11,14);tree.buildTree();console.log(tree.queryOverlap());tree.printTreeTopDown();var IntervalTree=require("interval-tree2");var itree=new IntervalTree(300);itree.add(22,56,"foo");itree.add(44,199,"bar");itree.add(1,38);var intervals2=itree.rangeSearch(22,199);console.log(intervals2)},0);

package.json

{
  "name": "requirebin-sketch",
  "version": "1.0.0",
  "dependencies": {
    "interval-query": "0.3.0",
    "interval-tree2": "1.1.0"
  }
}

page-body.html

<!-- contents of this file will be placed inside the <body> -->

page-head.html

<!-- contents of this file will be placed inside the <head> -->

requirebin.md

made with requirebin