/*
    *  XNap - A P2P framework and client.
    *
    *  See the file AUTHORS for copyright information.
    *
    *  This program is free software; you can redistribute it and/or modify
    *  it under the terms of the GNU General Public License as published by
    *  the Free Software Foundation.
    *
   *  This program is distributed in the hope that it will be useful,
   *  but WITHOUT ANY WARRANTY; without even the implied warranty of
   *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   *  GNU General Public License for more details.
   *
   *  You should have received a copy of the GNU General Public License
   *  along with this program; if not, write to the Free Software
   *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
   */
  
  package org.xnap.util;
  
  import java.util.Iterator;
  import java.util.LinkedList;
  import java.util.ListIterator;
  
  /***
   * A list of {@link Object} objects that is sorted descending by priority. 
   *
   * <p>This class is thread safe.
   */
  public class PriorityQueue
  {
  
      //--- Constant(s) ---
  
      //--- Data field(s) ---
      
      protected LinkedList queue = new LinkedList();
  
      //--- Constructor(s) ---
  
      public PriorityQueue()
      {
      }
  
      //--- Method(s) ---
  
      private synchronized void add(Item e)
      {
  		boolean inserted = false;
  		for (ListIterator i = queue.listIterator(); 
  			 i.hasNext() && !inserted;) {
  			if (e.priority > ((Item)i.next()).priority) {
  				i.previous();
  				i.add(e);
  				inserted = true;
  			}
  		}
  
  		if (!inserted) {
  			queue.add(e);
  		}
      }
      
      /***
       * Adds <code>o</code>.
       */
      public synchronized void add(Object o, int priority)
      {
  		Item e = new Item(o, priority);
  		add(e);
      }
  
      /***
       * Adds <code>o</code> if not already in queue.
       */
      public synchronized boolean addUnique(Object o, int priority)
      {
  		Item e = new Item(o, priority);
  		if (queue.contains(e)) {
  			return false;
  		}
  		else {
  			add(e);
  			return true;
  		}
      }	    
      
      public synchronized void clear()
      {
  		queue.clear();
      }
  
  	//      public synchronized Object get(int index)
  	//      {
  	//  	return ((Item)queue.get(index)).o;
  	//      }
  
  	//      public synchronized int indexOf(Object o)
 	//      {
 	//  	return queue.indexOf(new Item(o));
 	//      }
 
     public synchronized boolean isEmpty()
     {
 		return queue.isEmpty();
     }
 
     public synchronized Iterator iterator()
     {
 		return new PriorityQueueIterator(queue.iterator());
     }
     
     /***
      * Returns the item with the highest priority without removing it.
      */
     public synchronized Object peek()
     {
 		return ((Item)queue.getFirst()).o;
     }
 
     /***
      * Removes and returns the item with the highest priority.
      */
     public synchronized Object pop()
     {
 		if (queue.size() == 0) {
 			return null;
 		}
 		return ((Item)queue.removeFirst()).o;
     }
     
     public synchronized boolean remove(Object o)
     {
 		return queue.remove(new Item(o));
     }
 
     public synchronized int size()
     {
 		return queue.size();
     }
 
 	//      public synchronized Object[] toArray()
 	//      {
 	//  	Object[] elements = new Object[queue.size()];
 	//  	int i = 0;
 	//  	for (Iterator it = queue.iterator(); it.hasNext(); i++) {
 	//  	    elements[i] = ((Item)it.next()).o;
 	//  	}
 	//  	return elements;
 	//      }
 
     private class Item 
     {
 		public Object o;
 		public int priority;
 	
 		public Item(Object o, int priority)
 		{
 			this.o = o;
 			this.priority = priority;
 		}
 
 		public Item(Object o)
 		{
 			this.o = o;
 		}
 
 		public boolean equals(Object object)
 		{
 			if (object instanceof Item) {
 				return o.equals(((Item)object).o);
 			}
 
 			return false;
 		}
 
     }
 
     private class PriorityQueueIterator implements Iterator {
 
 		Iterator iterator;
 
 		PriorityQueueIterator(Iterator iterator)
 		{
 			this.iterator = iterator;
 		}
 
 		public boolean hasNext()
 		{
 			return iterator.hasNext();
 		}
 
 		public Object next()
 		{
 			return ((Item)iterator.next()).o;
 		}
 
 		public void remove()
 		{
 			iterator.remove();
 		}
 
     }
 
 }