package com.dwave.util;

/*
 *  PriorityQueue
 *
 *   Copyright (C) 2001  D-Wave Systems Inc.
 *
 *   This program is free software; you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation; either version 2 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program; if not, write to the Free Software
 *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */


/**
 *  A <code>PriorityQueue</code> with an internal array of <code>QueueObject</code>s.
 *  Items are kept in a sorted order by <i>ascending</i> priority.  The item with
 *  highest priority (0) is retrieved first with the <code>nextItem()</code>
 *  method.  Resizing of the internal array is conducted automatically depending
 *  on load, both for expansion and compression.
 *
 *  @author Michael Coury
 *  @version 1.0, 05/17/2001
 */
public class PriorityQueue implements java.io.Serializable {
  private static final long serialVersionUID = 7780256636299358021L;
  public static final int PRIORITY_LOW = 10,
                          PRIORITY_NORMAL = 5,
                          PRIORITY_HIGH = 0;
  private static final int EXPAND = 0,
                           COMPRESS = 1;
  private int maxSize;
  private QueueObject[] queueArray;
  private int nItems;
  private int initSize;

  /**
   *  Constructs a new <code>PriorityQueue</code> with an initial size of 10
   */
  public PriorityQueue() { this(10); }   
  /**
   *  Constructs a new <code>PriorityQueue</code> with a specified initial size.
   *  @param size initial size
   */
  public PriorityQueue(int size) {
    if(size <= 0)
      size = 1;
    maxSize = size;
    initSize = size;
    queueArray = new QueueObject[maxSize];
    nItems = 0;
  }

  /**
   *  Insert an item into the queue.  If there are no items, the item is inserted
   *  at 0, otherwise it starts at the end, and shifts lower priority items up
   *  the queue
   *  @param item the item to be inserted
   *  @param priority the item's priority
   */
  public synchronized void insert(Object item, int priority) {
    int i;
    if(nItems >= maxSize - 1)
      _resize(EXPAND);
    if(priority < 0)
      priority = 0;
    if(nItems==0)
      queueArray[nItems++]=new QueueObject(item, priority);
    else {
      for(i = nItems-1; i >= 0; i--) {
        if(priority >= queueArray[i].priority)
          queueArray[i+1] = queueArray[i];
        else
          break;
      }
      queueArray[i+1] = new QueueObject(item, priority);
      nItems++;
    }
  }

  /**
   *  Retrieve and remove the next item on the queue.  Same as calling the
   *  <code>nextItem()</code> method
   *  @return the next item on the queue
   */
  public synchronized Object removeMinimumItem() {
    if(nItems < maxSize/3 && maxSize/3 > initSize)
      _resize(COMPRESS);
    int n = --nItems;
    Object o = queueArray[n].object;
    queueArray[n] = null;
    return o;
  }        
  /**
   *  Retrieve and remove the next item on the queue. 
   *  @return the next item on the queue
   */
  public synchronized Object nextItem() {
    if(nItems < maxSize/3 && maxSize/3 > initSize)
      _resize(COMPRESS);
    int n = --nItems;
    Object o = queueArray[n].object;
    queueArray[n] = null;
    return o;
  }
  /**
   *  Retrieve the next item on the queue without removing it 
   *  @return the next item on the queue
   */
  public synchronized Object peekAtMinimumItem() { return queueArray[nItems-1].object; }
  /**
   *  Checks to see if the queue is empty
   *  @return true if the queue is empty
   */
  public synchronized boolean isEmpty() { return (nItems==0); }

  /**
   *  Resize the internal array
   */
  private synchronized void _resize(int mode) {
    QueueObject[] swap = queueArray;
    switch(mode) {
      case(COMPRESS):
        if(maxSize/2 < nItems) // double check
          return;
        queueArray = new QueueObject[maxSize/2];
       break;
      case(EXPAND):
        queueArray = new QueueObject[maxSize*2];
       break;
    }
    for(int i = 0; i < maxSize; i++) {
      if(swap[i] != null)
        queueArray[i] = swap[i];
    }
    maxSize = queueArray.length;
  }
  /**
   *  Displays the contents of the internal array, including empty space
   *  @return a string representation of the internal array
   */
  public synchronized String toString() {
    String s = "{ ";
    for(int i = 0; i < maxSize; i++) {
      if(queueArray[i] != null)
        s = s + "("+queueArray[i].object.toString()+","+queueArray[i].priority+") ";
      else
        s = s + "(empty) ";
    }
    return s + "}";
  }

  /**
   *
   */
  class QueueObject implements java.io.Serializable {
    int priority;
    Object object;

    QueueObject(Object o, int priority) {
      object = o;
      this.priority = priority;
    }
  }
}