CODEWITHSUNDEEP
scalagraphtree
Pravin Gadakh
Pravin Gadakh

Reputation: 633

scala: data structure for multiple-root tree or forest

I am in search of a good data structure for my requirement:

Assuming each Node can be uniquely identified, I have come up with a following data structure which seems a bit immature.

case class Node[T](data: T, children: List[Node[T]], parents: List[Node[T]])

class Forest[T](val roots: List[Node[T]]) {

  // other helper methods to create the Forest
}

object Forest {
  def apply[T](list: List[T]): Forest[T] = {
    val roots = for (l <- list) yield Node[T](l, List.empty[Node[T]], List.empty[Node[T]])
    new Forest[T](roots)
  }
}

Does anyone have better suggestions?

TIA

Upvotes: 0

Views: 837

Answers (1)

Rex Kerr
Rex Kerr

Reputation: 167891

I suggest you check out Graph for Scala. The library isn't being very actively developed, but the basic functionality doesn't need it and once you get used to the way it traverses nodes, you get a lot of functionality without much effort. (It might take a little thought to best fit the parent/child relationship into the graph; you could make a directed graph to represent that, or two graphs one in each direction, etc.)

Otherwise, the basics of what you have now is missing one detail--how do you actually create the forest? Right now, a node is immutable with immutable lists of parents and children, which means that the parents and children of every node must be created before the node is, which means...uh-oh.

You can solve this by adding an extra layer of indirection (have lists of node IDs and a map associating IDs with actual nodes), or by adding mutability somewhere (generally a little iffy in case classes, but in this case maybe it's what you need).

And then, of course, you need a bunch of methods to actually do something useful with the forest and provide higher-level ways of constructing it.

Upvotes: 3

Related Questions