package zieckey.datastructure.study.queue;

import zieckey.datastructure.study.graph.*;

/**
 * 有优先级的队列
 *
 * @author zieckey
 */
public class PriorityQueue
{
    // array in sorted order, from max at 0 to min at size-1

    private final int    SIZE    = 20;
    private Edge[]        queArray;
    private int            size;

    public PriorityQueue( )
    {
        queArray = new Edge[SIZE];
        size = 0;
    }

    /**
     * 插入一条边到队列中，同时保证优先级顺序
     * @param item
     */
    public void insert( Edge item ) // insert item in sorted order

    {
        if ( size >= SIZE )
        {
            System.out.println("The queue is full. Please remove some items before inserting new item into it.");
            return;
        }
        
        int j;
        for ( j = 0; j < size; j++ )
        {
            // find place to insert

            if ( item.distance >= queArray[j].distance )
            {
                break;
            }
        }
        for ( int k = size - 1; k >= j; k-- )
        {
            // move items up

            queArray[k + 1] = queArray[k];
        }
        queArray[j] = item; // insert item

        size++ ;
    }
    
    /**
     * 移出一条最小的边，即数组index最大的那个元素，同时，queue的size自减1
     * @return 返回该元素
     */
    public Edge removeMin()
    {
        return queArray[--size];
    }
    
    /**
     * 移出index=n的边，同时，queue的size自减1
     * @param n
     */
    public void removeN( int n ) // remove item at n

    {
        for ( int j = n; j < size - 1; j++ )
        {
            // move items down

            queArray[j] = queArray[j + 1];
        }
        size-- ;
    }
    
    /**
     *
     * @return 返回最小的元素，即数组index最大的那个元素
     */
    public Edge peekMin() // peek at minimum item

    {
        return queArray[size - 1];
    }

    /**
     *
     * @return 返回queue的元素个数
     */
    public int size() // return number of items

    {
        return size;
    }

    /**
     * 判断queue是否为空
     * @return 空，返回true；不空，返回false
     */
    public boolean isEmpty() // true if queue is empty

    {
        return ( size == 0 );
    }

    /**
     *
     * @param n index
     * @return 返回index=n的元素
     */
    public Edge peekN( int n ) // peek at item n

    {
        return queArray[n];
    }

}