A queue with an inner queue to stage appends

TurtlesQ.scala

  sealed trait TurtlesQ[A] {

    import TurtlesQ._

    // fixme: size is being calculated incorrecty for append nodes
    def size: Int

    def conswise: TurtlesQ[A]

    def snocwise: TurtlesQ[A]

    def isEmpty: Boolean

    // note: when appending, never tosnoc or tocons anything -- we want to attempt to .reverse to the last moment
    def ++(rhs: TurtlesQ[A]): TurtlesQ[A]

    def :+(a: A): NonEmpty[A]

    def +:(a: A): NonEmpty[A]

    def headTail: Option[(A, TurtlesQ[A])]

    def firstLast: Option[(TurtlesQ[A], A)]

    def map[B](f: A => B): TurtlesQ[B]

    def fold[B](zero: B)(f: (B, A) => B): B
  }


  object TurtlesQ {
    val tnil = TNil[Nothing]()

    def empty[A]: Empty[A] = tnil.asInstanceOf[Empty[A]] // hack

    sealed trait Empty[A] extends TurtlesQ[A] with ConsOrEmpty[A] with SnocOrEmpty[A] {
      final override def isEmpty: Boolean = true
    }

    sealed trait NonEmpty[A] extends TurtlesQ[A] {
      final override def isEmpty: Boolean = false

      final override def headTail: Some[(A, TurtlesQ[A])] = Some(headTailNonEmpty)

      final override def firstLast: Some[(TurtlesQ[A], A)] = Some(firstLastNonEmpty)

      final override def ++(rhs: TurtlesQ[A]): NonEmpty[A] = rhs match {
        case TNil() => this
        case r: NonEmpty[A] => this +:+ r
      }

      def +:+(rhs: NonEmpty[A]): NonEmpty[A]

      def headTailNonEmpty: (A, TurtlesQ[A])

      def firstLastNonEmpty: (TurtlesQ[A], A)

      override def conswise: NonEmpty[A]

      override def snocwise: NonEmpty[A]

      override def map[B](f: A => B): NonEmpty[B]
    }

    sealed trait ConsOrSnoc[A] extends TurtlesQ[A]

    sealed trait ConsOrEmpty[A] extends TurtlesQ[A]

    sealed trait SnocOrEmpty[A] extends TurtlesQ[A]

    case class TNil[A]() extends Empty[A] {

      override def size = 0

      override def conswise: TNil[A] = this

      override def snocwise: TNil[A] = this

      override def ++(rhs: TurtlesQ[A]): TurtlesQ[A] = rhs

      override def :+(a: A): Snoc[A] = Snoc(Nil, a)

      override def +:(a: A): Cons[A] = Cons(a, Nil)

      override def headTail: None.type = None

      override def firstLast: None.type = None

      override def map[B](f: A => B): TNil[B] = tnil.asInstanceOf[TNil[B]]

      override def fold[B](zero: B)(f: (B, A) => B): B = zero
    }

    case class Cons[A](head: A, tails: List[A]) extends NonEmpty[A] with ConsOrEmpty[A] {

      override def size = 1 + tails.size

      override def conswise: Cons[A] = this

      override def snocwise: Snoc[A] = {
        val l :: f = (head :: tails).reverse
        Snoc(f, l)
      }

      override def +:+(rhs: NonEmpty[A]): NonEmpty[A] = rhs match {
        case r@Cons(_, _) =>
          TqCA(this, r +: empty)
        case Snoc(f, l) =>
          TqCS(head, tails, f, l)
        case TqCA(c, a) =>
          TqCA(this, c +: a)
        case TqCAS(c, a, s) =>
          TqCAS(this, c +: a, s)
        case TqCS(h, t, f, l) =>
          TqCAS(this, Cons(h, t) +: empty, Snoc(f, l))
        case TqA(a) =>
          TqCA(this, a)
        case TqAS(a, s) =>
          TqCAS(this, a, s)
      }

      override def :+(a: A): TqCS[A] = TqCS(head, tails, Nil, a)

      override def +:(a: A): Cons[A] = Cons(a, head :: tails)

      override def headTailNonEmpty: (A, ConsOrEmpty[A]) = {
        (head,
          tails match {
            case Nil =>
              empty[A]
            case h :: t =>
              Cons(h, t)
          }
        )
      }

      override def firstLastNonEmpty: (SnocOrEmpty[A], A) = snocwise.firstLastNonEmpty

      override def map[B](f: (A) => B): Cons[B] = Cons(f(head), tails map f)

      override def fold[B](zero: B)(f: (B, A) => B): B = tails.foldLeft(f(zero, head))(f)
    }

    case class Snoc[A](firsts: List[A], last: A) extends NonEmpty[A] with SnocOrEmpty[A] {

      override def size = firsts.size + 1

      override def conswise: Cons[A] = {
        val h :: t = (last :: firsts).reverse
        Cons(h, t)
      }

      override def snocwise: Snoc[A] = this

      override def +:+(rhs: NonEmpty[A]): NonEmpty[A] = rhs match {
        case r@Cons(_, _) =>
          TqA(this +: r +: empty[NonEmpty[A]]) // choice to bias to left
        case r@Snoc(_, _) =>
          TqAS(empty :+ this, r)
        case TqCA(c, a) =>
          TqA(this +: c +: a)
        case TqCAS(c, a, s) =>
          TqAS(this +: c +: a, s)
        case TqCS(h, t, f, l) =>
          TqAS(this +: Cons(h, t) +: empty[NonEmpty[A]], Snoc(f, l))
        case TqA(a) =>
          TqA(this +: a)
        case TqAS(a, s) =>
          TqAS(this +: a, s)
      }

      override def :+(a: A): Snoc[A] = Snoc(last :: firsts, a)

      override def +:(a: A): TqCS[A] = TqCS(a, Nil, firsts, last)

      override def headTailNonEmpty: (A, ConsOrEmpty[A]) = conswise.headTailNonEmpty

      override def firstLastNonEmpty: (SnocOrEmpty[A], A) = {
        (firsts match {
          case Nil =>
            empty[A]
          case l :: f => Snoc(f, l)
        },
          last
        )
      }

      override def map[B](f: (A) => B): Snoc[B] = Snoc(firsts map f, f(last))

      override def fold[B](zero: B)(f: (B, A) => B): B = firsts.foldLeft(f(zero, last))(f)
    }

    case class TqCA[A](cons: Cons[A], appends: NonEmpty[NonEmpty[A]]) extends NonEmpty[A] {

      override def size: Int = cons.size + appends.size

      override def conswise: TqCA[A] = TqCA(cons, appends.conswise)

      override def snocwise: TqA[A] = TqA(cons.snocwise +: appends.snocwise)

      override def +:+(rhs: NonEmpty[A]): NonEmpty[A] = rhs match {
        case r@Cons(_, _) =>
          TqCA(cons, appends :+ r)
        case r@Snoc(_, _) =>
          TqCAS(cons, appends, r)
        case TqCA(cr, ar) =>
          TqCA(cons, appends +:+ (cr +: ar))
        case TqCAS(cr, ar, sr) =>
          TqCAS(cons, appends +:+ (cr +: ar), sr)
        case TqCS(hr, tr, fr, lr) =>
          TqCAS(cons, appends :+ Cons(hr, tr), Snoc(fr, lr))
        case TqA(ra) =>
          TqCA(cons, appends +:+ ra)
        case TqAS(ra, rs) =>
          TqCAS(cons, appends +:+ ra, rs)
      }

      override def :+(a: A): TqCAS[A] = TqCAS(cons, appends, Snoc(Nil, a))

      override def +:(a: A): TqCA[A] = TqCA(a +: cons, appends)

      override def headTailNonEmpty: (A, TurtlesQ[A]) = cons.headTailNonEmpty match {
        case (h, TNil()) =>
          (h, TqA(appends))
        case (h, t@Cons(_, _)) =>
          (h, TqCA(t, appends))
      }

      override def firstLastNonEmpty: (TurtlesQ[A], A) = appends.firstLastNonEmpty match {
        case (TNil(), al) =>
          al.firstLastNonEmpty match {
            case (TNil(), l) =>
              (cons, l)
            case (f, l) =>
              (cons ++ f, l)
          }
        case (af: NonEmpty[NonEmpty[A]], al) =>
          al.firstLastNonEmpty match {
            case (TNil(), l) =>
              (TqCA(cons, af), l)
            case (f@Cons(_, _), l) =>
              (TqCAS(cons, af, f.snocwise), l)
            case (f@Snoc(_, _), l) =>
              (TqCAS(cons, af, f), l)
            case (f: NonEmpty[A], l) =>
              (TqCA(cons, af :+ f), l)
          }
      }

      override def map[B](f: (A) => B): NonEmpty[B] = TqCA(cons map f, appends map (_ map f))

      override def fold[B](zero: B)(f: (B, A) => B): B = {
        // broken - no appends fold
        val c = cons.fold(zero)(f)
        c
      }
    }

    case class TqCAS[A](cons: Cons[A], appends: NonEmpty[NonEmpty[A]], snoc: Snoc[A]) extends NonEmpty[A] {

      override def size: Int = cons.size + appends.size + snoc.size

      override def conswise: TqCA[A] = TqCA(cons, appends.conswise :+ snoc.conswise)

      override def snocwise: TqAS[A] = TqAS(cons.snocwise +: appends.snocwise, snoc)

      override def +:+(rhs: NonEmpty[A]): NonEmpty[A] = rhs match {
        case r@Cons(_, _) =>
          TqCA(cons, appends :+ snoc :+ r)
        case r@Snoc(_, _) =>
          TqCAS(cons, appends :+ snoc, r)
        case TqCA(cr, ar) =>
          TqCA(cons, (appends :+ snoc) +:+ (cr +: ar))
        case TqCAS(cr, ar, sr) =>
          TqCAS(cons, (appends :+ snoc) +:+ (cr +: ar), sr)
        case TqCS(hr, tr, fr, lr) =>
          TqCAS(cons, appends :+ snoc :+ Cons(hr, tr), Snoc(fr, lr))
        case TqA(ar) =>
          TqCA(cons, (appends :+ snoc) +:+ ar)
        case TqAS(ar, sr) =>
          TqCAS(cons, (appends :+ snoc) +:+ ar, sr)
      }

      override def :+(a: A): TqCAS[A] = TqCAS(cons, appends, snoc :+ a)

      override def +:(a: A): TqCAS[A] = TqCAS(a +: cons, appends, snoc)

      override def headTailNonEmpty: (A, TurtlesQ[A]) = cons.headTailNonEmpty match {
        case (h, TNil()) =>
          (h, TqAS(appends, snoc))
        case (h, t@Cons(_, _)) =>
          (h, TqCAS(t, appends, snoc))
      }

      override def firstLastNonEmpty: (TurtlesQ[A], A) = snoc.firstLastNonEmpty match {
        case (TNil(), l) =>
          (TqCA(cons, appends), l)
        case (f@Snoc(_, _), l) =>
          (TqCAS(cons, appends, f), l)
      }

      override def map[B](f: (A) => B): NonEmpty[B] = TqCAS(cons map f, appends map (_ map f), snoc map f)

      override def fold[B](zero: B)(f: (B, A) => B): B = {
        // broken - no appends fold
        val c = cons.fold(zero)(f)
        val s = snoc.fold(c)(f)
        s
      }
    }

    case class TqCS[A](head: A, tails: List[A], firsts: List[A], last: A) extends NonEmpty[A] {

      override def size: Int = 1 + tails.size + firsts.size + 1

      def cons = Cons(head, tails)
      def snoc = Snoc(firsts, last)

      override def conswise: TqCA[A] = TqCA(cons, empty :+ snoc.conswise)

      override def snocwise: TqAS[A] = TqAS(cons.snocwise +: empty, snoc)

      override def +:+(rhs: NonEmpty[A]): NonEmpty[A] = rhs match {
        case r@Cons(_, _) =>
          TqCA(cons, snoc +: r +: empty[NonEmpty[A]]) // choice to bias to left
        case r@Snoc(_, _) =>
          TqCAS(cons, snoc +: empty, r)
        case TqCA(cr, ar) =>
          TqCA(cons, snoc +: cr +: ar)
        case TqCAS(cr, ar, sr) =>
          TqCAS(cons, snoc +: cr +: ar, sr)
        case TqCS(hr, tr, fr, lr) =>
          TqCAS(cons, snoc +: Cons(hr, tr) +: empty[NonEmpty[A]], Snoc(fr, lr))
        case TqA(ar) =>
          TqCA(cons, snoc +: ar)
        case TqAS(ar, as) =>
          TqCAS(cons, snoc +: ar, as)
      }

      override def :+(a: A): TqCS[A] = TqCS(head, tails, last :: firsts, a)

      override def +:(a: A): TqCS[A] = TqCS(a, head :: tails, firsts, last)

      override def headTailNonEmpty: (A, TurtlesQ[A]) = {
        tails match {
          case Nil =>
            (head, snoc)
          case th::tt =>
            (head, TqCS(th, tt, firsts, last))
        }
      }

      override def firstLastNonEmpty: (TurtlesQ[A], A) = {
        firsts match {
          case Nil =>
            (cons, last)
          case fh::ft =>
            (TqCS(head, tails, ft, fh), last)
        }
      }

      override def map[B](f: (A) => B): NonEmpty[B] = TqCS(f(head), tails map f, firsts map f, f(last))

      override def fold[B](zero: B)(f: (B, A) => B): B = {
        val c = cons.fold(zero)(f)
        val s = snoc.fold(c)(f)
        s
      }
    }

    case class TqA[A](appends: NonEmpty[NonEmpty[A]]) extends NonEmpty[A] {

      override def size: Int = appends.size

      override def conswise: TqA[A] = TqA(appends.conswise)

      override def snocwise: TqA[A] = TqA(appends.snocwise)

      override def +:+(rhs: NonEmpty[A]): NonEmpty[A] = rhs match {
        case r@Cons(_, _) =>
          TqA(appends :+ r)
        case r@Snoc(_, _) =>
          TqAS(appends, r)
        case TqCA(cr, ar) =>
          TqA((appends :+ cr) +:+ ar)
        case TqCAS(cr, ar, sr) =>
          TqAS((appends :+ cr) +:+ ar, sr)
        case TqCS(hr, tr, fr, lr) =>
          TqAS(appends :+ Cons(hr, tr), Snoc(fr, lr))
        case TqA(ar) =>
          TqA(appends +:+ ar)
        case TqAS(ar, sr) =>
          TqAS(appends +:+ ar, sr)
      }

      override def :+(a: A): TqAS[A] = TqAS(appends, Snoc(Nil, a))

      override def +:(a: A): TqCA[A] = TqCA(Cons(a, Nil), appends)

      override def headTailNonEmpty: (A, TurtlesQ[A]) = appends.headTailNonEmpty match {
        case (ah, TNil()) => ah.headTailNonEmpty match {
          case (h, TNil()) =>
            (h, empty)
          case (h, t) =>
            (h, t)
        }
        case (ah, at: NonEmpty[NonEmpty[A]]) => ah.headTailNonEmpty match {
          case (h, TNil()) =>
            (h, TqA(at))
          case (h, t@Cons(_, _)) =>
            (h, TqCA(t, at))
          case (h, t@Snoc(_, _)) =>
            (h, TqCA(t.conswise, at))
          case (h, t: NonEmpty[A]) =>
            (h, TqA(t +: at))
        }
      }

      override def firstLastNonEmpty: (TurtlesQ[A], A) = appends.firstLastNonEmpty match {
        case (TNil(), al) => al.firstLastNonEmpty match {
          case (TNil(), l) =>
            (empty, l)
          case (f, l) =>
            (f, l)
        }
        case (af: NonEmpty[NonEmpty[A]], al) => al.firstLastNonEmpty match {
          case (TNil(), l) =>
            (TqA(af), l)
          case (f@Cons(_, _), l) =>
            (TqAS(af, f.snocwise), l)
          case (f@Snoc(_, _), l) =>
            (TqAS(af, f), l)
          case (f: NonEmpty[A], l) =>
            (TqA(af :+ f), l)
        }
      }

      override def map[B](f: (A) => B): NonEmpty[B] = TqA(appends map (_ map f))

      override def fold[B](zero: B)(f: (B, A) => B): B = {
        // broken - no appends fold
        zero
      }

    }

    case class TqAS[A](appends: NonEmpty[NonEmpty[A]], snoc: Snoc[A]) extends NonEmpty[A] {

      override def size: Int = appends.size + snoc.size

      override def conswise: TqA[A] = TqA(appends.conswise :+ snoc.conswise)

      override def snocwise: TqAS[A] = TqAS(appends.snocwise, snoc)

      override def +:+(rhs: NonEmpty[A]): NonEmpty[A] = rhs match {
        case r@Cons(_, _) =>
          TqA(appends :+ snoc :+ r)
        case r@Snoc(_, _) =>
          TqAS(appends :+ snoc, r)
        case TqCA(cr, ar) =>
          TqA((appends :+ snoc) +:+ (cr +: ar))
        case TqCAS(cr, ar, sr) =>
          TqAS((appends :+ snoc) +:+ (cr +: ar), sr)
        case TqCS(hr, tr, fr, lr) =>
          TqAS(appends :+ snoc :+ Cons(hr, tr), Snoc(fr, lr))
        case TqA(ar) =>
          TqA((appends :+ snoc) +:+ ar)
        case TqAS(ar, sr) =>
          TqAS((appends :+ snoc) +:+ ar, sr)
      }

      override def :+(a: A): TqAS[A] = TqAS(appends, snoc :+ a)

      override def +:(a: A): TqCAS[A] = TqCAS(Cons(a, Nil), appends, snoc)

      override def headTailNonEmpty: (A, TurtlesQ[A]) = appends.headTailNonEmpty match {
        case (ah, TNil()) =>
          ah.headTailNonEmpty match {
            case (h, TNil()) =>
              (h, snoc)
            case (h, t) =>
              (h, t ++ snoc)
          }
        case (ah, at: NonEmpty[NonEmpty[A]]) =>
          ah.headTailNonEmpty match {
            case (h, TNil()) =>
              (h, TqAS(at, snoc))
            case (h, t@Cons(_, _)) =>
              (h, TqCAS(t, at, snoc))
            case (h, t@Snoc(_, _)) =>
              (h, TqCAS(t.conswise, at, snoc))
            case (h, t: NonEmpty[A]) =>
              (h, TqAS(t +: at, snoc))
          }
      }

      override def firstLastNonEmpty: (TurtlesQ[A], A) = snoc.firstLastNonEmpty match {
        case (TNil(), l) =>
          (TqA(appends), l)
        case (f@Snoc(_, _), l) =>
          (TqAS(appends, snoc), l)
      }

      override def map[B](f: (A) => B): NonEmpty[B] = TqAS(appends map (_ map f), snoc map f)

      override def fold[B](zero: B)(f: (B, A) => B): B = {
        // broken - no appends fold
        snoc.fold(zero)(f)
      }
    }

  }