Я пытаюсь реализовать приоритетную очередь для использования двусвязного списка с дозорными. Я хочу пузырьковую сортировку в enqueue(). Я знаю, что у этого способа нет большой сложности, но я хочу его использовать. Проблема в том, что пузырьковая сортировка не работает. Проблема выглядит скрытой в bubbleSort() или swapToNext(). Может быть, ветка, когда проблема будет в else if (before == front), может вызвать проблему. В любом случае, я полностью запуталась. Итак, не могли бы вы помочь решить эту проблему?
public class Node {
String name;
Node next;
Node prev;
int priority;
Node(String name, int priority){
this.name = name;
next = null;
prev = null;
this.priority = priority;
}
public String getName() {
return this.name;
}
public String toString(){
return this.prev.name + " <== [" + this.name + "] ==> " + this.next.name;
}
}
public class PriorityQueue {
private Node front = null;
private Node rear = null;
private int size = 0;
private Node sentinelNode;
static final String SENTINEL = "*SENTINEL*";
PriorityQueue(){
sentinelNode = new Node(SENTINEL,Integer.MIN_VALUE);
clear();
}
public void clear(){
front = sentinelNode;
rear = sentinelNode;
front.next = rear;
rear.prev = front;
size = 0;
}
public boolean isEmpty(){
return size == 0;
}
public boolean enqueue(String name, int priority){
try {
Node newNode = new Node(name,priority);
rear.next = newNode;
newNode.prev = rear;
newNode.next = front;
front.prev = newNode;
rear = newNode;
size++;
bubbleSort();
return true;
} catch (Exception e){
System.out.println(e);
return false;
}
}
private void bubbleSort() {
if (isEmpty() || size < 3) {
return;
}
for(int i=0;i < size-1;i++) {
Node current = front.next;
do {
if (current.priority > current.next.priority) {
swapToNext(current);
}
current = current.next;
} while(current != rear);
}
}
private void swapToNext(Node node) {
Node current = node;
Node before, after;
before =current.prev;
after = current.next;
if (before != front && after != rear) {
before.next = after;
current.next = after.next;
current.prev = after;
after.next = current;
after.prev = before;
} else if (before == front && after == rear) {
front.next = after;
current.next = front; // Cuz current gonna be rear.
current.prev = after;
after.next = current;
after.prev = front;
rear = current;
} else if (before == front) {
front.next = after;
current.next = after.next;
current.prev = after;
after.next = current;
after.prev = front;
} else if (after == rear) {
before.next = after;
current.next = front;
current.prev = after;
after.next = current;
after.prev = before;
rear = current;
} else {
return;
}
}
public Node dequeue(){
if (isEmpty()){
return null;
}else{
Node result = front.next;
Node resultNext = result.next;
front.next = resultNext;
resultNext.prev = front;
size--;
if (size==0){
rear = front;
}
return result;
}
}
public String toString(){
Node pos = front.next;
String s = "Queue=[\n";
while(pos != front){
s += " " + pos + "\n";
pos = pos.next;
}
s += "]\n front=" + front + "\n rear=" + rear;
return s;
}
}
public class Main {
static int isEmptyCount = 0;
static int isEmptyCorrectCount = 0;
static int enqueueCount = 0;
static int enqueueCorrectCount = 0;
static int dequeueCount = 0;
static int dequeueCorrectCount = 0;
public static void resetCount() {
isEmptyCount = 0;
isEmptyCorrectCount = 0;
enqueueCount = 0;
enqueueCorrectCount = 0;
dequeueCount = 0;
dequeueCorrectCount = 0;
}
public static void enqueueTest(PriorityQueue pq, String name, int priority, boolean estimated) {
enqueueCount++;
if (test(" enqueue("+name+")" , pq.enqueue(name,priority), estimated)) enqueueCorrectCount++;
}
public static void dequeueTest(PriorityQueue pq, String estimated) {
dequeueCount++;
if (test(" dequeue", pq.dequeue().name, estimated)) dequeueCorrectCount++;
}
public static void isEmptyTest(PriorityQueue pq, boolean estimated) {
isEmptyCount++;
if (test("isEmpty", pq.isEmpty(), estimated)) isEmptyCorrectCount++;
}
static public void printTestResult(String label, int count, int total) {
System.out.print(label + ": " + count + "/" + total + " ");
if (count == total) System.out.println("OK");
else System.out.println("NG");
}
static public void printAllTestResult() {
printTestResult(" isEmpty", isEmptyCorrectCount, isEmptyCount);
printTestResult(" enqueue", enqueueCorrectCount , enqueueCount);
printTestResult(" dequeue", dequeueCorrectCount , dequeueCount);
}
static public boolean test(String label, Object data, String estimated) {
System.out.print(label + ": result[" + data + "] estimated[" + estimated + "] ");
try {
if (data.equals(estimated)) { System.out.println("success."); return true;}
else { System.out.println("failure."); return false;}
} catch (NullPointerException e) {
System.out.println("failure. " + e); return false;
}
}
static public boolean test(String label, boolean result, boolean estimated) {
System.out.print(label + ": result[" + result + "] estimated[" + estimated + "] ");
if (result == estimated) { System.out.println("success."); return true;}
else { System.out.println("failure."); return false;}
}
public static void main(String[] args){
resetCount();
PriorityQueue pq = new PriorityQueue();
for (int i=1;i <= 10; i++) {
enqueueTest(pq, String.valueOf(i), i,true);
}
System.out.println(pq);
for (int i=1;i <= 10; i++) {
dequeueTest(pq, String.valueOf(i));
}
System.out.println(pq);
printAllTestResult();
for (int i=10;i >= 1; i--) {
enqueueTest(pq, String.valueOf(i), i,true);
}
System.out.println(pq);
for (int i=1;i <= 10; i++) {
dequeueTest(pq, String.valueOf(i));
}
System.out.println(pq);
printAllTestResult();
enqueueTest(pq, String.valueOf(4), 4,true);
enqueueTest(pq, String.valueOf(9), 9,true);
enqueueTest(pq, String.valueOf(2), 2,true);
enqueueTest(pq, String.valueOf(10), 10,true);
enqueueTest(pq, String.valueOf(1), 1,true);
enqueueTest(pq, String.valueOf(3), 3,true);
enqueueTest(pq, String.valueOf(7), 7,true);
enqueueTest(pq, String.valueOf(5), 5,true);
enqueueTest(pq, String.valueOf(6), 6,true);
enqueueTest(pq, String.valueOf(8), 8,true);
for (int i=1;i <= 10; i++) {
dequeueTest(pq, String.valueOf(i));
}
System.out.println(pq);
printAllTestResult();
enqueueTest(pq, String.valueOf(4), 4,true);
enqueueTest(pq, String.valueOf(9), 9,true);
enqueueTest(pq, String.valueOf(2), 2,true);
enqueueTest(pq, String.valueOf(10), 10,true);
enqueueTest(pq, String.valueOf(1), 1,true);
enqueueTest(pq, String.valueOf(3), 3,true);
enqueueTest(pq, String.valueOf(7), 7,true);
enqueueTest(pq, String.valueOf(5), 5,true);
enqueueTest(pq, String.valueOf(6), 6,true);
enqueueTest(pq, String.valueOf(8), 8,true);
enqueueTest(pq, String.valueOf(10), 10,true);
enqueueTest(pq, String.valueOf(7), 7,true);
enqueueTest(pq, String.valueOf(2), 2,true);
enqueueTest(pq, String.valueOf(9), 9,true);
enqueueTest(pq, String.valueOf(4), 4,true);
enqueueTest(pq, String.valueOf(3), 3,true);
enqueueTest(pq, String.valueOf(1), 1,true);
enqueueTest(pq, String.valueOf(6), 6,true);
enqueueTest(pq, String.valueOf(5), 5,true);
enqueueTest(pq, String.valueOf(8), 8,true);
for (int i=1;i <= 10; i++) {
dequeueTest(pq, String.valueOf(i));
dequeueTest(pq, String.valueOf(i));
}
System.out.println(pq);
printAllTestResult();
}
}
Это результат прямо сейчас.
enqueue(1): result[true] estimated[true] success.
enqueue(2): result[true] estimated[true] success.
enqueue(3): result[true] estimated[true] success.
enqueue(4): result[true] estimated[true] success.
enqueue(5): result[true] estimated[true] success.
enqueue(6): result[true] estimated[true] success.
enqueue(7): result[true] estimated[true] success.
enqueue(8): result[true] estimated[true] success.
enqueue(9): result[true] estimated[true] success.
enqueue(10): result[true] estimated[true] success.
Queue=[
*SENTINEL* <== [1] ==> 2
1 <== [2] ==> 3
2 <== [3] ==> 4
3 <== [4] ==> 5
4 <== [5] ==> 6
5 <== [6] ==> 7
6 <== [7] ==> 8
7 <== [8] ==> 9
8 <== [9] ==> 10
9 <== [10] ==> *SENTINEL*
]
front=10 <== [*SENTINEL*] ==> 1
rear=9 <== [10] ==> *SENTINEL*
dequeue: result[1] estimated[1] success.
dequeue: result[2] estimated[2] success.
dequeue: result[3] estimated[3] success.
dequeue: result[4] estimated[4] success.
dequeue: result[5] estimated[5] success.
dequeue: result[6] estimated[6] success.
dequeue: result[7] estimated[7] success.
dequeue: result[8] estimated[8] success.
dequeue: result[9] estimated[9] success.
dequeue: result[10] estimated[10] success.
Queue=[
]
front=*SENTINEL* <== [*SENTINEL*] ==> *SENTINEL*
rear=*SENTINEL* <== [*SENTINEL*] ==> *SENTINEL*
isEmpty: 0/0 OK
enqueue: 10/10 OK
dequeue: 10/10 OK
enqueue(10): result[true] estimated[true] success.
enqueue(9): result[true] estimated[true] success.
enqueue(8): result[true] estimated[true] success.
enqueue(7): result[true] estimated[true] success.
enqueue(6): result[true] estimated[true] success.
enqueue(5): result[true] estimated[true] success.
enqueue(4): result[true] estimated[true] success.
enqueue(3): result[true] estimated[true] success.
enqueue(2): result[true] estimated[true] success.
enqueue(1): result[true] estimated[true] success.
Queue=[
*SENTINEL* <== [1] ==> 2
1 <== [2] ==> 10
1 <== [10] ==> *SENTINEL*
]
front=1 <== [*SENTINEL*] ==> 1
rear=1 <== [10] ==> *SENTINEL*
dequeue: result[1] estimated[1] success.
dequeue: result[2] estimated[2] success.
dequeue: result[10] estimated[3] failure.
dequeue: result[*SENTINEL*] estimated[4] failure.
dequeue: result[*SENTINEL*] estimated[5] failure.
dequeue: result[*SENTINEL*] estimated[6] failure.
dequeue: result[*SENTINEL*] estimated[7] failure.
dequeue: result[*SENTINEL*] estimated[8] failure.
dequeue: result[*SENTINEL*] estimated[9] failure.
dequeue: result[*SENTINEL*] estimated[10] failure.
Queue=[
]
front=*SENTINEL* <== [*SENTINEL*] ==> *SENTINEL*
rear=*SENTINEL* <== [*SENTINEL*] ==> *SENTINEL*
isEmpty: 0/0 OK
enqueue: 20/20 OK
dequeue: 12/20 NG
enqueue(4): result[true] estimated[true] success.
enqueue(9): result[true] estimated[true] success.
enqueue(2): result[true] estimated[true] success.
enqueue(10): result[true] estimated[true] success.
enqueue(1): result[true] estimated[true] success.
enqueue(3): result[true] estimated[true] success.
enqueue(7): result[true] estimated[true] success.
enqueue(5): result[true] estimated[true] success.
enqueue(6): result[true] estimated[true] success.
enqueue(8): result[true] estimated[true] success.
dequeue: result[1] estimated[1] success.
dequeue: result[3] estimated[2] failure.
dequeue: result[5] estimated[3] failure.
dequeue: result[6] estimated[4] failure.
dequeue: result[8] estimated[5] failure.
dequeue: result[10] estimated[6] failure.
dequeue: result[*SENTINEL*] estimated[7] failure.
dequeue: result[*SENTINEL*] estimated[8] failure.
dequeue: result[*SENTINEL*] estimated[9] failure.
dequeue: result[*SENTINEL*] estimated[10] failure.
Queue=[
]
front=*SENTINEL* <== [*SENTINEL*] ==> *SENTINEL*
rear=*SENTINEL* <== [*SENTINEL*] ==> *SENTINEL*
isEmpty: 0/0 OK
enqueue: 30/30 OK
dequeue: 13/30 NG
enqueue(4): result[true] estimated[true] success.
enqueue(9): result[true] estimated[true] success.
enqueue(2): result[true] estimated[true] success.
enqueue(10): result[true] estimated[true] success.
enqueue(1): result[true] estimated[true] success.
enqueue(3): result[true] estimated[true] success.
enqueue(7): result[true] estimated[true] success.
enqueue(5): result[true] estimated[true] success.
enqueue(6): result[true] estimated[true] success.
enqueue(8): result[true] estimated[true] success.
enqueue(10): result[true] estimated[true] success.
enqueue(7): result[true] estimated[true] success.
enqueue(2): result[true] estimated[true] success.
enqueue(9): result[true] estimated[true] success.
enqueue(4): result[true] estimated[true] success.
enqueue(3): result[true] estimated[true] success.
enqueue(1): result[true] estimated[true] success.
enqueue(6): result[true] estimated[true] success.
enqueue(5): result[true] estimated[true] success.
enqueue(8): result[true] estimated[true] success.
dequeue: result[1] estimated[1] success.
dequeue: result[1] estimated[1] success.
dequeue: result[5] estimated[2] failure.
dequeue: result[8] estimated[2] failure.
dequeue: result[10] estimated[3] failure.
dequeue: result[*SENTINEL*] estimated[3] failure.
dequeue: result[*SENTINEL*] estimated[4] failure.
dequeue: result[*SENTINEL*] estimated[4] failure.
dequeue: result[*SENTINEL*] estimated[5] failure.
dequeue: result[*SENTINEL*] estimated[5] failure.
dequeue: result[*SENTINEL*] estimated[6] failure.
dequeue: result[*SENTINEL*] estimated[6] failure.
dequeue: result[*SENTINEL*] estimated[7] failure.
dequeue: result[*SENTINEL*] estimated[7] failure.
dequeue: result[*SENTINEL*] estimated[8] failure.
dequeue: result[*SENTINEL*] estimated[8] failure.
dequeue: result[*SENTINEL*] estimated[9] failure.
dequeue: result[*SENTINEL*] estimated[9] failure.
dequeue: result[*SENTINEL*] estimated[10] failure.
dequeue: result[*SENTINEL*] estimated[10] failure.
Queue=[
]
front=*SENTINEL* <== [*SENTINEL*] ==> *SENTINEL*
rear=*SENTINEL* <== [*SENTINEL*] ==> *SENTINEL*
isEmpty: 0/0 OK
enqueue: 50/50 OK
dequeue: 15/50 NG