Introduction

This tutorial is part of a collection tutorials on basic data structures and algorithms that are created using Kotlin. This project is useful if you are trying to get more fluency in Kotlin or need a refresher to do interview prep for software engineering roles.

How to run this project

You can get the code for this and all the other tutorials in this collection from this github repo. Here’s a screen capture of project in this repo in action.

Once you’ve cloned the repo, type gradle run in order to build and run this project on the command line.

Importing this project into Jetbrains IntelliJ IDEA

  • This project was created using Jetbrains Idea as a Gradle and Kotlin project (more info).
    • When you import this project into Idea as a Gradle project, make sure not to check “Offline work” (which if checked, won’t allow the gradle dependencies to be downloaded).
    • As of Jun 24 2018, Java 10 doesn’t work w/ this gradle distribution (v4.4.x), so you can use Java 9 or 8, or upgrade to a newer version of gradle (4.8+).

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.

Resources

CS Fundamentals

Data Structures

Math

Big-O Notation

Kotlin

Markdown utilities

Related Posts