/*
 *                 Sun Public License Notice
 * 
 * The contents of this file are subject to the Sun Public License
 * Version 1.0 (the "License"). You may not use this file except in
 * compliance with the License. A copy of the License is available at
 * http://www.sun.com/
 * 
 * The Original Code is NetBeans. The Initial Developer of the Original
 * Code is Sun Microsystems, Inc. Portions Copyright 1997-2001 Sun
 * Microsystems, Inc. All Rights Reserved.
 */
package org.netbeans.mdr.persistence.btreeimpl.btreestorage;
import java.util.*;

/** A doubly linked list in which the objects contain their pointers.
* this is used in preference to forte.util.LinkedList since objects can
* be removed from it in constant time.
* 

* Although this implements java.util.List, it has a few restrictions:
* 

* 

* Each element in an IntrusiveList must be a subclass of IntrusiveList.Member.
* 

* An element can only be a member of one IntrusiveList at a time, and
* can only appear at one postion in that list.
* 
* An IntrusiveList will often be manipulated with its native operations
* ([add|remove][First|Last]) rather than via the List interface.
*/
public class IntrusiveList extends AbstractSequentialList implements List {
    /* list head */
    private Member head;

    private int mySize;
    private int modLevel;

    /** create a new list */
    public IntrusiveList() {
        head = new Member();
        head.previous = head.next = head;
	modLevel = 0;
    }
    
    /** add an object at the head of the list */
    public void addFirst(Member m) {
    	addAfter(m, head);
    }

    /** add an object at the end of the list */
    public void addLast(Member m) {
    	addAfter(m, head.previous);
    }

    /** remove an object from the list */
    public void remove(Member m) {
	checkOwner(m);
        m.previous.next = m.next;
        m.next.previous = m.previous;
        m.previous = m.next = null;
	m.owner = null;
	mySize--;
	modLevel++;
    }

    /** remove the object at the head of the list */
    public Member removeFirst() {
        Member m = head.next;
        if (m == head)
            return null;
        remove(m);
        return m;
    }

    /** remove the object at the end of the list */
    public Member removeLast() {
        Member m = head.previous;
        if (m == head)
            return null;
        remove(m);
        return m;
    }

    /** return the number of elements in the list */
    public int size() {
    	return mySize;
    }
    
    /** return a ListIterator */
    public ListIterator listIterator(int index) {
    	return new ListItr(modLevel, index);
    }

    /* Add after aother element */
    private void addAfter(Member toAdd, Member afterMe) {
    	checkUnowned(toAdd);
	toAdd.next = afterMe.next;
	toAdd.previous = afterMe;
	toAdd.next.previous = toAdd;
	toAdd.previous.next = toAdd;
	toAdd.owner = this;
	mySize++;
	modLevel++;
    }

    /* Check that the object is a member of this list */
    private void checkOwner(Member m) {
    	if (m.owner != this) {
	    throw new IllegalArgumentException (
	    	"The object is not a member of the list!");
	}
    }

    private void checkUnowned(Member m) {
    	if (m.owner != null) {
	    throw new IllegalArgumentException (
	    	"The object is already a member of some list!");
	}
    }

    /** This class is an iterator over IntrusiveLists, returned by
    * IntrusiveList.listIterator. It exists to allow IntrusiveList to
    * implement java.util.List as a modifiable, variable-sized list.
    */
    class ListItr implements ListIterator {
	/* the member to be returned by next() */
	private Member nextMember;

	/* the last member returned by next() or previous() */
	private Member lastReturned;

	/* the index of the ember to be returned by next() */
	private int nextIndex;

	/* The modification level of the parent list the last time
	 * the iterator and parent synchronized 
	 */
	private int itrModLevel;

	/* true if the last time we returned a Member, it was from next(),
	 * not previous().  Only valid if lastReturned is non-null.
	 */
	boolean forward;

	ListItr(int level, int index) {
	    if (index < 0 || index > mySize) {
	    	throw new IndexOutOfBoundsException();
	    }
	    Member start = head;
	    for (int i = 0; i < index; i++) {
	    	start = start.next;
	    }
	    nextMember = start.next;
	    lastReturned = null;
	    nextIndex = index;
	    itrModLevel = level;
	}

	/** See if there's a next member, i.e. if we haven't 
	* wrapped around to the head */
	public boolean hasNext() {
	    checkLevel();
	    return nextMember != head;
	}

	/** See if there's a previous member, i.e. if we're not at the 
	* beginning */
	public boolean hasPrevious() {
	    checkLevel();
	    return nextMember.previous != head;
	}

	/** Return the index of the next member */
	public int nextIndex() {
	    checkLevel();
	    return nextIndex;
	}

	/** Return the index of the previous member */
	public int previousIndex() {
	    checkLevel();
	    return nextIndex - 1;
	}

	/** Get the next member */
	public Object next() {
	    checkLevel();
	    if (nextMember == head) {
	    	throw new NoSuchElementException();
	    }
	    lastReturned = nextMember;
	    nextMember = nextMember.next;
	    nextIndex++;
	    forward = true;
	    return lastReturned;
	}

	/** Get the previous member */
	public Object previous() {
	    checkLevel();
	    if (nextMember.previous == head) {
	    	throw new NoSuchElementException();
	    }
	    lastReturned = nextMember.previous;
	    nextMember = lastReturned;
	    nextIndex--;
	    forward = false;
	    return lastReturned;
	}

	/** remove the last member returned by next or previous (if any) */
	public void remove() {
	    checkLevel();
	    if (lastReturned == null) {
	    	throw new IllegalStateException();
	    }
	    nextMember = lastReturned.next;
	    IntrusiveList.this.remove(lastReturned);
	    lastReturned = null;
	    if (forward) {
	    	nextIndex--;
	    }
	    itrModLevel = modLevel;
	}

	/** Replace the last element returned by next or previous (if any) */
	public void set(Object o) {
	    checkLevel();
	    if (lastReturned == null) {
	    	throw new IllegalStateException();
	    }
	    Member m = (Member)o;
	    addAfter(m, lastReturned);
	    IntrusiveList.this.remove(lastReturned);
	    lastReturned = m;
	    nextMember = forward ? m.next : m;
	    itrModLevel = modLevel;
	}

	/** Insert a new member into the current position in the list 
	* (directly before the next element to be returned by next) */
	public void add(Object o) {
	    checkLevel();
	    Member m = (Member)o;
	    addAfter(m, nextMember.previous);
	    nextIndex++;
	    lastReturned = null;
	    itrModLevel = modLevel;
	}

	/* Check for concurrent modifications */
	private void checkLevel() {
	    if (itrModLevel != modLevel) {
	    	throw new ConcurrentModificationException();
	    }
	}
    }

    /** objects in an intrusive list must inherit from Member */
    public static class Member {
	IntrusiveList owner;
        Member previous;
        Member next;

    }
}