CODEWITHSUNDEEP
scalascala-collections
Pengin
Pengin

Reputation: 4772

Patch Seq using Queue

I'm writing a simulation where a number of operators take work from a single queue. At each time step I need to sequentially check elements of a sequence, and if a condition passes replace the current value with an item from the queue. What remains in the queue must be retained for later iterations.

I've written a routine called patch to do this, but it doesn't seem very neat. Is there a more idiomatic way to achieve the same thing? I'd like it to be fairly fast but still functional in style.

import scala.annotation.tailrec
import scala.collection.immutable.Queue

object SeqPimp extends App{

    val mySeq = Seq('a', 'B', 'C', 'd', 'E')
    val shortQ = Queue('+','-')
    val longQ = Queue('+','-','*','/','%')

    println(patch(mySeq)(_.isUpper, shortQ))
    //Output:   (List(a, +, -, d, E),Queue())

    println(patch(mySeq)(_.isUpper, longQ))
    //Output:   (List(a, +, -, d, *),Queue(/, %))

    def patch[T](to: Seq[T])(condition: T => Boolean, from: Queue[T]): (Seq[T], Queue[T]) = {
        @tailrec
        def go(acc: Seq[T], remaining: Seq[T], q: Queue[T]): (Seq[T], Queue[T]) = {
            if(acc.size == to.size) (acc.reverse, q)
            else if(q.size == 0) (acc.reverse ++: remaining, q)
            else{
                if(condition(remaining.head)){
                    val (item, q1) = q.dequeue
                    go(item +: acc, remaining.tail, q1)
                }else{
                    go(remaining.head +: acc, remaining.tail, q)
                }
            } 
        }

        go(Nil, to, from)
    }
}

Upvotes: 0

Views: 222

Answers (1)

Shrey
Shrey

Reputation: 2404

Prolly something like this...

def patch[T](to: Seq[T])(condition: T => Boolean, from: Queue[T]): (Seq[T], Queue[T]) = {
if (from.isEmpty) (to, from)
else {
  val i = to.indexWhere(condition)
  if (i == -1) (to, from)
  else patch(to.patch(i, Seq(from.head), 1))(condition, from.tail)
}
}

Or you can simply enrich Seq this way..

object SeqPimp extends App {

  implicit class EnSeq[T](val to: Seq[T]) extends AnyVal{
    def enPatch(condition: T => Boolean, from: Queue[T]): (Seq[T], Queue[T]) = {
      if (from.isEmpty) (to, from)
      else {
        val i = to.indexWhere(condition)
        if (i == -1) (to, from)
        else to.patch(i, Seq(from.head), 1).enPatch(condition, from.tail)
      }
    }
  }

  val mySeq = Seq('a', 'B', 'C', 'd', 'E')
  val shortQ = Queue('+', '-')
  val longQ = Queue('+', '-', '*', '/', '%')

  mySeq.enPatch(_.isUpper, shortQ)
  //Output:   (List(a, +, -, d, E),Queue())

  mySeq.enPatch(_.isUpper, longQ)
  //Output:   (List(a, +, -, d, *),Queue(/, %))

}

EDIT

Here is the def patch with better performance.. But not as pretty as before..

  def patch[T](to: Seq[T])(condition: T => Boolean, from: Queue[T]): (Seq[T], Queue[T]) = {
    @tailrec
    def go(acc: Seq[T], remaining: Seq[T], q: Queue[T]): (Seq[T], Queue[T]) = {
      if (q.isEmpty || remaining.isEmpty) (acc ++ remaining, q)
      else {
        val (accu, rem) = remaining.span(e => !condition(e))
        if (rem.isEmpty) (acc ++ accu, q)
        else go(acc ++ accu.:+(q.head), rem.tail, q.tail)
      }
    }
    go(Nil, to, from)
  }

Upvotes: 1

Related Questions