package structures;

import java.util.ArrayList;
import java.util.Random;

public class PNode<T extends Comparable<T>> {
	private PNode<T> m_prev;
	private PNode<T> m_next;
	private PNode<T> m_firstborn;
	private T m_key;




	public PNode(T key) {
		super();
		this.m_prev = null;
		this.m_next = null;
		this.m_firstborn = null;
		this.m_key = key;
	}

	public PNode<T> decreaseKey(PNode<T> root, T newKey) {
		m_key = newKey;
		if(m_prev == null) return this;

		if(m_next != null) m_next.m_prev = m_prev;
		if(isFirstborn()) m_prev.m_firstborn = m_next;
		else m_prev.m_next = m_next;

		m_next = m_prev = null;

		return merge(this, root);

	}
	
	
	
	

	private boolean isFirstborn() {
		return m_prev.m_firstborn == this;
	}

	public T getKey() {
		return m_key;
	}


	private void addFirstborn(PNode<T> node)
	{
		if(m_firstborn != null)
			m_firstborn.m_prev = node;

		node.m_next = m_firstborn;
		node.m_prev = this;
		m_firstborn = node;
	}


	
	
	
	
	
	static public <T extends Comparable<T>> PNode<T> extractMin(PNode<T> root)
	{
		if(root == null) return null;

		root.m_prev = root;
		PNode<T> head = root.m_firstborn;
		
		return mergePairs(head);
	}

	
	
	
	static public <T extends Comparable<T>> PNode<T> mergePairs(PNode<T> head)
	{
		if(head == null) return null;
		PNode<T> next = head.m_next;
		if(next == null) return head;
		PNode<T> rest = next.m_next;

		head.m_prev=head.m_next = null;
		next.m_prev=next.m_next = null;

		return merge(merge(head, next), mergePairs(rest)); // can be done in O(1) space
	}
	
	



	static public <T extends Comparable<T>> T lookupMin(PNode<T> root)
	{
		if(root == null) return null;
		else return root.m_key;
	}

	

	public PNode<T> merge(PNode<T> node)
	{
		if(node == null) return this;

		int cmp = m_key.compareTo(node.m_key);
		if(cmp < 0) 
		{
			addFirstborn(node);
			return this;
		}
		else
		{
			node.addFirstborn(this);
			return node;
		}
	}
	
	static public <T extends Comparable<T>> PNode<T> merge(PNode<T> a, PNode<T> b)
	{
		if(a == null) return b;
		else return a.merge(b);	
	}



	public static void main(String [] args)
	{
		Random rand = new Random();

		PairingHeap<Double> queue = new PairingHeap<>();
		
		int n =  10000;
		
		
		
		ArrayList<IReference<Double>> tbl = new ArrayList<>(n);


		for(int i = 0 ; i < n ; i++)
		{
			tbl.add(queue.insert(rand.nextDouble()));
		}
		
		
		
		
		

		for(int i = 0 ; i < n*n ; i++)
		{
			IReference<Double> p = tbl.get(rand.nextInt(n));

			p.decreaseKey(p.lookupKey() - rand.nextDouble());
		}
		
		for(int i = 0 ; i < n ; i++)
		{
			queue.insert(rand.nextDouble());
		}

		
		
		
		for(int i = 0 ; i < n/2 ; i++)
		{
				System.out.println(i + ":\t" + queue.extractMin());
			
				queue.insert(rand.nextDouble());
			//Pair<PNode<Double>, PNode<Double>> p = insert(queue,rand.nextDouble());
			//queue = p.fst();
		}

		
	
		System.out.println("**************************************************");
		

		long startTime = System.nanoTime();
		while(!queue.isEmpty())
		{
			queue.extractMin();
		}
		long endTime = System.nanoTime();
		
		System.out.println("Extract time: " + (endTime-startTime));

	}

	public boolean isValid() {
		return m_prev != this;
	}
}