import UIKit

//Linked lists are composed of Node(s)
class Node<T> {
    var value: T
    var next: Node?
    weak var prev: Node?

    init(value: T) {
        self.value = value
    }
}

extension Node: Equatable, Hashable {
    static func == (lhs: Node<T>, rhs: Node<T>) -> Bool {
        return
            lhs.next == rhs.next
    }

    func hash(into hasher: inout Hasher) {
        hasher.combine(next)
        hasher.combine(prev)
    }
}

class LinkedList<T> {
    var head: Node<T>?
    var tail: Node<T>?
    //starts at 1 because a linked list must have at least 1 node
    var nodeCount = 1

    init(head: Node<T>?) {
        self.head = head
    }

    func append(node: Node<T>) {
        //check if head exists
        guard head != nil else {
            head = node
            return
        }
        var current = head
        // loop through nodes
        while let _ = current?.next {
            //set current to next node
            current = current?.next
        }
        node.prev = current
        current?.next = node
        //set last node's `next` to given node
        tail = node
        nodeCount += 1
    }

    func removeNode(node: Node<T>) {
        let prev = node.prev
        let next = node.next

        next?.prev = prev
        prev?.next = next

        // if head node being removed
        if prev == nil {
            head = next
        }
    }

    func insertNode(node: Node<T>, position: Int) {
        var currentNode = head
        var currentPosition = 0

        //loop through nodes, starts at head node
        while let _ = currentNode?.next {
            if currentPosition == position {
                if let prevNode = currentNode?.prev {
                    currentNode?.prev = node
                    prevNode.next = node
                    node.next = currentNode
                } else {
                    //if head node
                    currentNode?.prev = node
                    node.next = currentNode
                    head = node
                }
                return
            }
            currentNode = currentNode?.next
            currentPosition += 1
            // nothing happens if requested position doesn't exist in Linked list
        }
    }
}

//1,2,3
let node0 = Node(value: 0)
let node1 = Node(value: 1)
let node2 = Node(value: 2)
let node3 = Node(value: 3)

let linkedList = LinkedList(head: node0)
linkedList.append(node: node1)
linkedList.append(node: node2)
linkedList.append(node: node3)
linkedList.append(node: Node.init(value: 5))
linkedList.append(node: Node.init(value: 8))
linkedList.append(node: Node.init(value: 8))
linkedList.append(node: Node.init(value: 8))
linkedList.append(node: Node.init(value: 9))
//linkedList.removeNode(node: node0)
//linkedList.insertNode(node: Node(value: 7), position: 1)

//2.1
//Remove Dups: Write code to remove duplicates from an unsorted linked list.
func removeDupes(LL: LinkedList<Int>) -> LinkedList<Int> {
    let linkedList = LL
    var storedInts = Set<Int>()
    var currentNode = linkedList.head

    while let _ = currentNode {
        guard let unwrappedCurrentNode = currentNode else {
            return linkedList
        }

        if !storedInts.contains(unwrappedCurrentNode.value) {
            storedInts.insert(unwrappedCurrentNode.value)
        } else {
            // remove duplicate node
            linkedList.removeNode(node: unwrappedCurrentNode)
        }
        currentNode = currentNode?.next
    }
    // for visualizing purposes
    dump(linkedList)
    return linkedList
}// loop through 1x 0(n^2) w/o req additional memory, loop through whole list each time while checking for value
//removeDupes(LL: linkedList)

//Q 2.2
//Return Kth to Last: Implement an algorithm to find the kth to last element of a singly linked list.
//Hints: #8, #25, #47, #67, # 726
func returnKthToLast(linkedList: LinkedList<Int>, position: Int) -> Int? {
    // if position doesn't exist
    if position < 0 || position > (linkedList.nodeCount - 1) {
        return nil
    }
    // negative number or number that is > count
    var currentNode = linkedList.tail
    var currentPosition = 0
    //store currentPosition
    //iterate bacwards till current position == position
    while currentPosition != position {
        currentNode = currentNode?.prev
        currentPosition += 1
    }
    dump(linkedList)
    return currentNode?.value
}
//returnKthToLast(linkedList: linkedList, position: 4)
//returnKthToLast(linkedList: linkedList, position: 0)
//returnKthToLast(linkedList: linkedList, position: 50)
//linkedList.nodeCount

//2.5 Sum Lists: You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list. (2 linked lists are passed in)
//EXAMPLE
//Input: (7-) 1 -) 6) + (5 -) 9 -) 2).Thatis,617 + 295. Output: 2 -) 1 -) 9.That is, 912.

