Jump To …

StackList.coffee

@private This class provides nodes for StackList. It is only data container.

 
class StackListNode

@private

 
  key: undefined

@private

 
  value: undefined

@private

 
  prev: undefined

@private

 
  next: undefined

  constructor: (@key, @value, @prev, @next) ->

This class provides data structure with some features of both stack and list. Class is used in implementation of LRU cache.

 
class StackList

@private

 
  limit: undefined

@private

 
  length: undefined

@private

 
  head: undefined

@private

 
  tail: undefined

@private

 
  map: undefined

Constructor. Head is null element. Data starts from head.next. Tail is the same as top. Map is used for rapid access to nodes by keys.

@param limit max number of elements that can be holded in list.

 
  constructor: (@limit) ->
    @head = new StackListNode undefined, undefined, undefined, undefined
    @tail = @head
    @length = 0
    @map = new Object()

@private Removes node from list.

@param node the node to be deleted.

 
  remove: (node) ->
    @map[node.key] = undefined
    node.prev.next = node.next
    if node.next != undefined
      node.next.prev = node.prev
    else
      @tail = node.prev
    @length -= 1

Push element to list top. If there is no more space, we delete the least recently used element - that is element in the bottom of stack (i.e. head of list).

@param key the key to push. @param value the value to push.

 
  push: (key, value) ->
    if @length >= @limit
      @remove @head.next
    node = new StackListNode key, value, @tail, undefined
    @tail.next = node
    @tail = node
    @length += 1
    @map[key] = @tail

Moves element to top of stack. This means that we have just used it, so that it won't be removed soon.

@param key the key of the node to be moved.

 
  moveToTop: (key) ->
    node = @map[key]
    if node != undefined
      value = node.value
      @remove node
      @push key, value

Gets data from list by key.

@param key to key of the data to be got. @return value or undefined if there is no such key in list.

 
  get: (key) ->
    if @map[key] != undefined
      return @map[key].value
    else
      return undefined

Gets key of the bottom element (it will be removed next if necessary).

@return the key.

 
  bottomKey: () ->
    return @head.next.key

exports.StackList = StackList