Source Code Cross Referenced for CollatingIterator.java in  » Library » Apache-common-Collections » org » apache » commons » collections » iterators » 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.iterators 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


001:        /*
002:         *  Copyright 1999-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.iterators;
017:
018:        import java.util.ArrayList;
019:        import java.util.BitSet;
020:        import java.util.Collection;
021:        import java.util.Comparator;
022:        import java.util.Iterator;
023:        import java.util.List;
024:        import java.util.NoSuchElementException;
025:
026:        import org.apache.commons.collections.list.UnmodifiableList;
027:
028:        /**
029:         * Provides an ordered iteration over the elements contained in
030:         * a collection of ordered Iterators.
031:         * <p>
032:         * Given two ordered {@link Iterator} instances <code>A</code> and <code>B</code>,
033:         * the {@link #next} method on this iterator will return the lesser of 
034:         * <code>A.next()</code> and <code>B.next()</code>.
035:         *
036:         * @since Commons Collections 2.1
037:         * @version $Revision: 155406 $ $Date: 2005-02-26 12:55:26 +0000 (Sat, 26 Feb 2005) $
038:         * 
039:         * @author Rodney Waldhoff
040:         * @author Stephen Colebourne
041:         */
042:        public class CollatingIterator implements  Iterator {
043:
044:            /** The {@link Comparator} used to evaluate order. */
045:            private Comparator comparator = null;
046:
047:            /** The list of {@link Iterator}s to evaluate. */
048:            private ArrayList iterators = null;
049:
050:            /** {@link Iterator#next Next} objects peeked from each iterator. */
051:            private ArrayList values = null;
052:
053:            /** Whether or not each {@link #values} element has been set. */
054:            private BitSet valueSet = null;
055:
056:            /** Index of the {@link #iterators iterator} from whom the last returned value was obtained. */
057:            private int lastReturned = -1;
058:
059:            // Constructors
060:            // ----------------------------------------------------------------------
061:            /**
062:             * Constructs a new <code>CollatingIterator</code>.  Natural sort order
063:             * will be used, and child iterators will have to be manually added 
064:             * using the {@link #addIterator(Iterator)} method.
065:             */
066:            public CollatingIterator() {
067:                this (null, 2);
068:            }
069:
070:            /**
071:             * Constructs a new <code>CollatingIterator</code> that will used the
072:             * specified comparator for ordering.  Child iterators will have to be 
073:             * manually added using the {@link #addIterator(Iterator)} method.
074:             *
075:             * @param comp  the comparator to use to sort, or null to use natural sort order
076:             */
077:            public CollatingIterator(final Comparator comp) {
078:                this (comp, 2);
079:            }
080:
081:            /**
082:             * Constructs a new <code>CollatingIterator</code> that will used the
083:             * specified comparator for ordering and have the specified initial
084:             * capacity.  Child iterators will have to be 
085:             * manually added using the {@link #addIterator(Iterator)} method.
086:             *
087:             * @param comp  the comparator to use to sort, or null to use natural sort order
088:             * @param initIterCapacity  the initial capacity for the internal list
089:             *    of child iterators
090:             */
091:            public CollatingIterator(final Comparator comp,
092:                    final int initIterCapacity) {
093:                iterators = new ArrayList(initIterCapacity);
094:                setComparator(comp);
095:            }
096:
097:            /**
098:             * Constructs a new <code>CollatingIterator</code> that will use the
099:             * specified comparator to provide ordered iteration over the two
100:             * given iterators.
101:             *
102:             * @param comp  the comparator to use to sort, or null to use natural sort order
103:             * @param a  the first child ordered iterator
104:             * @param b  the second child ordered iterator
105:             * @throws NullPointerException if either iterator is null
106:             */
107:            public CollatingIterator(final Comparator comp, final Iterator a,
108:                    final Iterator b) {
109:                this (comp, 2);
110:                addIterator(a);
111:                addIterator(b);
112:            }
113:
114:            /**
115:             * Constructs a new <code>CollatingIterator</code> that will use the
116:             * specified comparator to provide ordered iteration over the array
117:             * of iterators.
118:             *
119:             * @param comp  the comparator to use to sort, or null to use natural sort order
120:             * @param iterators  the array of iterators
121:             * @throws NullPointerException if iterators array is or contains null
122:             */
123:            public CollatingIterator(final Comparator comp,
124:                    final Iterator[] iterators) {
125:                this (comp, iterators.length);
126:                for (int i = 0; i < iterators.length; i++) {
127:                    addIterator(iterators[i]);
128:                }
129:            }
130:
131:            /**
132:             * Constructs a new <code>CollatingIterator</code> that will use the
133:             * specified comparator to provide ordered iteration over the collection
134:             * of iterators.
135:             *
136:             * @param comp  the comparator to use to sort, or null to use natural sort order
137:             * @param iterators  the collection of iterators
138:             * @throws NullPointerException if the iterators collection is or contains null
139:             * @throws ClassCastException if the iterators collection contains an
140:             *         element that's not an {@link Iterator}
141:             */
142:            public CollatingIterator(final Comparator comp,
143:                    final Collection iterators) {
144:                this (comp, iterators.size());
145:                for (Iterator it = iterators.iterator(); it.hasNext();) {
146:                    Iterator item = (Iterator) it.next();
147:                    addIterator(item);
148:                }
149:            }
150:
151:            // Public Methods
152:            // ----------------------------------------------------------------------
153:            /**
154:             * Adds the given {@link Iterator} to the iterators being collated.
155:             * 
156:             * @param iterator  the iterator to add to the collation, must not be null
157:             * @throws IllegalStateException if iteration has started
158:             * @throws NullPointerException if the iterator is null
159:             */
160:            public void addIterator(final Iterator iterator) {
161:                checkNotStarted();
162:                if (iterator == null) {
163:                    throw new NullPointerException("Iterator must not be null");
164:                }
165:                iterators.add(iterator);
166:            }
167:
168:            /**
169:             * Sets the iterator at the given index.
170:             * 
171:             * @param index  index of the Iterator to replace
172:             * @param iterator  Iterator to place at the given index
173:             * @throws IndexOutOfBoundsException if index &lt; 0 or index &gt; size()
174:             * @throws IllegalStateException if iteration has started
175:             * @throws NullPointerException if the iterator is null
176:             */
177:            public void setIterator(final int index, final Iterator iterator) {
178:                checkNotStarted();
179:                if (iterator == null) {
180:                    throw new NullPointerException("Iterator must not be null");
181:                }
182:                iterators.set(index, iterator);
183:            }
184:
185:            /**
186:             * Gets the list of Iterators (unmodifiable).
187:             * 
188:             * @return the unmodifiable list of iterators added
189:             */
190:            public List getIterators() {
191:                return UnmodifiableList.decorate(iterators);
192:            }
193:
194:            /**
195:             * Gets the {@link Comparator} by which collatation occurs.
196:             */
197:            public Comparator getComparator() {
198:                return comparator;
199:            }
200:
201:            /**
202:             * Sets the {@link Comparator} by which collation occurs.
203:             * 
204:             * @throws IllegalStateException if iteration has started
205:             */
206:            public void setComparator(final Comparator comp) {
207:                checkNotStarted();
208:                comparator = comp;
209:            }
210:
211:            // Iterator Methods
212:            // -------------------------------------------------------------------
213:            /**
214:             * Returns <code>true</code> if any child iterator has remaining elements.
215:             *
216:             * @return true if this iterator has remaining elements
217:             */
218:            public boolean hasNext() {
219:                start();
220:                return anyValueSet(valueSet) || anyHasNext(iterators);
221:            }
222:
223:            /**
224:             * Returns the next ordered element from a child iterator.
225:             *
226:             * @return the next ordered element
227:             * @throws NoSuchElementException if no child iterator has any more elements
228:             */
229:            public Object next() throws NoSuchElementException {
230:                if (hasNext() == false) {
231:                    throw new NoSuchElementException();
232:                }
233:                int leastIndex = least();
234:                if (leastIndex == -1) {
235:                    throw new NoSuchElementException();
236:                } else {
237:                    Object val = values.get(leastIndex);
238:                    clear(leastIndex);
239:                    lastReturned = leastIndex;
240:                    return val;
241:                }
242:            }
243:
244:            /**
245:             * Removes the last returned element from the child iterator that 
246:             * produced it.
247:             *
248:             * @throws IllegalStateException if there is no last returned element,
249:             *  or if the last returned element has already been removed
250:             */
251:            public void remove() {
252:                if (lastReturned == -1) {
253:                    throw new IllegalStateException(
254:                            "No value can be removed at present");
255:                }
256:                Iterator it = (Iterator) (iterators.get(lastReturned));
257:                it.remove();
258:            }
259:
260:            // Private Methods
261:            // -------------------------------------------------------------------
262:            /** 
263:             * Initializes the collating state if it hasn't been already.
264:             */
265:            private void start() {
266:                if (values == null) {
267:                    values = new ArrayList(iterators.size());
268:                    valueSet = new BitSet(iterators.size());
269:                    for (int i = 0; i < iterators.size(); i++) {
270:                        values.add(null);
271:                        valueSet.clear(i);
272:                    }
273:                }
274:            }
275:
276:            /** 
277:             * Sets the {@link #values} and {@link #valueSet} attributes 
278:             * at position <i>i</i> to the next value of the 
279:             * {@link #iterators iterator} at position <i>i</i>, or 
280:             * clear them if the <i>i</i><sup>th</sup> iterator
281:             * has no next value.
282:             *
283:             * @return <tt>false</tt> iff there was no value to set
284:             */
285:            private boolean set(int i) {
286:                Iterator it = (Iterator) (iterators.get(i));
287:                if (it.hasNext()) {
288:                    values.set(i, it.next());
289:                    valueSet.set(i);
290:                    return true;
291:                } else {
292:                    values.set(i, null);
293:                    valueSet.clear(i);
294:                    return false;
295:                }
296:            }
297:
298:            /** 
299:             * Clears the {@link #values} and {@link #valueSet} attributes 
300:             * at position <i>i</i>.
301:             */
302:            private void clear(int i) {
303:                values.set(i, null);
304:                valueSet.clear(i);
305:            }
306:
307:            /** 
308:             * Throws {@link IllegalStateException} if iteration has started 
309:             * via {@link #start}.
310:             * 
311:             * @throws IllegalStateException if iteration started
312:             */
313:            private void checkNotStarted() throws IllegalStateException {
314:                if (values != null) {
315:                    throw new IllegalStateException(
316:                            "Can't do that after next or hasNext has been called.");
317:                }
318:            }
319:
320:            /** 
321:             * Returns the index of the least element in {@link #values},
322:             * {@link #set(int) setting} any uninitialized values.
323:             * 
324:             * @throws IllegalStateException
325:             */
326:            private int least() {
327:                int leastIndex = -1;
328:                Object leastObject = null;
329:                for (int i = 0; i < values.size(); i++) {
330:                    if (valueSet.get(i) == false) {
331:                        set(i);
332:                    }
333:                    if (valueSet.get(i)) {
334:                        if (leastIndex == -1) {
335:                            leastIndex = i;
336:                            leastObject = values.get(i);
337:                        } else {
338:                            Object curObject = values.get(i);
339:                            if (comparator.compare(curObject, leastObject) < 0) {
340:                                leastObject = curObject;
341:                                leastIndex = i;
342:                            }
343:                        }
344:                    }
345:                }
346:                return leastIndex;
347:            }
348:
349:            /**
350:             * Returns <code>true</code> iff any bit in the given set is 
351:             * <code>true</code>.
352:             */
353:            private boolean anyValueSet(BitSet set) {
354:                for (int i = 0; i < set.size(); i++) {
355:                    if (set.get(i)) {
356:                        return true;
357:                    }
358:                }
359:                return false;
360:            }
361:
362:            /**
363:             * Returns <code>true</code> iff any {@link Iterator} 
364:             * in the given list has a next value.
365:             */
366:            private boolean anyHasNext(ArrayList iters) {
367:                for (int i = 0; i < iters.size(); i++) {
368:                    Iterator it = (Iterator) iters.get(i);
369:                    if (it.hasNext()) {
370:                        return true;
371:                    }
372:                }
373:                return false;
374:            }
375:
376:        }
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.