MinStack.kt

README.md

MinStack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

MinStack.kt

package dev.kioba.minstack

sealed class MinStack<out A> {
    companion object
}

object Nil : MinStack<Nothing>()
class Cons<A>(val head: A, val min: A, val tail: MinStack<A> = Nil) : MinStack<A>()

operator fun <A> MinStack.Companion.invoke(): MinStack<A> = Nil

fun <A> MinStack<A>.push(
    value: A
): Cons<A> where A : Comparable<A> =
    when (val it = this) {
        is Nil -> value
        is Cons -> if (value < it.min) value else it.min
    }.let {
        Cons(
            head = value,
            min = it,
            tail = this
        )
    }

fun <A> MinStack<A>.pop(): MinStack<A> =
    when (val it = this) {
        is Nil -> this
        is Cons -> it.tail
    }

fun <A> MinStack<A>.getMin(): A? =
    when (val it = this) {
        is Nil -> null
        is Cons -> it.min
    }

fun <A> MinStack<A>.top(): A? =
    when (val it = this) {
        is Nil -> null
        is Cons -> it.head
    }

fun <A, B> MinStack<A>.fold(
    initial: B,
    f: (A, B) -> B
): B =
    when (val it = this) {
        is Nil -> initial
        is Cons -> it.tail.fold(f(it.head, initial), f)
    }

fun <A> MinStack<A>.toList(): List<A> =
    fold(mutableListOf(), { a, b -> b.add(a); b })

MinStackTest.kt

package dev.kioba.minstack

import org.junit.Assert.assertEquals
import org.junit.Test

class MinStackTest {
    @Test
    fun test_creation() {
        val minStack = MinStack<Int>()
        assert(minStack is Nil)
    }

    @Test
    fun testPush() {
        val minStack: MinStack<Int> = MinStack<Int>()
            .push(-2)
            .push(0)
            .push(-3)

        assertEquals(minStack.toList(), listOf(-3, 0, -2))
    }

    @Test
    fun testMin() {
        val minStack: Int? = MinStack<Int>()
            .push(-2)
            .push(0)
            .push(-3)
            .getMin()

        assertEquals(minStack, -3)
    }

    @Test
    fun testPop() {
        val minStack: MinStack<Int> = MinStack<Int>()
            .push(-2)
            .push(0)
            .push(-3)
            .pop()

        assertEquals(minStack.toList(), listOf(0, -2))
    }

    @Test
    fun testTop() {
        val minStack: Int? = MinStack<Int>()
            .push(-2)
            .push(0)
            .push(-3)
            .pop()
            .top()

        assertEquals(minStack, 0)
    }

    @Test
    fun testSecondMin() {
        val minStack: Int? = MinStack<Int>()
            .push(-2)
            .push(0)
            .push(-3)
            .pop()
            .getMin()

        assertEquals(minStack, -2)
    }

    @Test
    fun testExtra() {
        val minStack: Int? = MinStack<Int>()
            .push(-3)
            .push(-2)
            .push(0)
            .pop()
            .push(-5)
            .push(1)
            .getMin()

        assertEquals(minStack, -5)
    }
}