Project 2: Virtual Directory Trees

In this project, you and your partner will complete the binary search tree (BST) implementation you started in lab 7. You will also implement a few functions for a shell that supports the creation of a virtual directory hierarchy where there is a root directory, /, that can contain zero or more subdirectories each of which can contain zero or more subdirectories and so on.

Goals for this project

By the time you have completed this project, you should:

  • fully understand the use and implementation of a binary search tree
  • understand how to use recursion to traverse a binary tree
  • be comfortable working with a general tree (a directory can have any number of subdirectories)

Project Preparation

To begin create a proj2 directory (assuming you haven’t already done so):

mkdir -p cs24/proj2

Change into the proj2 directory and copy the files you will need for this project:

cd cs24/proj2
cp ~bboe/public_html/cs24_f13/code/proj2/* .

The first thing you will want to do is copy the appropriate functions from your lab 7 bst.cpp to the bst.cpp for this project.

Building and testing the project

To build the project run:

make

If successful that will produce virtual_directory which you can run via:

./virtual_directory

This program has its own set of commands which you can list via the command help. You will need to implement each of those additional commands (by default they do nothing).

Understanding the assignment

The first thing you will want to do is understand what it is your are attempting to build. The files you copied contains a reference implementation that will run on the CSIL machines. Below is a complete sample execution of the reference implementation:

$ ./reference
> ls
> mkdir foo
> ls
foo 
> pwd
/
> mkdir blah
> mkdir zebra
> ls
blah foo zebra 
> cd foo
foo> mkdir bar
foo> cd bar
bar> pwd
/foo/bar
bar> cd ..
foo> cd ..
> rmdir foo
> ls
blah zebra 

Understanding the code

There are two core pieces of code you need to understand. The first is virtual_directory.cpp. This file contains the code that converts the user input into the commands to work with the virtual directory tree. All the code to handle the user input has already been written, however, you need to take note of how the input is converted into functions that you are to write. Also pay particular attention to the fact that the root directory is created on start-up and that the variable cwd points to the current (or sometimes called present) working directory.

That brings us to the second important part of the code, directory.h. In this file you will see the interface for the Directory class. The three attributes of a Directory are its name, its parent and its subdirs or subdirectories. Note is that we are using our BST class to store pointers, well wrapped pointers (for comparison and output purposes), to other Directory instances. Recall that a BST as well as a List is an implementation of a generic container ADT. We are using the BST because we want (1) ordered listings and (2) better than O(n) insertion, look-ups and removals. Avoid confusing the general tree of directories, and the BST that is used to merely hold a set of subdirectories.

The functions you must write in virtual_directory.cpp should directly interact with functions that are part of the Directory class. You must write some of those functions (in directory.cpp) many of which will interact with the BST class.

Suggested Approach

Before beginning make sure you received 100% on lab 7 as this assignment depends on your BST::insert and BST::~BST working properly. The following is the approach I suggest you take in completing this assignment as there are a lot of dependencies between parts (e.g., rmdir cannot be tested until both mkdir and ls work 100%).

Part 1 (Goal: complete by Friday, November 15)

1: ls and mkdir

The first thing to do is to get the commands ls and mkdir to work properly. This will allow you add to root’s (/) subdirectories and produce the correct output. You should be able to pass all the root_mkdir tests in addition to a few others (~12/55) on the submission system at this point.

Note: You will need to use recursion over the BST of subdirectories in order to output the items in the sorted order. You can skip the sorting until later if you wish. In such a case you will want to use either a stack or queue to output all the nodes. This will allow you to verify that your other operations work. However, you won’t be able to pass many tests on the submission system.

2: cd

Once you can list directories you need to implement the cd command to change directories. After completing this function you should additionally pass all the mkdir_chrdir tests (~22/55).

3: pwd

Finally write the functionality for the pwd command. At this point you should pass just under half of the tests (~26/55) and have a pretty good feel for how all the pieces interact.

Part 2: Start after part 1 is complete

The second part of the assignment is technically much more difficult than the first, despite only having one more command, rmdir, to implement.

1: rmdir

Implement everything necessary to remove a subdirectory. You will need to complete the BST::remove function for this to work properly. You must use recursion (you will need a helper function) to complete this process. (You can also implement it iteratively if you so desire but you must demonstrate that you can do it recursively).

When rmdir is completed you should pass 52/55 of the tests (assuming everything works up to this point).

2: Directory::~Directory

The last thing to do is to make sure that when a Directory is deallocated it does not leak any memory. Completing this part will reward you with those last three points.

Extra Credit

Once you receive 100% you can implement additional commands for up to 15% extra credit (2.1% of the overall grade). The amount of extra credit will depend on the quantity and relative difficulty of the extra commands. Please message “instructors” on Piazza to discuss any extra credit ideas you may have.

Submitting the project

Please review the submission instructions as needed. On the submission site you will find the command you need to use to submit the project. Note that you may resubmit this project as many times as necessary up until the deadline. If you are working with a partner, make sure to group up using the submission system.

 

Template design by Andreas Viklund