//
//  linkedlist.swift
//  CommandLinePlayground
//
//  Created by Michael Rockhold on 9/24/19.
//  Copyright © 2019 Michael Rockhold. All rights reserved.
//

import Foundation

indirect enum LinkedList<Value: Comparable> {

    enum LinkedListError : Error {
        case IndexOutOfRange
    }

    case Empty
    case List(LinkedList,Value)

    /** Initialize your data structure here. */
    init() {
        self = .Empty
    }

    private func _length(offset: Int) -> Int {
        if case let .List(next, _) = self {
            // this list is not empty
            return 1 + next._length(offset: offset+1)

        } else {
            // this list is empty
            return 0
        }
    }

    var length: Int {
        return _length(offset: 0)
    }

    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    func get(_ index: Int) throws -> Value {
        return try _get(index, offset: 0)
    }

    private func _get(_ index: Int, offset: Int) throws -> Value {

        if case let .List(next, value) = self {
            // this list is not empty
            return offset == index ? value : try next._get(index, offset: offset+1)

        } else {
            // this list is empty, return an error value
            throw LinkedListError.IndexOutOfRange
        }
    }

    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    mutating func addAtHead(_ val: Value) {

        if case .List(_, _) = self {
            // this list is not empty; make self a new list that points to current self as 'next'
            self = .List(self, val)

        } else {
            // this list is empty
            self = .List(.Empty, val)
        }
    }

    /** Append a node of value val to the last element of the linked list. */
    mutating func addAtTail(_ val: Value) {

        if case var .List(next, value) = self {
            // this list is not empty; append this new value to the 'next' list
            next.addAtTail(val)
            self = .List(next, value)

        } else {
            // this list is empty
            self = .List(.Empty, val)
        }
    }

    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    mutating func addAtIndex(_ index: Int, _ val: Value) {

        if case var .List(next, value) = self {
            // this list is not empty
            if index == 0 {
                addAtHead(val)
            } else {
                next.addAtIndex(index-1, val)
                self = .List(next, value)
            }

        } else {
            // this list is empty; if the index == 0, add this value here
            if index == 0 {
                self = .List(.Empty, val)
            } else {
                // this should raise an error
            }
        }
    }

    /** Delete the index-th node in the linked list, if the index is valid. */
    mutating func deleteAtIndex(_ index: Int) {

        if case var .List(next, value) = self {
            if index == 0 {
                self = next
            } else {
                next.deleteAtIndex(index - 1)
                self = .List(next, value)
            }
        } else {
            if index == 0 {
                self = .Empty
            } else {
                // this should raise an error, as the index is too big for this list
            }
        }
    }
}

class MyLinkedList {

    private var implList = LinkedList<Int>()

    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    func get(_ index: Int) -> Int {
        do {
            return try implList.get(index)
        } catch {
            return -1
        }
    }

    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    func addAtHead(_ val: Int) {
        implList.addAtHead(val)
    }

    /** Append a node of value val to the last element of the linked list. */
    func addAtTail(_ val: Int) {
        implList.addAtTail(val)
    }

    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    func addAtIndex(_ index: Int, _ val: Int) {
        implList.addAtIndex(index, val)
    }

    /** Delete the index-th node in the linked list, if the index is valid. */
    func deleteAtIndex(_ index: Int) {
        implList.deleteAtIndex(index)
    }
}




func test_linkedlist() {

    var list = LinkedList<Int>()

    let ret_1: Int
    do {
        ret_1 = try list.get(0)
    } catch {
        ret_1 = -1
    }

    print(ret_1 == -1)
    print(list.length == 0)

    list.addAtHead(7)
    do {
        print(try list.get(0) == 7)
    } catch {
        print("false")
    }
    print(list.length == 1)

    list.addAtTail(5)
    print(list.length == 2)

    list.addAtIndex(1, 3)
    print(list.length == 3)

    list.deleteAtIndex(1)
    print(list.length == 2)
}