Patch Seq using Queue

Question

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)
    }
}

Shrey · Accepted Answer · 2013-05-19 11:24:33Z

1

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)
  }

edited May 19, 2013 at 11:24

answered May 19, 2013 at 8:51

Shrey

2,4143 gold badges22 silver badges24 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Pengin Over a year ago

That seems much cleaner, just a shame that it seems about 30% slower, I guess it's because of extra traversals due to access by index. Was surprised that switching the input to IndexedSeq widened the speed gap to ~50%.

Shrey Over a year ago

Yep, performance is on the poor side.. try replace to.patch(i, Seq(from.head), 1) with to.updated(i, from.head).. if its any better.. lemme know.. will edit the answer

Pengin Over a year ago

Edit runs in less than half the time of my original, and with fewer lines too! Took a bit of thinking about to see why it's faster. The look-ahead is nice trick.

Collectives™ on Stack Overflow

Patch Seq using Queue

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related