Facebook
From Cream Dolphin, 11 Months ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 252
  1. /**
  2.  * Created by Jan on 12.01.2017.
  3.  */
  4. public class Queue<T> implements MyQueue<T> {
  5.     public Element<T> guard = new Element(null, -1);
  6.     public int rozmiar;
  7.  
  8.     public Queue(){
  9.         clear();
  10.     }
  11.  
  12.     public void enqueue(T value, int priority){
  13.         int index = 0;
  14.         Element<T> element = guard.getNext();
  15.         while(element.getPriority()>priority){
  16.             element = element.getNext();
  17.             index++;
  18.         }
  19.         insert(index, value, priority);
  20.     }
  21.     public T top(){
  22.         if(rozmiar == 0)
  23.             return null;
  24.         else {
  25.             return getElement(0);
  26.         }
  27.     }
  28.  
  29.     public void pop(){
  30.         Element<T> element = getElementB(0);
  31.         element.detach();
  32.         rozmiar--;
  33.     }
  34.     public void merge(Queue<T> queue){
  35.         for (int i = 0; i < queue.getSize(); i++)
  36.         {
  37.             this.enqueue(queue.getElement(i), queue.getElementB(i).getPriority());
  38.         }
  39.     }
  40.  
  41.     public void clear(){
  42.         guard.setNext(guard);
  43.         guard.setPrevious(guard);
  44.         rozmiar = 0;
  45.     }
  46.     public void insert(int index, T value, int priority) throws IndexOutOfBoundsException {
  47.         if (index < 0 || index > rozmiar) throw new IndexOutOfBoundsException();
  48.  
  49.         Element<T> element = new Element(value,priority);
  50.         element.attachBefore(getElementB(index));
  51.  
  52.         rozmiar++;
  53.     }
  54.  
  55.  
  56.     public T getElement(int index){
  57.         Element<T> element = guard.getNext();
  58.         for (int i = 0; i < index; i++)
  59.             element = element.getNext();
  60.         return element.getValue();
  61.     }
  62.     public Element getElementB(int index){
  63.         Element element = guard.getNext();
  64.         for (int i = 0; i < index; i++)
  65.             element = element.getNext();
  66.         return element;
  67.     }
  68.  
  69.  
  70.     public int getSize() {
  71.         return rozmiar;
  72.     }
  73.  
  74.     private static final class Element<T>{
  75.         private int priority;
  76.         private T value;
  77.         private Element previous;
  78.         private Element next;
  79.  
  80.         public Element(T v,int priority){
  81.             setValue(v);
  82.             setPriority(priority);
  83.         }
  84.  
  85.         public void setPriority(int priority) {
  86.             this.priority = priority;
  87.         }
  88.  
  89.         public int getPriority(){
  90.             return priority;
  91.         }
  92.  
  93.         public void setValue(T value){
  94.             this.value = value;
  95.         }
  96.  
  97.         public T getValue(){
  98.             return value;
  99.         }
  100.  
  101.         public Element getPrevious(){
  102.             return previous;
  103.         }
  104.  
  105.         public Element getNext(){
  106.             return next;
  107.         }
  108.  
  109.         public void setPrevious(Element previous){
  110.             this.previous = previous;
  111.         }
  112.  
  113.         public void setNext(Element next){
  114.             this.next = next;
  115.         }
  116.  
  117.         public void attachBefore(Element el){
  118.             Element previous = el.getPrevious();
  119.             setNext(el);
  120.             setPrevious(previous);
  121.             el.setPrevious(this);
  122.             previous.setNext(this);
  123.  
  124.         }
  125.  
  126.         public void detach(){
  127.             previous.setNext(next);
  128.             next.setPrevious(previous);
  129.         }
  130.     }
  131. }
  132. public class Test {
  133.     public static void main(String [] args){
  134.         Queue<Integer> kolejka = new Queue<Integer>();
  135.         Queue<Integer> kolejka_druga = new Queue<Integer>();
  136.         kolejka.enqueue(10,10);
  137.         System.out.println(kolejka.top());
  138.         kolejka.enqueue(9,9);
  139.         System.out.println(kolejka.top());
  140.         kolejka.enqueue(20,20);
  141.         System.out.println(kolejka.top());
  142.         kolejka.pop();
  143.         System.out.println(kolejka.top());
  144.         kolejka_druga.enqueue(21,21);
  145.         kolejka_druga.enqueue(5,5);
  146.         kolejka.merge(kolejka_druga);
  147.         System.out.println(kolejka.top());
  148.         kolejka.pop();
  149.         System.out.println(kolejka.top());
  150.         kolejka.pop();
  151.         System.out.println(kolejka.top());
  152.  
  153.     }
  154. }
  155.