LinkedLisk

package linkedlist

sealed class Option<out T> {
    data class Some<T>(val unwrappedValue: T): Option<T>()
    object None: Option<Nothing>()
}

data class Node<T>(val value: T, val next: LinkedList<T>)

class LinkedList<T>(private var head: Option<Node<T>>) : Collection<T> {
    constructor() : this(Option.None)

    override var size: Int = 0

    override fun isEmpty(): Boolean = this.head is Option.None

    override fun iterator(): Iterator<T> = IteratorImpl()

    override fun containsAll(elements: Collection<T>): Boolean {
        TODO("Not yet implemented")
    }

    override fun contains(element: T): Boolean {
        TODO("Not yet implemented")
    }

    fun addToFront(data: T): LinkedList<T> {
        val t = this.head // Either Some or None
        head = Option.Some(Node(data, LinkedList(t)))
        size++
        return this
    }

    fun addToBack(data: T, list: LinkedList<T> = this): LinkedList<T> {
        when(val iter = list.head) {
            is Option.Some -> list.addToBack(data, iter.unwrappedValue.next)
            is Option.None -> list.head = Option.Some(Node(data, LinkedList())) // OR call this.addToFront(..)
        }
        size++
        return this
    }

    fun get(index: Int): T {
        return when(val result = getNode(index)) {
            is Option.Some -> result.unwrappedValue.value
            is Option.None -> throw IndexOutOfBoundsException("index: $index is out of bounds")
        }
    }

    tailrec fun print(curr: Option<Node<T>> = this.head) {
        when(curr) {
            is Option.Some -> {
                print(curr.unwrappedValue.value)
                if (curr.unwrappedValue.next.head !is Option.None)
                    print("->")
                this.print(curr.unwrappedValue.next.head)
            }
            is Option.None -> return
        }
    }


    private fun getNode(index: Int): Option<Node<T>> {
        var current = this.head
        var currentIndex = index

        while (currentIndex > 0) {
            current = when (current) {
                is Option.Some -> current.unwrappedValue.next.head
                is Option.None -> return Option.None
            }
            currentIndex--
        }

        return current
    }

    private open inner class IteratorImpl : Iterator<T> {
        /** the index of the item that will be returned on the next call to [next]`()` */
        protected var index = 0

        override fun hasNext(): Boolean = index < size

        override fun next(): T {
            if (!hasNext()) throw NoSuchElementException()
            return get(index++)
        }
    }
}