javascript - 主干集合 : iterate & search effectively

Question

我有什么:我正在编写我的非常普通的媒体播放器。所以在其中的某个地方我收集了字幕(假设每部电影大约有 2000 个)。所以每个字幕看起来像:

Object {
  id: "1"
  startTime: 2468
  endTime: 4743
  text: "Test subtitle."
}

我想:非常有效地做两件事:

1. .next() 方法应该让我得到下一个字幕。
2. .getByTime(neededTime) 以有效的方式对整个字幕集合进行二进制搜索。重点是 neededTime 可能介于 startTime 和 endTime 属性之间(即 3000)。

问题:我要为我的字幕使用 Backbone 集合，但它如何处理这两个要求？我的意思是也许手动实现迭代器模式和二进制搜索会更好？

Answer 1

不知道这是否是最好的解决方案，但我以:

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\'s little Ben nodding off.' },
  { id: '2',
    startTime: 5389,
    endTime: 7698,
    text: 'Look at Aunt Monica\'s Little boy.' },
  { id: '3',
    startTime: 7948,
    endTime: 11099,
    text: '-Look, he\'s 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);