/**
 * Created by Jan on 12.01.2017.
 */
public class Queue<T> implements MyQueue<T> {
    public Element<T> guard = new Element(null, -1);
    public int rozmiar;

    public Queue(){
        clear();
    }

    public void enqueue(T value, int priority){
        int index = 0;
        Element<T> element = guard.getNext();
        while(element.getPriority()>priority){
            element = element.getNext();
            index++;
        }
        insert(index, value, priority);
    }
    public T top(){
        if(rozmiar == 0)
            return null;
        else {
            return getElement(0);
        }
    }

    public void pop(){
        Element<T> element = getElementB(0);
        element.detach();
        rozmiar--;
    }
    public void merge(Queue<T> queue){
        for (int i = 0; i < queue.getSize(); i++)
        {
            this.enqueue(queue.getElement(i), queue.getElementB(i).getPriority());
        }
    }

    public void clear(){
        guard.setNext(guard);
        guard.setPrevious(guard);
        rozmiar = 0;
    }
    public void insert(int index, T value, int priority) throws IndexOutOfBoundsException {
        if (index < 0 || index > rozmiar) throw new IndexOutOfBoundsException();

        Element<T> element = new Element(value,priority);
        element.attachBefore(getElementB(index));

        rozmiar++;
    }


    public T getElement(int index){
        Element<T> element = guard.getNext();
        for (int i = 0; i < index; i++)
            element = element.getNext();
        return element.getValue();
    }
    public Element getElementB(int index){
        Element element = guard.getNext();
        for (int i = 0; i < index; i++)
            element = element.getNext();
        return element;
    }


    public int getSize() {
        return rozmiar;
    }

    private static final class Element<T>{
        private int priority;
        private T value;
        private Element previous;
        private Element next;

        public Element(T v,int priority){
            setValue(v);
            setPriority(priority);
        }

        public void setPriority(int priority) {
            this.priority = priority;
        }

        public int getPriority(){
            return priority;
        }

        public void setValue(T value){
            this.value = value;
        }

        public T getValue(){
            return value;
        }

        public Element getPrevious(){
            return previous;
        }

        public Element getNext(){
            return next;
        }

        public void setPrevious(Element previous){
            this.previous = previous;
        }

        public void setNext(Element next){
            this.next = next;
        }

        public void attachBefore(Element el){
            Element previous = el.getPrevious();
            setNext(el);
            setPrevious(previous);
            el.setPrevious(this);
            previous.setNext(this);

        }

        public void detach(){
            previous.setNext(next);
            next.setPrevious(previous);
        }
    }
}
public class Test {
    public static void main(String [] args){
        Queue<Integer> kolejka = new Queue<Integer>();
        Queue<Integer> kolejka_druga = new Queue<Integer>();
        kolejka.enqueue(10,10);
        System.out.println(kolejka.top());
        kolejka.enqueue(9,9);
        System.out.println(kolejka.top());
        kolejka.enqueue(20,20);
        System.out.println(kolejka.top());
        kolejka.pop();
        System.out.println(kolejka.top());
        kolejka_druga.enqueue(21,21);
        kolejka_druga.enqueue(5,5);
        kolejka.merge(kolejka_druga);
        System.out.println(kolejka.top());
        kolejka.pop();
        System.out.println(kolejka.top());
        kolejka.pop();
        System.out.println(kolejka.top());

    }
}