習作 : LinkedDeque

gistfile1.java

package net.flourity.lib;

import java.util.*;

public class LinkedDeque<E> extends AbstractQueue<E> implements Deque<E>, Cloneable, java.io.Serializable
{
	private static final long serialVersionUID = -5959942865101061013L;

	private transient final Node<E> HEADER;
	private transient int size = 0;

	private transient int modCount = 0;

	public LinkedDeque()
	{
		HEADER = new Node<E>(null);
		HEADER.setNext(HEADER);
	}

	public LinkedDeque(Collection<E> c)
	{
		this();
		addAll(c);
	}

	@Override
	public void addFirst(E e)
	{
		if(!offerFirst(e)) throw new IllegalStateException();
	}

	@Override
	public void addLast(E e)
	{
		if(!offerLast(e)) throw new IllegalStateException();
	}

	@Override
	public boolean offerFirst(E e)
	{
		if(e==null) throw new NullPointerException();
		modCount++;
		new Node<E>(e).insertAfter(HEADER);
		size++;
		return true;
	}

	@Override
	public boolean offerLast(E e)
	{
		if(e==null) throw new NullPointerException();
		modCount++;
		new Node<E>(e).insertAfter(HEADER.prev);
		size++;
		return true;
	}

	@Override
	public E removeFirst()
	{
		if(size==0) throw new NoSuchElementException();
		modCount++;
		E res = HEADER.next.remove();
		size--;
		return res;
	}

	@Override
	public E removeLast()
	{
		if(size==0) throw new NoSuchElementException();
		modCount++;
		E res = HEADER.prev.remove();
		size--;
		return res;
	}

	@Override
	public E pollFirst()
	{
		return size==0 ? null : removeFirst();
	}

	@Override
	public E pollLast()
	{
		return size==0 ? null : removeLast();
	}

	@Override
	public E getFirst()
	{
		if(size==0) throw new NoSuchElementException();
		E res = HEADER.next.element;
		return res;
	}

	@Override
	public E getLast()
	{
		if(size==0) throw new NoSuchElementException();
		E res = HEADER.prev.element;
		return res;
	}

	@Override
	public E peekFirst()
	{
		return size==0 ? null : getFirst();
	}

	@Override
	public E peekLast()
	{
		return size==0 ? null : getLast();
	}

	@Override
	public boolean removeFirstOccurrence(Object o)
	{
		Node<E> entry = HEADER;
		while((entry=entry.next)!=HEADER)
		{
			if(o.equals(entry.element))
			{
				modCount++;
				entry.remove();
				size--;
				return true;
			}
		}
		return false;
	}

	@Override
	public boolean removeLastOccurrence(Object o)
	{
		Node<E> entry = HEADER;
		while((entry=entry.prev)!=HEADER)
		{
			if(o.equals(entry.element))
			{
				modCount++;
				entry.remove();
				size--;
				return true;
			}
		}
		return false;
	}

	@Override
	public boolean add(E e)
	{
		addLast(e);
		return true;
	}

	@Override
	public boolean offer(E e)
	{
		return offerLast(e);
	}

	@Override
	public E remove()
	{
		return removeFirst();
	}

	@Override
	public E poll()
	{
		return pollFirst();
	}

	@Override
	public E element()
	{
		return getFirst();
	}

	@Override
	public E peek()
	{
		return peekFirst();
	}

	@Override
	public void push(E e)
	{
		addFirst(e);
	}

	@Override
	public E pop()
	{
		return removeFirst();
	}

	@Override
	public Iterator<E> descendingIterator()
	{
		return new DescendingItr();
	}

	@Override
	public Iterator<E> iterator()
	{
		return new Itr();
	}

	@Override
	public int size()
	{
		return size;
	}


	private static class Node<E>
	{
		private Node<E> prev;
		private Node<E> next;
		private final E element;

		private Node(E value)
		{
			this.element = value;
		}
		private void insertAfter(Node<E> prev)
		{
			this.prev = prev;
			this.next = prev.next;
			this.next.prev = this;
			this.prev.next = this;
		}
		private void setNext(Node<E> next)
		{
			this.next = next;
			next.prev = this;
		}
		private E remove()
		{
			E res = element;
			next.prev = prev;
			prev.next = next;
			prev = null;
			next = null;
			return res;
		}
	}

	private class Itr implements Iterator<E>
	{
		private Node<E> now;
		private boolean canRemove = false;
		private int mod;

		public Itr()
		{
			now = HEADER;
			mod = modCount;
		}

		@Override
		public boolean hasNext()
		{
			return now.next!=HEADER;
		}

		@Override
		public E next()
		{
			checkModify();
			now = now.next;
			E res = now.element;
			canRemove = true;
			return res;
		}

		@Override
		public void remove()
		{
			if(canRemove)
			{
				checkModify();
				canRemove = false;
				modCount++;
				mod++;
				now = now.prev;
				now.next.remove();
				size--;
			}
			else throw new IllegalStateException();
		}

		private void checkModify()
		{
			if(mod!=modCount) throw new ConcurrentModificationException();
		}
	}

	private class DescendingItr implements Iterator<E>
	{
		private Node<E> now;
		private boolean canRemove = false;
		private int mod;

		public DescendingItr()
		{
			now = HEADER;
			mod = modCount;
		}

		@Override
		public boolean hasNext()
		{
			return now.prev!=HEADER;
		}

		@Override
		public E next()
		{
			checkModify();
			now = now.prev;
			E res = now.element;
			canRemove = true;
			return res;
		}

		@Override
		public void remove()
		{
			if(canRemove)
			{
				checkModify();
				canRemove = false;
				mod++;
				modCount++;
				now = now.next;
				now.prev.remove();
				size--;
			}
			else throw new IllegalStateException();
		}

		private void checkModify()
		{
			if(mod!=modCount) throw new ConcurrentModificationException();
		}
	}

}