I need to use my Queue.java to implement an Iterator over Files that will traverse (or walk) a filesystem tree in level order.

I will rate if your code passes all JUnit tests I provided in PublicLevelOrderIteratorTest .java.

Your computer stores files and directories on disk. The filesystem is a data structure that organizes these two types of nodes. Each node in the filesystem is either a file or a directory, and directories contain zero or more other nodes. If you drew out the content of a particular node, it would fan out in a tree-like structure. On OS X, this is explicit in the Finder:

In essence, my code have to perform a so-called breadth-first search (BFS) of a given tree within the filesystem.

Java represents filesystem nodes using class java.io.File. You'll want to skim through the API documentation for File. Pay attention to the constructor and the exists(), isDirectory(), and listFiles() methods.

The link of java.io.File: https://docs.oracle.com/javase/8/docs/api/java/io/File.html.

To ensure you traverse the tree in level order, your code will need to visit the nodes in first-in-first-out order, adding children of the current node to a queue of nodes waiting to be visited in order. (Use Queue.java I created in Problem 1; Please DON'T use java.util.Queue.)

When you obtain the children of a node, sort them in lexicographic before enqueueing them. The sorting can be done using Java's Arrays.sort method. The File class already defines a compareTo method, which Arrays.sort relies on.

A correct level-order traversal of the example tree above, rooted at src, is in the following order: src src/algorithms src/hanoi src/structures src/algorithms/RecursiveMath.java src/hanoi/ArrayBasedHanoiBoard.java src/hanoi/RecursiveHanoiSolver.java src/hanoi/StackBasedHanoiPeg.java

Here is the Queue.java:

package structures;

import java.util.NoSuchElementException;

/**************************************************************************************

* NOTE: before starting to code, check support/structures/UnboundedQueueInterface.java

* for detailed explanation of each interface method, including the parameters, return

* values, assumptions, and requirements

***************************************************************************************/

public class Queue implements UnboundedQueueInterface {

private Node front;

private Node rear;

private int num;

public Queue() {

// TODO 1

front = null;

rear = null;

num = 0;

}

public Queue(Queue other) {

// TODO 2

front = null;

rear = null;

num = 0;

Node curr = other.front;

while(curr!=null) {

enqueue(curr.data);

curr = curr.next;

}

}

@Override

public boolean isEmpty() {

// TODO 3

return front==null;

}

@Override

public int size() {

// TODO 4

return num;

}

@Override

public void enqueue(T element) {

// TODO 5

if(front == null) {

front = new Node(element);

rear = front;

}

else {

Node node = new Node(element);

rear.next = node;

rear = node;

}

num++;

}

@Override

public T dequeue() throws NoSuchElementException {

// TODO 6

T data = front.data;

if(front.next == null) {

front = null;

rear = null;

}

else

front = front.next;

num--;

return data;

}

@Override

public T peek() throws NoSuchElementException {

// TODO 7

return front.data;

}

@Override

public UnboundedQueueInterface reversed() {

// TODO 8

if(isEmpty()) {

return new Queue();

}

T arr[] = (T[]) new Object[size()];

Node curr = front;

int i=0;

while(curr != null) {

arr[i] = curr.data;

i++;

curr = curr.next;

}

Queue reverse = new Queue();

for(i=arr.length-1;i>=0;i--) {

reverse.enqueue(arr[i]);

}

return reverse;

}

}

class Node {

public T data;

public Node next;

public Node(T data) { this.data=data;}

public Node(T data, Node next) {

this.data = data; this.next=next;

}

}

Here is LevelOrderIterator.java which I have to work on:

package filesystem;

import java.io.File;

import java.io.FileNotFoundException;

import java.util.Arrays;

import java.util.NoSuchElementException;

/**

* An iterator to perform a level order traversal of part of a

* filesystem. A level-order traversal is equivalent to a breadth-

* first search.

*/

public class LevelOrderIterator extends FileIterator {

/**

* Instantiate a new LevelOrderIterator, rooted at the rootNode.

* @param rootNode

* @throws FileNotFoundException if the rootNode does not exist

*/

public LevelOrderIterator(File rootNode) throws FileNotFoundException {

// TODO 1

}

@Override

public boolean hasNext() {

// TODO 2

return false;

}

@Override

public File next() throws NoSuchElementException {

// TODO 3

return null;

}

@Override

public void remove() {

// Leave this one alone.

throw new UnsupportedOperationException();

}

}

Here is the JUnit test file PublicLevelOrderIteratorTest .java:

package filesystem;

import static org.junit.Assert.*;

import java.io.File;

import java.io.FileNotFoundException;

import java.io.IOException;

import java.nio.file.Files;

import java.util.NoSuchElementException;

import java.util.concurrent.TimeUnit;

import org.junit.After;

import org.junit.Before;

import org.junit.Rule;

import org.junit.Test;

import org.junit.rules.Timeout;

public class PublicLevelOrderIteratorTest {

@Rule

public Timeout timeout = new Timeout(10L, TimeUnit.SECONDS);

File tempFile;

LevelOrderIterator singleIterator;

File tempDir;

LevelOrderIterator nestedDirIterator;

File emptyDir;

LevelOrderIterator emptyDirIterator;

File subDir;

File leafDir;

LevelOrderIterator leafDirIterator;

/**

* Before each test, this method sets up the following hierarchy in a temporary directory:

*

* /

* /a.txt

* /empty/

* /subdir/

* /subdir/subsubdir/

* /subdir/subsubdir/bar.exe

* /subdir/subsubdir/foo.txt

* /subdir/yahoo

* /z.exe

*

* tempFile points at a single temporary file

* singleIterator creates a LevelOrderIterator initialized with tempFile

*

* tempDir points at the root of the temporary directory

* nestedFileIterator creates a LevelOrderIterator initialized with tempDir

*

* emptyDir points at /empty/

* emptyDirIterator creates a LevelOrderIterator initialized with emptyDir

*

* subDir points at /subdir/

* subDirIterator creates a LevelOrderIterator initialized with subDir

*

* leafDir points at /subdir/subsubdir/

* leafDirIterator creates a LevelOrderIterator initialized with leafDir

*

* @throws IOException

*/

@Before

public void before() throws IOException {

tempFile = File.createTempFile("queues", "tmp");

singleIterator = new LevelOrderIterator(tempFile);

tempDir = Files.createTempDirectory("queues").toFile();

for (String fileName: new String[] {"a.txt", "z.exe"}) {

File f = new File(tempDir, fileName);

f.createNewFile();

}

emptyDir = new File(tempDir, "empty");

emptyDir.mkdir();

emptyDirIterator = new LevelOrderIterator(emptyDir);

subDir = new File(tempDir, "subdir");

subDir.mkdir();

File subDirFile = new File(subDir, "yahoo");

subDirFile.createNewFile();

leafDir = new File(subDir, "subsubdir");

leafDir.mkdir();

for (String fileName: new String[] {"foo.txt", "bar.exe"}) {

File f = new File(leafDir, fileName);

f.createNewFile();

}

leafDirIterator = new LevelOrderIterator(leafDir);

nestedDirIterator = new LevelOrderIterator(tempDir);

}

@After

public void after() {

tempFile.delete();

tempDir.delete();

}

@SuppressWarnings("unused")

@Test(expected = FileNotFoundException.class)

public void testFileNotFound() throws Exception {

LevelOrderIterator i = new LevelOrderIterator(new File("probablyyoudon'thaveafilewiththisname"));

}

@Test

public void testHasNextAtStartSingle() throws Exception {

assertTrue(singleIterator.hasNext());

}

@Test

public void testHasNextAtEndSingle() throws Exception {

singleIterator.next();

assertFalse(singleIterator.hasNext());

}

@Test(expected = NoSuchElementException.class)

public void testExceptionAtEndSingle() throws Exception {

singleIterator.next();

singleIterator.next();

}

@Test

public void testSingleFile() throws Exception {

assertTrue(singleIterator.hasNext());

File f = singleIterator.next();

assertEquals(tempFile, f);

}

@Test

public void testEmptyDirectory() throws Exception {

assertTrue(emptyDirIterator.hasNext());

File f = emptyDirIterator.next();

assertEquals(emptyDir, f);

}

@Test(expected = NoSuchElementException.class)

public void testEmptyDirectoryException() throws Exception{

assertTrue(emptyDirIterator.hasNext());

emptyDirIterator.next();

emptyDirIterator.next();

}

@Test

public void testLeafDirIterator() throws Exception {

assertEquals(leafDir, leafDirIterator.next());

assertEquals(new File(leafDir, "bar.exe"), leafDirIterator.next());

assertEquals(new File(leafDir, "foo.txt"), leafDirIterator.next());

}

@Test

public void testNestedDirIterator() throws Exception {

assertEquals(tempDir, nestedDirIterator.next());

assertEquals(new File(tempDir, "a.txt"), nestedDirIterator.next());

assertEquals(emptyDir, nestedDirIterator.next());

assertEquals(subDir, nestedDirIterator.next());

assertEquals(new File(tempDir, "z.exe"), nestedDirIterator.next());

assertEquals(leafDir, nestedDirIterator.next());

assertEquals(new File(subDir, "yahoo"), nestedDirIterator.next());

assertEquals(new File(leafDir, "bar.exe"), nestedDirIterator.next());

assertEquals(new File(leafDir, "foo.txt"), nestedDirIterator.next());

assertFalse(nestedDirIterator.hasNext());

}

}

Today, 13:50 Yesterday, 14:32 Yesterday, 14:32 Mar 6, 2015, 13:02 Mar 6, 2015, 13:02 Mar 6, 2015,13:02 Mar 6, 2015, 13:02 Mar 6,2015, 13:02 algorithms RecursiveMath.java hanoi ArrayBasedHanoiBoard.java RecursiveHanoiSolver.java jStackBasedHanoiPeg.java Today, 13:50 Yesterday, 14:32 Yesterday, 14:32 Mar 6, 2015, 13:02 Mar 6, 2015, 13:02 Mar 6, 2015,13:02 Mar 6, 2015, 13:02 Mar 6,2015, 13:02 algorithms RecursiveMath.java hanoi ArrayBasedHanoiBoard.java RecursiveHanoiSolver.java jStackBasedHanoiPeg.java