home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: Java / Java.zip / jload18.zip / priorityqueue.java < prev    next >
Text File  |  1998-12-27  |  4KB  |  187 lines
  1. import java.util.NoSuchElementException;
  2.  
  3. public final class priorityqueue
  4. {
  5.  /* synonimum varianta     */
  6.  /* idea from Jachym Kolar */
  7.  
  8.  protected Queue queues[];
  9.  protected float  priorities[];
  10.  
  11.  protected static final int DEFAULTQUEUES=5;
  12.  protected static final int DEFAULTINCREMENT=5;
  13.  protected static final float INTERNAL_FREE_MARK=-999.9f;
  14.  protected int increment;
  15.  
  16.  
  17.  public priorityqueue()
  18.  {
  19.   this(DEFAULTQUEUES,DEFAULTINCREMENT);
  20.  }
  21.  
  22.  public priorityqueue(int size)
  23.  {
  24.   this(size,DEFAULTINCREMENT);
  25.  }
  26.  
  27.  public priorityqueue(int size,int increment)
  28.  {
  29.   if(size<=0) throw new IllegalArgumentException("size(queues) <= 0");
  30.   if(increment<0) throw new IllegalArgumentException("increment < 0");
  31.   queues=new Queue[size];
  32.   priorities=new float[size];
  33.   for(int i=size-1;i>=0;i--)
  34.    priorities[i]=INTERNAL_FREE_MARK;
  35.   this.increment=increment;
  36.  }
  37.  
  38.  public synchronized Object push(Object item) 
  39.  {
  40.   return push(item,1f);
  41.  }
  42.  
  43.  public synchronized Object push(Object item,float prio) 
  44.  {
  45.   // najdi patricnou pozici
  46.   for(int i=priorities.length-1;i>=0;i--)
  47.    {
  48.     Queue q;
  49.     q=queues[i];
  50.     float pc;
  51.     pc=priorities[i];
  52.     if(pc==prio) 
  53.      if(q!=null) {q.push(item);notify();return item;}
  54.       else
  55.                  { q=new Queue(increment,increment);
  56.                    queues[i]=q;
  57.                    q.push(item);
  58.                    notify();
  59.                    return item;
  60.                  }
  61.     if(pc==INTERNAL_FREE_MARK) 
  62.       { add(i,prio,item);notify();return item;}
  63.    }
  64.   // pridat....
  65.   //System.out.println("INCREASING STORAGE");
  66.   float ftmp[]=new float[priorities.length+increment];
  67.   Queue qtmp[]=new Queue[priorities.length+increment];
  68.   //System.arraycopy(priorities,0,ftmp,increment,priorities.length);
  69.   for(int i=0;i<increment;i++)
  70.    ftmp[i]=INTERNAL_FREE_MARK;
  71.   //System.arraycopy(queues,0,qtmp,increment,priorities.length);
  72.   priorities=ftmp;
  73.   queues=qtmp;
  74.   add(increment-1,prio,item);
  75.   notify();
  76.   return item;  
  77.   
  78.   // throw new OutOfMemoryError("Out of Queue Space!");
  79.   // return null;
  80.  }
  81.  
  82.  public String toString()
  83.  {
  84.   StringBuffer sb;
  85.   sb=new StringBuffer(128);
  86.   for(int i=priorities.length-1;i>=0;i--)
  87.    sb.append(priorities[i]+" ");
  88.   return sb.toString();
  89.  }
  90.  
  91.  public synchronized Object pop()
  92.  {
  93.   int pos=queues.length;
  94.   while(true)
  95.   try
  96.    {
  97.     return queues[--pos].pop();
  98.    }
  99.    catch
  100.     ( NullPointerException ignore)
  101.           {continue;}
  102.    catch
  103.     ( NoSuchElementException ignore)
  104.           {queues[pos]=null;continue;}
  105.    catch
  106.     ( ArrayIndexOutOfBoundsException br)
  107.       {break;}
  108.       
  109.    throw new NoSuchElementException();
  110.    
  111.  }
  112.  
  113.  public synchronized int search(Object item)
  114.  {
  115.   int pos=queues.length;
  116.   int add=0;
  117.   int i;
  118.   while(true)
  119.   {
  120.    try
  121.    {
  122.     i=queues[pos].search(item);
  123.     if(i==-1) add+=queues[pos].queuesize();
  124.       else
  125.        return i+add;
  126.    }
  127.    catch
  128.     ( NullPointerException ignore)
  129.           {continue;}
  130.    catch
  131.     ( ArrayIndexOutOfBoundsException br)
  132.       {break;}
  133.    
  134.   }
  135.   return -1;
  136.  }
  137.  
  138.  public Object peek()
  139.  {
  140.   int pos=queues.length;
  141.   while(true)
  142.   try
  143.    {
  144.     return queues[--pos].peek();
  145.    }
  146.    catch
  147.     ( NullPointerException ignore)
  148.           {continue;}
  149.    catch
  150.     ( NoSuchElementException ignore)
  151.           {queues[pos]=null;continue;}
  152.    catch
  153.     ( ArrayIndexOutOfBoundsException br)
  154.       {break;}
  155.       
  156.    throw new NoSuchElementException();
  157.    
  158.  }
  159.  
  160.        // pridej ho tedy
  161.  protected Object add(int i,float prio,Object item)
  162.  {
  163.       Queue q;
  164.       //System.out.println("adding "+prio+", free at "+i);
  165.       int inew=i; // zjisti misto, kam ho zaradit
  166.       /* 9 - 1
  167.          5 - 0.5
  168.          2 - 0.1
  169.          */
  170.       if(i<priorities.length-1 && priorities[i+1]<prio  )
  171.       {
  172.       for(int j=i+1;j<priorities.length;j++)
  173.        if(priorities[j]>prio) 
  174.          {
  175.           //System.out.println("making room for "+prio+" at "+j+"\n"+this);
  176.           System.arraycopy(priorities,i+1,priorities,i,j-i);
  177.           System.arraycopy(queues,i+1,queues,i,j-i);
  178.           //System.out.println("after room make "+this);
  179.           inew=j-1;break;
  180.          }
  181.       } 
  182.       q=new Queue(increment,increment);
  183.       queues[inew]=q;
  184.       priorities[inew]=prio;
  185.       return q.push(item);
  186.      }
  187. }