package general.datastructures;
import general.exceptions.EmptyListException;
/**
* A PriorityQueue for storing {@link Waypoint}s in a simple linked List.
*
* @version 0.4.1
* @since 0.4.0
* @author Tim
*/
public class PriorityQueue {
private PriorityNode head;
/**
* Creates an empty {@link PriorityQueue}
*/
public PriorityQueue()
{
head = null;
}
/**
* Stores the passed {@link Waypoint} in the {@link PriorityQueue}, ordered by the priority. A lower value means,
* that this object will be stored closer to the head. If the {@link Waypoint} is already stored in the {@link PriorityQueue}
* the entry will be updated, if the priority of the passed {@link Waypoint} is lower than the existing one
*
* @param wp The stored {@link Waypoint}
* @param priority Priority of the {@link Waypoint}.
*/
public void insert(Waypoint wp, double priority)
{
if (head!=null)
{
boolean update = head.insert(priority, wp);
if(update)
{
head = new PriorityNode(priority, wp, head);
head.remove(wp);
}
}
else
{
head = new PriorityNode(priority, wp);
}
}
/**
*
* @return Returns if the {@link PriorityQueue} is empty
*/
public boolean isEmpty()
{
return (head==null);
}
/**
* Returns and removes the first {@link Waypoint} of the {@link PriorityQueue}
*
* @return The first {@link Waypoint} stored in this {@link PriorityQueue}
* @throws EmptyListException Is thrown, if the List is empty
*/
public Waypoint getFirst() throws EmptyListException
{
if (head!=null)
{
Waypoint item = this.head.getWaypoint();
head = head.getNext();
return item;
}
throw new EmptyListException("Die Liste ist leer");
}
/**
* Checks if the passed {@link Waypoint} is contained in this {@link PriorityQueue}
*
* @param wp The {@link Waypoint} which is searched for
* @return True, if the {@link Waypoint} is contained, otherwise false
*/
public boolean contains(Waypoint wp)
{
if (head==null)
{
return false;
}
return head.contains(wp);
}
/**
* Tries to remove the passed {@link Waypoint} from the {@link PriorityQueue} recursively
*
* @param wp The {@link Waypoint} which should be removed
* @return True, if the {@link Waypoint} was removed
* @throws EmptyListException
*/
public boolean remove(Waypoint wp) throws EmptyListException
{
if (head==null)
{
throw new EmptyListException("The PriorityQueue is empty");
}
return head.remove(wp);
}
/**
* Prints out all information stored in this PriorityQueue ordered by their priority
*/
@Override
public String toString() {
String s = "Openlist:\n";
PriorityNode n = head;
while (n != null)
{
s += (n.toString()+"\n");
n = n.getNext();
}
return s;
}
}