CODE IS MOSTLY COMPLETE. THERE ARE A FEW FIELD THAT NEED TO BE FINISHD, SOURCE IS ATTACHED
In this assignment, you will use two different data structures to index the content of a disk filesystem and then use the index to locate files, similarly to the way the GNU locate utility operates.
Your solution will consist of a single file that contains the main function and all other classes and functions that build the index and then let you search it. Your solution should be in standard C++ and avoid any compiler-specific language constructs or features.
1)A disk filesystem consists of hierarchically arranged directories containing other directories and files. Thus, a filesystem is a multiway tree that stems from its root directory (specified as ":/" in Windows or as "/" in Linux). Its internal nodes are directories, its leaf nodes are files. Every node in the filesystem tree has a name. We will also use the term item to describe any node, whether it is a directory or a file. An item’s path is a string that includes concatenated names of all directory nodes from the root of the filesystem tree to the item. We will use the slash character ("/") to separate individual directory names that constitute a path name.
For example, in Linux, the directory listing program "ls" (which incidentally serves the same purpose as our directory container/iterator type pair) is located two levels down from the root, in the directory named "/usr/bin", and the path name of the "ls" executable file is "/usr/bin/ls".
Your first task is to build a filesystem index using one of the four associative STL container types you are familiar with. (Note that there is only one correct choice of the container type.) The container will use item names as keys. The value stored in each element of the container will be the directory path that specifies the location of the item corresponding to the element. For the previously mentioned "/usr/bin/ls", the container element corresponding to this file would have "ls" as its key and "/usr/bin" as its value.
Your main() function will prompt the user to enter the starting point in the filesystem as a path name, and an item name to look for. It will then iterate the filesystem subtree, beginning at the specified starting point, and build an index of all items in the subtree. Learn how to use the directory class and its iterator to traverse the subtree using a recursive function. Once the index is complete, report the number of items indexed, and perform a search of the index for the item specified by the user. Report the result by either printing "Item(s) not found" or reporting the name of the directory in which the item was found.
Important: There may be more than one item matching the name specified by the user. Make sure that your index is capable of locating all files with the specified name, and that you report all found files to the user.
Note: Remember to keep your code neatly formatted and readable. Define and use typedefs for all container related types, such as the container type, the const and/or non-const iterator type, and any other typename that would be complex enough, given its template parameter types.
2)Write a binary search tree class that can serve as another data structure for indexing a filesystem. It must use the same keys (item names) and values (directory paths) as the STL container you used in part 1 of this assignment. Add another section to your main() function that will again prompt the user for the same two inputs, populate your binary search tree with filesystem items using the same recursive traversal as in part 1, and search for the user-specified item by its name. Remember that the binary search tree must be able to accommodate multiple directory paths for any particular item name that occurs more than once within the indexed filesystem.