מימוש ל priority queue

[iceman90]

עצלנות משהו נפלה עלי, ואין לי יותר הרבה זמן או חשק לממש אחד כזה אז אם למישהי יש מימוש של  prioriry queue בבוידם או משהו, אני ממש אשמח אם הוא יחלוק אותו איתי.

תודה מראש.

עריכה כמעט שכחתי, ב-JAVA.

מטי.

[Holy]

sun כבר עשו את כל העבודה, כל מה שנשאר זה לחפש קצת באתר שלהם

import java.io.Serializable;

import java.util.*;

public class PriorityQueue

extends AbstractList

implements Serializable {

private final static int DEFAULT_PRIORITY_COUNT = 10;

private final static int DEFAULT_PRIORITY = 0;

private List queue[];

public PriorityQueue() {

this(DEFAULT_PRIORITY_COUNT);

}

public PriorityQueue(Collection col) {

this(col, DEFAULT_PRIORITY_COUNT);

}

public PriorityQueue(int count) {

this(null, count);

}

public PriorityQueue(Collection col, int count) {

if (count <= 0) {

throw new IllegalArgumentException(

"Illegal priority count: "+ count);

}

queue = new List[count];

if (col != null) {

addAll(col);

}

}

public boolean add(Object element) {

insert(element, DEFAULT_PRIORITY);

return true;

}

public void insert(Object element, int priority) {

if (priority < 0) {

throw new IllegalArgumentException(

"Illegal priority: " + priority);

}

if (queue[priority] == null) {

queue[priority] = new LinkedList();

}

queue[priority].add(element);

modCount++;

}

public Object getFirst() {

return iterator().next();

}

public Object get(int index) {

if (index < 0) {

throw new IllegalArgumentException(

"Illegal index: "+ index);

}

Iterator iter = iterator();

int pos = 0;

while (iter.hasNext()) {

Object obj = iter.next();

if (pos == index) {

return obj;

} else

{

pos++;

}

}

return null;

}

public void clear() {

for (int i=0, n=queue.length; i<n; i++) {

if (queue != null) {

queue.clear();

}

}

}

public Object removeFirst() {

Iterator iter = iterator();

Object obj = iter.next();

iter.remove();

return obj;

}

public int size() {

int size = 0;

for (int i=0, n=queue.length; i<n; i++) {

if (queue != null) {

size += queue.size();

}

}

return size;

}

public Iterator iterator() {

Iterator iter = new Iterator() {

int expectedModCount = modCount;

int priority = queue.length - 1;

int count = 0;

int size = size();

// Used to prevent successive remove() calls

int lastRet = -1;

Iterator tempIter;

// Get iterator for highest priority

{

if (queue[priority] == null) {

tempIter = null;

} else {

tempIter = queue[priority].iterator();

}

}

private final void checkForComodification() {

if (modCount != expectedModCount) {

throw new ConcurrentModificationException();

}

}

public boolean hasNext() {

return count != size();

}

public Object next() {

while (true) {

if ((tempIter != null) && (

tempIter.hasNext())) {

Object next = tempIter.next();

checkForComodification();

lastRet = count++;

return next;

} else {

// Get next iterator

if (--priority < 0) {

checkForComodification();

throw new NoSuchElementException();

} else {

if (queue[priority] == null) {

tempIter = null;

} else {

tempIter = queue[priority].iterator();

}

}

}

}

}

public void remove() {

if (lastRet == -1) {

throw new IllegalStateException();

}

checkForComodification();

tempIter.remove();

count--;

lastRet = -1;

expectedModCount = modCount;

}

};

return iter;

}

public String toString() {

StringBuffer buffer = new StringBuffer("{");

for (int n=queue.length-1, i=n; i>=0; --i) {

if (i != n) {

buffer.append(",");

}

buffer.append(i + ":");

if ((queue != null) && (

queue.size() > 0)) {

buffer.append(queue.toString());

}

}

buffer.append("}");

return buffer.toString();

}

}

נלקח מהאתר של sun

[iceman90]

תודה גבר. בסופו של דבר הצלחתי לשכנע את עצמי שאני צריך לעשות את זה או שזה לא יצא טוב, אז כתבתי אחד.

אגב... דרך ממש מוזרה לממש תור עדיפויות... יש דרכים יותר פשוטות.

מטי.