File Searching Homework

CSS 162 : Programming Methodology

Assignment by Rob Nash

Recursively Searching Files & Directories

Summary

Build a class and a driver for use in searching your computers secondary storage (hard disk or flash

memory) for a specific file from a set of files indicated by a starting path. Lets start by looking at a

directory listing. Note that every element is either a file or a directory.

Introduction & Driver

In this assignment, your job is to write a class that searches through a file hierarchy (a tree) for a

specified file. Your

FindFile

class will search a directory (and all subdirectories) for a target file name.

For example, in the file hierarchy pictured above, the file lesson.css will be found once in a directory

near the root or top-level drive name (e.g. C:\) . Your

FindFile

class will start at the path indicated and

will search each directory and subdirectory looking for a file match. Consider the following code that

could help you build your

Driver

.java:

String targetFile = lesson.css;

String pathToSearch =C:\\WCWC;

FindFile finder = new FindFile(MAX_NUMBER_OF_FILES_TO_FIND);

Finder.directorySearch(targetFile, pathToSearch);

File Searching

In general, searching can take multiple forms depending on the structure and order of the set to search.

If we can make promises about the data (this data is sorted, or deltas vary by no more than 10, etc.),

then we can leverage those constraints to perform a more efficient search. Files in a file system are

exposed to clients of the operating system and can be organized by filename, file creation date, size, and

a number of other properties. Well just be interested in the file names here, and well want perform a

brute force (i.e., sequential) search of these files looking for a specific file. The way in which well get

file information from the operating system will involve no ordering; as a result, a linear search is the best

we can do. Wed like to search for a target file given a specified path and return the location of the file,

if found. You should sketch out this logic linearly before attempting to tackle it recursively.

FindFile Class Interface:

FindFile(int maxFiles)

o

This constructor accepts the maximum number of files to find.

void directorySearch(String target, String dirName)

o

The parameters are the target file name to look for and the directory to start

in.

int getCount()

o

This accessor returns the number of matching files found

String[] getFiles()

o

This getter returns the array of file locations, up to maxFiles in size.

Requirements

Your program should be recursive.

You should build and submit at least two files:

FindFile

.java,

Driver

.java,

Throw an exception (IllegalArgumentException) if the path passed in as the starting directory is

not a valid directory.

Throw an exception if youve found the MAX_NUMBER_OF_FILES_TO_FIND, and catch and

handle this in your main driver.

o

Youre program shouldnt crash, but rather exit gracefully in the unusual situation that

weve discovered the maximum number of files we were interested in, reporting each of

the paths where the target files were found.

The only structures you can use in this assignment are basic arrays and your Stack,

Queue, or ArrayList from the previous homeworks.

o

Do not use built-in data structures like ArrayList.

o

To accomplish this, add the following constructor to your ArrayList, Stack, or

Queue

public ArrayList(Object[] input) {

data = input;

numElements = input.length;

}

public Object get(int index) {

return data[index];

}

Notes and Hints

Consider looking into the File class in Java for helpful methods like isDirectory() and toString().

o

http://docs.oracle.com/javase/7/docs/api/java/io/File.html

o

Useful File details have been taken from the link above and copied here for reference

import java.io.File;

Import the File class to use it.

File f = new File(dirName);

Next, create a File object.

String[] fileList = f.list()

This list files in current directory as Strings

File aFile = new File(dirName + "\\" + fileList[i]);

Notice the concatenation in the new File object

