import org.scalatest.{Matchers, WordSpec}

import scala.annotation.tailrec

/**
  * 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.
  *
  * Assumptions: both list has equal number of nodes
  *
  * for example (7-> 1 -> 6->Nil) + (5-> 9 -> 2-> Nil).That is,617 + 295 = 912
  * output will be : 9->1->2-Nil return new linklist
  * time complexity O(n+n)
  * space complexity O(n) //new linklist
  *
  * Created by Arun Sethia on 7/22/18.
  */
trait Linklist {

  /**
    * abstract Node
    */
  abstract class AbstractNode {
    def data: Int

    def next: AbstractNode
  }

  /**
    * Nil Node to indicate end of link list
    */
  object NilNode extends AbstractNode {
    def data = 0

    override def toString() = s"Nil"

    def next = throw new UnsupportedOperationException("tail of empty list")
  }

  /**
    * Node class
    *
    * @param data
    * @param next
    */
  case class Node(data: Int, next: AbstractNode) extends AbstractNode {
    override def toString() = s"data: ${data} next: ${next}"
  }

  /**
    * add new node in the beginning
    *
    * @param prevNode
    */
  implicit class NodeAddItem(prevNode: AbstractNode) {

    def prependItem(v: Int): AbstractNode = Node(v, prevNode)

    /**
      * prepand node2 with prevNode
      *
      * @param node2
      * @return
      */
    def prepand(node2: AbstractNode): AbstractNode = {
      if (node2.next != NilNode) prepand(node2.next).prepand(Node(node2.data, NilNode))
      else Node(node2.data, prevNode)
    }
  }


  /**
    * sum two linklist nodes and create new linklist
    * for example (7-> 1 -> 6->Nil) + (5-> 9 -> 2-> Nil).That is,617 + 295 = 912
    * output will be : 9->1->2-Nil
    *
    * @param node1
    * @param node2
    * @return
    */
  def addSumList(node1: AbstractNode, node2: AbstractNode): AbstractNode = {
    @tailrec
    def sumList(node1: AbstractNode, node2: AbstractNode, finalNode: AbstractNode, carryOver: Int): AbstractNode = {
      if (node1.next != NilNode && node2.next != NilNode) {
        val (data, newcarryOver) = getSumReminder(node1.data, node2.data, carryOver)
        val node = finalNode.prepand(Node(data, NilNode))
        sumList(node1.next, node2.next, node, newcarryOver)
      } else {
        val (data, newcarryOver) = getSumReminder(node1.data, node2.data, carryOver)
        val tmpNode = finalNode.prependItem(data)
        //add carryover for final result
        if (newcarryOver > 0)
          tmpNode.prependItem(newcarryOver)
        else tmpNode //don't add carryover for final result
      }
    }
    sumList(node1, node2, NilNode, 0)
  }

  /**
    * get sum all number and get sum and carryon for given numbers
    *
    * @return
    */
  private def getSumReminder(d: Int*): (Int, Int) = {
    val sum = d.sum
    val data = (sum % 10)
    val nextCarryon = sum / 10
    (data, nextCarryon)
  }

}

/**
  * test cases for sumList
  */
class LinkSumListSpec extends WordSpec
  with Matchers
  with Linklist {

  "(7-> 1 -> 6->Nil) + (5-> 9 -> 2-> Nil)" should {
    "return 9->1->2-Nil" in {
      val node1 = Node(7, Node(1, Node(6, NilNode)))
      val node2 = Node(5, Node(9, Node(2, NilNode)))
      val result = Node(9, Node(1, Node(2, NilNode)))
      assert(addSumList(node1, node2) == result)
    }
  }

  "(9-> 8 -> 7-> 6-> Nil) + (9-> 8 -> 7-> 6-> Nil)" should {
    "return 1->3->5->7->8->Nil" in {
      val node1 = Node(9, Node(8, Node(7, Node(6, NilNode))))
      val node2 = Node(9, Node(8, Node(7, Node(6, NilNode))))
      val result = Node(1,Node(3, Node(5, Node(7, Node(8, NilNode)))))
      assert(addSumList(node1, node2) == result)
    }
  }

}