001    /* PriorityQueue.java -- Unbounded priority queue
002       Copyright (C) 2004, 2005 Free Software Foundation, Inc.
003    
004    This file is part of GNU Classpath.
005    
006    GNU Classpath is free software; you can redistribute it and/or modify
007    it under the terms of the GNU General Public License as published by
008    the Free Software Foundation; either version 2, or (at your option)
009    any later version.
010    
011    GNU Classpath is distributed in the hope that it will be useful, but
012    WITHOUT ANY WARRANTY; without even the implied warranty of
013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014    General Public License for more details.
015    
016    You should have received a copy of the GNU General Public License
017    along with GNU Classpath; see the file COPYING.  If not, write to the
018    Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
019    02110-1301 USA.
020    
021    Linking this library statically or dynamically with other modules is
022    making a combined work based on this library.  Thus, the terms and
023    conditions of the GNU General Public License cover the whole
024    combination.
025    
026    As a special exception, the copyright holders of this library give you
027    permission to link this library with independent modules to produce an
028    executable, regardless of the license terms of these independent
029    modules, and to copy and distribute the resulting executable under
030    terms of your choice, provided that you also meet, for each linked
031    independent module, the terms and conditions of the license of that
032    module.  An independent module is a module which is not derived from
033    or based on this library.  If you modify this library, you may extend
034    this exception to your version of the library, but you are not
035    obligated to do so.  If you do not wish to do so, delete this
036    exception statement from your version. */
037    
038    
039    package java.util;
040    
041    import 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     */
048    public 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    }