Solution #8

8.1 SearchEngine.java

package searchengine;

 

import java.io.File;

import java.io.FileNotFoundException;

import java.util.Scanner;

import java.util.Stack;

 

/**

* Represents a search engine which supports searching words in a text file.

* To improve the search performance, a search cache is maintained and used.

*/

public class SearchEngine {

 

/** Denotes a String newline */

private static final String NEWLINE = "\n";

// instance variables

private String text;

private Stack<SearchResults> cache = null;

 

/**

* Constructs a new search engine object which supports searching terms in

* the given text file.

* Reads the text from the given file.

* @param filename the name of the text file to later conduct searches in.

* @param useCache denotes whether this search engine object should

* maintain an internal cache or not.

* @throws IllegalArgumentException if filename is null or blank.

*/

public SearchEngine(String filename, boolean useCache) {

// validate parameters

if (filename == null || filename.trim().length() == 0) {

throw new IllegalArgumentException("null or blank file name.");

}

 

// read the file into text

StringBuilder sb = new StringBuilder();

try {

Scanner fileScanner = new Scanner(new File(filename));

while (fileScanner.hasNextLine()) {

sb.append(fileScanner.nextLine() + NEWLINE);

}

} catch (FileNotFoundException e) {

System.out.println("File " + filename + " not found.");

System.exit(0);

}

this.text = sb.toString();

// maintain cache?

// STUDENT NOTE: you may also use a boolean instance variable instead.

if (useCache) {

cache = new Stack<SearchResults>();

}

}

 

/**

* Searches the text for a given search term.

* @param searchTerm the term to search for (case sensitive).

* @return the search result set, null if the search term was not found.

* @throws IllegalArgumentException if the search term is null or blank.

*/

public SearchResults search(String searchTerm) {

// validate parameters

if (searchTerm == null || searchTerm.trim().length() == 0) {

throw new IllegalArgumentException("Can't search an empty term.");

}

SearchResults results = null;

boolean useCach = (cache != null);

// search in cache first (when applicable)

if (useCach) {

results = searchInCache(searchTerm);

if (results != null) {

cache.push(results);

return results;

}

}

// no cache is used or the search does not exist in the cache

results = searchInText(searchTerm);

// cache the results if applicable

if (useCach) {

cache.push(results);

}

return results;

}

 

/**

* Returns a reference to the internal cache.

* Note: this is bad design, but it's mandatory for our tutors to inspect

* your internal implementation.

* @return a direct reference to your cache.

*/

public Stack<SearchResults> getCache() {

return cache;

}

 

/**

* Conducts a full text search of the search term in the text file.

* @param searchTerm the term to search (case sensitive)

* @return a reference to the result set, null if the term was not found.

*/

private SearchResults searchInText(String searchTerm) {

SearchResults results = new SearchResults(searchTerm);

Scanner textScanner = new Scanner(text);

int lineNumber = 0;

// scan line by line

while (textScanner.hasNextLine()) {

lineNumber++;

int wordNumber = 0;

Scanner lineScanner = new Scanner(textScanner.nextLine());

// scan word by word in each line

while (lineScanner.hasNext()) {

wordNumber++;

String word = lineScanner.next();

// compare the word in the text to the search term

if (word.equalsIgnoreCase(searchTerm)) {

// the search term was found!

results.getResults().add(

new SearchResult(lineNumber, wordNumber));

}

}

}

return results;

}

 

/**

* Performs a cache search.

* @param searchTerm the term to search (case sensitive).

* @return a reference to the result set, null if the term was not found.

*/

private SearchResults searchInCache(String searchTerm) {

// make sure cache is initialized (optional)

if (this.cache == null) {

this.cache = new Stack<SearchResults>();

return null;

}

 

boolean found = false;

SearchResults searchResults = new SearchResults(searchTerm);

Stack<SearchResults> tempCache = new Stack<SearchResults>();

SearchResults currResults = null;

 

// pop until we find the element

while (cache.size() > 0) {

currResults = cache.pop();

// compare the current result set with the given search term

if (currResults.equals(searchResults)) {

// we found the search term in the cache!

found = true;

break;

} else {

// keep whatever we pop in a temporary stack

tempCache.push(currResults);

}

}

 

// return everything we popped back to the cache

while (tempCache.size() > 0) {

cache.push(tempCache.pop());

}

 

if (found) {

return currResults;

}

 

// the cache does not contain a result set which corresponds to the

// given search term

return null;

 

}

}

 

