Facebook
From Melodic Mosquito, 9 Months ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 220
  1. trait MyQueue[T] {
  2.   def insert(x:T):Unit
  3.   def check:Boolean
  4.   def top: T
  5.   def pop: Unit
  6. }
  7.  
  8. import scala.collection.mutable._
  9.  
  10. class Queue[T<:Comparable[T]]( val L: Array[T]) extends MyQueue[T]{
  11.   var size:Int = 0
  12.   def top():T={
  13.     if(size == 0) throw new Exception("Pusty kopiec")
  14.     else
  15.      L(0)
  16.   }
  17.  
  18.   def swap(pos1:Int, pos2:Int){
  19.     var temp:T = L(pos1)
  20.     L(pos1) = L(pos2)
  21.     L(pos2) = temp
  22.   }
  23.  
  24.   def insert(x:T)={
  25.      if(size == 101) throw new Exception("Pelny kopiec")
  26.      if(size == 0){
  27.        L(0) = x //= new Element(x,p)
  28.        size = size + 1
  29.      }
  30.      else {
  31.        L(size) = x
  32.        var pos = size
  33.        size = size + 1
  34.        while(x.compareTo(L((pos-1)/2)) > 0){
  35.          swap(pos, (pos-1)/2)
  36.          pos = pos/2
  37.        }    
  38.      }    
  39.   }
  40.  
  41.   def pop()={
  42.       if(size == 0) throw new Exception("Pusty kopiec")
  43.       else{
  44.         var pos:Int = 0
  45.         size = size - 1
  46.         swap(pos,size)
  47.        
  48.        
  49.         if(size != 0)
  50.         while(pos*2+1<size && pos*2+2>= size &&(L(pos).compareTo(L(pos * 2 + 1)) < 0) || pos*2+2<size &&((L(pos).compareTo(L(pos * 2 + 1)) < 0) || (L(pos).compareTo(L(pos * 2 + 1)) < 0))){
  51.           if(pos*2+1 < size && pos*2+2>= size)
  52.             swap(pos,pos*2+1)
  53.             else{
  54.               if(L(pos * 2 + 1).compareTo(L(pos * 2 + 2)) > 0){
  55.                 swap(pos, pos * 2 + 1)
  56.                 pos = pos * 2 + 1
  57.               }
  58.               else{
  59.                 swap(pos, pos * 2 + 2)
  60.                 pos = pos * 2 + 2
  61.               }
  62.             }
  63.       }
  64.        
  65.       }
  66.   }
  67.   def check()={
  68.     size == 0
  69.   }
  70. }