package csu213;
import java.util.ArrayList ;
import java.util.Iterator;
// CSU213 Lecture Notes
// Wednesday, March 28, 2007
// Java Collections Framework and Loops


/*
  We have seen the Java ArrayList.  ArrayList is one of many ways
  to represent a collection of data.  The ArrayList is part of the
  Java Collections Framework.  The Java Collections Framework provides
  classes and interfaces which can be used by a programmer for a 
  variety of data representations with minimal new code required by the
  programmer.
  
  The Java Collections Framework contains two hierarchies.  An interface hierarchy
  and a class hierarchy.  The interface hierarchy defines the various methods that
  different sorts of collections must implement.  These lists of methods are sometimes
  rather extensive.  The aid the programmer, there is also a class hierarchy.  This
  class hierarchy contains some <em>concrete</em> classes which can be used directly,
  such as ArrayList, as well as some <em>abstract</em> classes that partially implement
  collection classes, providing default implementations many of the methods required
  by the interface.  With these partially implemented classes allow a programmer to write
  a collection class by implementing only a few methods--often only one or two.  Programmers
  may determine which methods need to be implemented by referring to the <a href="java.sun.com/j2se/1.5.0/docs/api">javadocs</a> for these
  classes.  Classes that must be implemented are marked <em>abstract</em>
  
  A universal feature of classes in the Java Collection Framework is the use of <em>iterators</em>.
  So before we explore the hierarchies, we need to discuss iterators and how they are used.
  Iterators are similar in some ways to the traversals that have been seen in this course.  However,
  An iterator for a collection of objects of type E will have methods:
  
  boolean hasNext()
  E next()
  void remove()
  
  hasNext() is similar to the isEmpty() method of a traversal, except that the meaning of the
  two methods are inverses of each other.  A collection obviously has a next value only if it is
  not empty.  

  next() shares a similarity with the first() method of a traversal.  Each method returns an element
  of the collection.  However, there are significant differences.  Repeated calls to first() will
  return the same value repeatedly.  Repeated calls to next(), however, will return a <em>sequence</em>
  of values in the collection.  Here is an example:
*/


public class LectureMarch28 {
	
	
	// prints out all elements of the given list of strings
	public static void printAll(ArrayList<String> alist) {
		Iterator<String> iter = alist.iterator() ;
		while (iter.hasNext()) {
			System.out.println(iter.next()) ;
		}
	}
	
	// prints out all elements of a given list of strings
	// this is alternative syntax that uses the iterator
	// implicitly
	public static void anotherPrintAll(ArrayList<String> alist) {
		for (String s : alist) {
			System.out.println(s) ;
		}
	}
	
	// for testing
	public static void main(String args[]) {
		ArrayList<String> alist = new ArrayList<String>() ;
		alist.add("This") ;
		alist.add("test") ;
		alist.add("should") ;
		alist.add("print") ;
		alist.add("6") ;
		alist.add("lines!") ;
		printAll(alist) ;
		anotherPrintAll(alist);
	}
	
/* Now that we have obtained an intuition of how Iterators work, we can look
 * at the Collections Hierarchy in more detail.  The top of the Iterface Hierarchy
 * is the interface Iterable<T>.  This interface contains just one method
 * 
 * <code>
 * <T> Iterator<T> iterator() ;
 * </code>
 * which returns the iterator for that collection.
 * 
 * The Iterable<T> interface is extended by (among others) the following interfaces.
 * Collection<T>, List<T>, Queue<T>, Set<T>
 * 
 * The Collection<T> interface defines a plethora of useful methods, including
 * 		boolean add(T obj) ;
 * 		boolean contains(T obj) ;
 * 		boolean isEmpty() ;
 * 		int size() ;
 * and many others.
 * 
 * To save effort in implementing a Collection<T>, the Java Collections Framework provides
 * an abstract class AbstractCollection<T>.  This class provides implementations for all
 * methods required by the Collection<T> interface except for
 * 		abstract Iterator<T> iterator() ;
 * 		abstract int size() ;
 * 
 * Two very useful kinds of Collections are Stacks and Queues.
 * A queue is a data structure that works on the First-In-First-Out (FIFO) principle.
 * The Java Collections Framework only provides an abstract Queue.
 * The methods for AbstractQueue<T> include
 * 		boolean add(T obj) ;  // adds the given element to the end of the queue
 * 		T element() ; // retrieves but does not remove the element at the front of the queue
 * 		T remove() ; // retrieves the element at the front of the queue and removes it from the queue.
 * 		
 * 
 * A stack is a data structure that works on the Last-In-First-Out (LIFO) principle.
 * The methods for the class Stack<T> include
 * 		boolean empty() ; // test to see if the stack is empty
 * 		T peek() ; // retrieve but do not remove the top element of the stack
 * 		T pop() ; // retrieve the element at the top of the stack and remove it
 * 		T push(T obj) ; // add the given object to the top of the stack.
 * 
 * Stacks and Queues are useful data structures for certain graph algorithms.
 * Depth first search and breadth first search are two strategies for traversing a
 * tree or graph.  Algorithms for these search strategies differ only in the fact that
 * breadth first search utilizes a queue to maintain a list of nodes that need to be
 * visited, while depth first search uses a stack for the same purpose.
 */
	
	
}