8.2 Company.java

package stockmarket;

 

/**

* Represents a publicly traded company.

*/

public class Company {

 

/**

* Represents a key by which a comparison between two companies can be made.

*/

public enum ComparisonKey {

COMPANY_NAME_CASE_INSENSITIVE,

NUMBER_OF_EMPLOYEES,

MARKET_CAP

}

 

// instance variables

private Company next; // the company that comes after this one

private Company prev; // the company that comes before this one

private String name; // the company name

private int numberOfEmployees; // the # of employees in this company

private double marketCap; // the market capitalization, in dollars

 

/**

* Constructs a new company object.

*

* @param name

* a non-empty string of the name of the company.

* @param numberOfEmployees

* a positive number denoting the number of employees working for

* this company.

* @param marketCap

* a positive number denoting the market capitalization of this

* company.

* @throws IllegalArgumentException

* if any of the arguments is invalid.

*/

public Company(String name, int numberOfEmployees, double marketCap) {

 

// validate parameters

if (name == null || name.trim().length() == 0 || numberOfEmployees <= 0

|| marketCap <= 0) {

throw new IllegalArgumentException("Invalid arguments.");

}

 

// set parameters

this.name = name;

this.numberOfEmployees = numberOfEmployees;

this.marketCap = marketCap;

 

// initialize defaults

setNext(null);

setPrev(null);

}

 

/**

* Gets the company name.

*

* @return the name of this company.

*/

public String getName() {

return name;

}

 

/**

* Sets the reference to the next company in the list.

*

* @param next

* the next company in the list, or null if this is the last

* company.

*/

public void setNext(Company next) {

this.next = next;

}

 

/**

* Gets the next company in the list.

*

* @return a reference to the next company in the list, or null if this is

* the last company.

*/

public Company getNext() {

return next;

}

 

/**

* Sets the reference to the previous company in the list.

*

* @param prev

* the previous company in the list, or null if this is the first

* company.

*/

public void setPrev(Company prev) {

this.prev = prev;

}

 

/**

* Gets the previous company in the list.

*

* @return a reference to the previous company in the list, or null if this

* is the first company.

*/

public Company getPrev() {

return prev;

}

 

/**

* Returns a string representation of this company.

*/

public String toString() {

return name + "($" + marketCap + "M," + numberOfEmployees + ")";

}

 

/**

* Compares this company with another. Two companies are defined as equal if

* their values are equal, respective to the comparison key.

*

* @param other

* the other company to compare to.

* @key the key to compare the companies by.

* @return true if the companies are equal, otherwise false.

*/

public boolean equals(Company other, ComparisonKey key) {

 

// validate parameters

if (other == null) {

return false;

}

 

// compare according to the key

switch (key) {

case COMPANY_NAME_CASE_INSENSITIVE:

return name.compareToIgnoreCase(other.name) == 0;

case MARKET_CAP:

return this.marketCap == other.marketCap;

case NUMBER_OF_EMPLOYEES:

return this.numberOfEmployees == other.numberOfEmployees;

default:

throw new IllegalArgumentException("Unsupported key: "

+ key.toString());

}

}

 

/**

* Compares this company with another and checks if this company is greater

* than another. The definition of greater depends on the comparison key.

* The key defines what value needs to be compared in order to decide if

* this company is larger or not.

*

* @param other

* the other company to compare to.

* @param key

* the key to compare by.

* @return true if this company is greater than the other (defined by the

* comparison key), otherwise false.

*/

public boolean greaterThan(Company other, ComparisonKey key) {

 

// validate parameters

if (other == null || key == null) {

return false;

}

 

// if they are equal, skip all comparisons

if (this.equals(other)) {

return false;

}

 

// compare according to the key

switch (key) {

case COMPANY_NAME_CASE_INSENSITIVE:

return name.compareToIgnoreCase(other.name) > 0;

case MARKET_CAP:

return this.marketCap > other.marketCap;

case NUMBER_OF_EMPLOYEES:

return this.numberOfEmployees > other.numberOfEmployees;

default:

throw new IllegalArgumentException("Unsupported key: "

+ key.toString());

}

}

 

}

 

