QUOTE(projeckt @ 15 Nov, 2008 - 05:39 PM)
QUOTE(pbl @ 15 Nov, 2008 - 02:05 PM)
Do your priorities have a predifed range (like 0 to 10) or they can go from -9999999 to +9999999 ?
They can go from -9999999 to +9999999. Lower priorities will be closer to the front of the queue.
Added a merge method to order the list. Still having trouble with incorporating it with my enqueue.. positionOf, clear and removeall not so much headway either.
CODE
/**
Prioritized queue class
@version 1.0
*/
import java.util.NoSuchElementException;
public class PrioritizedQueue<T extends Comparable<T>> {
private static class Node<T> {
public T data;
public int priority;
public Node <T> link;
}
private Node<T> head, last, cursor;
private int count;
/**
Construct an empty queue
*/
public PrioritizedQueue() {
head = last = new Node<T>();
cursor = null;
count = 0;
head.data = null;
head.link = null;
} /**
Add specified item to the rear of this queue, subject to the
specified priority; lower priority numbers have preference
[Runs in O(n) time]
@param item the item to be added
*/
public void enqueue(T item, int priority) {
last.link = new Node<T>();
last = last.link;
last.priority = priority;
last.data = item;
count++;
}
public PrioritizedQueue<T> merge(PrioritizedQueue<T> a, PrioritizedQueue<T> b){
PrioritizedQueue<T> result = new PrioritizedQueue<T>();
T aItem = a.first();
T bItem = b.first();
while (aItem != null && bItem != null) {
int c = aItem.compareTo(bItem);
if (c == 0) {
result.enqueue(aItem, last.priority);
aItem = a.next();
bItem = b.next();
} else if (c < 0) {
result.enqueue(aItem, last.priority);
aItem = a.next();
} else {
result.enqueue(bItem, last.priority);
bItem = b.next();
}
}
while (aItem != null) {
result.enqueue(aItem, last.priority);
aItem = a.next();
}
while (bItem != null) {
result.enqueue(bItem, last.priority);
bItem = b.next();
}
return result;
}
/**
Remove and return the item at the front of this queue
Throw NoSuchElementException if queue is empty
[Runs in O(1) time]
@param item the item to be inserted
*/
public T dequeue(T item) {
if (isEmpty()) {
throw new NoSuchElementException();
}
T result = head.link.data;
head.link = head.link.link;
count--;
if (count == 0) {
last = head;
}
return result;
}
/**
Determine the number of elements in the queue
[Runs in O(1) time]
@return the number of elements in the queue
*/
public int size() {
return count;
}
/**
Is the queue empty?
[Runs in O(1) time]
@return true if the queue is empty, false otherwise
*/
public boolean isEmpty() {
return size() == 0;
}
/**
Return the position of the specified item in this queue,
if found, and -1 if not found.
Position 0 is the front of the queue
[Runs in O(n) time]
@param item the item to locate
@return the position of the item, or -1
*/
int positionOf(T item) {
return;
}
/**
Clear the queue so that it is now empty
[Runs in O(1) time]
*/
public void clear() {
head = null;
count = 0;
cursor = null;
}
/**
Remove the first occurence of the specified item from the queue
Throw NoSuchElementException if item is not in queue
[Runs in O(n) time]
@param item the item to remove
*/
public void remove(T item) {
Node<T> prev = head;
Node<T> curr = head.link;
while (curr != null) {
if (item.equals(curr.data)) {
prev.link = curr.link;
if (curr == last ) {
last = prev;
}
count--;
return;
}
curr = curr.link;
prev = prev.link;
}
throw new NoSuchElementException();
}
/**
Remove all occurences of the specified item from the queue
Throw NoSuchElementException if item is not in queue
[Runs in O(n) time]
@param item the item to remove
*/
public void removeAll(T item) {
Node<T> curr = head.link;
Boolean found = false;
while (curr != head) {
if (item.equals(curr.data)) {
found = true;
curr.link = curr.link.link;
count--;
}
curr = curr.link;
}
if(!found){
throw new NoSuchElementException();
}
}
/**
Get the first element in the queue; set the cursor for iteration
[Runs in O(1) time]
@return the first element in the last; null if queue is empty
*/
public T first() {
cursor = head.link;
if (cursor == null) {
return null;
}
return cursor.data;
}
/**
Get the next element in the queue, relative to a previous call
[Runs in O(1) time]
@return the next element in the queue; null if no more elements
*/
public T next() {
cursor = cursor.link;
if (cursor == null) {
return null;
}
return cursor.data;
}
}
Forum Index:
Programming Help |
C and C++ |
VB6 |
Java |
VB.NET |
C# |
ASP.NET |
PHP |
ColdFusion |
Perl and Python |
Ruby |
Databases |
Other Languages |
Game Programming |
Mobile Development |
Software Development |
Computer Science |
Industry News |
Programming Tutorials |
C++ Tutorials |
Visual Basic Tutorials |
Java Tutorials |
VB.NET Tutorials |
C# Tutorials |
Linux Tutorials |
PHP Tutorials |
ColdFusion Tutorials |
Windows Tutorials |
HTML/JavaScript Tutorials |
CSS Tutorials |
Flash Tutorials |
Web Promotion Tutorials |
Graphic Design & Photoshop Tutorials |
Software Development Tutorials |
Database Tutorials |
Other Language Tutorials |
ASP.NET Tutorials |
Game Programming Tutorials |
15 Nov, 2008 - 01:15 AM
| 
