001/* PriorityQueue.java -- Unbounded priority queue
002   Copyright (C) 2004, 2005 Free Software Foundation, Inc.
003
004This file is part of GNU Classpath.
005
006GNU Classpath is free software; you can redistribute it and/or modify
007it under the terms of the GNU General Public License as published by
008the Free Software Foundation; either version 2, or (at your option)
009any later version.
010
011GNU Classpath is distributed in the hope that it will be useful, but
012WITHOUT ANY WARRANTY; without even the implied warranty of
013MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014General Public License for more details.
015
016You should have received a copy of the GNU General Public License
017along with GNU Classpath; see the file COPYING.  If not, write to the
018Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
01902110-1301 USA.
020
021Linking this library statically or dynamically with other modules is
022making a combined work based on this library.  Thus, the terms and
023conditions of the GNU General Public License cover the whole
024combination.
025
026As a special exception, the copyright holders of this library give you
027permission to link this library with independent modules to produce an
028executable, regardless of the license terms of these independent
029modules, and to copy and distribute the resulting executable under
030terms of your choice, provided that you also meet, for each linked
031independent module, the terms and conditions of the license of that
032module.  An independent module is a module which is not derived from
033or based on this library.  If you modify this library, you may extend
034this exception to your version of the library, but you are not
035obligated to do so.  If you do not wish to do so, delete this
036exception statement from your version. */
037
038
039package java.util;
040
041import java.io.Serializable;
042
043/**
044 * @author Tom Tromey (tromey@redhat.com)
045 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
046 * @since 1.5
047 */
048public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable
049{
050  private static final int DEFAULT_CAPACITY = 11;
051
052  private static final long serialVersionUID = -7720805057305804111L;
053
054  /** Number of elements actually used in the storage array.  */
055  int used;
056
057  /**
058   * This is the storage for the underlying binomial heap.
059   * The idea is, each node is less than or equal to its children.
060   * A node at index N (0-based) has two direct children, at
061   * nodes 2N+1 and 2N+2.
062   */
063  E[] storage;
064
065  /**
066   * The comparator we're using, or null for natural ordering.
067   */
068  Comparator<? super E> comparator;
069
070  public PriorityQueue()
071  {
072    this(DEFAULT_CAPACITY, null);
073  }
074
075  public PriorityQueue(Collection<? extends E> c)
076  {
077    this(Math.max(1, (int) (1.1 * c.size())), null);
078
079    // Special case where we can find the comparator to use.
080    if (c instanceof SortedSet)
081      {
082        SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
083        this.comparator = (Comparator<? super E>) ss.comparator();
084        // We can insert the elements directly, since they are sorted.
085        int i = 0;
086        for (E val : ss)
087          {
088            if (val == null)
089              throw new NullPointerException();
090            storage[i++] = val;
091          }
092      }
093    else if (c instanceof PriorityQueue)
094      {
095        PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
096        this.comparator = (Comparator<? super E>)pq.comparator();
097        // We can just copy the contents.
098        System.arraycopy(pq.storage, 0, storage, 0, pq.storage.length);
099      }
100
101    addAll(c);
102  }
103
104  public PriorityQueue(int cap)
105  {
106    this(cap, null);
107  }
108
109  public PriorityQueue(int cap, Comparator<? super E> comp)
110  {
111    if (cap < 1)
112      throw new IllegalArgumentException();
113    this.used = 0;
114    this.storage = (E[]) new Object[cap];
115    this.comparator = comp;
116  }
117
118  public PriorityQueue(PriorityQueue<? extends E> c)
119  {
120    this(Math.max(1, (int) (1.1 * c.size())),
121         (Comparator<? super E>)c.comparator());
122    // We can just copy the contents.
123    System.arraycopy(c.storage, 0, storage, 0, c.storage.length);
124  }
125
126  public PriorityQueue(SortedSet<? extends E> c)
127  {
128    this(Math.max(1, (int) (1.1 * c.size())),
129         (Comparator<? super E>)c.comparator());
130    // We can insert the elements directly, since they are sorted.
131    int i = 0;
132    for (E val : c)
133      {
134        if (val == null)
135          throw new NullPointerException();
136        storage[i++] = val;
137      }
138  }
139
140  public void clear()
141  {
142    Arrays.fill(storage, null);
143    used = 0;
144  }
145
146  public Comparator<? super E> comparator()
147  {
148    return comparator;
149  }
150
151  public Iterator<E> iterator()
152  {
153    return new Iterator<E>()
154    {
155      int index = -1;
156      int count = 0;
157
158      public boolean hasNext()
159      {
160        return count < used;
161      }
162
163      public E next()
164      {
165        while (storage[++index] == null)
166          ;
167
168        ++count;
169        return storage[index];
170      }
171
172      public void remove()
173      {
174        PriorityQueue.this.remove(index);
175        index--;
176      }
177    };
178  }
179
180  public boolean offer(E o)
181  {
182    if (o == null)
183      throw new NullPointerException();
184
185    int slot = findSlot(-1);
186
187    storage[slot] = o;
188    ++used;
189    bubbleUp(slot);
190
191    return true;
192  }
193
194  public E peek()
195  {
196    return used == 0 ? null : storage[0];
197  }
198
199  public E poll()
200  {
201    if (used == 0)
202      return null;
203    E result = storage[0];
204    remove(0);
205    return result;
206  }
207
208  public boolean remove(Object o)
209  {
210    if (o != null)
211      {
212        for (int i = 0; i < storage.length; ++i)
213          {
214            if (o.equals(storage[i]))
215              {
216                remove(i);
217                return true;
218              }
219          }
220      }
221    return false;
222  }
223
224  public int size()
225  {
226    return used;
227  }
228
229  // It is more efficient to implement this locally -- less searching
230  // for free slots.
231  public boolean addAll(Collection<? extends E> c)
232  {
233    if (c == this)
234      throw new IllegalArgumentException();
235
236    int newSlot = -1;
237    int save = used;
238    for (E val : c)
239      {
240        if (val == null)
241          throw new NullPointerException();
242        newSlot = findSlot(newSlot);
243        storage[newSlot] = val;
244        ++used;
245        bubbleUp(newSlot);
246      }
247
248    return save != used;
249  }
250
251  int findSlot(int start)
252  {
253    int slot;
254    if (used == storage.length)
255      {
256        resize();
257        slot = used;
258      }
259    else
260      {
261        for (slot = start + 1; slot < storage.length; ++slot)
262          {
263            if (storage[slot] == null)
264              break;
265          }
266        // We'll always find a slot.
267      }
268    return slot;
269  }
270
271  void remove(int index)
272  {
273    // Remove the element at INDEX.  We do this by finding the least
274    // child and moving it into place, then iterating until we reach
275    // the bottom of the tree.
276    while (storage[index] != null)
277      {
278        int child = 2 * index + 1;
279
280        // See if we went off the end.
281        if (child >= storage.length)
282          {
283            storage[index] = null;
284            break;
285          }
286
287        // Find which child we want to promote.  If one is not null,
288        // we pick it.  If both are null, it doesn't matter, we're
289        // about to leave.  If neither is null, pick the lesser.
290        if (child + 1 >= storage.length || storage[child + 1] == null)
291          {
292            // Nothing.
293          }
294        else if (storage[child] == null
295                 || (Collections.compare(storage[child], storage[child + 1],
296                                         comparator) > 0))
297          ++child;
298        storage[index] = storage[child];
299        index = child;
300      }
301    --used;
302  }
303
304  void bubbleUp(int index)
305  {
306    // The element at INDEX was inserted into a blank spot.  Now move
307    // it up the tree to its natural resting place.
308    while (index > 0)
309      {
310        // This works regardless of whether we're at 2N+1 or 2N+2.
311        int parent = (index - 1) / 2;
312        if (Collections.compare(storage[parent], storage[index], comparator)
313            <= 0)
314          {
315            // Parent is the same or smaller than this element, so the
316            // invariant is preserved.  Note that if the new element
317            // is smaller than the parent, then it is necessarily
318            // smaller than the parent's other child.
319            break;
320          }
321
322        E temp = storage[index];
323        storage[index] = storage[parent];
324        storage[parent] = temp;
325
326        index = parent;
327      }
328  }
329
330  void resize()
331  {
332    E[] new_data = (E[]) new Object[2 * storage.length];
333    System.arraycopy(storage, 0, new_data, 0, storage.length);
334    storage = new_data;
335  }
336}