Iterators


1   /*
2    * The contents of this file are subject to the terms of the Common Development
3    * and Distribution License (the License). You may not use this file except in
4    * compliance with the License.
5    *
6    * You can obtain a copy of the License at http://www.netbeans.org/cddl.html
7    * or http://www.netbeans.org/cddl.txt.
8    *
9    * When distributing Covered Code, include this CDDL Header Notice in each file
10   * and include the License file at http://www.netbeans.org/cddl.txt.
11   * If applicable, add the following below the CDDL Header, with the fields
12   * enclosed by brackets [] replaced by your own identifying information:
13   * "Portions Copyrighted [year] [name of copyright owner]"
14   *
15   * The Original Software is NetBeans. The Initial Developer of the Original
16   * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
17   * Microsystems, Inc. All Rights Reserved.
18   */
19  
20  package org.netbeans.modules.java.source.util;
21  
22  import java.util.ArrayList  ;
23  import java.util.Arrays  ;
24  import java.util.BitSet  ;
25  import java.util.Collection  ;
26  import java.util.Collections  ;
27  import java.util.Comparator  ;
28  import java.util.Iterator  ;
29  import java.util.List  ;
30  import java.util.NoSuchElementException  ;
31  //import org.netbeans.api.jogurt.patterns.ParametrizedFactory;
32  
33  /** XXX - tests (some still missing)
34   *  XXX - javadoc
35   *
36   * @author Petr Hrebejk
37   */
38  public final class Iterators {
39  
40      private static final String   NULL_AS_PARAMETER_MESSAGE = "Iterator(s) passed in as parameter must NOT be null."; // NOI18N
41      
42      /** Singleton */
43      private Iterators() {}
44  
45      public static <T> Iterator  <T> empty() {
46          return new EmptyIterator();
47      }
48      
49      public static <T> Iterator  <T> unmodifiable( Iterator  <T> iterator ) {
50          return new UnmodifiableIterator<T>( iterator );
51      }
52      
53      public static <T> Iterator  <T> chained( Iterator  <T>... iterators ) {
54          return new ChainedIterator<T>( iterators );
55      }
56      
57      public static <T> Iterator  <T> chained( Collection  <Iterator  <T>> iterators ) {        
58          return new ChainedIterator<T>( iterators );
59      }
60      
61      public static <T> Iterator  <T> colating( Iterator  <? extends T>... iterators ) {
62          return new CollatingIterator<T>( iterators );
63      }
64      
65      public static <T> Iterator  <T> colating( Comparator  <? super T> comparator, Iterator  <? extends T>... iterators ) {
66          return new CollatingIterator<T>( comparator, iterators );
67      }
68      
69      public static <T,P> Iterator  <T> translating( Iterator  <? extends P> delegate, Factory<? extends T,P> factory ) { 
70          return new TranslatingIterator<T,P>( delegate, factory );
71      }        
72  
73      /**
74       * Todo: Probably wrong
75       */
76      public static <T> Iterable  <T> toIterable( Iterator  <T> iterator ) {
77          return new IteratorIterable( iterator );
78      }
79      
80      
81      public static <T,P> Iterable  <T> translating (final Iterable  <? extends P> delegate, final Factory<? extends T,P> factory) {        
82          return new TranslatingIterable (delegate, factory);
83      }
84          
85      // Innerclasses ------------------------------------------------------------
86      
87      
88      private static class TranslatingIterable<T,P> implements Iterable  <T> {
89          
90          final Iterable  <? extends P> delegate;
91          final Factory<? extends T,P> factory;
92          
93          
94          public TranslatingIterable (final Iterable  <? extends P> delegate, final Factory<? extends T,P> factory) {
95              assert delegate != null;
96              assert factory != null;
97              this.delegate = delegate;
98              this.factory = factory;
99          }
100         
101         public Iterator  <T> iterator() {
102             return translating(this.delegate.iterator(),this.factory);
103         }        
104     }
105         
106     private static class EmptyIterator<T> implements Iterator  <T> {
107                 
108         public void remove() {
109             throw new UnsupportedOperationException  ( "Can't remove elements from emptu iterator");
110         }
111 
112         public boolean hasNext() {
113             return false;
114         }
115 
116         public T next() {
117             throw new NoSuchElementException  ( "Empty Iterator has no elements");
118         }
119                 
120     }
121     
122     private static class TranslatingIterator<T,P> implements Iterator  <T> {
123         
124         private Iterator  <? extends P> delegate;
125         private Factory<? extends T,P> factory;
126         
127         public TranslatingIterator( Iterator  <? extends P> delegate, Factory<? extends T,P> factory ) {
128             if ( delegate == null ) {
129                 throw new IllegalArgumentException  ( NULL_AS_PARAMETER_MESSAGE );
130             }
131             this.delegate = delegate;
132             this.factory = factory;
133         }
134         
135         public void remove() {
136             delegate.remove();
137         }
138 
139         public T next() {
140             return factory.create( delegate.next() );            
141         }
142 
143         public boolean hasNext() {
144             return delegate.hasNext();
145         }
146                         
147     }
148    
149     
150     private static class UnmodifiableIterator<T> implements Iterator  <T> {
151         
152         private Iterator  <T> delegate;
153         
154         public UnmodifiableIterator( Iterator  <T> delegate ) {
155             if ( delegate == null ) {
156                 throw new IllegalArgumentException  ( NULL_AS_PARAMETER_MESSAGE );
157             }
158             this.delegate = delegate;
159         }
160         
161         public void remove() {
162             throw new UnsupportedOperationException  (); 
163         }
164 
165         public T next() {
166             return delegate.next();            
167         }
168 
169         public boolean hasNext() {
170             return delegate.hasNext();
171         }
172                         
173     }       
174         
175     private static class ChainedIterator<E> implements Iterator  <E> {
176 
177         /** The chain of iterators */
178         protected final List  <Iterator  <E>> iteratorChain = 
179             new ArrayList  <Iterator  <E>>();
180 
181         /** The index of the current iterator */
182         protected int currentIteratorIndex = 0;
183 
184         /** The current iterator */
185         protected Iterator  <E> currentIterator = null;
186 
187         /**
188          * The "last used" <code>Iterator</code> is the <code>Iterator</code> upon
189          * which <code>next()</code> or <code>hasNext()</code> was most recently
190          * called used for the <code>remove()</code> operation only.
191          */
192         protected Iterator  <E> lastUsedIterator = null;
193 
194         /**
195          * <code>IteratorChain</code> is "locked" after the first time
196          * <code>next()</code> is called.
197          */
198         protected boolean isLocked = false;
199 
200 
201         /**
202          * Construct an <code>IteratorChain</code> with a list of
203          * <code>Iterator</code>s.
204          * 
205          * @param iterators the iterators to add to the <code>IteratorChain</code>
206          * 
207          * @throws NullPointerException if one of the provided iterator is
208          *  <code>null</code>
209          */
210         public ChainedIterator(final Iterator  <E>... iterators) {        
211             for (Iterator  <E> iterator : iterators) {
212                 if ( iterator == null ) {
213                     throw new IllegalArgumentException  ( NULL_AS_PARAMETER_MESSAGE );
214                 }
215                 iteratorChain.add(iterator);
216             }
217         }
218                 
219         /**
220          * Constructs a new <code>IteratorChain</code> over the collection of
221          * iterators.
222          *
223          * @param iterators the collection of iterators
224          * 
225          * @throws NullPointerException if iterators collection is or contains
226          *  <code>null</code>
227          */
228         public ChainedIterator(final Collection  <Iterator  <E>> iterators) {
229             for (Iterator  <E> iterator : iterators) {
230                 if ( iterator == null ) {
231                     throw new IllegalArgumentException  ( NULL_AS_PARAMETER_MESSAGE );
232                 }
233                 iteratorChain.add(iterator);
234             }
235         }
236 
237         // Public methods
238         // -------------------------------------------------------------------------
239 
240         /**
241          * Number of <code>Iterator</code>s in the current
242          * <code>IteratorChain</code>.
243          * 
244          * @return the <code>Iterator</code> count
245          */
246         public int size() {
247             return iteratorChain.size();
248         }
249 
250         /**
251          * Updates the current iterator field to ensure that the current
252          * <code>Iterator</code> is not exhausted
253          */
254         protected void updateCurrentIterator() {
255             if (currentIterator == null) {
256                 if (iteratorChain.isEmpty()) {
257                     // @todo How to manage the EmptyIterator.INSTANCE warning?
258                     currentIterator = Collections.<E>emptyList().iterator();
259                 } else {
260                     currentIterator = iteratorChain.get(0);
261                 }
262                 // set last used iterator here, in case the user calls remove
263                 // before calling hasNext() or next() (although they shouldn't)
264                 lastUsedIterator = currentIterator;
265             }
266 
267             while (currentIterator.hasNext() == false &&
268                    currentIteratorIndex < iteratorChain.size() - 1) {
269                 currentIteratorIndex++;
270                 currentIterator = iteratorChain.get(currentIteratorIndex);
271             }
272         }
273 
274         // Iterator interface methods
275         // -------------------------------------------------------------------------
276 
277         /**
278          * Return <code>true</code> if any <code>Iterator</code> in the
279          * <code>IteratorChain</code> has a remaining element.
280          * 
281          * @return <code>true</code> if elements remain
282          */
283         public boolean hasNext() {
284             updateCurrentIterator();
285             lastUsedIterator = currentIterator;
286 
287             return currentIterator.hasNext();
288         }
289 
290         /**
291          * Returns the next object of the current <code>Iterator</code>.
292          * 
293          * @return object from the current <code>Iterator</code>
294          * 
295          * @throws java.util.NoSuchElementException if all the
296          *  <code>Iterator</code>s are exhausted
297          */
298         public E next() {
299             updateCurrentIterator();
300             lastUsedIterator = currentIterator;
301 
302             return currentIterator.next();
303         }
304 
305         /**
306          * Removes from the underlying collection the last element 
307          * returned by the <code>Iterator</code>.
308          * <p>
309          * As with <code>next()</code> and <code>hasNext()</code>, this method calls
310          * <code>remove()</code> on the underlying <code>Iterator</code>. Therefore,
311          * this method may throw an <code>UnsupportedOperationException</code> if
312          * the underlying <code>Iterator</code> does not support this method. 
313          * 
314          * @throws UnsupportedOperationException if the remove operator is not
315          *  supported by the underlying <code>Iterator</code>
316          * @throws IllegalStateException if the next method has not yet been called,
317          *  or the remove method has already been called after the last call to the
318          *  next method
319          */
320         public void remove() {
321             updateCurrentIterator();
322 
323             lastUsedIterator.remove();
324         }
325 
326 
327     }
328     
329     
330 
331     private static class CollatingIterator<E> implements Iterator  <E> {
332 
333         // Instance fields.
334         // -------------------------------------------------------------------------
335 
336         /** The {@link Comparator} used to evaluate order. */
337         private Comparator  <? super E> comparator = null;
338 
339         /** The list of {@link Iterator}s to evaluate. */
340         private List  <Iterator  <? extends E>> iterators = null;
341 
342         /** {@link Iterator#next() Next} objects peeked from each iterator. */
343         private List  <E> values = null;
344 
345         /** Whether or not each {@link #values} element has been set. */
346         private BitSet   valueSet = null;
347 
348         /**
349          * Index of the {@link #iterators iterator} from whom the last returned
350          * value was obtained.
351          */
352         private int lastReturned = -1;
353 
354         // Constructors
355         // ----------------------------------------------------------------------
356 
357 
358         public CollatingIterator( Iterator  <? extends E>... iterators) {
359             this.iterators = Arrays.asList( iterators );
360         }
361 
362         public CollatingIterator( Comparator  <? super E> comp,
363                                   Iterator  <? extends E>... iterators) {
364             this.iterators = Arrays.asList( iterators );
365             this.comparator = comp;
366         }
367 
368         // Iterator Methods
369         // -------------------------------------------------------------------
370 
371         /**
372          * Returns <code>true</code> if any child iterator has remaining elements.
373          *
374          * @return <code>true</code> if this iterator has remaining elements
375          */
376         public boolean hasNext() {
377             start();
378             return anyValueSet(valueSet) || anyHasNext(iterators);
379         }
380 
381         /**
382          * Returns the next ordered element from a child iterator.
383          *
384          * @return the next ordered element
385          * 
386          * @throws NoSuchElementException if no child iterator has any more elements
387          */
388         public E next() throws NoSuchElementException   {
389             if (hasNext() == false) {
390                 throw new NoSuchElementException  ();
391             }
392             int leastIndex = least();
393             if (leastIndex == -1) {
394                 throw new NoSuchElementException  ();
395             } else {
396                 E val = values.get(leastIndex);
397                 clear(leastIndex);
398                 lastReturned = leastIndex;
399                 return val;
400             }
401         }
402 
403         /**
404          * Removes the last returned element from the child iterator that 
405          * produced it.
406          *
407          * @throws IllegalStateException if there is no last returned element,
408          *  or if the last returned element has already been removed
409          */
410         public void remove() {
411             if (lastReturned == -1) {
412                 throw new IllegalStateException  ("No value can be removed at present");
413             }
414             Iterator  <? extends E> it = iterators.get(lastReturned);
415             it.remove();
416         }
417 
418         // Private Methods
419         // -------------------------------------------------------------------
420 
421         /** 
422          * Initializes the collating state if it hasn't been already.
423          */
424         private void start() {
425             if (values == null) {
426                 values = new ArrayList  <E>(iterators.size());
427                 valueSet = new BitSet  (iterators.size());
428                 for (int i = 0; i < iterators.size(); i++) {
429                     values.add(null);
430                     valueSet.clear(i);
431                 }
432             }
433         }
434 
435         /** 
436          * Sets the {@link #values} and {@link #valueSet} attributes 
437          * at position <i>i</i> to the next value of the 
438          * {@link #iterators iterator} at position <i>i</i>, or 
439          * clear them if the <i>i</i><sup>th</sup> iterator
440          * has no next value.
441          *
442          * @return <code>false</code> if there was no value to set
443          */
444         private boolean set(final int i) {
445             Iterator  <? extends E> it = iterators.get(i);
446             if (it.hasNext()) {
447                 values.set(i, it.next());
448                 valueSet.set(i);
449                 return true;
450             } else {
451                 values.set(i, null);
452                 valueSet.clear(i);
453                 return false;
454             }
455         }
456 
457         /** 
458          * Clears the {@link #values} and {@link #valueSet} attributes 
459          * at position <i>i</i>.
460          */
461         private void clear(final int i) {
462             values.set(i, null);
463             valueSet.clear(i);
464         }
465 
466         /** 
467          * Throws {@link IllegalStateException} if iteration has started 
468          * via {@link #start}.
469          * 
470          * @throws IllegalStateException if iteration started
471          */
472         private void checkNotStarted() throws IllegalStateException   {
473             if (values != null) {
474                 throw new IllegalStateException  (
475                             "Can't do that after next or hasNext has been called.");
476             }
477         }
478 
479         /** 
480          * Returns the index of the least element in {@link #values},
481          * {@link #set(int) setting} any uninitialized values.
482          * 
483          * @throws IllegalStateException
484          */
485         private int least() {
486             int leastIndex = -1;
487             E leastObject = null;                
488             for (int i = 0; i < values.size(); i++) {
489                 if (valueSet.get(i) == false) {
490                     set(i);
491                 }
492                 if (valueSet.get(i)) {
493                     if (leastIndex == -1) {
494                         leastIndex = i;
495                         leastObject = values.get(i);
496                     } else {
497                         E curObject = values.get(i);
498                         if (comparator.compare(curObject,leastObject) < 0) {
499                             leastObject = curObject;
500                             leastIndex = i;
501                         }
502                     }
503                 }
504             }
505             return leastIndex;
506         }
507 
508         /**
509          * Returns <code>true</code> if any bit in the given set is 
510          * <code>true</code>.
511          */
512         private boolean anyValueSet(final BitSet   set) {
513             for (int i = 0; i < set.size(); i++) {
514                 if (set.get(i)) {
515                     return true;
516                 }
517             }
518             return false;
519         }
520 
521         /**
522          * Returns <code>true</code> if any {@link Iterator} 
523          * in the given list has a next value.
524          */
525         private boolean anyHasNext(final List  <Iterator  <? extends E>> iters) {
526             for (Iterator  <? extends E> it: iters) {
527                 if (it.hasNext()) {
528                     return true;
529                 }
530             }
531             return false;
532         }
533     }
534     
535     private static class IteratorIterable<T> implements Iterable  <T> {
536         
537         private Iterator  <T> iterator;
538         
539         public IteratorIterable( Iterator  <T> iterator ) {
540             if ( iterator == null ) {
541                 throw new IllegalArgumentException  ( NULL_AS_PARAMETER_MESSAGE );
542             }
543             this.iterator = iterator;
544         }
545 
546         public Iterator  <T> iterator() {
547             return iterator;
548         }
549     
550     }
551     
552 }
553
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags