1 17 18 package org.apache.avalon.cornerstone.blocks.scheduler; 19 20 import java.util.Comparator ; 21 import java.util.NoSuchElementException ; 22 23 32 public final class BinaryHeap 33 implements PriorityQueue 34 { 35 private static final class MinComparator 36 implements Comparator 37 { 38 public final int compare( final Object lhs, final Object rhs ) 39 { 40 return ( (Comparable )lhs ).compareTo( rhs ); 41 } 42 } 43 44 private static final class MaxComparator 45 implements Comparator 46 { 47 public final int compare( final Object lhs, final Object rhs ) 48 { 49 return ( (Comparable )rhs ).compareTo( lhs ); 50 } 51 } 52 53 57 public static final Comparator MIN_COMPARATOR = new MinComparator(); 58 59 63 public static final Comparator MAX_COMPARATOR = new MaxComparator(); 64 65 private static final int DEFAULT_CAPACITY = 13; 66 private static final Comparator DEFAULT_COMPARATOR = MIN_COMPARATOR; 67 private int m_size; 68 private Object [] m_elements; 69 private Comparator m_comparator; 70 71 74 public BinaryHeap() 75 { 76 this( DEFAULT_CAPACITY, DEFAULT_COMPARATOR ); 77 } 78 79 84 public BinaryHeap( final int capacity ) 85 { 86 this( capacity, DEFAULT_COMPARATOR ); 87 } 88 89 95 public BinaryHeap( final Comparator comparator ) 96 { 97 this( DEFAULT_CAPACITY, comparator ); 98 } 99 100 107 public BinaryHeap( final int capacity, final Comparator comparator ) 108 { 109 m_elements = new Object [ capacity + 1 ]; 111 m_comparator = comparator; 112 } 113 114 120 public BinaryHeap( final boolean isMinHeap ) 121 { 122 this( DEFAULT_CAPACITY, isMinHeap ); 123 } 124 125 133 public BinaryHeap( final int capacity, final boolean isMinHeap ) 134 { 135 this( capacity, isMinHeap ? MIN_COMPARATOR : MAX_COMPARATOR ); 136 } 137 138 141 public void clear() 142 { 143 m_size = 0; 144 } 145 146 151 public boolean isEmpty() 152 { 153 return ( 0 == m_size ); 154 } 155 156 161 public boolean isFull() 162 { 163 return ( m_elements.length == m_size + 1 ); 165 } 166 167 172 public int size() 173 { 174 return m_size; 175 } 176 177 182 public void insert( final Object element ) 183 { 184 if( isFull() ) 185 { 186 grow(); 187 } 188 189 percolateUpHeap( element ); 190 } 191 192 198 public Object peek() throws NoSuchElementException 199 { 200 if( isEmpty() ) 201 { 202 throw new NoSuchElementException (); 203 } 204 else 205 { 206 return m_elements[ 1 ]; 207 } 208 } 209 210 216 public Object pop() throws NoSuchElementException 217 { 218 final Object result = peek(); 219 m_elements[ 1 ] = m_elements[ m_size-- ]; 220 221 m_elements[ m_size + 1 ] = null; 224 225 if( m_size != 0 ) 226 { 227 percolateDownHeap( 1 ); 228 } 229 230 return result; 231 } 232 233 238 private void percolateDownHeap( final int index ) 239 { 240 final Object element = m_elements[ index ]; 241 242 int hole = index; 243 int child = hole << 1; 244 245 while( child <= m_size ) 246 { 247 if( child != m_size && 250 m_comparator.compare( m_elements[ child + 1 ], m_elements[ child ] ) < 0 ) 251 { 252 child++; 253 } 254 255 if( m_comparator.compare( m_elements[ child ], element ) >= 0 ) 257 { 258 break; 259 } 260 261 m_elements[ hole ] = m_elements[ child ]; 262 hole = child; 263 child = hole << 1; 264 } 265 266 m_elements[ hole ] = element; 267 } 268 269 274 private void percolateUpHeap( final Object element ) 275 { 276 int hole = ++m_size; 277 int next = hole >> 1; 278 279 m_elements[ hole ] = element; 280 281 while( hole > 1 && 282 m_comparator.compare( element, m_elements[ next ] ) < 0 ) 283 { 284 m_elements[ hole ] = m_elements[ next ]; 285 hole = next; 286 next = hole >> 1; 287 } 288 289 m_elements[ hole ] = element; 290 } 291 292 295 private void grow() 296 { 297 final Object [] elements = 298 new Object [ m_elements.length * 2 ]; 299 System.arraycopy( m_elements, 0, elements, 0, m_elements.length ); 300 m_elements = elements; 301 } 302 303 309 public String toString() 310 { 311 final StringBuffer sb = new StringBuffer (); 312 313 sb.append( "[ " ); 314 315 for( int i = 1; i < m_size + 1; i++ ) 316 { 317 if( i != 1 ) 318 { 319 sb.append( ", " ); 320 } 321 sb.append( m_elements[ i ] ); 322 } 323 324 sb.append( " ]" ); 325 326 return sb.toString(); 327 } 328 } 329 330 | Popular Tags |