Trunk collection: iterate and search efficiently
What I have: I am writing a very trivial media player. So somewhere in it I have a collection of subtitles (say, about 2 thousand per movie). Therefore, each subheading looks like this:
Object {
id: "1"
startTime: 2468
endTime: 4743
text: "Test subtitle."
}
I want to: Very efficient to do two things:
-
.next()
which should get me the next subtitle. -
.getByTime(neededTime)
that do something like a binary search through the entire collection of subtitles in an efficient way. The point is that thereneededTime
could be something between attributesstartTime
andendTime
(i.e. 3000).
Q: I'm going to use the Backbone collection for my subtitles, but how does it handle these two requirements? I mean maybe it would be better to implement the Iterator pattern and binary search by hand?
+3
source to share
1 answer
Don't know if this is the best solution, but I end up with:
if (!Number.isInteger) {
Number.isInteger = function isInteger (nVal) {
return typeof nVal === "number" && isFinite(nVal) && nVal > -9007199254740992 && nVal < 9007199254740992 && Math.floor(nVal) === nVal;
};
}
/**
* Model
*/
var Subtitle = Backbone.Model.extend({
defaults: {
'startTime': '',
'endTime': '',
'text': ''
},
validate: function(attrs) {
if (!this.get('startTime')) return 'You missed startTime';
if (!this.get('endTime')) return 'You missed endTime';
if (!this.get('text')) return 'You missed text';
if (this.get('startTime') > this.get('endTime')) return 'startTime cannot be greater than endTime';
},
/**
* Compare two time periods
* @param that Subtitle with which we compare the current one
* @returns {number} positive if {@code this} is greater than {@code that}, negative if {@code this} is less than {@code that}
* and zero if they are equals or overlaps or one time period contains another.
*/
equals: function(that) {
if (!(that instanceof Subtitle)) throw Error('Cannot compare with element that does not belong to Subtitle type');
if (this.get('startTime') > that.get('endTime')) return 1;
else if (that.get('startTime') > this.get('endTime')) return -1;
else return 0;
},
/**
*
* @param moment moment for which we need to find a time period
* @returns {number} positive if {@code moment} belongs to time period greater than {@code this},
* negative if {@code moment} belongs to time period less than {@code this}
* and zero if the curect time period contain the {@code moment}.
*/
containMoment: function(moment) {
if (!Number.isInteger(moment)) throw Error('Moment should be an Integer');
if (moment >= this.get('startTime') && moment <= this.get('endTime')) return 0;
else if (moment < this.get('startTime')) return -1;
else if (moment > this.get('endTime')) return +1;
else throw Error('Impossible case :-)');
}
});
/**
* Collection
*/
var Subtitles = Backbone.Collection.extend({
model: Subtitle,
index: 0,
next: function() {
return this.at(this.index++);
},
getByMoment: function(moment) {
return this._binarySearch(this.toArray(), moment);
},
_binarySearch: function(array, moment) {
'use strict';
var minIndex = 0;
var maxIndex = array.length - 1;
var currentIndex;
var currentElement;
while (minIndex <= maxIndex) {
currentIndex = (minIndex + maxIndex) / 2 | 0;
currentElement = array[currentIndex];
if (currentElement.containMoment(moment) > 0) {
minIndex = currentIndex + 1;
}
else if (currentElement.containMoment(moment) < 0) {
maxIndex = currentIndex - 1;
}
else {
return array[currentIndex];
}
}
throw Error('No subtitle for this moment');
}
});
/**
* Test
*/
var data = [
{ id: '1',
startTime: 2468,
endTime: 4743,
text: 'Here\ little Ben nodding off.' },
{ id: '2',
startTime: 5389,
endTime: 7698,
text: 'Look at Aunt Monica\ Little boy.' },
{ id: '3',
startTime: 7948,
endTime: 11099,
text: '-Look, he\ got Ross\' hair cut.\n-Let me see.' },
{ id: '4',
startTime: 11948,
endTime: 14907,
text: 'Oh, God!\nIs he just the sweetest thing?' },
{ id: '5',
startTime: 15148,
endTime: 17946,
text: 'You must just want\nto kiss him all over.' }
];
var subtitles = new Subtitles();
subtitles.add(data);
var moment = 3000;
console.log(subtitles.next().attributes);
console.log(subtitles.next().attributes);
console.log(subtitles.next().attributes);
console.log(subtitles.next().attributes);
console.log(subtitles.getByMoment(moment).attributes);
+2
source to share