Last active
August 29, 2015 13:56
-
-
Save joshuabambrick/9103568 to your computer and use it in GitHub Desktop.
Backbone Collection Binary Search
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(function (factory) { | |
if (typeof define === 'function' && define.amd) { | |
// AMD. Register as an anonymous module. | |
define(['underscore', 'backbone'], factory); | |
} else { | |
// Browser globals | |
factory( this._, this.Backbone ); | |
} | |
}(function (_, Backbone) { | |
if (_ == null || Backbone == null) throw new Error('Underscore or Backbone not found.'); | |
Backbone.Collection.prototype.search = function (value, returnIndex) { | |
var binarySearch, | |
index, | |
searchCompare; | |
binarySearch = function (searchCompare) { | |
var maxIndex = this.length - 1, minIndex = 0, currentIndex, relativeValue, foundMatch; | |
while (maxIndex >= minIndex && !foundMatch) { | |
currentIndex = Math.floor((maxIndex + minIndex) / 2); | |
relativeValue = +searchCompare(this.at(currentIndex)); | |
if (relativeValue > 0) { | |
// move up | |
minIndex = currentIndex + 1; | |
} else if (relativeValue < 0) { | |
// move down | |
maxIndex = currentIndex - 1; | |
} else { | |
// exact match found | |
foundMatch = true; | |
} | |
} | |
return foundMatch ? currentIndex : -1; | |
}; | |
if (this.comparator) { | |
// is sorted | |
if (_(value).isFunction()) { | |
searchCompare = value; | |
} else if (_(this.comparator).isFunction()) { | |
// use the comparator function | |
if (this.comparator.length === 2) { | |
searchCompare = _(this.comparator).bind(this, value); | |
} else if (this.comparator.length === 1) { | |
searchCompare = _(function (valueResult, comparisonModel) { | |
var comparisonResult = this.comparator(comparisonModel); | |
return valueResult === comparisonResult ? 0 : (valueResult > comparisonResult ? 1 : -1); | |
}).bind(this, this.comparator(value)); | |
} | |
} else { | |
// comparator is a string indicating the model property used to sort | |
searchCompare = _(function (comparisonModel) { | |
var comparisonValue = comparisonModel.get(this.comparator); | |
return value === comparisonValue ? 0 : (value > comparisonValue ? 1 : -1); | |
}).bind(this); | |
} | |
// use binary search to find the index | |
index = binarySearch.call(this, searchCompare); | |
} else { | |
// not sorted | |
throw new Error('Collection not sorted; define a comparator or use `find` to search instead'); | |
} | |
return returnIndex ? index : this.at(index); | |
}; | |
})); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment