// Archibald Haddock (123456789)
// COMP 202-A, Section 0 (Fall 2006)
// Instructor: Cuthbert Calculus
// Assignment 4, Question 2
// MODEL SOLUTION

/**
 * A <code>BookList</code> object is an array-backed container class which can
 * be used to store <code>Book</code> objects. It enables the programmer to
 * insert <code>Book</code> objects in a <code>BookList</code>, retrieve
 * the <code>Book</code> at some position in a <code>BookList</code>, and
 * determine whether the <code>BookList</code> contains a <code>Book</code>
 * object with a given title.
 * 
 * Note that internally, a <code>BookList</code> keeps <code>Book</code>
 * object sorted by title in alphabetical order. Thus, inserting a
 * <code>Book</code> object in a <code>BookList</code> always inserts at the
 * proper position.
 * 
 * A <code>BookList</code> can contain as many <code>Book</code> objects as
 * the Java Virtual Machine will be able to allocate memory for.
 */
public class BookList {
	// The array which will contain book references.
	private Book[] bookList;

	// The number of book references currently stored in the array. May be less
	// than the size of bookList.
	private int size;

	/**
	 * Creates a new <code>BookList</code> containing no <code>Book</code>
	 * objects.
	 */
	public BookList() {
		this.bookList = new Book[10];
		this.size = 0;
	}

	/**
	 * Returns the number of <code>Book</code> objects currently stored in
	 * this <code>BookList</code>.
	 * 
	 * @return The number of <code>Book</code> objects currently stored in
	 *         this <code>BookList</code>.
	 */
	public int getSize() {
		return this.size;
	}

	/**
	 * Returns the <code>Book</code> object currently stored at position
	 * <code>index</code> within the <code>BookList</code>.
	 * 
	 * @param index
	 *            An index in the <code>BookList</code>
	 * @return The <code>Book</code> object currently stored at position
	 *         <code>index</code> in the <code>BookList</code>.
	 */
	public Book get(int index) {
		return this.bookList[index];
	}

	/**
	 * Determines whether this <code>BookList</code> currently contains
	 * <code>Book</code> objects.
	 * 
	 * @return <code>true</code> if this <code>BookList</code> currently
	 *         contains no <code>Book</code> objects, <code>false</code>
	 *         otherwise.
	 */
	public boolean isEmpty() {
		return (this.size == 0);
	}

	/**
	 * Inserts a <code>Book</code> object in the <code>BookList</code>.
	 * This method ensures that the <code>Book</code> objects are always
	 * sorted by title within the <code>BookList</code>.
	 * 
	 * @param book
	 *            The <code>Book</code> object to be inserted in the
	 *            <code>BookList</code>.
	 */
	public void insert(Book book) {
		int position;
		int i;
		int stopPoint;
		boolean found;
		Book[] destination;

		// Determine the position at which the new Book should be inserted.
		found = false;
		i = 0;
		while ((i < this.size) && !found) {
			if (book.compareTo(this.bookList[i]) < 0) {
				found = true;
			} else {
				i = i + 1;
			}
		}
		position = i;

		// Determine whether the array should be grown or not.
		if (this.size == this.bookList.length) {
			destination = new Book[this.bookList.length * 2];
			stopPoint = 0;
		} else {
			destination = this.bookList;
			stopPoint = position;
		}

		// Move Book objects within the array to make room for the new Book
		// object. Also copy all Book references to the new array if the old
		// one needed to be regrown.
		i = this.size - 1;
		while (i >= stopPoint) {
			if (i >= position) {
				destination[i + 1] = this.bookList[i];
			} else {
				destination[i] = this.bookList[i];
			}
			i = i - 1;
		}
		this.bookList = destination;

		// Insert the new Book object and increment the size counter.
		this.bookList[position] = book;
		this.size++;
	}

	/**
	 * Search for a <code>Book</code> object within this <code>BookList</code>,
	 * and return it if it exists.
	 * 
	 * @param title
	 *            The title of the <code>Book</code> object to be searched
	 *            for.
	 * @return The <code>Book</code> object being searched for,
	 *         <code>null</code> if this <code>BookList</code> does not
	 *         contain a <code>Book</code> object with this title.
	 */
	public Book search(String title) {
		Book book;
		int low;
		int high;
		int middle;
		int comparison;

		low = 0;
		high = this.size - 1;
		book = null;

		// We stop once we found the book (wt which point variable book is no
		// longer null) or once the searching area has been reduced to nothing
		// (at which point low becomes greater than high).
		while ((book == null) && (low <= high)) {
			// Compute the middle point.
			middle = (low + high) / 2;
			comparison = title.compareToIgnoreCase(this.bookList[middle]
					.getTitle());
			if (comparison == 0) {
				// This is what we were looking for.
				book = this.bookList[middle];
			} else {
				if (comparison < 0) {
					// What were are looking for occurs before the middle book.
					// Move the high pivot.
					high = middle - 1;
				} else {
					// What were are looking for occurs after the middle book.
					// Move the low pivot.
					low = middle + 1;
				}
			}
		}
		return book;
	}
}