package java2scala.homeworks

sealed trait LinkedMap[K, V] extends Traversable[(K, V)] {

  /** должен вернуть `false` если коллекция содержит хотя бы один элемент */
  override def isEmpty: Boolean = this match {
    case LinkedMap.Empty() => true
    case _                 => false
  }

  /** должен вернуть `true` если коллекция содержит ключ `key` */
  def contains(key: K): Boolean = this match {
    case LinkedMap.Empty()          => false
    case LinkedMap.Cons(k, _, rest) =>
      if (k == key) true
      else rest.contains(key)
  }

  /** возвращает Some со значением значения, если коллекция содержит ключ `key`
    * и None если не содержит */
  def apply(key: K): Option[V] = this match {
    case LinkedMap.Empty()          => None
    case LinkedMap.Cons(k, v, rest) =>
      if (k == key) Some(v)
      else rest.apply(key)
  }

  /** возвращает новый LinkedMap[K, V],
    * в котором добавлено или изменено значение для ключа `key` на `value` */
  def update(key: K, value: V): LinkedMap[K, V] = {
    def go(lm: LinkedMap[K, V], acc: LinkedMap[K, V]): LinkedMap[K, V] = lm match {
      case LinkedMap.Empty()          => acc.reverse
      case LinkedMap.Cons(k, v, rest) =>
        if (k == key) go(rest, LinkedMap.Cons(k, value, acc))
        else go(rest, LinkedMap.Cons(k, v, acc))
    }

    if (this.contains(key)) go(this, LinkedMap.Empty())
    else LinkedMap.Cons(key, value, this)
  }

  /** возвращает новый LinkedMap[K, V]
    * состоящий из тех же позиций, но в обратном порядке */
  def reverse: LinkedMap[K, V] = {
    def go(lm: LinkedMap[K, V], acc: LinkedMap[K, V]): LinkedMap[K, V] = lm match {
      case LinkedMap.Empty()          => acc
      case LinkedMap.Cons(k, v, rest) => go(rest, LinkedMap.Cons(k, v, acc))
    }

    go(this, LinkedMap.Empty())
  }

  /** создаёт новый LinkedMap, состоящий из элементов `this` и `other`
    * если какой-то ключ встречается в обеих коллекциях,
    * может быть выбрано любое значение*/
  def ++(other: LinkedMap[K, V]): LinkedMap[K, V] = {
    def go(lml: LinkedMap[K, V], lmr: LinkedMap[K, V]): LinkedMap[K, V] = lml match {
      case LinkedMap.Empty()          => lmr
      case LinkedMap.Cons(k, v, rest) =>
        if (lmr.contains(k)) go(rest, lmr)
        else go(rest, LinkedMap.Cons(k, v, lmr))
    }

    go(this, other)
  }

  /** создаёт новый LinkedMap , где ко всем значениям применена заданная функция */
  def mapValues[W](f: V => W): LinkedMap[K, W] = {
    def go(lm: LinkedMap[K, V], acc: LinkedMap[K, W]): LinkedMap[K, W] = lm match {
      case LinkedMap.Empty()          => acc.reverse
      case LinkedMap.Cons(k, v, rest) => go(rest, LinkedMap.Cons(k, f(v), acc))
    }

    go(this, LinkedMap.Empty())
  }

  /** создаёт новый LinkedMap , где ко всем значениям применена заданная функция,
    * учитывающая ключ*/
  def mapWithKey[W](f: (K, V) => W): LinkedMap[K, W] = {
    def go(lm: LinkedMap[K, V], acc: LinkedMap[K, W]): LinkedMap[K, W] = lm match {
      case LinkedMap.Empty()          => acc.reverse
      case LinkedMap.Cons(k, v, rest) => go(rest, LinkedMap.Cons(k, f(k, v), acc))
    }

    go(this, LinkedMap.Empty())
  }

  /** конструирует новый LinkedMap, содеоржащий все записи текущего, кроме заданного ключа */
  def delete(key: K): LinkedMap[K, V] = {
    def go(lm: LinkedMap[K, V], acc: LinkedMap[K, V]): LinkedMap[K, V] = lm match {
      case LinkedMap.Empty()          => acc.reverse
      case LinkedMap.Cons(k, v, rest) =>
        if (k == key) go(rest, acc)
        else go(rest, LinkedMap.Cons(k, v, acc))
    }

    go(this, LinkedMap.Empty())
  }

  /** применяет действие `action` с побочным эффектом ко всем элементам коллекции */
  def foreach[U](action: ((K, V)) => U): Unit = this match {
    case LinkedMap.Empty()          => ()
    case LinkedMap.Cons(k, v, rest) =>
      action(k, v)
      rest.foreach(action)
  }
}

object LinkedMap {

  /** конструирует новый `LinkedMap` на основании приведённых элементов
    * каждый ключ должен присутствовать в результате только один раз
    * если в исходных данныхх ключ встречается несколько раз, может быть
    * выбрано любое из значений
    */
  def apply[K, V](kvs: (K, V)*): LinkedMap[K, V] = {
    def go(KVSeq: Seq[(K, V)], acc: LinkedMap[K, V]): LinkedMap[K, V] = KVSeq match {
      case Seq()          => acc
      case (k, v) +: tail =>
        if (acc.contains(k)) go(tail, acc)
        else go(tail, LinkedMap.Cons(k, v, acc))
    }

    go(kvs, Empty())
  }

  final case class Cons[K, V](key: K, value: V, rest: LinkedMap[K, V]) extends LinkedMap[K, V]
  final case class Empty[K, V]()                                       extends LinkedMap[K, V]
}