Clever Geek Handbook

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 there neededTime

    could be something between attributes startTime

    and endTime

    (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






More articles:


All Articles