Search code examples
scalasetlistbuffer

Dependencies in a ListBuffer[Set[Int]] in Scala

I'm solving a problem and I got this:

ant : scala.collection.mutable.ListBuffer[Set[Int]] = ListBuffer(Set(), Set(0), Set(0), Set(1), Set(2), Set(1), Set(3,4), Set(5, 6), Set(7))

The Sets in the ListBuffer represent dependencies, for example: ant(1) is the Set(0), which means that ant(1) depends of ant(0) which is the Set(). The same with the others, another example: ant(7) is the Set(5, 6) which means that ant(7) depends of ant(5) and ant(6).

What I need to obtain is a new ListBuffer[Set[Int]] with all the dependencies between the Sets without repetitions, for example: ant(6) depends of ant(3) and ant(4), at the same time ant(3) depends of ant(1) and ant(4) depends of ant(2), and ant(1) and ant(2) depend of ant(0), so the result with all the dependencies in ant(6) is: Set(3,4,1,2,0)

So the result of the initial ListBuffer should be:

 solution : scala.collection.mutable.ListBuffer[Set[Int]] = ListBuffer(Set(), Set(0), Set(0), Set(1,0), Set(2,0), Set(1,0), Set(3,4,1,2,0), Set(5,6,1,3,4,0,2), Set(7,5,6,1,0,4,3,2))

Which is the best way to do it?

Thanks.

Solution

  • This is definitely the wrong data structure for what you are trying to represent. To get the result you seek you'll have to go through a tortured sequence of steps even more convoluted than the data structure itself.

    So here's where we start.

    import collection.mutable.ListBuffer
val ant: ListBuffer[Set[Int]] = ListBuffer(Set(), Set(0), Set(0), Set(1), Set(2),
                                           Set(1), Set(3,4), Set(5, 6), Set(7))

    Now we need to add the sub-dependencies to each of the current Sets of dependencies. Since these are Sets of Ints, the order of presentation doesn't matter.

    ant.map(_.flatMap(x => ant(x) + x))
// ListBuffer(Set(), Set(0), Set(0), Set(0, 1), Set(0, 2), Set(0, 1), Set(1, 3, 2, 4), Set(5, 1, 6, 3, 4), Set(5, 6, 7))

    Now we need to repeat that until the new result is the same as the previous result. A Stream iterator will set up the repetitions and we'll dropWhile each element is different from the previous.

    // a ListBuffer Stream
val lbStrm: Stream[ListBuffer[Set[Int]]] = 
     Stream.iterate[ListBuffer[Set[Int]]](ant)(_.map(_.flatMap(x => ant(x) + x)))

// grab the first one after the results settle
lbStrm.zipWithIndex.dropWhile{case (lb,x) => lb != lbStrm(x+1)}.head._1
// ListBuffer(Set(), Set(0), Set(0), Set(0, 1), Set(0, 2), Set(0, 1), Set(0, 1, 2, 3, 4), Set(0, 5, 1, 6, 2, 3, 4), Set(0, 5, 1, 6, 2, 7, 3, 4))

    Not pretty, but doable. It would be much better to redesign that starting data structure.