ds.js

//设计一个类Time Traveling Hashtable，有以下方法： 
// void put(double t, String k, String v) 在某一时刻t以k为键v为值加入hashtable 
// String get(double t, String k) 对于k，获得某一时刻t之前（或相等）离t时间上最近的value
// void remove(double t, String k) 对于k，删除某一时刻t之前（或相等）离t时间上最近的value 

// 比如在如下操作之后 

// ht.put(1, "A", "X"); 
// ht.put((2, "A", "Y"); 
// ht.put(0, "A", "M"); 
// ht.get(1.5, "A"); 得到 "X"
// ht.get(2, "A"); 得到 "Y" 
// ht.remove(1.5, "A"); 删除X 

var output = 
  {'A' : [
    {time: 0, value: 1},
    {time: 1, value: 2},
  ],
  
  'B' : [
    {time: 0, value: 1},
    {time: 2, value: 2},
  ] 
  }

function Factory(){
  this.hash = {}
}
  
Factory.prototype.binarySearchIndex = function(time, key, isPut){
  var out = {
    found: false,
    index: -1
  }

  if(!this.hash.hasOwnProperty(key)) return out
  
  var start = 0
  var end = this.hash[key].length - 1
  
  while(start + 1 < end){
    var mid = Math.floor((start + end) / 2)
    var _time = this.hash[key][mid].time
    if( _time === time) {
      out.found = true
      out.index = mid
      return out
    }else if(_time > time){
      end = mid - 1
    }else start = mid + 1    
  }
  
  var sT = this.hash[key][start].time
  var eT = this.hash[key][end].time
  
  var index = -1
  index = sT === time ? start : index
  index = eT === time ? end : index
       
  if(index !== -1) out.found = true
  
  if(out.found || !isPut){
    out.index = index
    return out
  }else{

    if(sT > time) out.index = start
    else if(eT > time) out.index = end
    else out.index = end + 1
    return out
  }
}

Factory.prototype.get = function(time, key){
  var index = this.binarySearchIndex(time, key, false).index
  if(index === -1) return
  else return this.hash[key][index].value
}

Factory.prototype.delete = function(time, key){
  var index = this.binarySearchIndex(time, key, false).index
  if(index === -1) return
  else this.hash[key].splice(index, 1)
}

Factory.prototype.put = function(time, key, value){
  var result = this.binarySearchIndex(time, key, true)
  if(result.found){
    this.hash[key][result.index].value = value
  }else{
    if(!this.hash[key]) this.hash[key] = []
    insert(this.hash[key], result.index, {time: time, value: value})
  }
}

function insert(arr, index, obj){
  arr.splice(index, 0, obj);
}

var ht = new Factory();
ht.put(1, "A", "X"); 
ht.put(3, 'C', 'CC');
ht.put(3, 'A', 'AAA');
ht.put(1, "A", "XX"); 
ht.put(2, "A", "Y"); 
ht.put(0, "A", "M"); 
console.log(ht.hash)
// ht.get(1.5, "A"); //=>得到 "X" 
// ht.get(2, "A"); //=>得到 "Y" 
// ht.get(2, "B"); //=>得到 "YY" 
// ht.remove(1.5, "A"); //=>删除X