/*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 * 
 * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
 * 
 * The contents of this file are subject to the terms of either the GNU
 * General Public License Version 2 only ("GPL") or the Common Development
 * and Distribution License("CDDL") (collectively, the "License").  You
 * may not use this file except in compliance with the License. You can obtain
 * a copy of the License at https://glassfish.dev.java.net/public/CDDL+GPL.html
 * or glassfish/bootstrap/legal/LICENSE.txt.  See the License for the specific
 * language governing permissions and limitations under the License.
 * 
 * When distributing the software, include this License Header Notice in each
 * file and include the License file at glassfish/bootstrap/legal/LICENSE.txt.
 * Sun designates this particular file as subject to the "Classpath" exception
 * as provided by Sun in the GPL Version 2 section of the License file that
 * accompanied this code.  If applicable, add the following below the License
 * Header, with the fields enclosed by brackets [] replaced by your own
 * identifying information: "Portions Copyrighted [year]
 * [name of copyright owner]"
 * 
 * Contributor(s):
 * 
 * If you wish your version of this file to be governed by only the CDDL or
 * only the GPL Version 2, indicate your decision by adding "[Contributor]
 * elects to include this software in this distribution under the [CDDL or GPL
 * Version 2] license."  If you don't indicate a single choice of license, a
 * recipient has the option to distribute your version of this file under
 * either the CDDL, the GPL Version 2 or to extend the choice of license to
 * its licensees as provided above.  However, if you add GPL Version 2 code
 * and therefore, elected the GPL Version 2 license, then the option applies
 * only if the new code is made subject to such option by the copyright
 * holder.
 */

//NOTE: Tabs are used instead of spaces for indentation. 
//  Make sure that your editor does not replace tabs with spaces. 
//  Set the tab length using your favourite editor to your 
//  visual preference.

/*
 * Filename: DList.java	
 *
 * Copyright 2000-2001 by iPlanet/Sun Microsystems, Inc.,
 * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
 * All rights reserved.
 * 
 * This software is the confidential and proprietary information
 * of iPlanet/Sun Microsystems, Inc. ("Confidential Information").
 * You shall not disclose such Confidential Information and shall
 * use it only in accordance with the terms of the license 
 * agreement you entered into with iPlanet/Sun Microsystems.
 */
 
/**
 * <BR> <I>$Source: /cvs/glassfish/appserv-commons/src/java/com/sun/enterprise/util/collection/DList.java,v $</I>
 * @author     $Author: tcfujii $
 * @version    $Revision: 1.4 $ $Date: 2007/05/05 05:32:10 $
 */
 
package com.sun.enterprise.util.collection;

import java.util.*;

/**
 * A DList is an implementation of an unsynchronized doubly linked list. Unlike
 *	java.util.LinkedList, each node in the DList (DListNode) can be delinked 
 *	in constant time. However, to do this the application must have the reference
 *	of the node to be delinked. DLists are exrtemely usefull if nodes are 
 *	removed/inserted quite frequently. DList is used in the implementation of
 *	com.sun.enterprise.util.cache.AdaptiveCache.
 */