8.2 CompanyList.java

package stockmarket;

 

/**

* Represents a doubly linked list of references to objects of type Company.

*/

public class CompanyList {

 

// instance variables

private Company head = null;

 

/**

* Sets the head of the list to the first company in the list.

*

* @param head

* the first company in the list, or null if the list is empty.

*/

public void setHead(Company head) {

this.head = head;

}

 

/**

* Gets the head, the first company in the list.

*

* @return reference to the first company in the list (pointed to by the

* head), or null if the list is empty.

*/

public Company getHead() {

return head;

}

 

/**

* Gets the company located at the given index (zero-based).

*

* @param index

* the index of the company to get.

* @return reference to the company located at the given index.

*/

public Company getCompany(int index) {

// validate parameters

if (index < 0 || index >= size()) {

throw new IndexOutOfBoundsException("Index is out of bounds.");

}

 

int currIndex = 0;

Company currCompany = head;

// iterate through the list to find the company

while (currCompany != null) {

if (currIndex++ == index) {

// we found the company!

return currCompany;

}

currCompany = currCompany.getNext();

}

 

// if we got here then we have a bug.

throw new RuntimeException("We have a bug.");

}

 

/**

* Gets the size of this list. The size of the list is defined as the number

* of elements in it.

*

* @return the size of this list, 0 if the list is empty.

*/

public int size() {

int size = 0;

Company currCompany = head;

// count all the companies in the list

while (currCompany != null) {

++size;

currCompany = currCompany.getNext();

}

return size;

}

 

/**

* Returns a string representation of the list.

*/

public String toString() {

 

// handle an empty list

if (head == null) {

return "Empty list";

}

 

// print the head

String result = ">>";

Company currCompany = head;

 

// print all the companies in the list

while (currCompany != null) {

result += " ==> ";

result += currCompany;

currCompany = currCompany.getNext();

}

 

return result;

}

}

 

 

8.2 EmptyListException.java

package stockmarket;

 

/**

* A runtime exception to be thrown when an operation is made on an empty list,

* and the operation on an empty list is unsupported.

*/

public class EmptyListException extends RuntimeException {

/**

* Constructs a new exception object with the given error message.

* @param message A descriptive error message.

*/

public EmptyListException(String message) {

super(message);

}

 

}

 

 

8.2 StockMarketAlgorithms.java

(does not include the main method)

package stockmarket;

 

import java.util.ArrayList;

 

import stockmarket.Company.ComparisonKey;

 

/**

* A utility class which provides functionality of various algorithms related to

* the doubly linked list of companies.

*/

