Find String in Char iterator

Question

I have a use case where I need to return a String up to a delimiter String (if found) from an iterator of Char.

The contract:

• if iterator is exhausted (only at the begin), return None
• if the delimiter String is found, return all characters before it (empty String is fine), delimiter will be dropped
• else return the remaining characters
• do not eagerly exhaust the iterator!

I do have this working solution, but it feels like Java (which is where I'm coming from)

class MyClass(str: String) {
  def nextString(iterator: Iterator[Char]): Option[String] = {
    val sb = new StringBuilder
    if(!iterator.hasNext) return None
    while (iterator.hasNext) {
      sb.append(iterator.next())
      if (sb.endsWith(str)) return Some(sb.stripSuffix(str))
    }
    Some(sb.toString())
  }
}

Is there a way I can do this in a more functional way (ideally without changing the method signature)?

Update: Here is how I test this

val desmurfer = new MyClass("_smurf_")
val iterator: Iterator[Char] = "Scala_smurf_is_smurf_great_smurf__smurf_".iterator
println(desmurfer.nextString(iterator))
println(desmurfer.nextString(iterator))
println(desmurfer.nextString(iterator))
println(desmurfer.nextString(iterator))
println(desmurfer.nextString(iterator))
println
println(desmurfer.nextString("FooBarBaz".iterator))
println(desmurfer.nextString("".iterator))

Output:

Some(Scala)
Some(is)
Some(great)
Some()
None

Some(FooBarBaz)
None

Answer 1

What about this one?

def nextString(iterator: Iterator[Char]): Option[String] = {
    val t = iterator.toStream

    val index = t.indexOfSlice(s)
    if(t.isEmpty) None
    else if(index == -1) Some(t.mkString)
    else Some(t.slice(0,index).mkString)
  }

it passed this tests:

val desmurfer = new MyClass("_smurf_")
val iterator: Iterator[Char] = "Scala_smurf_is_smurf_great_smurf__smurf_".iterator
assert(desmurfer.nextString(iterator) == Some("Scala"))
assert(desmurfer.nextString(iterator) == Some("is"))
assert(desmurfer.nextString(iterator) == Some("great"))
assert(desmurfer.nextString(iterator) == Some(""))
assert(desmurfer.nextString(iterator) == None)

assert(desmurfer.nextString("FooBarBaz".iterator) == Some("FooBarBaz"))
assert(desmurfer.nextString("".iterator) == None)

Updated: removed "index == -1 &&" from the first "if condition clause".

Answer 2

A colleague provided the makings of this answer, which is a mixture between his original approach and some polishing from my side. Thanks, Evans! Then another colleague also added some input. Thanks Ako :-)

class MyClass(str: String) {
  def nextString(iterator: Iterator[Char]): Option[String] = {

    def nextString(iterator: Iterator[Char], sb: StringBuilder): Option[String] = {
      if (!iterator.hasNext || sb.endsWith(str)) {
        Some(sb.stripSuffix(str))
      } else {
        nextString(iterator, sb.append(iterator.next()))
      }
    }

    if (!iterator.hasNext) None
    else nextString(iterator, new StringBuilder)
  }
}

So far, I like this approach best, so I will accept it in two days unless there is a better answer by then.

Answer 3

Here's one I'm posting just because it's a bit warped :) I wouldn't recommend actually using it:

  class MyClass2(str: String) {
    val sepLength = str.length
    def nextString(iterator: Iterator[Char]): Option[String] = {
      if (!iterator.hasNext) return None

      val sit = iterator.sliding(sepLength)
      val prefix = sit.takeWhile(_.mkString != str).toList

      val prefixString = prefix.toList.map(_.head).mkString
      if (prefix.head.length < sepLength) Some(prefix.head.mkString)
      else if (!iterator.hasNext) Some(prefix.head.mkString + prefix.last.mkString)
      else Some(prefixString)

    }
  }

