Source Code Cross Referenced for BinaryHeap.java in  » Library » Apache-common-Collections » org » apache » commons » collections » Java Source Code / Java DocumentationJava Source Code and Java Documentation

Java Source Code / Java Documentation
1. 6.0 JDK Core
2. 6.0 JDK Modules
3. 6.0 JDK Modules com.sun
4. 6.0 JDK Modules com.sun.java
5. 6.0 JDK Modules sun
6. 6.0 JDK Platform
7. Ajax
8. Apache Harmony Java SE
9. Aspect oriented
10. Authentication Authorization
11. Blogger System
12. Build
13. Byte Code
14. Cache
15. Chart
16. Chat
17. Code Analyzer
18. Collaboration
19. Content Management System
20. Database Client
21. Database DBMS
22. Database JDBC Connection Pool
23. Database ORM
24. Development
25. EJB Server geronimo
26. EJB Server GlassFish
27. EJB Server JBoss 4.2.1
28. EJB Server resin 3.1.5
29. ERP CRM Financial
30. ESB
31. Forum
32. GIS
33. Graphic Library
34. Groupware
35. HTML Parser
36. IDE
37. IDE Eclipse
38. IDE Netbeans
39. Installer
40. Internationalization Localization
41. Inversion of Control
42. Issue Tracking
43. J2EE
44. JBoss
45. JMS
46. JMX
47. Library
48. Mail Clients
49. Net
50. Parser
51. PDF
52. Portal
53. Profiler
54. Project Management
55. Report
56. RSS RDF
57. Rule Engine
58. Science
59. Scripting
60. Search Engine
61. Security
62. Sevlet Container
63. Source Control
64. Swing Library
65. Template Engine
66. Test Coverage
67. Testing
68. UML
69. Web Crawler
70. Web Framework
71. Web Mail
72. Web Server
73. Web Services
74. Web Services apache cxf 2.0.1
75. Web Services AXIS2
76. Wiki Engine
77. Workflow Engines
78. XML
79. XML UI
Java
Java Tutorial
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java Source Code / Java Documentation » Library » Apache common Collections » org.apache.commons.collections 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


