package cz.cuni.amis.utils.astar;
   
   import java.util.ArrayList;
   import java.util.Collection;
   import java.util.Comparator;
   import java.util.HashMap;
   import java.util.Iterator;
   import java.util.List;
   import java.util.Set;
  
  /**
   * This is Heap used by AStar algorithm.
   * 
   * Note that we assume that inserted Object has correctly implemented hashCode()
   * and equals() function!
   */
  public class AStarHeap<NODE> implements Collection<NODE> {
  	
  	private NODE[] nodes;
  	private int count;
  	private int items;
  	private HashMap<NODE, Integer> references;
  	private Comparator<NODE> cmp;
  	
  	private void grow(){
  		NODE[] tempNodes = (NODE[]) new Object[count*2];
  		for (int i = 0; i <= items; ++i){
  			tempNodes[i] = nodes[i];
  		}
  		nodes = tempNodes;
  		count = count * 2;
  	}
  	
  	private int left(int reference){
  		return 2*reference;
  	}
  	
  	private int right(int reference){
  		return 2*reference+1;
  	}
  	
  	private int upRef(int reference){
  		return reference / 2;
  	}
  	
  	private NODE getNode(int reference){
  		while (reference >= count) 
  			grow();		
  		return nodes[reference];
  	}
  	
  	private int downNode(int reference){
  		NODE currentNode = getNode(reference);
  		if (currentNode == null) {
  			return reference;
  		}
  		NODE leftNode = null;
  		NODE rightNode = null;
  		int way = 0;
  	
  		while (true){
  			way = 0;
  			leftNode = getNode(left(reference));
  			rightNode = getNode(right(reference));
  		
  			if ((leftNode == null) && (rightNode == null)){
  				references.put(currentNode, reference);
  				return reference;
  			}
  			if (rightNode == null) way = -1;
  			else
  				if (leftNode  == null) way = 1;
  			if (way == 0) way = cmp.compare(leftNode, rightNode);
  			
  			if (way < 0){
  				// we've got to ascend to the left
  				if (cmp.compare(currentNode, leftNode) > 0){
  					nodes[reference] = leftNode;
  					references.put(leftNode, new Integer(reference));
  					reference = left(reference);
  					nodes[reference] = currentNode;					
  				} else {
  					references.put(currentNode, reference);				
  					return reference;
  				}				 
  			} else {
  				// we've got to ascend to the right
  				if (cmp.compare(currentNode, rightNode) > 0){
  					nodes[reference] = rightNode;
  					references.put(rightNode, new Integer(reference));
  					reference = right(reference);
  					nodes[reference] = currentNode;					
  					
  				} else {
  					references.put(currentNode, reference);				
  					return reference;
  				}				 
  			}			
  		}		
 	}
 	
 	private int upNode(int reference){
 		if (reference == 1) 
 			return reference;
 		NODE currentNode = getNode(reference);
 		if (currentNode == null) 
 			return reference;
 		NODE upNode = null;
 		while (reference > 1){
 			upNode = getNode(upRef(reference));
 			if (cmp.compare(currentNode, upNode) < 0){
 				nodes[reference] = upNode;
 				references.put(upNode, reference);				
 				reference = upRef(reference);
 			} else {
 				break;
 			}
 		}
 		nodes[reference] = currentNode;
 		references.put(currentNode, reference);
 		return reference;
 	}
 	
 	private void initHeap(int capacity){
 		if (capacity < 2) capacity = 2;
 		nodes = (NODE[]) new Object[capacity];
 		count = capacity;
 		items = 0;
 		references = new HashMap(capacity);
 	}
 	
 	public AStarHeap(Comparator<NODE> comp, int capacity){
 		initHeap(capacity);	
 		cmp = comp;
 	}
 	
 	public AStarHeap(Comparator<NODE> comp){
 		initHeap(20);
 		cmp = comp;
 	}
 	
 	public NODE getMin(){
 		return nodes[1]; // capacity is always >= 1
 	}
 	
 	public boolean deleteMin(){
 		if (items == 0) 
 			return false;
 		return remove(nodes[1], 1);
 	}
 	
 	public boolean decreaseKey(NODE arg0){
 		Integer reference = (Integer)references.get(arg0);
 		if (reference == null){
 			return add(arg0);
 		}
 		upNode(reference.intValue());
 		return true;
 	}
 
 	public boolean add(NODE arg0) {
 		Integer reference = (Integer)references.get(arg0);
 		if (reference == null){
 			getNode(items+1); // ensure that capacity is sufficient
 			nodes[items+1] = arg0;
 			upNode(items+1);
 			items = items + 1;
 			return true;
 		} else {
 			int tempRef = upNode(reference.intValue());
 			if (tempRef == reference.intValue()) 
 				downNode(reference.intValue());
 			return true;
 		}		
 	}
 
 	@Override
 	public boolean addAll(Collection arg0) {
 		Iterator<NODE> iter = arg0.iterator();
 		while (iter.hasNext())
 			add(iter.next());		
 		return true;
 	}
 	
 	public boolean addAll(NODE[] arg0){
 		boolean ok = true;
 		for (int i = 0; i < arg0.length; ++i){
 			ok = this.add(arg0[i]) && ok;
 		}
 		return ok;
 	}
 
 	public void clear() {
 		for (int i = 0; i < count; ++i){
 			nodes[i] = null;
 			references.clear();
 		}
 	}
 
 	public boolean contains(Object arg0) {
 		return references.containsKey(arg0);		
 	}
 
 	public boolean containsAll(Collection arg0) {
 		return references.containsKey(arg0);
 	}
 	
 	public boolean containsAll(Object[] arg0) {
 		for (int i = 0; i < arg0.length; ++i){
 			if (!this.contains(arg0[i])) {
 				return false;
 			}
 		}
 		return true;
 	}
 
 	public boolean isEmpty() {
 		return references.isEmpty();
 	}
 
 	public Iterator<NODE> iterator() {
 		return new AStarHeapIterator<NODE>(nodes, items, this);
 	}
 	
 	private boolean remove(NODE arg0, int reference){
 		references.remove(arg0);
 		if (items == 1){
 			nodes[1] = null;
 			items = 0;
 			return true;
 		}
 		nodes[reference] = nodes[items];
 		nodes[items] = null;
 		items = items - 1;
 		downNode(reference);	
 		return true;
 	}
 
 	public boolean remove(Object arg0) {
 		Integer reference = (Integer)references.get(arg0);
 		if (reference == null) 
 			return false;
 		return remove(reference.intValue());		
 	}
 
 	public boolean removeAll(Collection arg0) {
 		Iterator iter = arg0.iterator();
 		while (iter.hasNext())
 			remove(iter.next());
 		return true;
 	}
 
 	public boolean retainAll(Collection arg0) {
 		Iterator iter = references.keySet().iterator();
 		Object item; Integer reference;
 		while (iter.hasNext()){
 			item = iter.next();
 			reference = (Integer)references.get(item);
 			if (!arg0.contains(item)) remove((NODE) item, reference.intValue());
 		}
 		return true;
 	}
 
 	public int size() {
 		return items;
 	}
 	
 	public boolean empty() {
 		return items == 0;
 	}
 
 	public Object[] toArray() {
 		return references.keySet().toArray();
 	}
 
 	public Object[] toArray(Object[] arg0) {
 		return references.keySet().toArray(arg0);
 	}
 	
 	public Set toSet(){
 		return references.keySet();
 	}
 
 	
 // =======================
 // MAIN METHOD - TEST ONLY
 // =======================
 	
 	public static String mainToStr(Integer[] nums){
 		if (nums.length == 0) return "";
 		String str = nums[0].toString();
 		for (int i = 1; i < nums.length; ++i){
 			str += ", " + nums[i].toString();
 		}
 		return str;
 	}
 	
 	public static boolean mainCheck(AStarHeap heap, Integer[] nums){
 		System.out.println("Removing and checking " + mainToStr(nums));
 		List heapInts = new ArrayList();
 		List desiredInts = new ArrayList();
 		for (int i = 0; i < nums.length; ++i){
 			desiredInts.add(nums[i]);
 			heapInts.add(heap.getMin());
 			heap.deleteMin();
 		}
 		if ( heapInts.containsAll(desiredInts) ){
 			System.out.println("OK");
 			return true;
 		} else {
 			System.out.println("KO!");
 			System.exit(1);
 		}
 		return false;
 	}
 	
 	public static void mainAdd(AStarHeap heap, Integer[] nums){
 		System.out.println("Adding: " + mainToStr(nums));
 		for (int i = 0; i < nums.length; ++i){
 			heap.add(nums[i]);
 		}
 	}
 	
 	public static void main(String[] args){
 		/*
 		AStarHeap heap = new AStarHeap(new Comparator(){
                                                             public int compare(Object arg0, Object arg1) {
                                                                     return (Integer)arg0 - (Integer)arg1;
                                                             }
                                                        },
                                                        20
                                                       );
 		
 		mainAdd(  heap, new Integer[]{10, 100, 1, 50, 5});
 		mainCheck(heap, new Integer[]{1,5});
 		mainCheck(heap, new Integer[]{10,50});
 		mainAdd(  heap, new Integer[]{80, 60, 70});
 		mainCheck(heap, new Integer[]{60, 70, 80, 100});
 		mainAdd(  heap, new Integer[]{5,8,3,7,4,1,9});
 		mainCheck(heap, new Integer[]{5,8,3,7,4,1,9});
 		mainAdd(  heap, new Integer[]{2,7,3,5,6,4,9,1});
 		mainCheck(heap, new Integer[]{1,2,3,4});
 		mainAdd(  heap, new Integer[]{20,70,30,50,60,2,3,1,4});
 		mainCheck(heap, new Integer[]{20,70,30,50,60,2,3,1,4,5,6,7,9});
 		*/
 	}
 	
 }