The idea is that by calling sliding() on our underlying iterator, we can get a sequence, one of which will be our delimiter, if it's present. So we can use takeWhile to find the delimiter. Then the first characters of each of the sliding strings before our delimiter is the string we skipped over. As I said, warped.

I'd really like sliding to be defined so that it produced all subsequences of length n and at the end sequences of length n-1, n-2....1 for this particular use case, but it doesn't, and the horrible if statement at the end is dealing with the various cases.

It passes the test cases :)

Answer 4

Updated: This works without converting the iterator to String

def nextString(iterator: Iterator[Char]): Option[String] = {
  if (iterator.isEmpty) None
  else Some(iterator.foldLeft("") { (result, currentChar) => if (res.endsWith(str)) result else result + currentChar})
}

Answer 5

This seems to be doing what you'd want. @Eastsun answer motivated me

val str = "hello"

  def nextString2(iterator: Iterator[Char]): Option[String] = {
    val maxSize = str.size
    @tailrec
    def inner(collected: List[Char], queue: Queue[Char]): Option[List[Char]] =
      if (queue.size == maxSize && queue.sameElements(str))
        Some(collected.reverse.dropRight(maxSize))
      else
        iterator.find(x => true) match {
          case Some(el) => inner(el :: collected, if (queue.size == maxSize) queue.dequeue._2.enqueue(el) else queue.enqueue(el))
          case None => Some(collected.reverse)
        }

    if (iterator.hasNext)
      inner(Nil, Queue.empty).map(_.mkString)
    else
      None
  }

  test(nextString2(Nil.iterator)) === None
  test(nextString2("".iterator)) === None
  test(nextString2("asd".iterator)) === Some("asd")
  test(nextString2("asfhello".iterator)) === Some("asf")
  test(nextString2("asehelloasdasd".iterator)) === Some("ase")

But I honestly think it's too complicated to be used. Sometimes you have to use non FP stuff in scala to be performance effecient.

P.S. I didn't know how to match iterator on it's first element, so I've used iterator.find(x => true) which is ugly. Sorry.

P.P.S. A bit of explanation. I recoursively build up collected to fill the elements you are searching for. And I also build queue with last str.size-elements. Then I just check this queue over str each time. This might not be the most efficient way of doing this stuff. You might go with Aho–Corasick algorithm or an analogue if you want more.

P.P.P.S. And I am using iterator as a state, which is probably not FP way

P.P.P.P.S. And you test passes as well:

  val desmurfer = new MyClass("_smurf_")
  val iterator: Iterator[Char] = "Scala_smurf_is_smurf_great".iterator
  test(desmurfer.nextString2(iterator)) === Some("Scala")
  test(desmurfer.nextString2(iterator)) === Some("is")
  test(desmurfer.nextString2(iterator)) === Some("great")
  test(desmurfer.nextString2(iterator)) === None
  println()
  test(desmurfer.nextString2("FooBarBaz".iterator)) === Some("FooBarBaz")
  test(desmurfer.nextString2("".iterator)) === None

Answer 6

How about this one:

scala> def nextString(itr: Iterator[Char], sep: String): Option[String] = {
     |    def next(res: String): String =
     |      if(res endsWith sep) res dropRight sep.size else if(itr.hasNext) next(res:+itr.next) else res
     |   if(itr.hasNext) Some(next("")) else None
     | }
nextString: (itr: Iterator[Char], sep: String)Option[String]

scala> val iterator: Iterator[Char] = "Scala_smurf_is_smurf_great".iterator
iterator: Iterator[Char] = non-empty iterator

scala> println(nextString(iterator, "_smurf_"))
Some(Scala)

scala> println(nextString(iterator, "_smurf_"))
Some(is)

scala> println(nextString(iterator, "_smurf_"))
Some(great)

scala> println(nextString(iterator, "_smurf_"))
None

scala> println(nextString("FooBarBaz".iterator, "_smurf_"))
Some(FooBarBaz)