3

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
Improve this question
4
  • what is the sample output you are expecting ? Commented Dec 18, 2015 at 10:08
  • @S.Karthik added sample output Commented Dec 18, 2015 at 10:25
  • please check the answer Commented Dec 18, 2015 at 11:01
  • please check the answer Commented Dec 20, 2015 at 13:37

6 Answers 6

Reset to default
3

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)
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

This is nice, but I guess :+ should be O(n) and also have memory issues with lots of calls. Please see my answer (much-much bigger though) as my try on an improvement. Your answer still might be better because of simplicity
3

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".

Improve this answer

1 Comment

Very nice indeed. Just curious: why test index twice? Is it possible for t.isEmpty while at the same time index != -1?
2

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
Improve this answer

Comments

2

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

Improve this answer

2 Comments

I like this one best so far. Had also looked at .sliding but then rejected it as too complicated.
There are edge cases where the delimiter is the very last thing or very first thing in the underlying iterator. It messes up in those cases. I may get around to fixing that later. You probably need more test cases...
0

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})
}
Improve this answer

4 Comments

If I was allowed to convert to String, the answer would be obvious. The constraint I have is that I should only take as many characters as needed (added that to the contract)
I missed that part. I have updated my answer to do it without converting the iterator to String
foldLeft still consumes the whole iterator though.
Yup, The best solution obviously is to use a recursive function. The answer from Eastsun seems to be perfect.
0

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.

Improve this answer

1 Comment

You should turn this into an iterator itself. class MyIterator(iterator:Iterator[Char]) extends Iterator { def hasNext() = iterator.hasNext; def next() = {<body of your nextString, mostly>)}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.