public class DList
	implements List, DListNodeFactory
{
    
    protected DListNode first;
    protected DListNode last;
    protected int size = 0;
    protected DListNodeFactory		nodeFactory;
    
    /**
     * Create a DList.
     */
    public DList() {
    	first = new DListNode(null);
    	last = new DListNode(null);
    	first.next = last;
    	last.prev = first;
    	first.prev = last.next = null;
    	this.nodeFactory = this;
    }
    
    /**
     * Create a DList.
     */
    public DList(DListNode firstNode, DListNode lastNode, DListNodeFactory factory) {
    	initDListWithNodes(firstNode, lastNode, factory);
    }
    	
    protected void initDListWithNodes(DListNode firstNode, DListNode lastNode, DListNodeFactory factory) {
    	first = firstNode;
    	last = lastNode;
    	first.next = last;
    	last.prev = first;
    	first.prev = last.next = null;
    	this.nodeFactory = (factory == null) ? this : factory;
    }
    
    
    /**
     * Create a DList.
     */
    public DList(DListNodeFactory nodeFactory) {
    	first = new DListNode(null);
    	last = new DListNode(null);
    	first.next = last;
    	last.prev = first;
    	first.prev = last.next = null;
    	this.nodeFactory = nodeFactory;
    }
    
    
    private DList(DListNode firstNode, DListNode lastNode, int size, DListNodeFactory nodeFactory) {
    	first = firstNode;
    	last = lastNode;
    	this.size = size;
    	this.nodeFactory = nodeFactory;
    }
    
    
    
    /**
     * Inserts the object at the specified index. Note that this
     *	method is an O(n) operation as it has to iterate through the nodes
     *	in the list till the appropriate index is reached.
     * @return The DListNode holding this object or null if the index is invalid.
     */
    public void add(int index, Object object) {
    	insertAt(index, object);
    	size++;
    }
    
    /**
     * Inserts the object at the end of the list.
     * @return The DListNode holding this object or null if the index is invalid.
     */
    public boolean add(Object object) {
    	last.insertBefore(nodeFactory.createDListNode(object));
    	size++;
    	return true;
    }
    
    /**
     * Inserts the object at the specified index. Note that this
     *	method is an O(n) operation as it has to iterate through the nodes
     *	in the list till the appropriate index is reached.
     * @return The DListNode holding this object or null if the index is invalid.
     */
    public boolean addAll(Collection collection) {
    	Iterator iter = collection.iterator();
    	boolean added = false;
    	while (iter.hasNext()) {
    		add(iter.next());
    		added = true;
    	}
    	
    	size += collection.size();
    	return added;
    }
    
    /**
     * Inserts the object at the specified index. Note that this
     *	method is an O(n) operation as it has to iterate through the nodes
     *	in the list till the appropriate index is reached.
     * @return The DListNode holding this object or null if the index is invalid.
     */
    public boolean addAll(int index, Collection collection) {
    	DListNode node = getDListNodeAt(index);
    	Iterator iter = collection.iterator();
    	boolean added = iter.hasNext();
    	DListNode head = new DListNode(null);
    	DListNode last = head;
    	while (iter.hasNext()) {
    		last.insertAfter(nodeFactory.createDListNode(iter.next()));
    		last = last.next;
    	}
    	if (head != last) {
    		node.prev.next = head.next;
    		node.prev = last;
    		
    		head.next.prev = node;
    		last.next = node;
    	}
    	
    	size += collection.size();
    	return added;
    }
    
    public void clear() {
    	first.next = last;
    	last.prev = first;
    	size = 0;
    }
    
    public boolean contains(Object o) {
    	return (indexOf(o) != -1);
    }
    
    public boolean containsAll(Collection collection) {
    	Iterator iter = collection.iterator();
    	while (iter.hasNext()) {
    		Object o = iter.next();
    		if (indexOf(o) == -1) {
    			return false;
    		}
    	}
    	return true;
    }
    
    public boolean equals(Object o) {
    	if (o instanceof List) {
    		List list = (List) o;
    		if (list.size() != size()) {
    			return false;
    		} 
    		
    		Object myObj = null, otherObj = null;
    		DListNode node = first;
    		for (int i=0; i<size; i++) {
    			myObj = node.next.object;
    			otherObj = list.get(i);
    			if (! myObj.equals(otherObj)) {
    				return false;
    			}
    			node = node.next;
    		}
    		return true;
    	}
    	return false;
    }
    
    public int hashCode() {
		int hashCode = 1;
    	DListNode node = first;
    	Object myObj = null;
    	for (int i=0; i<size; i++) {
    		myObj = node.next.object;
			hashCode = 31*hashCode + (myObj==null ? 0 : myObj.hashCode());
			node = node.next;
		}
		return hashCode;
    }
    
    /**
     * Return the object at the specified index
     * @param The index between 0 and size()-1
     */
    public Object get(int index) {
    	DListNode node = getDListNodeAt(index);
    	return (node == null) ? null : node.object;
    }
    
    
    /**
     * Obtains the index at which this object appears in the list. The method relies on the 
     *	equals() method to identify objects in the list. Note that this
     *	method is an O(n) operation as it has to iterate through the nodes
     *	in the list till a match is found.
     * @return The (0 based) index at which this object appears in the list -1 if not found.
     */
    public int indexOf(Object o) {
    	int index = 0;
    	for (DListNode node = first.next; node != last; node = node.next) {
    		if (node.object.equals(o)) {
    			return index;
    		}
    		index++;
    	}
    	return -1;
    }
    
	/**
	 * Returns true if this list contains no elements.
	 * @return true if this list contains no elements false otherwise.
	 */
	public boolean isEmpty() {
		return (this.size > 0);
	}
	
    /**
     * Returns an iterator for iterating the entries in the list. Each object returned
     *	by the iterator.next() is the actual object added to the list.
     * @return An iterator.
     */
	public Iterator iterator() {
		return new DListIterator(first, last, false, 0);
	}
	
    /**
     * Returns the index in this list of the last occurrence of the specified element, 
     *	or -1 if this list does not contain this element. More formally, returns the highest
     *	index i such that (o==null ? get(i)==null : o.equals(get(i))), or -1 if there is no such index.
     * @param element to search for.
     * @return the index in this list of the last occurrence of the specified element, 
     *	or -1 if this list does not contain this element.
     */
	public int lastIndexOf(Object obj) {
    	int index = size - 1;
    	for (DListNode node = last.prev; node != first; node = node.prev) {
    		if (node.object.equals(obj)) {
    			return index;
    		}
    		index--;
    	}
    	return -1;
	}
	
    /**
     * Returns a list iterator of the elements in this list (in proper sequence).
     *	retrieve the object.
     * @return A ListIterator.
     */
	public ListIterator listIterator() {
		return new DListIterator(first, last, true, 0);
	}
	
    /**
     * Returns a list iterator of the elements in this list (in proper sequence), starting 
     *	at the specified position in this list. The specified index indicates the first element
     *	that would be returned by an initial call to the next method. An initial call to the 
     *	previous method would return the element with the specified index minus one.
     * @param index of first element to be returned from the list iterator (by a call to the next method).
     * @return a list iterator of the elements in this list (in proper sequence), starting 
    	at the specified position in this list.
     */
	public ListIterator listIterator(int index) {
		return new DListIterator(first, last, true, index);
	}
	
	/**
	 * Removes the element at the specified position in this list (optional operation). 
	 *	Shifts any subsequent elements to the left (subtracts one from their indices).
     * @return the element that was removed from the list.	 
     */
	public Object remove(int index) {
		DListNode node = getDListNodeAt(index);
		node.delink();
		size--;
		Object object = node.object;
		destroyDListNode(node);
		return object;
	}

	/**
	 * Removes the first occurrence in this list of the specified element (optional operation). 
	 *	If this list does not contain the element, it is unchanged. More formally,
     *	removes the element with the lowest index i such that 
     *	(o==null ? get(i)==null : o.equals(get(i))) (if such an element exists).
     * @return true if this list contained the specified element.
     */
	public boolean remove(Object object) {
		DListNode node = getDListNode(object);
		if (node == null) {
			return false;
		} else {
			node.delink();
			destroyDListNode(node);
			size--;
			return true;
		}
	}

	public boolean removeAll(Collection collection) {
		Iterator iter = collection.iterator();
		boolean removed = false;
		while (iter.hasNext()) {
			if (remove(iter.next())) {
				size--;
				removed = true;
			}
		}
		return removed;
	}

	public boolean retainAll(Collection collection) {
		
		boolean removed = false;
		DListNode node = first;
		DListNode dnode = null;
		while (node.next != last) {
			dnode = node.next;
			if (collection.contains(dnode.object)) {
				dnode.delink();
				destroyDListNode(dnode);
				size--;
				removed = true;
			} else {
				node = node.next;
			}
		}
		return removed;
	}

    /**
     * Return the object at the specified index
     * @param The index between 0 and size()-1
     */
    public Object set(int index, Object object) {
    	DListNode node = getDListNodeAt(index);
    	Object oldObject =  (node == null) ? null : node.object;
    	node.object = object;
    	return oldObject;
    }
    
    
    /**
     * Inserts the object at the specified index. Note that this
     *	method is an O(n) operation as it has to iterate through the nodes
     *	in the list till the appropriate index is reached.
     * @return The DListNode holding this object or null if the index is invalid.
     */
    public DListNode insertAt(int index, Object object) {
    	if ((index < 0) || (index >= size)) {
    		return null;
    	}
    	int mid = size >> 1;	//Divide by 2!!
   		DListNode node = null;
    	if (index <= mid) {
    		node = first.next;
    		for (int i=0; i<index ; i++) {
    			node = node.next;
    		}
    	} else {
    		index = size - index - 1;
    		node = last.prev;
    		for (int i=0; i<index ; i++) {
    			node = node.prev;
    		}
    	}
    	DListNode newNode = nodeFactory.createDListNode(object);
   		node.insertBefore(newNode);
   		size++;
    	return newNode;
    }
    
    /**
     * Obtain the size of the list.
     * @return The number of entries in the list.
     */
    public int size() {
    	return size;
    }
    
    
    /**
     * Returns a view of the portion of this list between the specified fromIndex, 
     *	inclusive, and toIndex, exclusive. (If fromIndex and toIndex are equal, the
     *	returned list is empty.) The returned list is backed by this list, so changes 
     *	in the returned list are reflected in this list, and vice-versa. The returned list supports
     *	all of the optional list operations supported by this list.
     * <p> This method eliminates the need for explicit range operations (of the sort 
     *	that commonly exist for arrays). Any operation that expects a list can be used as a
     *	range operation by passing a subList view instead of a whole list. For example, 
     *	the following idiom removes a range of elements from a list: 
     * <p> list.subList(from, to).clear();
     * <p>Similar idioms may be constructed for indexOf and lastIndexOf, and all of the 
     *	algorithms in the Collections class can be applied to a subList.
     * <p>The semantics of this list returned by this method become undefined if the backing 
     *	list (i.e., this list) is structurally modified in any way other than via the
     *	returned list. (Structural modifications are those that change the size of this 
     *	list, or otherwise perturb it in such a fashion that iterations in progress may yield
     *	incorrect results.)
     * @param low endpoint (inclusive) of the subList.
     * @param high endpoint (exclusive) of the subList.
     */
    public List subList(int fromIndex, int toIndex) {
    	System.out.println("subList(" + fromIndex + ", " + toIndex + ")");
    	DListNode startNode = getDListNodeAt(fromIndex);
    	System.out.println("nodeAt(" + fromIndex + "): " + startNode.object);
    	DListNode toNode = getDListNodeAt(toIndex);
    	System.out.println("nodeAt(" + toIndex + "): " + toNode.object);
    	return new DList(startNode.prev, toNode, toIndex - fromIndex, nodeFactory);
    }
    
    
    
    /**
	 * Returns an array containing all of the elements in this collection. If the collection 
	 *	makes any guarantees as to what order its elements are returned by its iterator, this 
	 *	method must return the elements in the same order.
	 * <p> The returned array will be "safe" in that no references to it are maintained by this 
	 *	collection. (In other words, this method must allocate a new array even if this
     *	collection is backed by an array). The caller is thus free to modify the returned array.     
     * @return an array containing all of the elements in this collection.
     */
	public Object[] toArray() {
		Object[]	array = new Object[size];
		int index = 0;
    	for (DListNode node = first.next; node != last; node = node.next) {
    		array[index++] = node.object;
    	}
    	return array;
	}
	
    /**
	 * Returns an array containing all of the elements in this collection whose runtime type 
	 *	is that of the specified array. If the collection fits in the specified array, it is
	 *	returned therein. Otherwise, a new array is allocated with the runtime type of the 
	 *	specified array and the size of this collection. 
	 * <p> If this collection fits in the specified array with room to spare (i.e., the 
	 *	array has more elements than this collection), the element in the array immediately 
	 *	following the end of the collection is set to null. This is useful in determining 
	 *	the length of this collection only if the caller knows that this collection does 
	 *	not contain any null elements.)
	 * <p> If this collection makes any guarantees as to what order its elements are returned 
	 *	by its iterator, this method must return the elements in the same order.
	 * <p>Like the toArray method, this method acts as bridge between array-based and 
	 *	collection-based APIs. Further, this method allows precise control over the runtime 
	 *	type of the output array, and may, under certain circumstances, be used to save allocation costs.
	 * <p>Suppose l is a List known to contain only strings. The following code can be 
	 *	used to dump the list into a newly allocated array of String: 
	 * <p>String[] x = (String[]) v.toArray(new String[0]);
	 * @return an array containing all of the elements in this collection.
     */
	public Object[] toArray(Object[] array) {
		
		if (array.length < size) {
			array = (Object[]) java.lang.reflect.Array.newInstance(array.getClass().getComponentType(), size);
		}
		
		int index = 0;
    	for (DListNode node = first.next; node != last; node = node.next) {
    		array[index++] = node.object;
    	}

        if (array.length > size) {
            array[size] = null;
        }
            
        return array;

	}
	

	/*******************************************************************************************************/
	/*******************************************************************************************************/
	/*******************************************************************************************************/
	/*******************************************************************************************************/
	/*******************************************************************************************************/

	public DListNode createDListNode(Object object) {
		return new DListNode(object);
	}
	
	public void destroyDListNode(DListNode node) {
	}
	
	public DListNodeFactory getDListNodeFactory() {
		return this.nodeFactory;
	}
	
	public void setDListNodeFactory(DListNodeFactory nodeFactory) {
		this.nodeFactory = nodeFactory;
	}
	
    /**
     * Add a DListNode as the first node in the list.
     * @param node The node to be added.
     */
    public void addAsFirstNode(DListNode node) {
    	DListNode fNode = first.next;
    	node.next = fNode;
    	node.prev = first;
    	fNode.prev = first.next = node;
    	size++;
    }

    /**
     * Add an object as the first node in the list.
     * @param object The object to be added.
     * @return The DListNode enclosing the object. This
     *	DListNode object can later be used to delink
     *	the object from the list in constant time.
     */
    public DListNode addAsFirstObject(Object object) {
    	DListNode node = nodeFactory.createDListNode(object);
    	addAsFirstNode(node);
    	return node;
    }
    
    /**
     * Add a DListNode as the last node in the list.
     * @param node The node to be added.
     */
    public void addAsLastNode(DListNode node) {
    	DListNode lNode = last.prev;
    	node.next = last;
    	node.prev = lNode;
    	lNode.next = last.prev = node;
    	size++;
    }
    
    /**
     * Add an object as the last node in the list.
     * @param object The object to be added.
     * @return The DListNode enclosing the object. This
     *	DListNode object can later be used to delink
     *	the object from the list in constant time.
     */
    public DListNode addAsLastObject(Object obj) {
    	DListNode node= nodeFactory.createDListNode(obj);
    	addAsLastNode(node);
    	return node;
    }
    
    /**
     * Removes the first DListNode from the list.
     * @return The DListNode at the head of the list or null if the list is empty.
     */
    public DListNode delinkFirstNode() {
    	if (size > 0) {
    		DListNode node = first.next;
    		node.delink();
    		size--;
    		return node;
    	}
    	return null;
    }
    
    /**
     * Removes the first object from the list.
     * @return The object at the head of the list or null if the list is empty.
     */
    public Object removeFirstObject() {
    	DListNode node = delinkFirstNode();
    	if (node == null) {
    		return null;
    	} else {
    		Object object = node.object;
    		destroyDListNode(node);
    		return object;
    	}
    }
    
    
    /**
     * Removes the last DListNode from the list.
     * @return The DListNode at the tail of the list or null if the list is empty.
     */
    public DListNode delinkLastNode() {
    	if (size > 0) {
    		DListNode node = last.prev;
    		node.delink();
    		size--;
    		return node;
    	}
    	return null;
    }
    
    /**
     * Removes the last object from the list.
     * @return The object at the tail of the list or null if the list is empty.
     */
    public Object removeLastObject() {
    	DListNode node = delinkLastNode();
    	if (node == null) {
    		return null;
    	} else {
    		Object object = node.object;
    		destroyDListNode(node);
    		return object;
    	}
    }
        

    /**
     * Obtains the DListNode that contains this object. The method relies on the 
     *	equals() method to identify objects in the list. Note that this
     *	method is an O(n) operation as it has to iterate through the nodes
     *	in the list till a match is found.
     * @return The DListNode holding this object or null if the object is not in the list.
     */
    public DListNode getDListNode(Object o) {
    	for (DListNode node = first.next; node != last; node = node.next) {
    		if (node.object.equals(o)) {
    			return node;
    		}
    	}
    	return null;
    }
    
    public void delink(DListNode node) {
    	node.delink();
    	size--;
    }
    
    /**
     * Obtains the DListNode at the specified index. Note that this
     *	method is an O(n) operation as it has to iterate through the nodes
     *	in the list till a match is found.
     * @return The DListNode at the specifed index or null if the index is invalid.
     */
    public DListNode getDListNodeAt(int index) {
    	if ((index < 0) || (index >= size)) {
    		throw new ArrayIndexOutOfBoundsException("DList size: " + size + "; index: " + index);
    	}
    	int mid = size >> 1;	//Divide by 2!!
   		DListNode node = null;
    	if (index <= mid) {
    		node = first.next;
    		for (int i=0; i<index ; i++) {
    			node = node.next;
    		}
    	} else {
    		index = size - index - 1;
    		node = last.prev;
    		for (int i=0; i<index ; i++) {
    			node = node.prev;
    		}
    	}
    	return node;
    }
    
    public DListNode getFirstDListNode() {
    	return (size == 0) ? null : first.next;
    }
    
    public DListNode getLastDListNode() {
    	return (size == 0) ? null : last.prev;
    }
    
    public DListNode getNextNode(DListNode node) {
    	DListNode nextNode = node.next;
    	return (nextNode == last) ? null : nextNode;
    }
    
    public DListNode getPreviousNode(DListNode node) {
    	DListNode prevNode = node.prev;
    	return (prevNode == first) ? null : prevNode;
    }
    
    /**
     * Returns an iterator for iterating the entries in the list. Each object returned
     *	by the iterator.next() is an instance of DListNode. Use DListNode.object to
     *	retrieve the object.
     * @return An iterator.
     */
	public Iterator nodeIterator() {
		return new DListIterator( first, last, true, 0);
	}
	

    
    
    
    
	/************************************************************************/
	/* ************** AN INNER CLASS FOR SUPPORTING ITERATOR ************** */
	
	private class DListIterator
		implements java.util.ListIterator
	{
		DListNode firstNode;
		DListNode lastNode;
		DListNode currentNode;
		boolean toReturnNode;
		int currentIndex = -1;
		
		DListIterator(DListNode firstNode, DListNode lastNode, boolean toReturnNode, int skip) {
			this.firstNode =  this.currentNode = firstNode;
			this.lastNode = lastNode;
			this.toReturnNode = toReturnNode;
			
			for (int i=0; i<skip; i++) {
				currentNode = currentNode.next;
			}
			this.currentIndex = skip;
			
		}
		
		DListIterator(int startIndex, int endIndex, boolean toReturnNode, int skip) {
			this.firstNode =  this.currentNode = firstNode;
			this.lastNode = getDListNodeAt(endIndex);
			this.toReturnNode = toReturnNode;
			
			for (int i=0; i<skip; i++) {
				currentNode = currentNode.next;
			}
			this.currentIndex = skip;
			
		}
		
		public void add(Object obj) {
			currentNode.insertAfter(nodeFactory.createDListNode(obj));	
		}
		
		public boolean hasNext() {
			return (currentNode.next != lastNode);
		}
		
		public boolean hasPrevious() {
			return (currentNode != firstNode);
		}
		
		public Object next() {
			if (currentNode.next == lastNode) {
				throw new java.util.NoSuchElementException("No next after this element");
			}
			currentNode = currentNode.next;
			currentIndex++;
			return (toReturnNode ? currentNode : currentNode.object);
		}
		
		public int nextIndex() {
			return (currentIndex+1);
		}
		
		public Object previous() {
			if (currentNode == firstNode) {
				throw new java.util.NoSuchElementException("No previous before this element");
			}
			DListNode node = currentNode;
			currentNode = currentNode.prev;
			currentIndex--;
			return (toReturnNode ? node : node.object);
		}
		
		public int previousIndex() {
			return (currentIndex-1);
		}
		
		public void remove() {
			throw new UnsupportedOperationException("list.remove() not supported by DList iterator....");
		}
		
		public void set(Object o) {
			throw new UnsupportedOperationException("list.remove() not supported by DList iterator....");
		}
	}


}