Decode the Coding Interview in Elixir: 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 module:

  • init(nested_list) initializes the iterator with the nested_list.
  • next() returns the next file in the nested directories.
  • has_next() 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 has_next 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 has_next function is called.

The next function first calls the has_next function to check if there is any file or directory in the stack. If the has_next 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:

Press + to interact
main.exs
NestedDirectories.ex
defmodule DirectoryIterator do
  defstruct stack: []
  # Constructor initializes a single file if a value has been passed
  # else initializes an empty list
  def init(nested_list) do
    obj = %__MODULE__{}
    %__MODULE__{obj | stack: nested_list |> :lists.reverse |> Arrays.new}
  end
  defp has_next(obj, top_list, i) do
    cond do
      i >= 0 ->
        obj = %__MODULE__{obj | stack: obj.stack |> Arrays.append(top_list[i])}
        has_next(obj, top_list, i-1)
      true -> obj
    end
  end
  def has_next(obj) do
    cond do
      Arrays.size(obj.stack) > 0 ->
        top = obj.stack[-1]
        
        {res, obj} =
          case NestedDirectories.is_file(top) do
            false -> 
              {:ok, {list, stack}} = Arrays.extract(obj.stack)
              top_list = list |> NestedDirectories.get_list
              i = length(top_list) - 1
              obj = %__MODULE__{obj | stack: stack}
              obj = has_next(obj, Arrays.new(top_list), i)
              {false, obj}
            _ -> {true, obj}
          end
        if res == true, do: {true, obj}, else: has_next(obj)
      true -> {false, obj}
    end
  end
  def next(obj) do
    {res, obj} = DirectoryIterator.has_next(obj)
    case res do
      true -> 
        {:ok, {file, stack}} = Arrays.extract(obj.stack)
        obj = %__MODULE__{obj | stack: stack}
        {file |> NestedDirectories.get_file, obj}
      _ -> {nil, obj}
    end
  end
end
# Driver Code
defmodule Main do
  def itr_printer(itr) do
    {res, itr} = DirectoryIterator.has_next(itr)
    case res do
      true -> 
        IO.write("itr.next(): ")
        {file, itr} = DirectoryIterator.next(itr)
        IO.inspect file
        itr_printer(itr)
      _ -> :ok
    end
  end
  def main do
    # Driver Code
    IO.puts "-----------------------------"
    IO.puts "PROGRAM OUTPUT:"
    nested_list = []
    l1 = NestedDirectories.init(nil)
    nested_list = [NestedDirectories.init("F1") | nested_list]
    l1 = l1 |> NestedDirectories.add(NestedDirectories.init("F2"))
    l1 = l1 |> NestedDirectories.add(NestedDirectories.init("D1"))
    l1 = %NestedDirectories{l1 | n_list: l1.n_list |> :lists.reverse}
    nested_list = [l1 | nested_list] 
    nested_list = [NestedDirectories.init("D2") | nested_list] |> :lists.reverse
    itr = DirectoryIterator.init(nested_list)
    IO.puts("Original structure: [F1, [F2, D1], D2]")
    IO.puts("Output:")
    itr |> itr_printer
  end
end
Main.main

Complexity measures

Time complexity Space complexity
O(n+l)O(n + l)
...
Access this course and 1400+ top-rated courses and projects.