Caches

• LRU and MRU
  • Notes on implementation
• References

LRU and MRU

class Cache<T>(val type: Type, val size: Int) {
    val map = mutableMapOf<T, Int>()
    var rank = 0

    fun put(value: T): T? {
        var evictedKey: T? = null

        when {
            map.containsKey(value) -> {
                // Increase rank of existing value
                map[value] = rank++
            }
            map.size == size -> {
                // Remove the lowest rank item in the map
                evictedKey = findKeyToEvict()
                map.remove(evictedKey)
                map.put(value, rank++)
            }
            else -> {
                // Add the new item
                map.put(value, rank++)
            }
        }

        return evictedKey
    }

    /**
     * LRU means evict the item in the map w/ the lowest rank.
     * MRU means evict the item in the map w/ the highest rank.
     */
    fun findKeyToEvict(): T {
        var rankToEvict = map.values.first()
        var keyToEvict = map.keys.first()

        when (type) {
            Type.MRU -> {
                // Find the highest rank item
                for (entry in map) {
                    if (entry.value > rankToEvict) {
                        rankToEvict = entry.value
                        keyToEvict = entry.key
                    }
                }
            }
            Type.LRU -> {
                // Find the lowest rank item
                for (entry in map) {
                    if (entry.value < rankToEvict) {
                        rankToEvict = entry.value
                        keyToEvict = entry.key
                    }
                }
            }
        }

        return keyToEvict
    }
    
    override fun toString(): String = StringBuilder().apply {
        val list = mutableListOf<String>().apply {
            for (entry in map) 
                add("'${entry.key}'->rank=${entry.value}".yellow())
        }
        append(list.joinToString(", ", "{", "}"))
    }.toString()
}

Notes on implementation

• According to the LRU Algorithm, the lowest rank item will be removed when a new one is inserted and there's no space left in the cache. Also, every time an item is inserted into the cache it's rank is set to the highest rank.
• According to the MRU Algorithm, the highest rank item will be removed when a new one is inserted and there's no space left in the cache. Also, every time an item is inserted into the cache it's rank is set to the highest rank.

References

You can get more information on Cache replacement policies on wikipedia.