func sumList(linkedList1: LinkedList<Int>, linkedList2: LinkedList<Int>) -> LinkedList<Int> {
    var currentNodeLL1 = linkedList1.head
    var currentNodeLL2 = linkedList2.head
    var greaterThan10 = false
    var total = 0
    var newLinkedList = LinkedList<Int>(head: nil)

    //iterate through both linked lists
    while let _ = currentNodeLL1, let _ = currentNodeLL2 {
        total = (currentNodeLL1?.value ?? 0) + (currentNodeLL2?.value ?? 0) + (greaterThan10 ? 1 : 0)

        if total >= 10 {
            greaterThan10 = true
            total = total % 10
        } else {
            greaterThan10 = false
        }
        //create new node with each total
        let node = Node(value: total)
        if newLinkedList.head == nil {
            newLinkedList.head = node
        } else {
            newLinkedList.append(node: node)
            if currentNodeLL1 == linkedList1.tail && greaterThan10 {
                newLinkedList.append(node: Node(value: 1))
            }
        }
        currentNodeLL1 = currentNodeLL1?.next
        currentNodeLL2 = currentNodeLL2?.next
    }
    dump(newLinkedList)
    return newLinkedList
}

let sumListNode1 = Node(value: 9)
let sumListNode2 = Node(value: 2)
let sumListNode3 = Node(value: 2)
let sumListNode4 = Node(value: 2)
let sumListNode5 = Node(value: 2)
let sumListNode6 = Node(value: 9)
let sumListTestLL1 = LinkedList(head: sumListNode1)
sumListTestLL1.append(node: sumListNode2)
sumListTestLL1.append(node: sumListNode3)

let sumListTestLL2 = LinkedList(head: sumListNode4)
sumListTestLL2.append(node: sumListNode5)
sumListTestLL2.append(node: sumListNode6)

//sumList(linkedList1: sumListTestLL1, linkedList2: sumListTestLL2)

//2.6 Palindrome: Implement a function to check if a linked list is a palindrome.
//Hints: #5, #13, #29, #61, #101
//input LL
//output Bool
func isLinkedListPalindrome(LL: LinkedList<Int>) -> Bool {
    // reverse LL & compare to the passed in LL
    // store inputCurrentNode
    var currentFrontNode = LL.head
    //store currentReversedNode
    var currentBackNode = LL.tail
    // traverse LL from both ends in opp directions at the same time, input from the head, reversed starting from the tail
    while let _ = currentFrontNode, let _ = currentBackNode{
        // if node value is !=, return false
        if currentFrontNode?.value != currentBackNode?.value {
            return false
        }
        currentFrontNode = currentFrontNode?.next
        currentBackNode = currentBackNode?.prev
    }
    return true
}

let palinListNode1 = Node(value: 1)
let palinListNode2 = Node(value: 1)
let palinListNode3 = Node(value: 0)
//let palinListNode4 = Node(value: 1)

let palinListTestLL1 = LinkedList(head: palinListNode1)
let palinListTestLL2 = LinkedList(head: palinListNode2)

palinListTestLL1.append(node: palinListNode3)
palinListTestLL2.append(node: palinListNode3)
//palinListTestLL1.append(node: palinListNode4)

//isLinkedListPalindrome(LL: palinListTestLL1)
palinListTestLL1.head?.next == palinListTestLL2.head?.next

//2.7 Intersection: Given two (singly) linked lists, determine if the two lists intersect. Return the inter- secting node. Note that the intersection is defined based on reference, not value. That is, if the kth node of the first linked list is the exact same node (by reference) as the jth node of the second linked list, then they are intersecting.
//Hints: #20, #45, #55, #65, #76, #93, #111, #120, #129

func areLinkedListsIntersecting(LL1: LinkedList<Int>, LL2: LinkedList<Int>) -> Node<Int>? {
    //store current nodes in both LL
    var currentLL1Node = LL1.head
    var currentLL2Node = LL2.head

    //traverse both LL at the same time
    while let _ = currentLL1Node, let _ = currentLL2Node {
    // if the .next node is the same(made Node class conform to equatable above), return node
        if currentLL1Node?.next == currentLL2Node?.next {
            // for visualizing node value purposes
            dump(currentLL1Node?.next?.value,name:"intersecting node value")
            return currentLL1Node?.next
        }
        currentLL1Node = currentLL1Node?.next
        currentLL2Node = currentLL2Node?.next
    }
    return nil
}
//areLinkedListsIntersecting(LL1: palinListTestLL1, LL2: palinListTestLL2)

//2.8 Loop Detection: Given a circular linked list, implement an algorithm that returns the node at the beginning of the loop.
//DEFINI TION
//Circular linked list: A (corrupt) linked list in which a node's next pointer points to an earlier node, so as to make a loop in the linked list.
//EXAMPLE
//Input: A -) B -) C -) 0 -) E -) C[the same C as earlier] Output: C
//Hints: #50, #69, #83, #90

func loopDetection(LL: LinkedList<Int>) -> Node<Int>? {
    //traverse through list
    // store currentNode
    var currentNode = LL.head
    //set to keep track of what i've seen
    var seenNodes = Set<Node<Int>>()
    while let unwrappedCurrentNode = currentNode { // instead of .next, confirm should cover last node
        // if node.next ! in the set, add it else return the node.next
        if !seenNodes.contains(unwrappedCurrentNode) {
            seenNodes.insert(unwrappedCurrentNode)
        } else {
            return currentNode
        }
        currentNode = currentNode?.next
    }
    return nil
}

//loopDetection(LL: palinListTestLL1)