heaps.java

只是一个简单模拟操作系统

/*
 * Heaps.java
 *
 * Created on 2006年3月18日, 上午9:08
 *
 *
 */

package os.process;

/**
 * Get the the Process that have the largest priority
 * @author Vernkin
 * @version 1.0
 */


public class Heaps{
    
    /**
     * The heaps name
     */
    private String name;
    /**
     * The largst allocated space
     */
    private int MAX_SIZE;
    /**
     * the current size,between 0 and MAX_SIZE(including MAX_SIZE)
     */
    private int currentSize;
    /**
     * MyProcess Array
     */
    private MyProcess[] data;
    /**
     * Whether the Heaps is used for IOQueue
     */
    private boolean isIOQueue;
    /**
     * Creates a new instance of Heaps
     * @param name Heaps name
     * @param maxSize Allocate for the Heaps Size
     * @param isIOQueue Whether this Queue is used for IO Queue
     */
    public Heaps(String name,int maxSize,boolean isIOQueue) {
        this.name = name;
        this.MAX_SIZE = maxSize;
        this.isIOQueue = isIOQueue;
        data = new MyProcess[MAX_SIZE+1];
        currentSize = 0;
    }
    
    
    /**
     * Add a new MyProcess into the queue
     * @param p A new Process
     * @return If success execute add opeartion,return true
     */
    public boolean add(MyProcess p){
        if(isIOQueue){
            if(data[0] == null){
                data[0] = p;
                return true;
            }
        }
        if(currentSize >= MAX_SIZE || p == null)
            return false;
        
        currentSize++;
        if(isIOQueue)
            p.setStatus("Blocked");
        else
            p.setStatus("Ready");
        //Each time enter a Heaps , change system_id
        p.setSystemID();
        insert(p,currentSize);
        System.out.println("Heaps add "+p+" in "+name);
        return true; 
    }
    
    /**
     * Insert the param p into the heaps and makes neccsary adjustment
     * @param p The insert Process
     * @param hole The begin index
     */
    private void insert(MyProcess p,int hole){
       while(hole>1){
           if(!MyProcess.firstRun(data[hole/2], p))
               data[hole] = data[hole/2];
           else
               break;
           hole /= 2;
       }
       data[hole] = p; 
    }
    
    /**
     * Internal method topercolate down in the heap.
     * @param hole the index at which the percolate begins
     */
    private void percolateDown(int hole){
        int child;
        MyProcess tmp = data[hole];
        
        for(;hole*2<=currentSize;hole=child){
            child = hole * 2;
            if(child != currentSize && !MyProcess.firstRun(data[child], data[child+1]))
                child++;
            if(MyProcess.firstRun(data[child], data[hole]))
                data[hole] = data[child];
            else
                break;
        }
        data[hole] = tmp;
    }
    
    /**
     * Get Process with largest priority and deos not remove in
     * @return Process with largest priority
     */
    public MyProcess getFirstProcess(){
        if(isIOQueue)
            return data[0];
        else
            return data[1];
    }
    
    /**
     * Also remove the first*
     * @return return the Process that hava the largest priority
     * (In IOQueue,return the first index)
     */
    public MyProcess findMax(){
        MyProcess temp;
        if(isIOQueue){
            temp = data[0];
            if(currentSize == 0){
                data[0] = null;
                return temp;
            }
            data[0] = data[1];
            
            if(currentSize == 1){
                data[currentSize--] = null;
                return temp;
            }
            
            data[1] = data[currentSize];
            currentSize--;
            percolateDown(1);
            return temp;
        }else{
            if(currentSize == 0)
                return null;
            
            temp = data[1];
            if(currentSize == 1){
                data[currentSize--] = null;
                return temp;
            }
            
            data[1] = data[currentSize--];
            percolateDown(1);
            return temp;
        }
 }
    
    /**
     * Whether the Heaps is Empty
     * @return If heaps is empty , return true
     */
    public boolean isEmpty(){
        if(isIOQueue)
            return currentSize == 0 && data[0] == null;
        else
            return currentSize == 0;
    }
    
    
    public int getSize(){
        return currentSize;
    }
    
    
    public int getMaxSize(){
        return MAX_SIZE;
    }
    
    public boolean isFull(){
        return currentSize>=MAX_SIZE;
    }
    
    
    public void makeEmpty(){
        if(isIOQueue)
            data[0] = null;
        currentSize = 0;
    }
    
    
    public MyProcess[] getProcessGroup(){
        if(isEmpty())
            return null;
        int count = currentSize;
        int size = count;
        if(isIOQueue)
            size = count + 1;
        MyProcess[] ret = new MyProcess[size];
        for(int i=0;i<count;i++)
            ret[i] = data[i+1];
        if(isIOQueue)
            ret[count] = data[0];
        
        return ret;
    }
    
    
    
}