simplelist.java

Java程序设计(美) David D. Riley著 机械工业出版社 书籍配套 代码

/** SimpleList Class
 * Author: David D. Riley
 * Date: June, 2004
 *
 *	class invariant
 *		A SimpleList object...
 *			* is a container of zero or more other objects arranged in a linear order
 *			* maintains an iterator that conceptually is positioned  
 *				either in front of the first item, behind the 
 *				last item or between two consecutive list items.  
 *				(The iterator can be thought of as an integer that 
 *				counts the number of items preceding its position.) 
 */
public class SimpleList <E> extends java.util.AbstractCollection<E> implements java.util.Iterator<E>{

	protected class ListCell<E> {
		private E content;
		public ListCell<E> next;
	
		public ListCell(E e) {
			content = e;
			next = null;
		}
	}

	private ListCell<E> anchor;
	private ListCell<E> prevCell, preprevCell;
	private int privateCount;

	/**	post:   this is empty (i.e. size() == 0)
     *          and iterator == 0  (i.e. the iterator has zero items before it)
     *          and preprevvCell == null	
     */
	public SimpleList()  {
        super();
		anchor = new ListCell<E>(null);
		prevCell = anchor;
        reset();
	}  

	/**	post:   iterator == 0  (i.e. positioned before all items in the list)
     *          and  preprevCell== null 
     */
	public void reset() {
        preprevCell = null;
		prevCell = anchor;
	} 

	/**	post:   hasNext()  implies
     *              (iterator == iterator@pre + 1  
     *              and result == item immediately following iterator@pre
     *              and preprevCell is positioned at iterator@pre)
     *          and not hasNext() implies NoSuchElementException is thrown 
     */
	public E next()  {
		if (hasNext())  {
            preprevCell = prevCell;
			prevCell = prevCell.next;
            return prevCell.content;
        } else
            throw new java.util.NoSuchElementException("The iterator is positioned off the list when next() is called.");
	}  

	/** post:   result == ( iterator != size() )   
     *              (i.e. result is false exactly when iterator is 
     *              positioned at the rear of this list)  
     */
	public boolean hasNext()  {
		return (prevCell.next != null);
	} 

	/**	post:   this == this@pre with e inserted at the iterator@pre position 
     *          and  size() = size()@pre + 1
     *          and  iterator == iterator@pre + 1
     *          and  preprevCell == null   
     */
	public boolean add(E e)  {
		ListCell<E> newCell = new ListCell<E>(e);
		newCell.next = prevCell.next;
		prevCell.next = newCell;
        preprevCell = null;
        prevCell = prevCell.next;
		privateCount++;
        return true;
	} 

	/**	post:   (prepevCell@pre != null)  implies
     *              (this == this@pre with the item preceding iterator@pre removed  
     *              and  size() == size()@pre - 1
     *              and iterator == iterator@pre - 1
     *              and preprevCell == null) 
     *              and  (preprevcell@pre==null) implies an IllegalStateException is thrown 
     */
	public void remove()  {
		if (preprevCell != null)  {
			preprevCell.next = preprevCell.next.next;
			privateCount--;
			prevCell = preprevCell;			
            preprevCell = null;
		}  else 
            throw new IllegalStateException("The remove operation is legal only immediately after an item() call.");
	} 

	/**	post:   result == the number of items in this list */
	public int size()  {
		return privateCount;
	}

	/**	post:   result == this
     *          and  iterator == 0  (i.e. positioned before all items in the list)
     *  note:   This method is required to properly extend AbstractCollection
     *          and in turn to make the shortened form of the for statement work.
     */
	public java.util.Iterator<E> iterator()  {
        reset();
		return this;
	}

}