Decode the Coding Interview in Scala: Real-World Examples/

...

/

Feature #11: Directory Iterator

Feature #11: Directory Iterator

Implementing the "Directory Iterator" feature for our "Operating System" project.

We'll cover the following...

Description

In this feature, we will create a directory tree iterator. A directory can contain files or other directories. Similarly, subdirectories can contain both files and other directories. We will be given a directory structure for a specific directory in the file system. This directory will be available as a list. Each element of this list is either a file represented as a scalar element, or a directory represented as a nested list. We will have to iterate over all of the files one by one, using an iterator.

The task is to implement the NestedIterator class:

  • var list: ListBuffer[NestedDirectories] the list of NestedDirectories.
  • next returns the next file in the nested directories.
  • hasNext returns true if there are still some files in the nested list. If there are no files left in the nested list, it returns false.

Solution

We will use a stack to solve this feature. The stack will be used to store the directories and files on the iterator object. In the constructor, we will push all the files and the directories in the stack in reverse order.

The hasNext function checks if the top element of the stack is a file or directory. If so, then it returns true. Otherwise, if the top element is a list of files or directories, then it pops from the stack and pushes each element of the list in the stack in reverse order. This way, the lists at the top of the stack are converted into individual files or a directory whenever the hasNext function is called.

The next function first calls the hasNext function to check if there is any file or directory in the stack. If the hasNext function returns true, then it pops from the stack and returns the topmost value.

Here is an example of how this function works:

Let’s look at the code for this solution:

import scala.collection.mutable
import scala.collection.mutable.ListBuffer
class NestedDirectories() // Constructor initializes an empty nested list.
{
  var list: ListBuffer[NestedDirectories] = new ListBuffer[NestedDirectories]()
  var file: String = null
  // Constructor initializes a single file.
  def this(value: String) {
    this()
    this.file = value
  }
  // @return true if this NestedDirectories holds a single file, rather than a nested list.
  def isFile: Boolean = {
    if (this.file != null) return true
    false
  }
  // @return the single file that this NestedDirectories holds, if it holds a single file
  // Return null if this NestedDirectories holds a nested list
  def getFile: String = this.file
  // Set this NestedDirectories to hold a single file.
  def setFile(value: String): Unit = {
    this.list = null
    this.file = value
  }
  // Set this NestedDirectories to hold a nested list and adds a nested file to it.
  def addOne(ni: NestedDirectories): Unit = {
    if (this.file != null) {
      this.list = new ListBuffer[NestedDirectories]()
      list.addOne(new NestedDirectories(this.file))
      this.file = null
    }
    list.addOne(ni)
  }
  // @return the nested list that this NestedDirectories holds, if it holds a nested list
  // Return null if this NestedDirectories holds a single file
  def getList: ListBuffer[NestedDirectories] = list
}
object Main extends App{
  class NestedIterator(val nestedList: ListBuffer[NestedDirectories]) {
    private var stack = new mutable.Stack[NestedDirectories]
    for (i <- nestedList.size - 1 to 0 by -1) {
      this.stack.push(nestedList(i))
    }
    
    def hasNext: Boolean = {
      while ( {
        stack.size > 0
      }) {
        val top = stack.top
        if (top.isFile) return true
        val topList = stack.pop.getList
        for (i <- topList.size - 1 to 0 by -1) {
          this.stack.push(topList(i))
        }
      }
      false
    }
    def next: String = {
      if (hasNext) return this.stack.pop.getFile
      null
    }
  }
  
    val nestedList = new ListBuffer[NestedDirectories]
    val l1 = new NestedDirectories
    nestedList.addOne(new NestedDirectories("F1"))
    l1.addOne(new NestedDirectories("F2"))
    l1.addOne(new NestedDirectories("D1"))
    nestedList.addOne(l1)
    nestedList.addOne(new NestedDirectories("D2"))
    val itr = new NestedIterator(nestedList)
    println("Original structure: [F1, [F2, D1], D2]")
    println("")
    println("Output:")
    while ( {
      itr.hasNext
    }) {
      print("itr.next: ")
      println(itr.next)
    }
  
}
Directory Iterator

Complexity measures

Time complexity Space complexity
O(n+l)O(n + l)
...