package chap12;


import chap3.EmptyCollectionException;

/**
 * @author LbZhang
 * @version 创建时间：2015年11月30日 下午8:56:51
 * @description 类说明
 */
public class LinkedHeap<T extends Comparable<T>> extends LinkedBinaryTree<T> implements HeapADT<T> {

	public HeapNode<T> lastNode;

	public LinkedHeap() {
		super();
	}

	@Override
	public void addElement(T obj) {
		// 一个堆结点
		HeapNode<T> node = new HeapNode<T>(obj);

		if (root == null)
			root = node;// 如果为空 就把root指向当前的结点
		else {
			// 获取父结点 把需要添加的父结点返回
			HeapNode<T> nextParent = getNextParentAdd();

			if (nextParent.getLeft() == null)
				nextParent.setLeft(node);
			else
				nextParent.setRight(node);

			node.setParent(nextParent);
		}

		lastNode = node;// 最后的结点的引用
		modCount++;

		if (size() > 1)
			heapifyAdd();

	}

	/**
	 * 添加修改当前堆
	 */
	private void heapifyAdd() {
		T temp;
		// 获取最后一个结点
		HeapNode<T> next = lastNode;

		// 临时保存
		temp = next.getElement();

		// 如果不是root结点而且小于当前的结点的父结点就进行循环
		while ((next != root)
				&& (((Comparable) temp)
						.compareTo(next.getParent().getElement()) < 0)) {

			next.setElement(next.getParent().getElement());
			next = next.parent;
		}
		next.setElement(temp);// 放置到最后的结点

	}

	/**
	 * 获取当前需要添加位置的结点的父结点
	 * 
	 * @return
	 */
	private HeapNode<T> getNextParentAdd() {

		HeapNode<T> result = lastNode;// 当前的空白结点

		while ((result != root) && (result.getParent().getLeft() != result))
			result = result.getParent();

		if (result != root) {
			// /不是一个满堆
			if (result.getParent().getRight() == null)
				result = result.getParent();
			else {
				result = (HeapNode<T>) result.getParent().getRight();
				// 不断的向下寻找最后的父结点
				while (result.getLeft() != null)
					result = (HeapNode<T>) result.getLeft();
			}
		} else {// 当前堆是一个满堆
			while (result.getLeft() != null)
				result = (HeapNode<T>) result.getLeft();
		}

		return result;
	}

	@Override
	public T removeMin() throws EmptyCollectionException {
		if (isEmpty())
			throw new EmptyCollectionException("LinkedHeap");

		T minElement = root.getElement();

		if (size() == 1) {
			root = null;
			lastNode = null;
		} else {
			// 获取一个新的尾结点
			HeapNode<T> nextLast = getNewLastNode();

			if (lastNode.getParent().getLeft() == lastNode)
				lastNode.getParent().setLeft(null);
			else
				lastNode.getParent().setRight(null);

			((HeapNode<T>) root).setElement(lastNode.getElement());

			lastNode = nextLast;
			heapifyRemove();
		}

		modCount++;

		return minElement;
	}

	/**
	 * 这里面的规则其实比较简单 就是在描述的时候比较麻烦： 【1】首先我们需要在程序中找到当前的最后一个结点，
	 * 【2】然后判断如果当前结点不是根节点，并且是父结点的左孩子，就不断的迭代向上查找；反之终止迭代
	 * 【3】然后判断当前结点不是是根节点,就寻找当前结点父结点的左孩子 【4】获取当前结点的右孩子是不是空 如果不为空
	 * 迭代一直到result的右孩子为空为止
	 * 
	 * @return
	 * 
	 *         返回最新的最末结点
	 */
	private HeapNode<T> getNewLastNode() {
		HeapNode<T> result = lastNode;

		// 非根的右边结点
		while ((result != root) && (result.getParent().getLeft() == result))
			result = result.getParent();

		if (result != root)
			result = (HeapNode<T>) result.getParent().getLeft();

		while (result.getRight() != null)
			result = (HeapNode<T>) result.getRight();

		return result;
	}

	private void heapifyRemove() {

		T temp;
		HeapNode<T> node = (HeapNode<T>) root;//用户遍历的根结点
		HeapNode<T> left = (HeapNode<T>) node.getLeft();
		HeapNode<T> right = (HeapNode<T>) node.getRight();
		HeapNode<T> next;

		if ((left == null) && (right == null))
			next = null;
		else if (right == null)
			next = left;
		else if (((Comparable) left.getElement()).compareTo(right.getElement()) < 0)
			next = left;
		else
			next = right;

		temp = node.getElement();
		
		while ((next != null)
				&& (((Comparable) next.getElement()).compareTo(temp) < 0)) {
			node.setElement(next.getElement());
			node = next;
			left = (HeapNode<T>) node.getLeft();
			right = (HeapNode<T>) node.getRight();

			if ((left == null) && (right == null))
				next = null;
			else if (right == null)
				next = left;
			else if (((Comparable) left.getElement()).compareTo(right
					.getElement()) < 0)
				next = left;
			else
				next = right;
		}
		
		node.setElement(temp);

	}

	@Override
	public T findMin() {
		if (isEmpty())
			throw new EmptyCollectionException("LinkedHeap");

		return root.getElement();
	}



}