Doc Classic

Class PriorityQueue

  1 /*
  2  * Copyright (c) 2016 Vivid Solutions.
  3  *
  4  * All rights reserved. This program and the accompanying materials
  5  * are made available under the terms of the Eclipse Public License 2.0
  6  * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
  7  * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
  8  * and the Eclipse Distribution License is available at
  9  *
 10  * http://www.eclipse.org/org/documents/edl-v10.php.
 11  */
 12 package org.locationtech.jts.util;
 13  
 14 import java.util.ArrayList;
 15  
 16 /**
 17  * A priority queue over a set of {@link Comparable} objects.
 18  * 
 19  * @author Martin Davis
 20  * @deprecated
 21  */
 22 public class PriorityQueue 
 23 {
 24   private int size; // Number of elements in queue
 25   private ArrayList items; // The queue binary heap array
 26  
 27   /**
 28    * Creates a new empty priority queue
 29    */
 30   public PriorityQueue() {
 31     size = 0;
 32     items = new ArrayList();
 33     // create space for sentinel
 34     items.add(null);
 35   }
 36  
 37   /**
 38    * Insert into the priority queue.
 39    * Duplicates are allowed.
 40    * @param x the item to insert.
 41    */
 42   public void add(Comparable x) 
 43   {
 44     // increase the size of the items heap to create a hole for the new item
 45     items.add(null);
 46  
 47     // Insert item at end of heap and then re-establish ordering
 48     size += 1;
 49     int hole = size;
 50     // set the item as a sentinel at the base of the heap
 51     items.set(0, x);
 52  
 53     // move the item up from the hole position to its correct place
 54     for (; x.compareTo(items.get(hole / 2)) < 0; hole /= 2) {
 55       items.set(hole, items.get(hole / 2));
 56     }
 57     // insert the new item in the correct place
 58     items.set(hole, x);
 59   }
 60  
 61   /**
 62    * Establish heap from an arbitrary arrangement of items. 
 63    */
 64   /*
 65    private void buildHeap( ) {
 66    for( int i = currentSize / 2; i > 0; i-- )
 67    reorder( i );
 68    }
 69    */
 70  
 71   /**
 72    * Test if the priority queue is logically empty.
 73    * @return true if empty, false otherwise.
 74    */
 75   public boolean isEmpty() {
 76     return size == 0;
 77   }
 78  
 79   /**
 80    * Returns size.
 81    * @return current size.
 82    */
 83   public int size() {
 84     return size;
 85   }
 86  
 87   /**
 88    * Make the priority queue logically empty.
 89    */
 90   public void clear() {
 91     size = 0;
 92     items.clear();
 93   }
 94  
 95   /**
 96    * Remove the smallest item from the priority queue.
 97    * @return the smallest item, or null if empty
 98    */
 99   public Object poll() 
100   {
101     if (isEmpty())
102       return null;
103     Object minItem = items.get(1);
104     items.set(1, items.get(size));
105     size -= 1;
106     reorder(1);
107  
108     return minItem;
109   }
110  
111   public Object peek() 
112   {
113     if (isEmpty())
114       return null;
115     Object minItem = items.get(1);
116     return minItem;
117   }
118   
119   /**
120    * Internal method to percolate down in the heap.
121    * 
122    * @param hole the index at which the percolate begins.
123    */
124   private void reorder(int hole) 
125   {
126     int child;
127     Object tmp = items.get(hole);
128  
129     for (; hole * 2 <= size; hole = child) {
130       child = hole * 2;
131       if (child != size
132           && ((Comparable) items.get(child + 1)).compareTo(items.get(child)) < 0)
133         child++;
134       if (((Comparable) items.get(child)).compareTo(tmp) < 0)
135         items.set(hole, items.get(child));
136       else
137         break;
138     }
139     items.set(hole, tmp);
140   }
141 }
142