lru-cache.coffee

class LRUCache
    constructor: (size_limit) ->
        @limit = size_limit or Infinity
        @data  = {}
        @size  = 0
        @order = []
    set: (key, val) ->
        @data[key] = val
        @size++
        @order.push key
        if @size > @limit
            @order.splice 0, 1
            delete @data[@order[0]]
            @size-- 
    get: (key) ->
        for item, index in @order
            if item is key
                @order.splice index, 1
                @order.push key
        @data[key]

note splice is not O(1) t is O(n) , see here http://stackoverflow.com/questions/11514308/big-o-of-javascript-arrays
javascript arrays O -

• Access - O(1)
• Appending - Amortized O(1) (sometimes resizing the hashtable is required; usually only insertion is required)
• Prepending - O(n) via unshift, since it requires reassigning all the indexes
• Insertion - Amortized O(1) if the value does not exist. O(n) if you want to shift existing values (Eg, using splice).
• Deletion - Amortized O(1) to remove a value, O(n) if you want to reassign indices via splice.
• Swapping - O(1)