Important note: to solve this exercise, we provided you with some resources.

Before you begin reading the exercise, download the packed zip file from here.

Whenever the exercise text refers to this file, it will be highlighted with a yellow marker.

·         Practicing text file handling.

·         Practicing throwing IllegalArgumentException on invalid arguments.

·         Practicing StringBuilder.

·         Practicing String and File Scanners.

·         Understanding and practicing the Stack data structure.

·         Further practicing of algorithms.

·         Practicing the doubly linked list data structure.

·         Further practicing of utility class and static methods.

·         Understanding the role of common comparison methods.

·         Understanding the structure and throwing of custom exceptions.

·         Further practice of testing programs.

 

The SearchEngine class is a simple text search engine with a twist. When constructing a SearchEngine object, the search engine reads a text file and saves the text internally. The only functionality the search engine supports is searching for a word in the text file. The returned value is a result set, where each result consists of two numbers:

·         The number of the line in which the search term was found.

·         The number of the word within the line in which the search term was found.

(Notes: both results are zero-based. Also, the search engine supports searching for words only, not free text).

The twist, cache memory

To improve the search performance, the search engine supports cache. A cache is a data structure in memory, which saves the searches conducted by the search engine. Once a search is invoked, the engine first checks if an identical search term has been searched lately. If it has, there is no need to search the entire text from the beginning, but rather return the result saved in the cache memory. However, if this is the first time this specific search is conducted, the engine will scan the entire text, and then cache the results.

To improve the efficiency of common searches, the cache is implemented using a LIFO mechanism; the latest search term conducted will be the first to be found in the cache. The most natural LIFO data structure is the Stack.

Note: our search engine can be constructed with cache support or without.

Example:

Search term

Text scan required?

Cache state after

Remarks

<CONSTRUCTION>

<EMPTY>

Start with an empty cache.

“int”

Yes

“int”

Push “int” to the stack

“return”

Yes

“return”

“int”

Push “return”

“int”

No

“int”

“return”

Result popped. “int” moved to top.

“long”

Yes

“long”

“int”

“return”

Push “long”

“return”

No

“return”

“long”

“int”

Result popped. “return” moved to top.

Inspect both classes (in your resources file) SearchResult.java and SearchResults.java. Study both classes; the design, the implementation and the behavior. See how they validate the method parameters and throw the IllegalArgumentException (you will do so yourself later).

Write a class called SearchEngine in the same package (searchengine). The class represents the entire search engine. Use the following instance variables (you can add more if you wish):

·         private String text;

·         private Stack<SearchResults> cache = null;

 Implement the following API (can also be found here):

·         public SearchEngine(String filename, boolean useCache)

o   Don’t forget to validate the parameters (filename in this case).

o   Use a StringBuilder to build the string from the text file.

o   useCache is just a flag you will use in the search method. Choose your own way of saving this flag.

·         public SearchResults search(String searchTerm)

o   Don’t forget to validate the parameter!

o   The algorithm should be as follows:

§  Realize whether cache is applicable or not (depending on the parameter passed to the constructor).

§  If the cache is applicable, inspect the cache first to find previous searches of the same search term.

§  If the search term was found in cache, move the result set to the top of the cache and return it.

§  If the search term had not been cached before, or caching is not applicable, look for the search term in the entire text.

§  If found, cache the results (if applicable) and return.

·         public Stack<SearchResults> getCache()

o   So that the tutors can inspect your internal variables (in the real world, this is considered bad design).

o   Just return the reference to cache.

·         You may (and probably should) design some private methods to better divide your solution. You may not, of course, add any public member.

·         Java’s implementation of Stack provides many methods. However, to use the cache, you may only use these (all or some) Stack methods: empty, push, pop, peek and size. The Stack API is given here.

·         In both methods, if any of the parameters is invalid, throw the IllegalArgumentException. Use the constructor which accepts a String to add a descriptive message about the error.

·         To test your program you can use any text file. We provide you with sched.c (in the resources file). It’s the part of the Linux operating system kernel that is in charge of the system scheduling (written in the C language).

 

Consider the given classes Company and CompanyList (copy them to your working folder):

·         Company represents a publicly traded company (a real corporation). It’s also implemented as an element of a doubly linked list.

·         CompanyList is a collection of publicly traded companies. It holds a head reference which points to the beginning of a doubly linked list of references to Company objects.

Here are some more background pointers:

·         The Company class is missing 2 important methods, which you will have to implement. These methods compare one company against another. Such methods are mandatory when we want to sort or search collections.

·         We can compare two companies by the company names (lexicographically), the number of employees or their market capitalization. To decide on the comparison, we have the enum named ComparisonKey. Use it wisely.

·         You will have to write a utility class which implements some algorithms to manipulate a doubly linked list of companies.

·         You’re also provided with your first custom exception, which, for now, we have written for you. Find EmptyListException.java in the resources file and copy it to your project. In future exercises you will be asked to write your own exceptions, which will look similar to this one.

·         The API of this entire section is given here.

Copy the utility class StockMarketAlgorithms.java from the resources file. We provided you the class with the following implementation:

1.       A partial testing main.

2.       The full implementation of the addCompany method.

3.       A private method which finds the last company in a list.

The class includes enough information to give you a real push as to how to write the rest of the methods.

Class Company

In class Company, implement the following public methods. Both should return a boolean result, and never throw an exception:

·         equals(Company other, ComparisonKey key)

·         greaterThan(Company other, ComparisonKey key)

Class CompanyList

Implement the following:

·         public int size()

Utilitiy class StockMarketAlgorithms

Complete the implementation of StockMarketAlgorithms in package stockmarket. Implement the following public static methods (description in the API):

·         Company getCompany(CompanyList list, String companyName)

·         void removeCompany(CompanyList list, String companyName)

·         void reverseList(CompanyList list)

·         void sortList(CompanyList list, Company.ComparisonKey key)

·         void insertInOrder(CompanyList list, Company company, Company.ComparisonKey key)

Bonus 5 points:

·         boolean hasLoops(CompanyList list)

 

·         Modify the given main method so that it will test your code thoroughly. Consider both normal and esoteric cases, such as handling an empty list, a list with a single company, changing the first/last company, and others.

·         Submit the main along with the class. You will be graded according to how this method covers all cases and how lovely it looks with comments and printouts.

·         You can use a real list of publicly traded companies given here.

·         We suggest that you first code all the method definitions so that your code compiles. You can then fill them with the ‘beef’ (correct algorithms) one by one.

·         Some methods require parameter validation. As in the previous section, if you encounter an invalid parameter, throw an instance of IllegalArgumentException with a descriptive error message.

·         Think where throwing the EmptyListException is most appropriate, and throw it there.

·         Note that since both IllegalArgumentException and EmptyListException are both of type RuntimeException (unchecked), you do not have to change the signature of the throwing method.

Submit both a hard copy and a soft copy. Both copies should be submitted on time. Late submissions will not be checked.

Hard and soft copies should be completely identical!

The soft copy should consist of a single file called Ex08.zip, with the given structure below, and emailed as usual:

·         Ex08.zip (file):

o   searchengine (folder):

§  SearchEngine.java

o   stockmarket (folder):

§  Company.java

§  CompanyList.java

§  EmptyListException.java

§  StockMarketAlgorithms.java (including the main)

 

Good luck, ninjas!

 

© 2010 Boaz Kantor