/* * 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(); } } }
Copyrights © - Joinc, All Rights Reserved. Inherited From - Yundream Rebranded By - Joonphil
Recent Posts
Archive Posts
Tags