001:        /*
002:         *  Copyright 2001-2004 The Apache Software Foundation
003:         *
004:         *  Licensed under the Apache License, Version 2.0 (the "License");
005:         *  you may not use this file except in compliance with the License.
006:         *  You may obtain a copy of the License at
007:         *
008:         *      http://www.apache.org/licenses/LICENSE-2.0
009:         *
010:         *  Unless required by applicable law or agreed to in writing, software
011:         *  distributed under the License is distributed on an "AS IS" BASIS,
012:         *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013:         *  See the License for the specific language governing permissions and
014:         *  limitations under the License.
015:         */
016:        package org.apache.commons.collections;
017:
018:        import java.util.AbstractCollection;
019:        import java.util.Comparator;
020:        import java.util.Iterator;
021:        import java.util.NoSuchElementException;
022:
023:        /**
024:         * Binary heap implementation of <code>PriorityQueue</code>.
025:         * <p>
026:         * The <code>PriorityQueue</code> interface has now been replaced for most uses
027:         * by the <code>Buffer</code> interface. This class and the interface are
028:         * retained for backwards compatibility. The intended replacement is
029:         * {@link org.apache.commons.collections.buffer.PriorityBuffer PriorityBuffer}.
030:         * <p>
031:         * The removal order of a binary heap is based on either the natural sort
032:         * order of its elements or a specified {@link Comparator}.  The 
033:         * {@link #pop()} method always returns the first element as determined
034:         * by the sort order.  (The <code>isMinHeap</code> flag in the constructors
035:         * can be used to reverse the sort order, in which case {@link #pop()}
036:         * will always remove the last element.)  The removal order is 
037:         * <i>not</i> the same as the order of iteration; elements are
038:         * returned by the iterator in no particular order.
039:         * <p>
040:         * The {@link #insert(Object)} and {@link #pop()} operations perform
041:         * in logarithmic time.  The {@link #peek()} operation performs in constant
042:         * time.  All other operations perform in linear time or worse.
043:         * <p>
044:         * Note that this implementation is not synchronized.  Use SynchronizedPriorityQueue
045:         * to provide synchronized access to a <code>BinaryHeap</code>:
046:         *
047:         * <pre>
048:         * PriorityQueue heap = new SynchronizedPriorityQueue(new BinaryHeap());
049:         * </pre>
050:         *
051:         * @deprecated Replaced by PriorityBuffer in buffer subpackage.
052:         *  Due to be removed in v4.0.
053:         * @since Commons Collections 1.0
054:         * @version $Revision: 155406 $ $Date: 2005-02-26 12:55:26 +0000 (Sat, 26 Feb 2005) $
055:         * 
056:         * @author Peter Donald
057:         * @author Ram Chidambaram
058:         * @author Michael A. Smith
059:         * @author Paul Jack
060:         * @author Stephen Colebourne
061:         */
062:        public final class BinaryHeap extends AbstractCollection implements 
063:                PriorityQueue, Buffer {
064:
065:            /**
066:             * The default capacity for a binary heap.
067:             */
068:            private final static int DEFAULT_CAPACITY = 13;
069:            /**
070:             * The number of elements currently in this heap.
071:             */
072:            int m_size; // package scoped for testing
073:            /**
074:             * The elements in this heap.
075:             */
076:            Object[] m_elements; // package scoped for testing
077:            /**
078:             * If true, the first element as determined by the sort order will 
079:             * be returned.  If false, the last element as determined by the
080:             * sort order will be returned.
081:             */
082:            boolean m_isMinHeap; // package scoped for testing
083:            /**
084:             * The comparator used to order the elements
085:             */
086:            Comparator m_comparator; // package scoped for testing
087:
088:            /**
089:             * Constructs a new minimum binary heap.
090:             */
091:            public BinaryHeap() {
092:                this (DEFAULT_CAPACITY, true);
093:            }
094:
095:            /**
096:             * Constructs a new <code>BinaryHeap</code> that will use the given
097:             * comparator to order its elements.
098:             * 
099:             * @param comparator  the comparator used to order the elements, null
100:             *  means use natural order
101:             */
102:            public BinaryHeap(Comparator comparator) {
103:                this ();
104:                m_comparator = comparator;
105:            }
106:
107:            /**
108:             * Constructs a new minimum binary heap with the specified initial capacity.
109:             *  
110:             * @param capacity  The initial capacity for the heap.  This value must
111:             *  be greater than zero.
112:             * @throws IllegalArgumentException  
113:             *  if <code>capacity</code> is &lt;= <code>0</code>
114:             */
115:            public BinaryHeap(int capacity) {
116:                this (capacity, true);
117:            }
118:
119:            /**
120:             * Constructs a new <code>BinaryHeap</code>.
121:             *
122:             * @param capacity  the initial capacity for the heap
123:             * @param comparator  the comparator used to order the elements, null
124:             *  means use natural order
125:             * @throws IllegalArgumentException  
126:             *  if <code>capacity</code> is &lt;= <code>0</code>
127:             */
128:            public BinaryHeap(int capacity, Comparator comparator) {
129:                this (capacity);
130:                m_comparator = comparator;
131:            }
132:
133:            /**
134:             * Constructs a new minimum or maximum binary heap
135:             *
136:             * @param isMinHeap  if <code>true</code> the heap is created as a 
137:             * minimum heap; otherwise, the heap is created as a maximum heap
138:             */
139:            public BinaryHeap(boolean isMinHeap) {
140:                this (DEFAULT_CAPACITY, isMinHeap);
141:            }
142:
143:            /**
144:             * Constructs a new <code>BinaryHeap</code>.
145:             *
146:             * @param isMinHeap  true to use the order imposed by the given 
147:             *   comparator; false to reverse that order
148:             * @param comparator  the comparator used to order the elements, null
149:             *  means use natural order
150:             */
151:            public BinaryHeap(boolean isMinHeap, Comparator comparator) {
152:                this (isMinHeap);
153:                m_comparator = comparator;
154:            }
155:
156:            /**
157:             * Constructs a new minimum or maximum binary heap with the specified 
158:             * initial capacity.
159:             *
160:             * @param capacity the initial capacity for the heap.  This value must 
161:             * be greater than zero.
162:             * @param isMinHeap if <code>true</code> the heap is created as a 
163:             *  minimum heap; otherwise, the heap is created as a maximum heap.
164:             * @throws IllegalArgumentException 
165:             *  if <code>capacity</code> is <code>&lt;= 0</code>
166:             */
167:            public BinaryHeap(int capacity, boolean isMinHeap) {
168:                if (capacity <= 0) {
169:                    throw new IllegalArgumentException("invalid capacity");
170:                }
171:                m_isMinHeap = isMinHeap;
172:
173:                //+1 as 0 is noop
174:                m_elements = new Object[capacity + 1];
175:            }
176:
177:            /**
178:             * Constructs a new <code>BinaryHeap</code>.
179:             *
180:             * @param capacity  the initial capacity for the heap
181:             * @param isMinHeap  true to use the order imposed by the given 
182:             *   comparator; false to reverse that order
183:             * @param comparator  the comparator used to order the elements, null
184:             *  means use natural order
185:             * @throws IllegalArgumentException 
186:             *  if <code>capacity</code> is <code>&lt;= 0</code>
187:             */
188:            public BinaryHeap(int capacity, boolean isMinHeap,
189:                    Comparator comparator) {
190:                this (capacity, isMinHeap);
191:                m_comparator = comparator;
192:            }
193:
194:            //-----------------------------------------------------------------------
195:            /**
196:             * Clears all elements from queue.
197:             */
198:            public void clear() {
199:                m_elements = new Object[m_elements.length]; // for gc
200:                m_size = 0;
201:            }
202:
203:            /**
204:             * Tests if queue is empty.
205:             *
206:             * @return <code>true</code> if queue is empty; <code>false</code> 
207:             *  otherwise.
208:             */
209:            public boolean isEmpty() {
210:                return m_size == 0;
211:            }
212:
213:            /**
214:             * Tests if queue is full.
215:             *
216:             * @return <code>true</code> if queue is full; <code>false</code>
217:             *  otherwise.
218:             */
219:            public boolean isFull() {
220:                //+1 as element 0 is noop
221:                return m_elements.length == m_size + 1;
222:            }
223:
224:            /**
225:             * Inserts an element into queue.
226:             *
227:             * @param element  the element to be inserted
228:             */
229:            public void insert(Object element) {
230:                if (isFull()) {
231:                    grow();
232:                }
233:                //percolate element to it's place in tree
234:                if (m_isMinHeap) {
235:                    percolateUpMinHeap(element);
236:                } else {
237:                    percolateUpMaxHeap(element);
238:                }
239:            }
240:
241:            /**
242:             * Returns the element on top of heap but don't remove it.
243:             *
244:             * @return the element at top of heap
245:             * @throws NoSuchElementException  if <code>isEmpty() == true</code>
246:             */
247:            public Object peek() throws NoSuchElementException {
248:                if (isEmpty()) {
249:                    throw new NoSuchElementException();
250:                } else {
251:                    return m_elements[1];
252:                }
253:            }
254:
255:            /**
256:             * Returns the element on top of heap and remove it.
257:             *
258:             * @return the element at top of heap
259:             * @throws NoSuchElementException  if <code>isEmpty() == true</code>
260:             */
261:            public Object pop() throws NoSuchElementException {
262:                final Object result = peek();
263:                m_elements[1] = m_elements[m_size--];
264:
265:                // set the unused element to 'null' so that the garbage collector
266:                // can free the object if not used anywhere else.(remove reference)
267:                m_elements[m_size + 1] = null;
268:
269:                if (m_size != 0) {
270:                    // percolate top element to it's place in tree
271:                    if (m_isMinHeap) {
272:                        percolateDownMinHeap(1);
273:                    } else {
274:                        percolateDownMaxHeap(1);
275:                    }
276:                }
277:
278:                return result;
279:            }
280:
281:            /**
282:             * Percolates element down heap from the position given by the index.
283:             * <p>
284:             * Assumes it is a minimum heap.
285:             *
286:             * @param index the index for the element
287:             */
288:            protected void percolateDownMinHeap(final int index) {
289:                final Object element = m_elements[index];
290:                int hole = index;
291:
292:                while ((hole * 2) <= m_size) {
293:                    int child = hole * 2;
294:
295:                    // if we have a right child and that child can not be percolated
296:                    // up then move onto other child
297:                    if (child != m_size
298:                            && compare(m_elements[child + 1], m_elements[child]) < 0) {
299:                        child++;
300:                    }
301:
302:                    // if we found resting place of bubble then terminate search
303:                    if (compare(m_elements[child], element) >= 0) {
304:                        break;
305:                    }
306:
307:                    m_elements[hole] = m_elements[child];
308:                    hole = child;
309:                }
310:
311:                m_elements[hole] = element;
312:            }
313:
314:            /**
315:             * Percolates element down heap from the position given by the index.
316:             * <p>
317:             * Assumes it is a maximum heap.
318:             *
319:             * @param index the index of the element
320:             */
321:            protected void percolateDownMaxHeap(final int index) {
322:                final Object element = m_elements[index];
323:                int hole = index;
324:
325:                while ((hole * 2) <= m_size) {
326:                    int child = hole * 2;
327:
328:                    // if we have a right child and that child can not be percolated
329:                    // up then move onto other child
330:                    if (child != m_size
331:                            && compare(m_elements[child + 1], m_elements[child]) > 0) {
332:                        child++;
333:                    }
334:
335:                    // if we found resting place of bubble then terminate search
336:                    if (compare(m_elements[child], element) <= 0) {
337:                        break;
338:                    }
339:
340:                    m_elements[hole] = m_elements[child];
341:                    hole = child;
342:                }
343:
344:                m_elements[hole] = element;
345:            }
346:
347:            /**
348:             * Percolates element up heap from the position given by the index.
349:             * <p>
350:             * Assumes it is a minimum heap.
351:             *
352:             * @param index the index of the element to be percolated up
353:             */
354:            protected void percolateUpMinHeap(final int index) {
355:                int hole = index;
356:                Object element = m_elements[hole];
357:                while (hole > 1 && compare(element, m_elements[hole / 2]) < 0) {
358:                    // save element that is being pushed down
359:                    // as the element "bubble" is percolated up
360:                    final int next = hole / 2;
361:                    m_elements[hole] = m_elements[next];
362:                    hole = next;
363:                }
364:                m_elements[hole] = element;
365:            }
366:
367:            /**
368:             * Percolates a new element up heap from the bottom.
369:             * <p>
370:             * Assumes it is a minimum heap.
371:             *
372:             * @param element the element
373:             */
374:            protected void percolateUpMinHeap(final Object element) {
375:                m_elements[++m_size] = element;
376:                percolateUpMinHeap(m_size);
377:            }
378:
379:            /**
380:             * Percolates element up heap from from the position given by the index.
381:             * <p>
382:             * Assume it is a maximum heap.
383:             *
384:             * @param index the index of the element to be percolated up
385:             */
386:            protected void percolateUpMaxHeap(final int index) {
387:                int hole = index;
388:                Object element = m_elements[hole];
389:
390:                while (hole > 1 && compare(element, m_elements[hole / 2]) > 0) {
391:                    // save element that is being pushed down
392:                    // as the element "bubble" is percolated up
393:                    final int next = hole / 2;
394:                    m_elements[hole] = m_elements[next];
395:                    hole = next;
396:                }
397:
398:                m_elements[hole] = element;
399:            }
400:
401:            /**
402:             * Percolates a new element up heap from the bottom.
403:             * <p>
404:             * Assume it is a maximum heap.
405:             *
406:             * @param element the element
407:             */
408:            protected void percolateUpMaxHeap(final Object element) {
409:                m_elements[++m_size] = element;
410:                percolateUpMaxHeap(m_size);
411:            }
412:
413:            /**
414:             * Compares two objects using the comparator if specified, or the
415:             * natural order otherwise.
416:             * 
417:             * @param a  the first object
418:             * @param b  the second object
419:             * @return -ve if a less than b, 0 if they are equal, +ve if a greater than b
420:             */
421:            private int compare(Object a, Object b) {
422:                if (m_comparator != null) {
423:                    return m_comparator.compare(a, b);
424:                } else {
425:                    return ((Comparable) a).compareTo(b);
426:                }
427:            }
428:
429:            /**
430:             * Increases the size of the heap to support additional elements
431:             */
432:            protected void grow() {
433:                final Object[] elements = new Object[m_elements.length * 2];
434:                System.arraycopy(m_elements, 0, elements, 0, m_elements.length);
435:                m_elements = elements;
436:            }
437:
438:            /**
439:             * Returns a string representation of this heap.  The returned string
440:             * is similar to those produced by standard JDK collections.
441:             *
442:             * @return a string representation of this heap
443:             */
444:            public String toString() {
445:                final StringBuffer sb = new StringBuffer();
446:
447:                sb.append("[ ");
448:
449:                for (int i = 1; i < m_size + 1; i++) {
450:                    if (i != 1) {
451:                        sb.append(", ");
452:                    }
453:                    sb.append(m_elements[i]);
454:                }
455:
456:                sb.append(" ]");
457:
458:                return sb.toString();
459:            }
460:
461:            /**
462:             * Returns an iterator over this heap's elements.
463:             *
464:             * @return an iterator over this heap's elements
465:             */
466:            public Iterator iterator() {
467:                return new Iterator() {
468:
469:                    private int index = 1;
470:                    private int lastReturnedIndex = -1;
471:
472:                    public boolean hasNext() {
473:                        return index <= m_size;
474:                    }
475:
476:                    public Object next() {
477:                        if (!hasNext())
478:                            throw new NoSuchElementException();
479:                        lastReturnedIndex = index;
480:                        index++;
481:                        return m_elements[lastReturnedIndex];
482:                    }
483:
484:                    public void remove() {
485:                        if (lastReturnedIndex == -1) {
486:                            throw new IllegalStateException();
487:                        }
488:                        m_elements[lastReturnedIndex] = m_elements[m_size];
489:                        m_elements[m_size] = null;
490:                        m_size--;
491:                        if (m_size != 0 && lastReturnedIndex <= m_size) {
492:                            int compareToParent = 0;
493:                            if (lastReturnedIndex > 1) {
494:                                compareToParent = compare(
495:                                        m_elements[lastReturnedIndex],
496:                                        m_elements[lastReturnedIndex / 2]);
497:                            }
498:                            if (m_isMinHeap) {
499:                                if (lastReturnedIndex > 1
500:                                        && compareToParent < 0) {
501:                                    percolateUpMinHeap(lastReturnedIndex);
502:                                } else {
503:                                    percolateDownMinHeap(lastReturnedIndex);
504:                                }
505:                            } else { // max heap
506:                                if (lastReturnedIndex > 1
507:                                        && compareToParent > 0) {
508:                                    percolateUpMaxHeap(lastReturnedIndex);
509:                                } else {
510:                                    percolateDownMaxHeap(lastReturnedIndex);
511:                                }
512:                            }
513:                        }
514:                        index--;
515:                        lastReturnedIndex = -1;
516:                    }
517:
518:                };
519:            }
520:
521:            /**
522:             * Adds an object to this heap. Same as {@link #insert(Object)}.
523:             *
524:             * @param object  the object to add
525:             * @return true, always
526:             */
527:            public boolean add(Object object) {
528:                insert(object);
529:                return true;
530:            }
531:
532:            /**
533:             * Returns the priority element. Same as {@link #peek()}.
534:             *
535:             * @return the priority element
536:             * @throws BufferUnderflowException if this heap is empty
537:             */
538:            public Object get() {
539:                try {
540:                    return peek();
541:                } catch (NoSuchElementException e) {
542:                    throw new BufferUnderflowException();
543:                }
544:            }
545:
546:            /**
547:             * Removes the priority element. Same as {@link #pop()}.
548:             *
549:             * @return the removed priority element
550:             * @throws BufferUnderflowException if this heap is empty
551:             */
552:            public Object remove() {
553:                try {
554:                    return pop();
555:                } catch (NoSuchElementException e) {
556:                    throw new BufferUnderflowException();
557:                }
558:            }
559:
560:            /**
561:             * Returns the number of elements in this heap.
562:             *
563:             * @return the number of elements in this heap
564:             */
565:            public int size() {
566:                return m_size;
567:            }
568:
569:        }
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.