public class StockMarketAlgorithms {

 

/**

* Adds a new company to the given list. The company is added to the end of

* the list.

*

* @param list

* the list to add the company to.

* @param company

* the company to add to the list.

*/

public static void addCompany(CompanyList list, Company company) {

// validate parameters

if (list == null || company == null) {

throw new IllegalArgumentException("Some parameters are null.");

}

 

// find the last company in the list

Company lastCompany = getLastCompany(list);

 

// handle an empty list

if (lastCompany == null) {

list.setHead(company);

company.setNext(null);

company.setPrev(null);

return;

}

 

// add the company to the end of the list

lastCompany.setNext(company);

company.setNext(null);

company.setPrev(lastCompany);

}

 

/**

* Returns a reference to a company with the given name in the given list,

* if such company exists in the list. The search is case insensitive.

*

* @param list

* the list to search the company in.

* @param companyName

* the name of the company to find.

* @return a reference to the company, or null if no such company found.

*/

public static Company getCompany(CompanyList list, String companyName) {

Company currCompany = list.getHead();

 

// iterate through the entire list

while (currCompany != null) {

 

// see if this current company is the one we're looking for

if (currCompany.getName().equalsIgnoreCase(companyName)) {

return currCompany;

}

 

// keep looking..

currCompany = currCompany.getNext();

}

 

// the company is not found in the list

return null;

}

 

/**

* Removes a company from the given list.

*

* @param list

* the list to remove the company from.

* @param companyName

* the name of the company to remove (case insensitive).

* @throws EmptyListException

* if the list is empty

*/

public static void removeCompany(CompanyList list, String companyName) {

 

// handle an empty list

if (list == null || list.getHead() == null) {

throw new EmptyListException("Can't remove an element "

+ "from an empty list");

}

 

// handle a non-empty list

Company listHead = list.getHead();

Company currCompany = listHead;

 

// iterate on the entire list

while (currCompany != null) {

 

// see if it's the company we're looking for

if (currCompany.getName().equalsIgnoreCase(companyName)) {

if (listHead == currCompany) {

 

// handle removal of first element in the list

list.setHead(currCompany.getNext());

listHead.getNext().setPrev(null);

 

} else if (currCompany.getNext() == null) {

 

// handle removal of last element in the list

currCompany.getPrev().setNext(null);

 

} else {

 

// remove the element from the list

currCompany.getPrev().setNext(currCompany.getNext());

currCompany.getNext().setPrev(currCompany.getPrev());

}

return;

}

currCompany = currCompany.getNext();

}

}

 

/**

* Reverses the oder of companies in a list. For example, the list:

*

* <pre>

* >>-->1-->2-->3-->||

* </pre>

*

* will become, after calling reverse:

*

* <pre>

* >>-->3-->2-->1-->||

* </pre>

*

* @param list

* the list whose elements order will be reversed

*/

public static void reverseList(CompanyList list) {

 

// validate parameters

if (list == null || list.getHead() == null) {

return;

}

 

Company currentCompany = list.getHead();

Company lastCompany = currentCompany;

 

// iterate on the entire list

while (currentCompany != null) {

Company next = currentCompany.getNext();

currentCompany.setNext(currentCompany.getPrev());

currentCompany.setPrev(next);

lastCompany = currentCompany;

currentCompany = next;

}

 

// don't forget the head!!

list.setHead(lastCompany);

}

 

/**

* Sorts the list in an ascending order, according to the given comparison

* key. For example, if the key is

* {@link ComparisonKey#COMPANY_NAME_CASE_INSENSITIVE}, the elements in the

* list will be sorted lexicographically.

*

* @param list

* the list to sort

* @param key

* the key according to which the list order should be determined

* @throws IllegalArgumentException

* if any of the parameters is null

*/

public static void sortList(CompanyList list, Company.ComparisonKey key) {

 

// validate parameters

if (list == null || key == null) {

throw new IllegalArgumentException("Null arguments.");

}

 

// no need to sort an empty list or a single element

if (list.getHead() == null || list.getHead().getNext() == null) {

return;

}

 

// STUDENTS NOTE: you can use any viable sorting algorithms here.

 

// sort using "Stupid Sort" (the simplest algorithm, yet not the most

// efficient. AKA Gnome Sort. Look it up).

int currPosition = 1;

while (currPosition < list.size()) {

Company currentCompany = list.getCompany(currPosition);

Company prevCompany = currentCompany.getPrev();

 

if (currentCompany.greaterThan(prevCompany, key)

|| currentCompany.equals(prevCompany, key)) {

 

// this couple is already ordered

currPosition++;

continue;

}

 

// swap them

Company theOneBefore = prevCompany.getPrev();

Company theOneAfter = currentCompany.getNext();

if (theOneBefore == null) {

list.setHead(currentCompany);

} else {

theOneBefore.setNext(currentCompany);

}

currentCompany.setPrev(theOneBefore);

if (theOneAfter != null) {

theOneAfter.setPrev(prevCompany);

}

currentCompany.setNext(prevCompany);

prevCompany.setPrev(currentCompany);

prevCompany.setNext(theOneAfter);

 

// it's possible that we messed the order of the previous

// couple. get back and recheck.

if (currPosition > 1) {

currPosition--;

}

}

}

 

/**

* Given a list, sorted according to the comparison key in an ascending

* order, adds a company to the list in the appropriate location.

*

* @param list

* the list to insert the company into, has to be sorted in an

* ascending order according to key.

* @param company

* the company to add to the list.

* @param key

* the key by which the order should be preserved.

*/

public static void insertInOrder(CompanyList list, Company company,

Company.ComparisonKey key) {

 

// validate parameters

if (list == null || company == null || key == null) {

throw new IllegalArgumentException("Arguments can't be null.");

}

 

// handle an empty list

if (list.getHead() == null) {

list.setHead(company);

company.setNext(null);

company.setPrev(null);

return;

}

 

Company nextCompany = list.getHead();

Company prevCompany = nextCompany;

 

// find the appropriate location

while (nextCompany != null && company.greaterThan(nextCompany, key)) {

prevCompany = nextCompany;

nextCompany = nextCompany.getNext();

}

 

if (prevCompany == list.getHead()) {

list.setHead(company);

company.setPrev(null);

} else {

prevCompany.setNext(company);

company.setPrev(prevCompany);

}

// update the previous company references

company.setNext(nextCompany);

 

// make sure it's not the tail of the list

if (nextCompany != null) {

nextCompany.setPrev(company);

}

}

 

/**

* Finds out whether the given list contains a loop. A list loop is defined

* as a case where no element points to 'null' as the next element, and

* there exists at least one element which is referenced by at least two

* elements as the 'next' reference.

*

* @param list

* the list to find a loop in.

* @return true if a loop was found in the list, otherwise false.

*/

public static boolean hasLoops(CompanyList list) {

 

// validate parameters

if (list == null || list.getHead() == null) {

return false;

}

 

// use an auxiliary array which holds every company we've encountered

// so far.

ArrayList<Company> scannedCompanies = new ArrayList<Company>();

 

Company currentCompany = list.getHead();

 

// iterate through the entire list

while (currentCompany.getNext() != null) {

 

// search the company in the companies list

if (scannedCompanies.contains(currentCompany)) {

 

// if this company is already in the array, it means we bumped

// into it in a previous iteration.

return true;

}

 

// we haven't encountered this company yet, so remember it for the

// future.

scannedCompanies.add(currentCompany);

 

currentCompany = currentCompany.getNext();

}

 

// if we got here, there are no holes in the list

return false;

}

 

/**

* Returns a reference to the last company in the list.

*

* @param list

* a non-null reference to a list of companies.

* @return a reference to the last company in the list, or null if the list

* is empty.

*/

private static Company getLastCompany(CompanyList list) {

 

// handle an empty list

if (list == null || list.getHead() == null) {

return null;

}

 

// handle a non-empty list

Company lastCompany = list.getHead();

while (lastCompany.getNext() != null) {

lastCompany = lastCompany.getNext();

}

 

return lastCompany;

}

}

 

 

2010 Boaz Kantor, IDC Herzliya