#ifndef PriorityQueue_h
#define PriorityQueue_h
#include <iostream>
template <class T>
struct PriorityNode{
    short priority;                 //优先级
    T data;                         //数据域
    struct PriorityNode<T> * next; //指针域
};
#define PRIORITY_NUMBER 10
template < class T>
class PriorityQueue{
public:
    PriorityQueue();
    ~PriorityQueue();
    void Push(T x, short pri);
    T Pop();
    bool Empty();
    void PushAdjustLastNodeArray(short pri, PriorityNode<T> *p);//入队时调整数组
    void PopAdjustLastNodeArray(PriorityNode<T> *p);//出队时调整数组
private:
    PriorityNode <T> * front;                          //头结点
    PriorityNode <T> * lastNodeArray[PRIORITY_NUMBER]; //最后结点指针数组
};
template <class T>
PriorityQueue<T>::PriorityQueue(){
    front = new PriorityNode <T>;
    front->next = NULL;
    for(int i = 0; i< PRIORITY_NUMBER;i++){
        lastNodeArray[i] = front;
    }
}
template <class T>
PriorityQueue<T>::~PriorityQueue(){   //析构函数
    PriorityNode <T> * p = front;
    while(p){
        p = p->next;
        delete front;
        front = p;
    }
}
template <class T>
bool PriorityQueue<T>::Empty(){
    if(!front->next)
        return true;
    else
        return false;
}
template <class T>
void PriorityQueue<T>::Push(T x, short pri){
    if(pri>=PRIORITY_NUMBER) throw "Priority too great!";
    PriorityNode<T> *s = new PriorityNode<T>;
    s->data = x;
    s->priority = pri;
    //新结点加入到链中
    s->next = lastNodeArray[pri] -> next;
    lastNodeArray[pri]->next = s;
    PushAdjustLastNodeArray(pri,s);
}
template <class T>
T PriorityQueue<T>::Pop(){
    if(!front->next) throw "Queue is NULL";
    PriorityNode<T>*p = front->next;        //保存队头结点
    front->next = p->next;
    T x = p->data;
    PopAdjustLastNodeArray(p);
    delete p;
    return x;
}
template <class T>
void PriorityQueue<T>::PushAdjustLastNodeArray(short pri,PriorityNode<T> *p){
    short i= pri-1;
    while (i>=0 && lastNodeArray[i] == lastNodeArray[pri]){
        lastNodeArray[i] = p;
        i--;
    }
    lastNodeArray[pri] = p;
}
template <class T>
void PriorityQueue<T>::PopAdjustLastNodeArray(PriorityNode<T> *p){
    short pri = p->priority;
    if(lastNodeArray[pri] == p){  //只有当出队元素为该优先级最后一个元素时，才需要调整
        PriorityNode<T> * newLastNode = (pri==PRIORITY_NUMBER-1)?front:lastNodeArray[pri+1];
        short i = pri - 1;
        while(i>=0 && lastNodeArray[i] == lastNodeArray[pri]){
            lastNodeArray[i] = newLastNode;
        }
        lastNodeArray[pri] = newLastNode;
    }
    
}
#endif /* PriorityQueue_h */