rate_limit2.js

// 实现两个函数addorupdate()和recentevents(limit), 
// 就是类似lru cache，第一个函数是加入或者更新一个事件，
// 然后第二个函数返回limit个最近加入或访问的事件。

function DataStructure(){
  this.hash = {}
  this.dummyHead = new Dbll(null)
  this.dummyTail = new Dbll(null)
  this.dummyHead.next = this.dummyTail
  this.dummyTail.pre = this.dummyHead
}

function Dbll(val){
  this.val = val
  this.pre = null
  this.next = null
}

DataStructure.prototype.removeNode = function(node){  
  node.pre.next = node.next  
  node.next.pre = node.pre
}

DataStructure.prototype.setTail = function(node){
  node.pre = this.dummyTail.pre
  node.next = this.dummyTail
  this.dummyTail.pre.next = node
  this.dummyTail.pre = node
}

DataStructure.prototype.add = function(obj){
  var key = Object.keys(obj)[0]
  var value = obj[key]
  
  if(this.hash.hasOwnProperty(key)){
    var node = this.hash[key]
    this.removeNode(node)

  }else{
    node = new Dbll(value)
    this.hash[key] = node
  }
  
  this.setTail(node)
  node.val = value
  
}


DataStructure.prototype.getRecents = function(limit){
  //limit
  var result = []
  var tmp = this.dummyTail.pre
  while(limit-- && tmp !== null){
    result.push(tmp.val)
    tmp = tmp.pre
  }
  return result
}

//dblinkedilist => add/update 
 // - tail
 // - remove + tail 
//this.tail

//hash
//same key

var ds = new DataStructure()
ds.add({'xx': 'yy'})

console.log(node)

ds.add({'xx': 'dd'})
ds.add({'bb': '2'})
ds.add({'cc': 0})
console.log(ds.getRecents(3)) //=> // ['dd', '2', 0]


ds.add({'1': '2'})
console.log(ds.getRecents(3)) //=> // ['2', 0, '2']