package edu.princeton.cs.algs4.growingtree.framework;
/*
 * @(#)AffineTransformList.java
 *
 * Last Modified: 9/01/02
 */

import java.awt.geom.*;
import java.util.*;
import java.util.*;

/**
 * Linked list implementation of the <tt>List</tt> interface containing AffineTransforms.  Implements all
 * optional list operations, but only permits <code>AffineTransform</code> insertion.  In addition to implementing the <tt>List</tt> interface,
 * the <tt>AffineTransformList</tt> class extends the uniformly named methods within LinkedList to
 * <tt>get</tt>, <tt>remove</tt> and <tt>insert</tt> an element at the
 * beginning and end of the list.  These operations allow AffineTransformLists to be
 * used as a stack, queue, or double-ended queue (deque).<p>
 *
 * The primary purpose of the class is for the development of </tt>getTransformStep</tt>,
 * which returns the <code>AffineTransform</code> found passing a double index. The double index transforms
 * into an intermidiary <code>AffineTransform</code> developed from the list of <code>AffineTransforms.</code><p>
 *
 * The iterators returned by the this class's <tt>iterator</tt> and
 * <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is
 * structurally modified at any time after the iterator is created, in any way
 * except through the Iterator's own <tt>remove</tt> or <tt>add</tt> methods,
 * the iterator will throw a <tt>ConcurrentModificationException</tt>.  Thus,
 * in the face of concurrent modification, the iterator fails quickly and
 * cleanly, rather than risking arbitrary, non-deterministic behavior at an
 * undetermined time in the future.
 *
 * @author  Corey Sanders
 * @version 1.4 9/01/02
 * @see	    java.util.LinkedList
 * @see	    java.awt.geom.AffineTransform
 */

public class AffineTransformList {

    private LinkedList<AffineTransform> list;
	/**
     * Constructs an empty list.
     */
	public AffineTransformList() {
		list = new LinkedList<AffineTransform>();
	}

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param c the collection whose elements are to be placed into this list.
     */
    public AffineTransformList(Collection<AffineTransform> c) {
	 	list = new LinkedList<AffineTransform>(c);
    }

    /**
     * Gets the number of elements in this list.
     */
    public int size() {
        return list.size();
    }

    /**
     * Gets the element at index in this list.
     */
    public AffineTransform get(int index) {
        return list.get(index);
    }

	/**
     * Appends the given <code>AffineTransform</code> to the end of this list.
     *
     * @param a the <code>AffineTransform</code> to be inserted at the end of this list.
     * @return <tt>true</tt> (as per the general contract of
	 * <tt>Collection.add</tt>).
     */
	public boolean add(AffineTransform a) {
		return list.add(a);
	}

	/**
     * Inserts the specified <code>AffineTransform</code> at the specified position in this list.
     * Shifts the <code>AffineTransform</code> currently at that position (if any) and any
     * subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted.
     * @param element <code>AffineTransform</code> to be inserted.
     *
     * @throws IndexOutOfBoundsException if the specified index is out of
     *		  range (<tt>index &lt; 0 || index &gt; size()</tt>).
     */
	public void add(int index, AffineTransform element) {
		list.add(index, element);
	}

	/**
     * Inserts the given <code>AffineTransform</code> at the beginning of this list.
     *
     * @param a the <code>AffineTransform</code> to be inserted at the beginning of this list.
     */
	public void addFirst(AffineTransform a) {
		list.addFirst(a);
	}

	/**
     * Appends the given <code>AffineTransform</code> to the end of this list.  (Identical in
     * function to the <tt>add</tt> method; included only for consistency.)
     *
     * @param a the <code>AffineTransform</code> to be inserted at the end of this list.
     */
	public void addLast(AffineTransform a) {
		list.addFirst(a);
	}

	/**
     * Replaces the <code>AffineTransform</code> at the specified position in this list with the
     * specified <code>AffineTransform</code>.
     *
     * @param index index of element to replace.
     * @param element <code>AffineTransform</code> to be stored at the specified position.
     * @return the <code>AffineTransform</code> previously at the specified position.
     * @throws IndexOutOfBoundsException if the specified index is out of
     *		  range (<tt>index &lt; 0 || index &gt;= size()</tt>).
     */
	public AffineTransform set(int index, AffineTransform element) {
		return list.set(index, element);
	}

