/* Introduction a l'informatique II (ITI 1521)
 * Introduction to Computing II (ITI 1121)
 */

/**
 * 
 * @author Marcel Turcotte, Universite d'Ottawa/University of Ottawa
 */

import java.util.NoSuchElementException;

public class Path {

	/** A constant to represent the line separator on the computer
	 *  running the program.
	 */

	public static final String NL = System.getProperty( "line.separator" );

	/** An instance variable to store the number of elements in this path
	 */

	private int size;

	/** A nested static class.  Linked Elements are used to store the
	 *  URLs of this path.
	 */

	private static class Elem {

		private String url;
		private Elem next;

		private Elem( String url, Elem next ) {
			this.url = url;
			this.next = next;
		}
	}

	/** Instance variable designating the <code>first</code> element
	 *  of this <code>Path</code>.
	 */

	private Elem first;

	/** Instance variable designating the <code>last</code> element of this
	 *  <code>Path</code>.
	 */

	private Elem last;

	/** Creates a new path that extends an existing path by one URL.
	 *
	 * @param partial a partial solution to the Web Crawler problem
	 * @param url the new last URL of this path
	 */

	public Path( Path partial, String url ) {

		if ( url == null ) {
			throw new IllegalArgumentException( "The URL cannot be null" );
		}

		first = last = null;
		size = 0;

		if ( partial != null ) {
			Elem p = partial.first;
			while ( p != null ) {
				// Two paths should not share elem objects, since any
				// change to the structure of one path would affect the
				// other, however, URLs, which are immutable objects can
				// be shared.
				Elem newElem = new Elem( p.url, null );
				size++;
				if ( last == null ) {
					first = newElem;
				} else {
					last.next = newElem;
				}
				last = newElem;
				p = p.next;
			}
		}

		Elem newElem = new Elem( url, null );
		size++;

		if ( last == null ) {
			first = newElem;
		} else {
			last.next = newElem;
		}
		last = newElem;
	}

	/** Returns the size of the path, i.e. the number of urls stored in the list.
	 *
	 * @return the length of the path
	 */

	public int size() {
		return size;
	}

	/** Returns <code>true</code> if this path contains the specified url.
	 *
	 * @param url whose presence in this path is to be tested
	 * @return <code>true</code> if this path contains the specified url
	 */

	public boolean contains( String url ) {
		Elem p = first;
		boolean found = false;
		while ( p != null && (! found) ) {
			if ( p.url.equals( url ) ) {
				found = true;
			} else {
				p = p.next;
			}
		}
		return found;
	}

	/** Returns the URL at the specified postion of the path
	 *
	 * @param pos index of the url to return
	 * @return the URL at the specified position in this path
	 * @throws <code>IndexOutOfBoundsException</code>
	 */

	public String getURL( int pos ) {
		if ( pos < 0 || pos > (size-1) ) {
			throw new IndexOutOfBoundsException( Integer.toString( pos ) );
		}
		Elem p = first;
		for ( int i=0; i<pos; i++ ) {
			p = p.next;
		}
		return p.url;
	}

	/** Returns the last URL of the path.
	 *
	 * @return the past URL in this path
	 * @throws <code>NoSuchElementException</code>
	 */

	public String getLastURL() {
		if ( last == null ) {
			throw new NoSuchElementException();
		}
		return last.url;
	}

	/** Returns a string representation of the path.
	 *
	 * @return a string represenation of the path
	 */

	public String toString() {
		StringBuffer str = new StringBuffer( "" );

		Elem p = first;

		while ( p != null ) {
			str.append( p.url );
			p = p.next;
			if ( p != null ) {
				str.append( " ->" );
			}
			str.append( NL );
		}
		return str.toString();
	}

}