001: /*
002: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
003: *
004: * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
005: *
006: * The contents of this file are subject to the terms of either the GNU
007: * General Public License Version 2 only ("GPL") or the Common
008: * Development and Distribution License("CDDL") (collectively, the
009: * "License"). You may not use this file except in compliance with the
010: * License. You can obtain a copy of the License at
011: * http://www.netbeans.org/cddl-gplv2.html
012: * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
013: * specific language governing permissions and limitations under the
014: * License. When distributing the software, include this License Header
015: * Notice in each file and include the License file at
016: * nbbuild/licenses/CDDL-GPL-2-CP. Sun designates this
017: * particular file as subject to the "Classpath" exception as provided
018: * by Sun in the GPL Version 2 section of the License file that
019: * accompanied this code. If applicable, add the following below the
020: * License Header, with the fields enclosed by brackets [] replaced by
021: * your own identifying information:
022: * "Portions Copyrighted [year] [name of copyright owner]"
023: *
024: * Contributor(s):
025: *
026: * The Original Software is NetBeans. The Initial Developer of the Original
027: * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
028: * Microsystems, Inc. All Rights Reserved.
029: *
030: * If you wish your version of this file to be governed by only the CDDL
031: * or only the GPL Version 2, indicate your decision by adding
032: * "[Contributor] elects to include this software in this distribution
033: * under the [CDDL or GPL Version 2] license." If you do not indicate a
034: * single choice of license, a recipient has the option to distribute
035: * your version of this file under either the CDDL, the GPL Version 2 or
036: * to extend the choice of license to its licensees as provided above.
037: * However, if you add GPL Version 2 code and therefore, elected the GPL
038: * Version 2 license, then the option applies only if the new code is
039: * made subject to such option by the copyright holder.
040: */
041:
042: package org.netbeans.lib.collab.util;
043:
044: import java.util.*;
045:
046: /**
047: * This is PriorityQueue for JDK1.4. It offers
048: * the same interface as jDK1.5 PriorityQueue.
049: * It offers log(n) for offer and poll.
050: *
051: * @author Vijayakumar Palaniappan
052: */
053: public class PriorityQueue {
054: private ArrayList _list = null;
055: private Comparator _comparator = null;
056:
057: public static void main(String s[]) {
058: PriorityQueue pq = new PriorityQueue();
059: Random r = new Random();
060: for (int i = 10; i > 0; i--) {
061: pq.offer(new Integer(r.nextInt(1000)));
062: }
063:
064: for (int i = 0; i < 11; i++) {
065: System.out.println(pq.poll());
066: }
067: }
068:
069: public PriorityQueue() {
070: this (null);
071: }
072:
073: public PriorityQueue(Comparator comp) {
074: _list = new ArrayList();
075: _comparator = comp;
076: }
077:
078: public boolean offer(Object value) {
079: if (_comparator == null) {
080: if (!(value instanceof Comparable)) {
081: throw new IllegalArgumentException(
082: "value should implement Comparable interface");
083: }
084: }
085: _list.add(value);
086: percolateUp(_list.size() - 1);
087: return true;
088: }
089:
090: public Object poll() {
091: Object value = peek();
092: if (value != null) {
093: int size = _list.size();
094: _list.set(0, _list.get(size - 1));
095: _list.remove(size - 1);
096: if (_list.size() > 1) {
097: pushDownRoot(0);
098: }
099: }
100: return value;
101:
102: }
103:
104: public Object peek() {
105: if (_list.size() > 0) {
106: return _list.get(0);
107: } else {
108: return null;
109: }
110: }
111:
112: public int size() {
113: return _list.size();
114: }
115:
116: public void clear() {
117: _list.clear();
118: }
119:
120: public Iterator iterator() {
121: return _list.iterator();
122: }
123:
124: private void pushDownRoot(int root) {
125: int size = _list.size();
126: Object value = _list.get(root);
127: while (true) {
128: int childPos = leftChildOf(root);
129: if (childPos < size) {
130: if (rightChildOf(root) < size
131: && compare(_list.get(childPos + 1), _list
132: .get(childPos)) < 0) {
133: childPos++;
134: }
135:
136: if (compare(_list.get(childPos), value) < 0) {
137: _list.set(root, _list.get(childPos));
138: root = childPos;
139: } else {
140: _list.set(root, value);
141: return;
142: }
143:
144: } else {
145: _list.set(root, value);
146: return;
147: }
148: }
149: }
150:
151: private void percolateUp(int leaf) {
152: int parent = parentOf(leaf);
153: Object value = _list.get(leaf);
154: while (leaf > 0 && compare(value, _list.get(parent)) < 0) {
155: _list.set(leaf, _list.get(parent));
156: leaf = parent;
157: parent = parentOf(leaf);
158: }
159: _list.set(leaf, value);
160: }
161:
162: private int compare(Object o1, Object o2) {
163: if (_comparator == null) {
164: return ((Comparable) o1).compareTo(o2);
165: } else {
166: return _comparator.compare(o1, o2);
167: }
168: }
169:
170: private static int parentOf(int index) {
171: return (index - 1) / 2;
172: }
173:
174: private static int leftChildOf(int index) {
175: return 2 * index + 1;
176: }
177:
178: private static int rightChildOf(int index) {
179: return 2 * (index + 1);
180: }
181: }
|