	/**
	 * Finds the appropriate <code>AffineTransform</code> given a double step. The double step
	 * refers to inbetween two <code>AffineTransform</code>s, defined by integer indices. The <code>AffineTransform</code>
	 * returns that takes the step and finds the AffineTransform that fits at that given point
	 * between the two integer indices.
	 *
	 *@param step double step referring to inbetween two indices of the AffineTransformList.
	 *@return <code>AffineTransform</code> that represents the transform for the double step between
	 * two <code>AffineTransform</code>s.
	 *@throws IndexOutOfBoundsException if the specified step is out of
     *		  range (<tt>step &lt; 0 || step &gt;= size()</tt>).
     */

	public AffineTransform getTransformStep(double step) throws IndexOutOfBoundsException{

		if (step > (size()-1)) {
			//throw new IndexOutOfBoundsException();
            step = size() - 1;
		}

		AffineTransform previous = (AffineTransform)get((int)Math.floor(step));
		AffineTransform next = (AffineTransform)get((int)Math.ceil(step));

		double previousWeight = 1.0 - (step - Math.floor(step));
		double nextWeight = step - Math.floor(step);

		double m00, m01, m02,
			   m10, m11, m12;


		// Matrix entries according to : {[m00, m01, m02]
		//								  [m10, m11, m12]}

		m00 = (previous.getScaleX() * previousWeight) + (next.getScaleX() * nextWeight);
		m11 = (previous.getScaleY() * previousWeight) + (next.getScaleY() * nextWeight);

		m01 = (previous.getShearX() * previousWeight) + (next.getShearX() * nextWeight);
		m10 = (previous.getShearY() * previousWeight) + (next.getShearY() * nextWeight);

		m02 = (previous.getTranslateX() * previousWeight) + (next.getTranslateX() * nextWeight);
		m12 = (previous.getTranslateY() * previousWeight) + (next.getTranslateY() * nextWeight);

		return new AffineTransform(m00, m10, m01, m11, m02, m12);
	}

	/**
	 * Finds the appropriate <code>AffineTransform</code> given a double step and two AffineTrasforms. The double step
	 * refers to a number between 1 and 0. The <code>AffineTransform</code>
	 * returned takes the step and finds the AffineTransform that fits at that given point
	 * between the two integer indices, 0 returns <code>AffineTransform</code> a and 1 returns <code>AffineTrasform</code> b.
	 *
	 *@param a AffineTransform that is returned at step 0.
	 *@param b AffineTransform that is returned at step 1.
	 *@param step double step referring to inbetween two indices of the AffineTransformList.
	 *@return <code>AffineTransform</code> that represents the transform for the double step between
	 * two <code>AffineTransform</code>s a and b.
	 *@throws IndexOutOfBoundsException if the specified step is out of
     *		  range (<tt>step &lt; 0 || step &gt;= size()</tt>).
     */
	public static AffineTransform getTransformStep(AffineTransform a, AffineTransform b, double step) {

		if (step > 1 || step < 0)
			return null;

		double previousWeight = 1.0 - (step);
		double nextWeight = step;

		double m00, m01, m02,
			   m10, m11, m12;

		m00 = (a.getScaleX() * previousWeight) + (b.getScaleX() * nextWeight);
		m11 = (a.getScaleY() * previousWeight) + (b.getScaleY() * nextWeight);

		m01 = (a.getShearX() * previousWeight) + (b.getShearX() * nextWeight);
		m10 = (a.getShearY() * previousWeight) + (b.getShearY() * nextWeight);

		m02 = (a.getTranslateX() * previousWeight) + (b.getTranslateX() * nextWeight);
		m12 = (a.getTranslateY() * previousWeight) + (b.getTranslateY() * nextWeight);

		return new AffineTransform(m00, m10, m01, m11, m02, m12);
	}

}