/**
 * 
 */
package dataStructures;

/**
 * @author Ricardo Gaspar Nr. 35277
 * @author Hugo Ant�nio Nr. 34334 Turno P2 Docente Vasco Amaral
 */
public class OrderedDoublyLL<K extends Comparable<K>, V> implements
		OrderedDictionary<K, V> {

	private static final long serialVersionUID = 1L;

	// Node at the head of the list.
	protected DListNode<Entry<K, V>> head;

	// Node at the tail of the list.
	protected DListNode<Entry<K, V>> tail;

	// Number of elements in the list.
	protected int currentSize;

	/**
	 * Construtor da OrderedDoublyLL. Inicializa a cabe�a, cauda e o tamanho da
	 * lista.
	 */
	public OrderedDoublyLL() {
		head = null;
		tail = null;
		currentSize = 0;
	}

	@Override
	public boolean isEmpty() {
		return currentSize == 0;
	}

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

	@Override
	public V find(K key) {
		V value = null;
		if (!this.isEmpty()) {
			DListNode<Entry<K, V>> node = findNode(key);
			if (node != null && node.getElement().getKey().compareTo(key) == 0)
				value = node.getElement().getValue();
		}
		return value;
	}

	@Override
	public V insert(K key, V value) {

		Entry<K, V> newEntry = new EntryClass<K, V>(key, value);
		if (this.isEmpty()) {
			addFirst(newEntry);
			return null;
		}

		DListNode<Entry<K, V>> nodeFound = findNode(key);
		if (nodeFound != null) {
			Entry<K, V> entryFound = nodeFound.getElement();

			if (entryFound.getKey().compareTo(key) == 0) {
				V resultValue = entryFound.getValue();
				nodeFound.setElement(newEntry);
				return resultValue;

			} else if (entryFound.getKey().compareTo(key) > 0) {
				if (nodeFound == head)
					addFirst(newEntry);
				else
					addMiddle(newEntry, nodeFound);
				return null;
			} 
		}
		addLast(newEntry);
		return null;
	}

	@Override
	public V remove(K key) {

		if (this.isEmpty())
			return null;

		DListNode<Entry<K, V>> nodeFound = findNode(key);

		if (nodeFound != null) {
			Entry<K, V> entryFound = nodeFound.getElement();
			if (entryFound.getKey().compareTo(key) == 0) {
				V resultValue = entryFound.getValue();
				if (nodeFound == head)
					removeFirstNode();
				else if (nodeFound == tail)
					removeLastNode();
				else
					removeMiddleNode(nodeFound);

				return resultValue;
			}
		}

		return null;
	}

	@Override
	public Iterator<Entry<K, V>> iterator() {

		return new DoublyLLIterator<Entry<K, V>>(head, tail);
	}

	@Override
	public Entry<K, V> minEntry() throws EmptyDictionaryException {

		if (this.isEmpty())
			return null;
		return head.getElement();
	}

	@Override
	public Entry<K, V> maxEntry() throws EmptyDictionaryException {

		if (this.isEmpty())
			return null;
		return tail.getElement();
	}

	/**
	 * M�todos Auxiliares
	 */

	/**
	 * Devolve o um n� da lista que contenha a chave dada. Caso n�o exista
	 * devolve o primeiro cuja chave � maior. Devolve <code>null</code> se
	 * chegar ao fim da lista sem encontrar o n� pretendido.
	 * 
	 * @param key
	 *            Chave do elemento a procurar.
	 * @return Devolve um <code>DListNode< Entry< K,V > ></code> com a chave (
	 *         <code>key</code>) dada, caso exista. Caso n�o exista: -
	 *         <code>DListNode< Entry< K,V > ></code> do primeiro n� cuja chave
	 *         � maior que <code>key</code>. - <code>null</code> quando
	 *         <code>key</code> � maior que todas as chaves existentes.
	 */
	protected DListNode<Entry<K, V>> findNode(K key) {
		DListNode<Entry<K, V>> node = head;
		while (node != null && node.getElement().getKey().compareTo(key) < 0)
			node = node.getNext();
		return node;
	}

	/**
	 * Adiciona um elemento � cabe�a da lista.
	 * 
	 * @param element
	 *            Elemento a inserir.
	 */
	protected void addFirst(Entry<K, V> element) {
		DListNode<Entry<K, V>> newNode = new DListNode<Entry<K, V>>(element,
				null, head);
		if (this.isEmpty())
			tail = newNode;
		else
			head.setPrevious(newNode);
		head = newNode;
		currentSize++;
	}

	/**
	 * Adiciona um elemento � cauda da lista.
	 * 
	 * @param element
	 *            Elemento a inserir.
	 */
	protected void addLast(Entry<K, V> element) {

		DListNode<Entry<K, V>> newNode = new DListNode<Entry<K, V>>(element,
				tail, null);
		if (this.isEmpty())
			head = newNode;
		else
			tail.setNext(newNode);
		tail = newNode;
		currentSize++;
	}

	/**
	 * Adiciona um elemento no meio da lista (entre dois n�s). O elemento �
	 * adicionado antes de um dado n�.
	 * 
	 * @param element
	 *            Elemento a inserir.
	 * @param node
	 *            N� seguinte ao elemento.
	 */
	protected void addMiddle(Entry<K, V> element, DListNode<Entry<K, V>> node) {

		DListNode<Entry<K, V>> PrevNode = node.getPrevious();
		DListNode<Entry<K, V>> newNode = new DListNode<Entry<K, V>>(element,
				PrevNode, node);
		PrevNode.setNext(newNode);
		node.setPrevious(newNode);
		currentSize++;
	}

	/**
	 * Remove a cabe�a da lista.
	 * 
	 * @Pre: A lista n�o est� vazia
	 */
	protected void removeFirstNode() {

		head = head.getNext();
		if (head == null)
			tail = null;
		else
			head.setPrevious(null);
		currentSize--;
	}

	/**
	 * Remove a cauda da lista.
	 * 
	 * @Pre: A lista n�o est� vazia
	 */
	protected void removeLastNode() {

		tail = tail.getPrevious();
		if (tail == null)
			head = null;
		else
			tail.setNext(null);
		currentSize--;
	}

	/**
	 * Remove um dado n� que se encontra a meio da lista.
	 * 
	 * @Pre: O n� n�o � cabe�a nem cauda da lista.
	 */
	protected void removeMiddleNode(DListNode<Entry<K, V>> node) {

		DListNode<Entry<K, V>> prevNode = node.getPrevious();
		DListNode<Entry<K, V>> nextNode = node.getNext();
		prevNode.setNext(nextNode);
		nextNode.setPrevious(prevNode);
		currentSize--;
	}

}