package org.jaxen.util;

/*
 * $Header$
 * $Revision: 1257 $
 * $Date: 2006-11-13 14:10:09 -0800 (Mon, 13 Nov 2006) $
 *
 * ====================================================================
 *
 * Copyright 2000-2005 bob mcwhirter & James Strachan.
 * All rights reserved.
 *
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 * 
 *   * Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 * 
 *   * Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and/or other materials provided with the distribution.
 * 
 *   * Neither the name of the Jaxen Project nor the names of its
 *     contributors may be used to endorse or promote products derived 
 *     from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * ====================================================================
 * This software consists of voluntary contributions made by many
 * individuals on behalf of the Jaxen Project and was originally
 * created by bob mcwhirter <bob@werken.com> and
 * James Strachan <jstrachan@apache.org>.  For more information on the
 * Jaxen Project, please see <http://www.jaxen.org/>.
 *
 * $Id: PrecedingAxisIterator.java 1257 2006-11-13 22:10:09Z elharo $
*/

import org.jaxen.JaxenConstants;
import org.jaxen.JaxenRuntimeException;
import org.jaxen.Navigator;
import org.jaxen.UnsupportedAxisException;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.NoSuchElementException;

/**
 * <p>
 * Represents the XPath <code>preceding</code> axis. 
 * The "<code>preceding</code> axis contains all nodes in the same document as the context 
 * node that are before the context node in document order, excluding any ancestors 
 * and excluding attribute nodes and namespace nodes."
 * 
 * <p>
 * This implementation of '<code>preceding</code>' works like so:
 * the <code>preceding</code> axis includes preceding siblings of this node and 
 * their descendants. Also, for each ancestor node of this node, it includes
 * all preceding siblings of that ancestor, and their descendants. Finally, it
 * includes the ancestor nodes themselves.
 * </p>
 * 
 * <p>
 * The reversed <code>descendant-or-self</code> axes that are required are calculated using a
 * stack of reversed 'child-or-self' axes. When asked for a node, it is always taken
 * from a child-or-self axis. If it was the last node on that axis, the node is returned.
 * Otherwise, this axis is pushed on the stack, and the process is repeated with the child-or-self
 * of the node. Eventually this recurses down to the last descendant of any node, then works
 * back up to the root.
 * </p>
 * 
 * <p>
 * Most object models could provide a faster implementation of the reversed
 * 'children-or-self' used here.</p>
 * 
 * @version 1.2b12
 */
public class PrecedingAxisIterator implements Iterator
{
    private Iterator ancestorOrSelf;
    private Iterator precedingSibling;
    private ListIterator childrenOrSelf;
    private ArrayList stack;

    private Navigator navigator;

    /**
     * Create a new <code>preceding</code> axis iterator.
     * 
     * @param contextNode the node to start from
     * @param navigator the object model specific navigator
     */
    public PrecedingAxisIterator(Object contextNode,
                                 Navigator navigator) throws UnsupportedAxisException
    {
        this.navigator = navigator;
        this.ancestorOrSelf = navigator.getAncestorOrSelfAxisIterator(contextNode);
        this.precedingSibling = JaxenConstants.EMPTY_ITERATOR;
        this.childrenOrSelf = JaxenConstants.EMPTY_LIST_ITERATOR;
        this.stack = new ArrayList();
    }


    /**
     * Returns true if there are any preceding nodes remaining; false otherwise.
     * 
     * @return true if any preceding nodes remain; false otherwise
     * 
     * @see java.util.Iterator#hasNext()
     */
    public boolean hasNext()
    {
        try
        {
            while (!childrenOrSelf.hasPrevious())
            {
                if (stack.isEmpty())
                {
                    while (!precedingSibling.hasNext())
                    {
                        if (!ancestorOrSelf.hasNext())
                        {
                            return false;
                        }
                        Object contextNode = ancestorOrSelf.next();
                        precedingSibling = new PrecedingSiblingAxisIterator(contextNode, navigator);
                    }
                    Object node = precedingSibling.next();
                    childrenOrSelf = childrenOrSelf(node);
                }
                else
                {
                    childrenOrSelf = (ListIterator) stack.remove(stack.size()-1);
                }
            }
            return true;
        }
        catch (UnsupportedAxisException e)
        {
            throw new JaxenRuntimeException(e);
        }
    }

    private ListIterator childrenOrSelf(Object node)
    {
        try
        {
            ArrayList reversed = new ArrayList();
            reversed.add(node);
            Iterator childAxisIterator = navigator.getChildAxisIterator(node);
            if (childAxisIterator != null)
            {
                while (childAxisIterator.hasNext())
                {
                    reversed.add(childAxisIterator.next());
                }
            }
            return reversed.listIterator(reversed.size());
        }
        catch (UnsupportedAxisException e)
        {
            throw new JaxenRuntimeException(e);
        }
    }

    /**
     * Returns the next preceding node.
     * 
     * @return the next preceding node
     * 
     * @throws NoSuchElementException if no preceding nodes remain
     * 
     * @see java.util.Iterator#next()
     */
    public Object next() throws NoSuchElementException
    {
        if (!hasNext())
        {
            throw new NoSuchElementException();
        }
        while (true)
        {
            Object result = childrenOrSelf.previous();
            if (childrenOrSelf.hasPrevious())
            {
                // if this isn't 'self' construct 'descendant-or-self'
                stack.add(childrenOrSelf);
                childrenOrSelf = childrenOrSelf(result);
                continue;
            }
            return result;
        }
    }


    /**
     * This operation is not supported.
     * 
     * @throws UnsupportedOperationException always
     */
    public void remove() throws UnsupportedOperationException
    {
        throw new UnsupportedOperationException();
    }
    
}
