Recommanded Free YOUTUBE Lecture: <% selectedImage[1] %>

/*
 * PriorityQueue.java
 *
 * Created on 2006년 9월 28일 (목), 오후 9:41
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package com.wkang.util.priorityqueue;

import java.security.InvalidParameterException;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Random;

/**
 *급하게 짰으므로 다른태클 삼가ㄳ 
 * added oct 3 06 : actually it doesnt really need a pop operation because iterator has 
 * remove() method. however, i added anyway
 * @author 자바하는놈/자바쉑키
 */

public class PriorityQueue<E extends Comparable<E>> implements Iterable<E>{
    private int size;
    private LinkedList<E> topList = new LinkedList<E>();
    
    
    public PriorityQueue(int size) {
        if(size <= 0) {
            throw new IllegalArgumentException();
        }
        this.size = size;
    }
    
    public boolean offer(E o) {
        try {
            E lowest = null;
            E highest = null;
            //if empty
            try {
                lowest = topList.getFirst();
                highest = topList.getLast();
            } catch(NoSuchElementException e) {
                return topList.offer(o);
            }
            //not empty
            
            {//search , insert
                int idx = topList.size() / 2;
                int range = topList.size() / 4;
                if(range < 1) {
                    range = 1;
                }
                while(true) {//search
                    E val = topList.get(idx);

                    if( o.compareTo(val) == 0 ) { // if it's the same'
                        topList.add(idx+1, o);
                        break;
                    } else {
                        if(topList.size()-1 >= idx) { //if idx is not at the very end
                            if(o.compareTo(topList.getLast()) > 0) {// if it's bigger than the biggest
                                topList.addLast(o);
                                System.out.println(o + " is bigger than "+ val + " : putting in");
                                break;
                            }if(o.compareTo(topList.getFirst()) < 0) {
                                topList.addFirst(o);
                                System.out.println(o + " is smaller than the smallest, putting it");
                                break;
                            }
                        }
                        if( (o.compareTo(val)) > 0 && ( o.compareTo(topList.get(idx+1)) < 0 ) ) { // if it fits in the middle
                            topList.add(idx+1, o);
                            System.out.println(o + " is bigger than "+ val + " and smaller than " + topList.get(idx+1) + " : putting in");
                            break;
                        }
                    }
                    if( o.compareTo(val) < 0) { // smaller
                        idx = idx - range;
                        System.out.println(o + " is smaller than " + val + " changing idx to " + idx);
                    } else { // bigger
                        idx = idx + range;
                        System.out.println(o + " is bigger than " + val + " changing to " + idx);
                    }
                    if(range > 1) {
                        range = range / 2;
                        System.out.println("setting range to +"+ range);
                    }
                }//while end
            }
            if(topList.size() > size) {
                topList.remove(0);
            }
            
        } catch(Exception e) {
            e.printStackTrace();
            return false;
        }
        return true;
    }

    public Iterator<E> iterator() {
        return topList.iterator();
    }
    public E pop() {
        return topList.remove(topList.size()-1);
    }

    //TESTING MAIN
    public static void  main(String args[]) {
        PriorityQueue<Integer> q = new PriorityQueue<Integer>(100);
        Random r = new Random();
        for(int ix=0;ix<1000; ix++) {
            q.offer(r.nextInt(1000));
            for(Integer i: q) {
                System.out.print("[ "+ i + " ] ");
            }
            System.out.println();
        }
        
    }
    
  
}