// **********************************************************************
//
// Copyright (c) 2003-2006 ZeroC, Inc. All rights reserved.
//
// This copy of Ice is licensed to you under the terms described in the
// ICE_LICENSE file included in this distribution.
//
// **********************************************************************

package Freeze;

//
// Stripped down LinkedList implementation for use in the Evictor. The
// API is similar to java.util.LinkedList.
//
// Major differences:
//  * listIterator() is not implemented.
//  * Operation riterator() returns a reverse iterator.
//  * This implementation also has the property that an Iterator can be
//    retained over structural changes to the list itself (similar to an
//    STL list).
//
public class LinkedList
{
    public
    LinkedList()
    {
        _header.next = _header.previous = _header;
    }

    public java.lang.Object
    getFirst()
    {
	if(_size == 0)
	{
	    throw new java.util.NoSuchElementException();
	}

	return _header.next.element;
    }

    public void
    addFirst(java.lang.Object o)
    {
	addBefore(o, _header.next);
    }

    public boolean
    isEmpty()
    {
	return _size == 0;
    }

    public int
    size()
    {
	return _size;
    }

    public java.util.Iterator
    iterator()
    {
	return new ForwardIterator();
    }

    public java.util.Iterator
    riterator()
    {
	return new ReverseIterator();
    }

    private class ForwardIterator implements java.util.Iterator
    {
	public boolean
	hasNext()
	{
	    return _next != null;
	}

	public java.lang.Object
	next()
	{
            if(_next == null)
	    {
                throw new java.util.NoSuchElementException();
	    }

	    _current = _next;

	    if(_next.next != _header)
	    {
		_next = _next.next;
	    }
	    else
	    {
		_next = null;
	    }
	    return _current.element;
	}

	public void
	remove()
	{
	    if(_current == null)
	    {
                throw new IllegalStateException();
	    }
	    LinkedList.this.remove(_current);
	    _current = null;
	}

	ForwardIterator()
	{
	    if(_header.next == _header)
	    {
		_next = null;
	    }
	    else
	    {
		_next = _header.next;
	    }
	    _current = null;
	}

	private Entry _current;
	private Entry _next;
    }

    private class ReverseIterator implements java.util.Iterator
    {
	public boolean
	hasNext()
	{
	    return _next != null;
	}

	public java.lang.Object
	next()
	{
            if(_next == null)
	    {
                throw new java.util.NoSuchElementException();
	    }

	    _current = _next;

	    if(_next.previous != _header)
	    {
		_next = _next.previous;
	    }
	    else
	    {
		_next = null;
	    }
	    return _current.element;
	}

	public void
	remove()
	{
	    if(_current == null)
	    {
                throw new IllegalStateException();
	    }
	    LinkedList.this.remove(_current);
	    _current = null;
	}

	ReverseIterator()
	{
	    if(_header.next == _header)
	    {
		_next = null;
	    }
	    else
	    {
		_next = _header.previous;
	    }
	    _current = null;
	}

	private Entry _current;
	private Entry _next;
    }

    private static class Entry 
    {
	java.lang.Object element;
	Entry next;
	Entry previous;

	Entry(java.lang.Object element, Entry next, Entry previous)
	{
	    this.element = element;
	    this.next = next;
	    this.previous = previous;
	}
    }

    private Entry
    addBefore(java.lang.Object o, Entry e)
    {
	Entry newEntry = new Entry(o, e, e.previous);
	newEntry.previous.next = newEntry;
	newEntry.next.previous = newEntry;
	_size++;
	return newEntry;
    }

    private void
    remove(Entry e)
    {
	if(e == _header)
	{
	    throw new java.util.NoSuchElementException();
	}

	e.previous.next = e.next;
	e.next.previous = e.previous;
	_size--;
    }

    private Entry _header = new Entry(null, null, null);
    private int _size = 0;
}