/**
 * 
 */
package dataStructures1112;

/**
 * @author Ricardo Gaspar nº 35277 Ricardo Cruz nº 34951 Turno P8 Docente
 *         Armanda Rodrigues
 */
public class OrderedDoublyLL<K extends Comparable<K>, V> implements
		OrderedDictionary<K, V> {

	/**
	 * Número de série da versão.
	 */
	private static final long serialVersionUID = 1L;

	/**
	 * Cabeça da lista.
	 */
	private DListNode<Entry<K, V>> head;

	/**
	 * Cauda da lista.
	 */
	private DListNode<Entry<K, V>> tail;

	/**
	 * Tamanho da lista.
	 */
	private 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) {
		DListNode<Entry<K, V>> node = this.findNode(key);
		if (node != null) {
			if (key.compareTo(node.getElement().getKey()) == 0)
				return node.getElement().getValue();
			else
				return null;
		}
		return null;
	}

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

		DListNode<Entry<K, V>> node = this.findNode(key);
		Entry<K, V> newEntry = new EntryClass<K, V>(key, value);
		if (node != null && node.getElement().getKey().compareTo(key) == 0) {
			V oldValue = node.getElement().getValue();
			node.setElement(newEntry);
			return oldValue;
		}

		if (node != null && node.getElement().getKey().compareTo(key) > 0) {
			if (node == head)
				this.addFirst(newEntry);
			else
				this.addMiddle(newEntry, node);
		}

		else {
			if (currentSize != 0)
				this.addLast(newEntry);

			else
				this.addFirst(newEntry);
		}

		return null;
	}

	@Override
	public V remove(K key) {
		DListNode<Entry<K, V>> node = this.findNode(key);
		if (node == null)
			return null;
		K tempKey = node.getElement().getKey();
		V tempValue = node.getElement().getValue();
		if (tempKey.compareTo(key) > 0)
			return null;

		else if (currentSize == 1) {
			head = null;
			tail = null;
			currentSize--;
			return tempValue;
		}

		else if (node == head) {
			removeFirst();
			return tempValue;
		}

		else if (node == tail) {
			removeLast();
			return tempValue;
		} else
			removeMiddle(node);
		return tempValue;
	}

	@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())
			throw new EmptyDictionaryException();
		return head.getElement();
	}

	@Override
	public Entry<K, V> maxEntry() throws EmptyDictionaryException {
		if (this.isEmpty())
			throw new EmptyDictionaryException();
		return tail.getElement();
	}

	/**
	 * Procura um nó da lista, dado uma chave. Caso encontre o nó com a chave
	 * dada devolve-o. Caso a chave dada seja maior que as chaves existentes na
	 * lista, devolve <code>null</code>. Caso a chave seja menor, devolve o
	 * primeiro nó cuja chave é maior que a chave dada.
	 * 
	 * @param key
	 *            Chave do elemento a procurar.
	 * @return Devolve um nó(<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 é
	 *         menor 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 newEntry
	 *            Elemento a inserir.
	 * @param node
	 *            Nó seguinte ao elemento.
	 */
	protected void addMiddle(Entry<K, V> newEntry, DListNode<Entry<K, V>> node) {

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

	}

	/**
	 * Remove a cabeça da lista.
	 */
	protected void removeFirst() {
		head = head.getNext();
		head.setPrevious(null);
		currentSize--;
	}

	/**
	 * Remove a cauda da lista.
	 */
	protected void removeLast() {
		tail = tail.getPrevious();
		tail.setNext(null);
		currentSize--;
	}

	/**
	 * Remove um dado nó que se encontra no meio da lista.
	 * 
	 * @param node
	 *            Nó a remover.
	 */
	protected void removeMiddle(DListNode<Entry<K, V>> node) {
		DListNode<Entry<K, V>> previousNode = node.getPrevious();
		DListNode<Entry<K, V>> nextNode = node.getNext();
		previousNode.setNext(nextNode);
		nextNode.setPrevious(previousNode);
		currentSize--;
	}
}