if (aFile.isDirectory()) {

check whether it is a directory

Test your FindFile.java class.

o

Try to find a file that exists once

o

Try to find a file that doesnt exist

o

Try to find a file that exists twice

o

Try to find a file that exists MAX_NUMBER_OF_FILES_TO_FIND

o

...

In your recursive call, make sure you dont loose the directory path by concatenating it with the

file name.

Recursive Binary Search Homework

CSS 162: Programming Methodology

Instructor Lesley Kalmin

Assignment by Rob Nash

Summary

Build two classes (LinearSearch ,BinarySearch) that inherit from the provided parent class

SearchAlgorithm, and a third exception class. Each of the subclasses classes will implement only one

public method that facilitates the appropriate search over an array of Strings. Also, you will need to

build one exception class (10 lines of code or less) that services these two searches in the event the item

isnt found in the String array.

Introduction

The best introduction to this homework is probably to start in the BinSearchDriver code that will be used

to test your two search classes. Walking through this code, you can see that we will create two objects

for use in searching through a large array of words. This array is populated from a sequential text file

(longwords.txt), and all of this code is written for you in the driver. Your job is to construct two

subclasses

that derive from the superclass SearchAlgorithm; these two classes will each need to provide

a version of the abstract search method declared in SearchAlgorithm. Note that you will not need to

change any of the code in main for the driver, and in fact, should only need to modify the

FILE_AND_PATH class constant to point at your local version of the input file (longwords.txt). Beyond

that, the driver is self-contained, and should compile and execute without modification once your two

classes {BinarySearch, LinearSearch} are built and in the same working directory. Lets discuss the two

subclasses more in detail next, starting with an item-by-item (linear) search.

The LinearSearch Class

This class should loop through the words from beginning to end, comparing the current string with the

target string at each step. Note that you must call the utility function incrementCount() each time you

make a comparison (ie, each time in the loop) so that when your search is complete, you have an

accurate count of the comparisons required by your search strategy. You must implement this

iteratively and then attempt to implement this recursively. Report on the results in your submission.

The BinarySearch Class

The binary search algorithm can be accomplished in a number of ways, but the basic algorithm is

outlined below. You must implement this

recursively

.

LowIndex = 0

HighIndex = arraySize 1

While LowIndex is less than or equal to HighIndex

Set MidIndex to be equal to half way between the low and high index

If the target word matches the word at MidIndex, return MidIndex (first case)

If the target word is before the word at MidIndex, then set HighIndex to MidIndex - 1

If the target word is after the word at MidIndex, then set LowIndex to MidIndex + 1

If the target word was not found, throw an ItemNotFoundException (you create this class)

The ItemNotFoundException Class

This class should be under 15 lines of code, and is an exercise in inheriting from classes provided to you

by the Java API. Your class should have only two methods (both constructors) and no data items; see

the slides on exceptions for an example of such a class.

Recursion

Provide the iterative implementation for the linear & binary search in the search() methods that you

override, and put the recursive versions of these same methods in the recSearch() methods,

respectively. Note that you must extend the driver to call your recursive functions!

Notes

Your classes

must

inherit from the SearchAlgorithm class to compile and run.

Use the extra utility functions in SearchAlgorithm to track the number of comparisons

that have been executed in each search.

Interested in determining if string1 comes before string2 alphabetically? This ordering

can be determined using the compareTo() function; if string1.compareTo(string2)

returns a positive int, then string 1 > string2. If negative, then string1 < string2.

If you fail to find the target word in the set, be sure to throw an ItemNotFoundException

Your three classes will be graded by compiling them with the provided SearchAlgorithm

and BinSearchDriver classes

without modification

/**

* Linear and Binary Search Homework 5 Driver

*

* Note that nothing in this class needs to be changed except for your

FILE_AND_PATH variable

*

* Implement the Binary Search using both the iterative and recursive

techniques covered

* in class

*/

import java.io.File;

import java.io.FileNotFoundException;

import java.util.ArrayList;

import java.util.Scanner;

public class BinSearchDriver {

public final static String FILE_AND_PATH = "c:\\longwords.txt";

/*

* TODO: Be sure to change the FILE_AND_PATH to point to your local

* copy of longwords.txt or a FileNotFoundException will result

*/

//Note how we deal with Java's Catch-or-Declare rule here by

declaring the exceptions we might throw

public static void main(String[] args) throws FileNotFoundException

{

Scanner input = new Scanner(new File(FILE_AND_PATH));

int wordCount = 0;

ArrayList theWords = new ArrayList();

//read in words, count them

while(input.hasNext()) {

theWords.add( input.next() );

wordCount++;

}

//make a standard array from an ArrayList

String[] wordsToSearch = new String[theWords.size()];

theWords.toArray(wordsToSearch);

//start with the linear searches

tryLinearSearch(wordsToSearch, "DISCIPLINES");

tryLinearSearch(wordsToSearch, "TRANSURANIUM");

tryLinearSearch(wordsToSearch, "HEURISTICALLY");

tryLinearSearch(wordsToSearch, "FOO");

//and compare these results to the binary searches

tryBinarySearch(wordsToSearch, "DISCIPLINES");

tryBinarySearch(wordsToSearch, "TRANSURANIUM");

tryBinarySearch(wordsToSearch, "HEURISTICALLY");

tryBinarySearch(wordsToSearch, "FOO");

}

/**

* Method tryBinarySearch

* precondition: wordsToSearch is a nonempty array of Strings, and

target is a non-null string to search for

* in our collection of strings

* postcondition: Uses a BinarySearch object (which implements this

style of search) to try to find the target string

*/

private static void tryBinarySearch(String[] wordsToSearch, String

target) {

//Todo: Build a LinearSearch class that inherits from

SearchAlgorithm, and put it in the same directory as this class to

successfully compile

SearchAlgorithm bs = new BinarySearch();

try {

System.out.print( target + " found at index:

" + bs.search(wordsToSearch,target));

System.out.println( " taking " +

bs.getCount() + " comparisons.");

}

catch( ItemNotFoundException e ) {

System.out.println( target + ":" +

e.getMessage());

}

}

/**

* Method tryLinearSearch

* precondition: wordsToSearch is a nonempty array of Strings, and

target is a non-null string to search for

* in our collection of strings

* postcondition: Uses a LinearSearch object to try to find the

target string

*/

private static void tryLinearSearch(String[] wordsToSearch, String

target) {

//Todo: Build a LinearSearch class that inherits from

SearchAlgorithm, and put it in the same directory as this class to

successfully compile

SearchAlgorithm bs = new LinearSearch();

try {

System.out.print( target + " found at index:

" + bs.search(wordsToSearch,target));

System.out.println( " taking " +

bs.getCount() + " comparisons.");

}

catch( ItemNotFoundException e ) {

System.out.println( target + ":" +

e.getMessage());

}

}

}

ZOOM

/**

*

* SearchAlgorithm

* A class used to delegate a search strategy or style

*

* @author: originally by cfolsen, this version modified by rnash

*/

public abstract class SearchAlgorithm {

/**

* Method search: a "to-be-defined" method used to implement a

specific search strategy over the given array looking for the target word

* Precondition: words is a nonempty array and target is a non-null

string

* Postcondition: if the target word is found, return its index.

* If not found, throw an ItemNotFoundException (a

subclass which you have to make)

*

*/

public abstract int search(String[] words, String wordToFind) throws

ItemNotFoundException;

public abstract int recSearch(String[] words, String wordToFind)

throws ItemNotFoundException;

/**

* Utility Features: This class can be used to track the number of

search comparisons

* for use in comparing two different search

algorithms

*/

private int count = 0;

public void incrementCount() {

count++;

}

public int getCount() {

return count;

}

public void resetCount() {

count = 0;

}

}