I need to write a very basic file/directory browser. The data structure I'm using is pretty simple - a Node with an optional parent and children. Along with the data structure I also need a simple function that will recurse a file system building up the tree of nodes. This is what I have come up with so far and I'd really appreciate any advice as to how I can improve it:
case class Node(name: String, parent: Option[Node]) {
val children : ListBuffer[Node] = ListBuffer[Node]()
def addChild(child: Node): Unit = children += child
def removeChild(child: Node): Unit = children -= child
def getChildren : Seq[Node] = children.toSeq
}
def getTree: Node = {
def getChildren(file: File, parent: Node) : Node = {
val self = Node(file.getName, Some(parent))
parent.addChild(self)
if (file.isDirectory) file.listFiles().foreach(child => getChildren(child, self))
self
}
val rootNode = Node("test", Option.empty)
getChildren(new File("/tmp/test"), rootNode)
}
// simple test
def printNode(node: Node, indent: String = "") : Unit = {
println(indent + node.name)
node.children.foreach(printNode(_, indent + " "))
}
I'm pretty happy with the data structure (although I don't mind changing it) but I'm no so happy with the getTree function. In particular I don't like the fact that it's not tail call recursive and I could end up with quite a large stack ... but maybe I'm worrying about nothing?
1 Answer 1
Normally, I'd suggest trying to get rid of as much mutable state as possible. That's not really possible here, the circular reference to the parent pretty much guarantees that something is going to need to be mutable.
Vanilla Version
Without deviating much from your original design, there are a few cleanup suggestions that I can make.
First, as suggested by @Carcigenicate , getTree could use some naming fixes. In the version below I used loop, but it could have been any number of choices. I also inlined the creation of rootNode.
def getTree(pathToRoot: String): Node = {
def loop(file: File, parent: Node) : Node = {
val self = Node(file.getName, Some(parent))
parent add self
if (file.isDirectory) file.listFiles().foreach(child => loop(child, self))
self
}
loop(new File(pathToRoot), Node("test", Option.empty))
}
Along those same lines, printNode became printTree because that's really what it does. I also moved the helper functions into Node's companion object. It's a good default organization strategy.
Node itself had mostly structural changes.
I changed the visibility of children, so that mutating it has to pass through the helpers. It also became a Set, as the OS doesn't generally make guarantees about listing order, so I wanted to avoid implying that the order was something that could be relied on not to change.
getChildren became just children and passes a defensive copy of the internal set.
That gives us this final version, with a small driver to make testing easier.
case class Node(name: String, parent: Option[Node]) {
private[Node] val _children : mutable.Set[Node] = mutable.Set[Node]()
def addChild(child: Node): Unit = _children += child
def removeChild(child: Node): Unit = _children -= child
def children: Set[Node] = Set(_children.toSeq:_*)
}
object Node extends ((String, Option[Node]) => Node) {
def getTree(pathToRoot: String): Node = {
def loop(file: File, parent: Node) : Node = {
val self = Node(file.getName, Some(parent))
parent addChild self
if (file.isDirectory) file.listFiles().foreach(child => loop(child, self))
self
}
loop(new File(pathToRoot), Node("test", Option.empty))
}
// simple test
def printTree(node: Node, indent: String = "") : Unit = {
println(indent + node.name)
node.children.foreach(printTree(_, indent + " "))
}
}
object FileSystemTree {
def main(args: Array[String]): Unit = args.foreach(arg => {
Node.printTree(Node.getTree(arg))
})
}
Lazy Version
It's possible to build a tree in a tail-recursive manner. It's much more difficult to do that with the references to the parent node.
So I cheated by making it a lazy data structure instead.
The first version was pretty basic.
case class Node(file: File, parent: Option[Node]) {
lazy val children: Set[Node] =
if (file.isDirectory) file.listFiles().map(f => Node(f, Some(this))).toSet
else Set()
}
With each node only building the list of children on demand, the getTree function became a one-liner.
object Node extends ((File, Option[Node]) => Node) {
def getTree(pathToRoot: String): Node = Node(new File(pathToRoot), None)
}
This sacrifices quite a bit of functionality to pull this off, mainly because of my preference for vals. To add the ability to add/remove child nodes, I went with a view instead. This way the data itself stays the same, just our view of it changes.
I also added a helper to provide depth-first traversal, to abstract away doing things with the nodes in the tree.
import java.io.File
case class Node(file: File, parent: Option[Node]) {
private var filter = (x: Node) => true
private lazy val _children: Set[Node] =
if (file.isDirectory) file.listFiles().map(f => Node(f, Some(this))).toSet
else Set()
def children: Set[Node] = _children.filter(filter)
def withFilter(p: Node => Boolean): Node = {
filter = p
this
}
def foreachDepthFirst(f: (Node, Int) => Unit, depth: Int = 0): Unit = {
f(this, depth)
children.foreach(_.foreachDepthFirst(f, depth + 1))
}
}
object Node extends ((File, Option[Node]) => Node) {
def getTree(pathToRoot: String): Node = Node(new File(pathToRoot), None)
def printTree(root: Node): Unit = root.foreachDepthFirst({
case (Node(f, _), depth) => println((" " * depth) + f.getName)
})
}
object FileSystemTree {
def main(args: Array[String]): Unit = args.foreach(arg => {
Node.printTree(Node.getTree(arg))
})
}
getChildrensomething else. It took me a second to find the recursion since you've also defined agetChildreninstance method. \$\endgroup\$