embracing-nondeterminism-code/src/main/scala/green/thisfieldwas/embracingnondeterminism/data/NonEmptyChain.scala

package green.thisfieldwas.embracingnondeterminism.data

/** A singly-linked list specialization optimized for constant-time
  * concatenation. This list, or "Chain", has a non-zero length which makes it
  * especially useful for cases where there is always at least one of some piece
  * of data.
  *
  * In the context of validation: as failures occur they must be gathered in a
  * way that is computationally cheap. Concatenation using this structure is a
  * constant-time operation, so large graphs of validation functions may fail
  * quickly without burdening the system with potentially large numbers of error
  * cases should they be produced in quantity. As validation failure implies a
  * non-zero presence of errors, this Chain structure represents one or more
  * values indicating reasons for failure.
  *
  * @tparam A
  *   The type of the values held within the chain.
  */
trait NonEmptyChain[+A] {

  import NonEmptyChain._

  /** The first value in the chain.
    *
    * @return
    *   The value.
    */
  def head: A

  /** All but the first value in the chain, if the chain has more than one
    * value.
    *
    * @return
    *   The rest of the chain
    */
  def tail: Option[NonEmptyChain[A]]

  /** The length of the chain, which is always non-zero.
    *
    * @return
    *   The length of the chain.
    */
  def length: Int

  /** Conses a value to the start of the chain.
    *
    * @param newHead
    *   The new start of the chain.
    * @tparam B
    *   The type of the head.
    * @return
    *   The new chain.
    */
  def cons[B >: A](newHead: B): NonEmptyChain[B] = prepend(Singleton(newHead))

  /** Prepends a chain to the start of this one.
    *
    * @param prefix
    *   The chain to prepend.
    * @tparam B
    *   The type of the chain.
    * @return
    *   The new chain.
    */
  def prepend[B >: A](prefix: NonEmptyChain[B]): NonEmptyChain[B] = prefix.append(this)

  /** Appends a chain to the end of this one.
    *
    * @param suffix
    *   The chain to append.
    * @tparam B
    *   The type of the chain.
    * @return
    *   The new chain.
    */
  def append[B >: A](suffix: NonEmptyChain[B]): NonEmptyChain[B] = Append(this, suffix)

  /** Converts the chain to a Scala Seq.
    *
    * @return
    *   The values in a Seq.
    */
  def toSeq: Seq[A] = head +: tail.fold(Seq[A]())(_.toSeq)

  override def equals(obj: Any): Boolean =
    if (!obj.isInstanceOf[NonEmptyChain[Any]]) {
      false
    } else {
      val other = obj.asInstanceOf[NonEmptyChain[Any]]
      toSeq == other.toSeq
    }

  override def hashCode(): Int =
    toSeq.foldLeft(7)((hash, value) => 31 * hash + value.hashCode())
}

object NonEmptyChain {

  import green.thisfieldwas.embracingnondeterminism.syntax.functor._

  /** Creates a `NonEmptyChain` using idiomatic syntax:
    *
    * {{{
    *   NonEmptyChain(1, 2, 3, ...)
    * }}}
    *
    * @param value
    *   The first, and required, value of the chain.
    * @param rest
    *   The rest, and optional, values of the chain.
    * @tparam A
    *   The type of the values.
    * @return
    *   The new chain.
    */
  def apply[A](value: A, rest: A*): NonEmptyChain[A] =
    rest.map[NonEmptyChain[A]](Singleton(_)).foldLeft[NonEmptyChain[A]](Singleton(value))(_ append _)

  /** Unapplies the chain for pattern matching. Allows idiomatic syntax:
    *
    * {{{
    *   nec match {
    *     case NonEmptyChain(1, 2, 3) => ???
    *   }
    * }}}
    *
    * @param chain
    *   The chain to unapply.
    * @tparam A
    *   The type of values in the chain.
    * @return
    *   A Some containing the Seq of values in the chain.
    */
  def unapply[A](chain: NonEmptyChain[A]): scala.Option[Seq[A]] =
    scala.Some(chain.toSeq)

  /** Represents the singleton case of the chain, where only one value exists.
    *
    * @param head
    *   The single value.
    * @tparam A
    *   The type of the values held within the chain.
    */
  case class Singleton[+A](head: A) extends NonEmptyChain[A] {

    override def tail: Option[NonEmptyChain[A]] = None

    override def length: Int = 1
  }

  /** The concatenation case of the chain. This represents the linkage between
    * two chains and is a constant-time encoding of the operation.
    *
    * @param prefix
    *   The left-hand side of the concatenated chain.
    * @param suffix
    *   The right-hand side of the concatenated chain.
    * @tparam A
    *   The type of the values held within the chain.
    */
  case class Append[+A](prefix: NonEmptyChain[A], suffix: NonEmptyChain[A]) extends NonEmptyChain[A] {

    override def head: A = prefix.head

    override def tail: Option[NonEmptyChain[A]] = prefix.tail.map(suffix.prepend).orElse(Some(suffix))

    override def length: Int = prefix.length + suffix.length
  }

  /** The Semigroup instance of the NonEmptyChain. This is a simple proxy over
    * the append() operation.
    *
    * @tparam A
    *   The type of the values held by the chain.
    * @return
    *   The Semigroup instance.
    */
  implicit def nonEmptyChainSemigroup[A]: Semigroup[NonEmptyChain[A]] = _ append _
}