001: /*
002: * GeoTools - OpenSource mapping toolkit
003: * http://geotools.org
004: * (C) 2002-2006, GeoTools Project Managment Committee (PMC)
005: * (C) 2002, Refractions Reserach Inc.
006: *
007: * This library is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU Lesser General Public
009: * License as published by the Free Software Foundation;
010: * version 2.1 of the License.
011: *
012: * This library is distributed in the hope that it will be useful,
013: * but WITHOUT ANY WARRANTY; without even the implied warranty of
014: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015: * Lesser General Public License for more details.
016: */
017: package org.geotools.graph.util;
018:
019: import java.lang.reflect.Array;
020: import java.util.Collection;
021: import java.util.Comparator;
022: import java.util.HashMap;
023: import java.util.Iterator;
024: import java.util.NoSuchElementException;
025:
026: public class PriorityQueue implements Collection, Queue {
027: public static double RESIZE_FACTOR = 1.5;
028:
029: private Comparator m_comparator = null;
030: private Object[] m_values = null;
031: private int m_count = 0;
032: private HashMap m_obj2index = null;
033:
034: public PriorityQueue(Comparator comparator) {
035: m_comparator = comparator;
036: m_obj2index = new HashMap();
037: }
038:
039: public void init(int size) {
040: if (m_values == null || size > m_values.length)
041: resize(size + 1, false);
042:
043: for (int i = 0; i < m_values.length; i++) {
044: m_values[i] = null;
045: }
046: m_count = 0;
047: }
048:
049: public void insert(Object value) {
050: ++m_count;
051: if (m_count >= m_values.length)
052: resize((int) (m_values.length * RESIZE_FACTOR), true);
053:
054: m_values[m_count] = value;
055: m_obj2index.put(value, new Integer(m_count));
056:
057: moveUp(m_count);
058: }
059:
060: public Object extract() {
061: if (m_count == 0)
062: throw new NoSuchElementException("Heap empty.");
063:
064: Object value = m_values[1];
065: swap(1, m_count);
066:
067: m_values[m_count--] = null;
068: moveDown(1);
069:
070: m_obj2index.remove(value);
071: return (value);
072: }
073:
074: public Object getRoot() {
075: if (m_count == 0)
076: throw new NoSuchElementException("Heap Empty.");
077:
078: return (m_values[1]);
079: }
080:
081: public void update() {
082: int n = (int) size() / 2;
083: for (int i = 1; i <= n; i++) {
084: update(i);
085: }
086: }
087:
088: public int update(int i) {
089: //check parent, if value is less, propogate value up
090: if (i > 1 && compare(i, i / 2) < 0) {
091: return (moveUp(i));
092: }
093:
094: //check children, if value more, propogate value down
095: if ((2 * i <= size() && compare(i, 2) > 0)
096: || (2 * i + 1 <= size() && compare(i, 2 * i + 1) > 0)) {
097: return (moveDown(i));
098: }
099:
100: return (i);
101: }
102:
103: public void update(Object value) {
104: Integer index = ((Integer) m_obj2index.get(value));
105: if (index == null) {
106: for (int i = 1; i < m_count; i++) {
107: Object o = (Object) m_values[i];
108: if (o == value)
109: System.out.println();
110: }
111: }
112: update(index.intValue());
113: //TODO: improve performance, dont use a linear search
114: // for (int i = 1; i < m_values.length; i++) {
115: // if (m_values[i] == value) {
116: // update(i);
117: // return;
118: // }
119: // }
120: }
121:
122: public boolean isEmpty() {
123: return (m_count == 0);
124: }
125:
126: public int size() {
127: return (m_count);
128: }
129:
130: private int moveDown(int n) {
131: int minchild = 0;
132:
133: if (2 * n <= m_count) {
134: minchild = 2 * n;
135: if (2 * n + 1 <= m_count) {
136: minchild = (compare(2 * n, 2 * n + 1) < 0) ? 2 * n
137: : 2 * n + 1;
138: }
139:
140: if (compare(minchild, n) < 0) {
141: swap(minchild, n);
142: return (moveDown(minchild));
143: }
144: }
145: return (n);
146: }
147:
148: private int moveUp(int n) {
149: int parent = (n % 2 == 0) ? n / 2 : (n - 1) / 2;
150: if (parent > 0 && compare(n, parent) < 0) {
151: swap(n, parent);
152: return (moveUp(parent));
153: }
154: return (n);
155: }
156:
157: private int compare(int i, int j) {
158: return (m_comparator.compare(m_values[i], m_values[j]));
159: }
160:
161: private void resize(int size, boolean preserve) {
162: Object[] resized = new Object[size];
163:
164: if (preserve) {
165: for (int i = 0; i < m_values.length && i < size; i++) {
166: resized[i] = m_values[i];
167: }
168: }
169:
170: m_values = resized;
171: }
172:
173: /** TODO: DOCUMENT ME! Note that this method should be used cautiously **/
174: public void swap(int i, int j) {
175: //first swap the reference to the indicies
176: if (m_obj2index.get(m_values[i]) == null
177: || m_obj2index.get(m_values[j]) == null)
178: System.out.println();
179:
180: Object tmp = m_obj2index.get(m_values[i]);
181: m_obj2index.put(m_values[i], m_obj2index.get(m_values[j]));
182: m_obj2index.put(m_values[j], tmp);
183:
184: //swap objects in array
185: tmp = m_values[i];
186: m_values[i] = m_values[j];
187: m_values[j] = tmp;
188:
189: }
190:
191: public void clear() {
192: init(0);
193: }
194:
195: public Object[] toArray() {
196: return (m_values);
197: }
198:
199: public boolean add(Object o) {
200: insert(o);
201: return (true);
202: }
203:
204: public Object get(int i) {
205: if (i == 0 && i > m_count)
206: return (null);
207: return (m_values[i]);
208:
209: }
210:
211: public boolean contains(Object o) {
212: for (int i = 0; i < m_values.length; i++) {
213: if (m_values[i].equals(o))
214: return (true);
215: }
216: return (false);
217: }
218:
219: public boolean remove(Object o) {
220: //TODO: improve performance, dont use a linear search
221: for (int i = 1; i < m_values.length; i++) {
222: if (m_values[i] == o) {
223: remove(i);
224: return (true);
225: }
226: }
227: return (false);
228: }
229:
230: public void remove(int i) {
231: //check to see if item is last in heap
232: if (i < m_count) {
233: //first do a swap with last element in heap
234: swap(i, m_count);
235:
236: //remove last element
237: m_values[m_count--] = null;
238:
239: //update previous last element
240: update(i);
241: } else {
242: //simply remove the last element
243: m_values[m_count--] = null;
244: }
245: }
246:
247: public boolean addAll(Collection c) {
248: for (Iterator itr = c.iterator(); itr.hasNext();) {
249: add(itr.next());
250: }
251: return (true);
252: }
253:
254: public boolean containsAll(Collection c) {
255: for (Iterator itr = c.iterator(); itr.hasNext();) {
256: if (!contains(itr.next()))
257: return (false);
258: }
259: return (true);
260: }
261:
262: public boolean removeAll(Collection c) {
263: throw new UnsupportedOperationException(
264: "Heap#removeAll(Collection) not supported");
265: }
266:
267: public boolean retainAll(Collection c) {
268: throw new UnsupportedOperationException(
269: "Heap#retainAll(Collection) not supported");
270: }
271:
272: public Iterator iterator() {
273: return (new Iterator() {
274: int i = 1;
275:
276: public void remove() {
277: throw new UnsupportedOperationException(
278: "Iterator#remove() not supported");
279: }
280:
281: public boolean hasNext() {
282: return (i < m_values.length);
283: }
284:
285: public Object next() {
286: return (m_values[i++]);
287: }
288: });
289: }
290:
291: public Object[] toArray(Object[] a) {
292: if (a.length < m_values.length)
293: a = (Object[]) Array.newInstance(a.getClass()
294: .getComponentType(), m_values.length);
295:
296: for (int i = 0; i < m_values.length; i++) {
297: a[i] = m_values[i];
298: }
299: if (a.length > m_values.length)
300: a[m_values.length] = null;
301: return (a);
302: }
303:
304: //Queue implementation
305: public Object deq() {
306: return (extract());
307: }
308:
309: public void enq(Object object) {
310: insert(object);
311: }
312: }
|