Algorithm mixing

Question

I have a class that extends Iterator and model an complex algorithm (MyAlgorithm1). Thus, the algorithm can advance step by step through the Next method.

class MyAlgorithm1(val c:Set) extends Iterator[Step] {
   override def next():Step {
       /* ... */
   }
   /* ... */
}

Now I want apply a different algorithm (MyAlgorithm2) in each pass of the first algorithm. The iterations of algorithm 1 and 2 should be inserted

class MyAlgorithm2(val c:Set) { /* ... */ }

How I can do this in the best way? Perhaps with some Trait?

UPDATE:

MyAlgorithm2 recives a set and transform it. MyAlgorithm1 too, but this is more complex and it's necessary runs step by step. The idea is run one step of MyAlgoirthm1 and then run MyAlgorithm2. Next step same. Really, MyAlgorithm2 simplifies the set and may be useful to simplify work of MyAlgorithm1.

Answer 1

I have a class that extends Iterator and model an complex algorithm (MyAlgorithm1).

Well, stop for a moment there. An algorithm is not an iterator, so it doesn't make sense for it to extend Iterator.

Answer 2

Extending Iterator is probably more work than you actually need to do. Let's roll back a bit.

You've got some stateful object of type MyAlgorithm1

val alg1 = new MyAlgorithm1(args)

Now you wish to repeatedly call some function on it, which will alter it's state and return some value. This is best modeled not by having your object implement Iterator, but rather by creating a new object that handles the iteration. Probably the easiest one in the Scala standard library is Stream. Here's an object which creates a stream of result from your algorithm.

val alg1Stream:Stream[Step] = Stream.continually(alg1.next())

Now if you wanted to repeatedly get results from that stream, it would be as easy as

for(step<-alg1Stream){
   // do something
}

or equivalently

alg1Stream.forEach{
    //do something
}

Now assume we've also encapsulated myAlgorithm2 as a stream

val alg2=new MyAlgorithm2(args)
val alg2Stream:Stream[Step] = Stream.continually(alg2.next())

Then we just need some way to interleave streams, and then we could say

for(step<-interleave(alg1Stream, algStream2)){
   // do something
}

Sadly, a quick glance through the standard library, reveals no Stream interleaving function. Easy enough to write one

def interleave[A](stream1:Stream[A], stream2:Stream[A]):Stream[A] ={
    var str1 = stream1
    var str2 = stream2
    var streamToUse = 1
    Stream.continually{
        if(streamToUse == 1){
           streamToUse = 2
           val out = str1.head
           str1 = str1.tail
           out
        }else{
           streamToUse = 1
           val out = str2.head
           str2 = str1.tail
           out
        }
    }
}

That constructs a stream that repeatedly alternates between two streams, fetching the next result from the appropriate one and then setting up it's state for the next fetch. Note that this interleave only works for infinite streams, and we'd need a more clever one to handle streams that can end, but that's fine for the sake of the problem.

Answer 3

It seems as if you might want to use a fold or a map instead, depending on exactly what it is that you want to do. This is a common pattern in functional programming: You generate a list/sequence/stream of something and then run a function on each element. If you want to run two functions on each element, you can either compose the functions or run another map.

Answer 4

As described, the problem can be solved with either inheritance or trait. For instance:

class MyAlgorithm1(val c:Set) extends Iterator[Step] {
  protected var current = Step(c)
  override def next():Step = {
    current = process(current)
    current 
  }
  override def hasNext: Boolean = !current.set.isEmpty
  private def process(s: Step): Step = s
}

class MyAlgorithm2(c: Set) extends MyAlgorithm1(c) {
  override def next(): Step = {
    super.next()
    current = process(current)
    current
  }
  private def process(s: Step): Step = s
}

With traits you could do something with abstract override, but designing it so that the result of the simplification gets fed to the first algorithm may be harder.

But, let me propose you are getting at the problem in the wrong way.

Instead of creating a class for the algorithm extending an iterator, you could define your algorithm like this:

class MyAlgorithm1 extends Function1[Step, Step] {
  def apply(s: Step): Step = s
}

class MyAlgorithm2 extends Function1[Step, Step] {
  def apply(s: Step): Step = s
}

The iterator then could be much more easily defined:

Iterator.iterate(Step(set))(MyAlgorithm1 andThen MyAlgorithm2).takeWhile(_.set.nonEmpty)