/*
 * Copyright 2005 by Oracle USA
 * 500 Oracle Parkway, Redwood Shores, California, 94065, U.S.A.
 * All rights reserved.
 */
package javax.ide.extension.spi;

import java.util.AbstractCollection;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

/**
 * Convenient implementation of a Last In First Out (LIFO) stack. This
 * implementation differs from the one in java.util.Stack in two ways. 
 * 
 * First, like most of the collection APIs, it is unsynchronized for better
 * performance when synchronization is not required. If a synchronized stack
 * is required, you can use the 
 * {@link java.util.Collections#synchronizedCollection(java.util.Collection) Collections.synchronizedCollection()}
 * method to retrieve a synchronized instance.
 * 
 * Second, it does not expose its internal implementation via its superclass. 
 * Extending <tt>AbstractCollection</tt> instead of <tt>Vector</tt> allows 
 * objects of this class to be used interchangably with other collection 
 * framework classes without exposing its internal implementation.
 * 
 * @author Brian.Duff@oracle.com
 */
public final class Stack<T> extends AbstractCollection<T> 
  implements Iterable<T>
{
  private ArrayList<T> _list;
  
  /**
   * Construct a stack with no additional arguments.
   */
  public Stack()
  {
  }
  
  /**
   * Construct a stack initialized to contain all the items in the specified
   * collection. The items will be pushed on to the stack in their order in
   * the collection.
   * 
   * @param c a collection of items to push onto the stack.
   */
  public Stack( Collection<T> c )
  {
    addAll( c );
  }

  /**
   * Gets (or lazily instantiates) the list implementation used by this stack.
   * 
   * @return a list.
   */
  private List<T> getList()
  {
    if ( _list == null )
    {
      _list = new ArrayList<T>();
    }
    return _list;
  }
  
  /**
   * Gets whether there are more elements on the stack.
   * 
   * @return true if there are no more elements on the stack.
   */
  public boolean isEmpty()
  {
    return size() == 0;
  }
  
  /**
   * Pushes an element onto the stack.
   * 
   * @param o an element to push onto the stack
   * @return true if the stack changed as a result of this operation.
   */
  public boolean push( T o )
  {
    return getList().add( o );
  }
  
  /**
   * Obtains the top element on the stack without removing it.
   * 
   * @return the top element on the stack.
   */
  public T peek()
  {
    int size = size();
    if ( size == 0 )
    {
      throw new IllegalStateException( "Illegal peek()" );  // NOTRANS
    }
    return getList().get( size - 1 );
  }
  
  /**
   * Replaces the top of the stack with the specified object.
   * 
   * @param o the object to replace the top of the stack with.
   */
  public void replace( T o )
  {
    int size = size();
    if ( size == 0 )
    {
      throw new IllegalStateException( "Illegal replace()" );   // NOTRANS
    }
    
    getList().set( size - 1, o );
  }
  
  /**
   * Pops the top element off the stack and returns it.
   * 
   * @return the old top element
   */
  public T pop()
  {
    int size = size();
    if ( size == 0 )
    {
      throw new IllegalStateException( "Illegal pop()" );   // NOTRANS
    }

    T theValue = _list.remove( size-1 );

    if ( size == 1 )  // i.e. we removed the last remaining single item
    {
      _list = null;
    }
    
    return theValue;
  }
  
  /**
   * Gets an iterator for elements on the stack. This iterator starts at the
   * bottom of the stack and proceeds to the top.
   * 
   * @return an iterator over stack elements.
   */
  public Iterator<T> reverseIterator()
  {
    if ( isEmpty() )
    {
      // Do not remove this cast. Eclipse compiler fails without it.
      return (Iterator<T>)Collections.emptyList().iterator();
    }
    return _list.iterator();
  }

  // java.util.Collection implementation
  
  public boolean add( T o )
  {
    return push( o );
  }
  
  public void clear()
  {
    if ( _list != null )
    {
      _list.clear();
    }
  }

  /**
   * Gets an iterator for elements on the stack. The iterator starts at the
   * top of the stack and proceeds to the bottom of the stack.
   * 
   * @return an iterator over stack elements.
   */
  public Iterator<T> iterator()
  {
    if ( isEmpty() )
    {
      return Collections.EMPTY_LIST.iterator();
    }
  
    return new ReverseListIterator<T>( _list );
  }
  
  public int size()
  {
    return _list == null ? 0 : _list.size();
  }
  
  /**
   * Iterator that traverses a list in reverse order. It does this by just
   * adapting the ListIterator of the list.
   */
  private final static class ReverseListIterator<T>
    implements Iterator<T>
  {
    private final ListIterator<T> _listIterator;
    
    public ReverseListIterator( List<T> list )
    {
      _listIterator = list.listIterator( list.size() );
    }
    
    public boolean hasNext()
    {
      return _listIterator.hasPrevious();
    }
    
    public T next()
    {
      return _listIterator.previous();
    }
    
    public void remove()
    {
      _listIterator.remove();
    }
    
  }
}