intervals.js

// How fast can you get all the intervals that overlap with another interval?
// WTF.. who cares.  Well if you are given the task to find all the stories 
// from a facebook timeline visible to the user, 
// how would you do that without blocking the user's scrolling?
// Imagine, you mark the stories as read and notify the server that the user saw those stories.
 
// It turns out you can achieve this task in log time using a segment tree.
// More about segment trees: 
// http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Segment_Trees
// Sample:
// var segments = getSegments([[3,4], [0,1], [16, 19]])
// segments([9, 20])
//  -> [[ 16, 19 ]]
 
// * * * * * * * * * *
// Mapping it to DOM:
//
// function getSegmentForElement(el) {
//   var $el = $(el);
//   var offset = $el.offset();
//   var outerHeight = $el.outerHeight(false);
//   return [offset.top, offset.top + outerHeight];  
// }
//  var segments = getSegments(document.body.childNodes.map(getSegmentForElement));
//  visibleElements = segments($(window).scrollTop(), $(window).scrollTop() + $(window).height());
 
 
function getSegments(intervals) {
  // the null inside the tree is a sentinel, so don't worry about it
  var tree = [null];
  var maxEnd = new Array(intervals.length);
 
  // Preprocessing time takes O(n*log(n)) + 2n 
  // if the intervals are sorted, 
  // for example: if you scan visible elements on the screen as they are positioned on one axis, 
  // then you don't need to sort the intervals. and this part would take linear time to build the tree
  // BTW this should be done only once, if the interval's values don't change.
 
  intervals.sort(function(a, b) { 
    return a[0] - b[0];
  });
 
  maxEnd[0] = intervals[0][1];
 
  for (var i = 1; i < maxEnd.length; i++) {
    maxEnd[i] = Math.max(intervals[i][1], maxEnd[i - 1]);
  }
 
  var buildTree = function(index, i, j) {
    if (i <= j) {
      if (i === j) {
        tree[index] = intervals[i];
      } else {
        var rootIndex = (i + j) >> 1;
        tree[index] = [intervals[i][0], maxEnd[j]];
        buildTree(index << 1, i, rootIndex);
        buildTree((index << 1) + 1, rootIndex + 1, j);
      }
    }
  };
 
  buildTree(1, 0, intervals.length - 1);
  
  // here is where the fun begins
  // the search takes O(log n) + m
  // where `m` is the number of segments found
 
  var treeLength = tree.length;
  var searchTree = function(index, segment, segmentsFound) {
    if (index >= treeLength) {
      return null;
    }
    if (segment[1] >= tree[index][0] && segment[0] <= tree[index][1]) {
      var leftSubtree = searchTree(index << 1, segment, segmentsFound);
      var rightSubtree = searchTree((index << 1) + 1, segment, segmentsFound);
      if (leftSubtree === null && rightSubtree === null) {
        // `index` is a leaf
        segmentsFound.push(tree[index]);
      }
    }
    return true;
  };
 
  return function(segment) {
    var segmentsFound = [];
    searchTree(1, segment, segmentsFound);
    return segmentsFound;
  }
}