LookAheadIterator


1   // ============================================================================
2   // $Id: LookAheadIterator.java,v 1.19 2005/08/02 23:45:22 davidahall Exp $
3   // Copyright (c) 2003-2005  David A. Hall
4   // ============================================================================
5   // The contents of this file are subject to the Common Development and
6   // Distribution License (CDDL), Version 1.0 (the License); you may not use this 
7   // file except in compliance with the License.  You should have received a copy
8   // of the the License along with this file: if not, a copy of the License is 
9   // available from Sun Microsystems, Inc.
10  //
11  // http://www.sun.com/cddl/cddl.html
12  //
13  // From time to time, the license steward (initially Sun Microsystems, Inc.) may
14  // publish revised and/or new versions of the License.  You may not use,  
15  // distribute, or otherwise make this file available under subsequent versions 
16  // of the License.
17  // 
18  // Alternatively, the contents of this file may be used under the terms of the 
19  // GNU Lesser General Public License Version 2.1 or later (the "LGPL"), in which
20  // case the provisions of the LGPL are applicable instead of those above. If you 
21  // wish to allow use of your version of this file only under the terms of the 
22  // LGPL, and not to allow others to use your version of this file under the 
23  // terms of the CDDL, indicate your decision by deleting the provisions above 
24  // and replace them with the notice and other provisions required by the LGPL. 
25  // If you do not delete the provisions above, a recipient may use your version 
26  // of this file under the terms of either the CDDL or the LGPL.
27  // 
28  // This library is distributed in the hope that it will be useful,
29  // but WITHOUT ANY WARRANTY; without even the implied warranty of
30  // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 
31  // ============================================================================
32  
33  package net.sf.jga.util;
34  
35  import java.lang.reflect.Array  ;
36  import java.util.ArrayList  ;
37  import java.util.NoSuchElementException  ;
38  import java.util.Iterator  ;
39  
40  /**
41   * Iterator that allows the program to look at and operate on the next few
42   * elements without consuming them.
43   * <p>
44   * Copyright &copy; 2003-2005  David A. Hall
45   *
46   * @author <a HREF="mailto:davidahall@users.sf.net">David A. Hall</a>
47   */
48  
49  public class LookAheadIterator<T> implements Iterator  <T>, Iterable  <T> {
50      // The base iterator
51      private Iterator  <? extends T> _base;
52  
53      // ring buffer, to hold the elements that have been read ahead of the
54      // current position.
55      private Object  [] _buffer;
56  
57      // index of the next element to read from the buffer
58      private int _readptr = 0;
59  
60      // index of the next element to write to the buffer
61      private int _writeptr = 0;
62  
63      // number of elements in the buffer
64      private int _cnt = 0;
65  
66      // size of the buffer
67      private int _size;
68  
69      /**
70       * Builds a LookAheadIterator that can look ahead 1 element.
71       */
72        
73      public LookAheadIterator (Iterator  <? extends T> base) {
74          this(base, 1);
75      }
76  
77      /**
78       * Builds a LookAheadIterator that can look ahead the given number of
79       * elements.
80       * 
81       * @throws IllegalArgumentException if max <= 0.
82       */
83        
84      public LookAheadIterator (Iterator  <? extends T> base, int max) {
85          if (max <= 0)
86              throw new IllegalArgumentException  ();
87          
88          _base = (base != null) ? base : new EmptyIterator<T>();
89          _size = max;
90  
91          _buffer = new Object  [_size];
92      }
93  
94      /**
95       * Returns true if there is an element at the Nth position.  Put another
96       * way, returns true if there are enough elements remaining in the iterator
97       * that next() could be called N times without having a
98       * NoSuchElementException thrown.
99       *
100      * @return true if there is an element at the Nth position
101      * @throws IllegalArgumentException if n < 0 or n > max lookahead
102      */
103     
104     public boolean hasNextPlus(int n) {
105         if (n < 0 || n > _size)
106             throw new IllegalArgumentException  ();
107 
108         if (n == 0)
109             return hasNext();
110 
111         return readAhead(n);
112     }
113 
114     /**
115      * Returns the element at the Nth position.  Put another way, returns the
116      * element that the Nth call to next() would return.  The current position
117      * of the iteration is not modified.
118      *
119      * @return the element at the Nth position
120      * @throws IllegalArgumentException if n < 0 or n > max lookahead
121      * @throws NoSuchElementException if the Nth position is off the end of
122      *         the iteration
123      */
124     
125     public T peek(int n) {
126         if (n < 0 || n > _size)
127             throw new IllegalArgumentException  ();
128 
129         if (!readAhead(n)) {
130             throw new NoSuchElementException  ();
131         }
132             
133         int offset = (_readptr + n - 1) % _size;
134         
135         // @SuppressWarnings
136         // This generates an unchecked cast warning: it's ok since the only
137         // thing that can get into the buffer came from an
138         // Iterator<? extends T>, we know that the cast is always valid
139         
140         return (T) _buffer[offset];
141     }
142     
143     /**
144      * Returns the maximum offset that may be peeked.
145      */
146     public int getMaxPeekSize() {
147         return _size;
148     }
149 
150     // - - - - - - - - - - -
151     // Iterable<T> interface
152     // - - - - - - - - - - -
153 
154     public Iterator  <T> iterator() { return this; }
155     
156     // - - - - - - - - - - -
157     // Iterator<T> interface
158     // - - - - - - - - - - -
159     
160     public boolean hasNext() {
161         if (_cnt > 0)
162             return true;
163         else 
164             return _base.hasNext();
165     }
166 
167     public T next() {
168         if (_cnt == 0)
169             return _base.next();
170 
171         // @SuppressWarnings
172         // This generates an unchecked cast warning: it's ok since the only
173         // thing that can get into the buffer came from an
174         // Iterator<? extends T>, we know that the cast is always valid
175         
176         T value = (T) _buffer[_readptr];
177         _readptr = advance(_readptr);
178         _cnt--;
179 
180         return value;
181     }
182 
183     // private implementation
184     
185     public void remove() { throw new UnsupportedOperationException  (); }
186 
187         private boolean readAhead(int n) {
188         if (n <= _cnt)
189             return true;
190         
191         while (n > _cnt &&_base.hasNext()) {
192             // this line generates an unchecked cast warning, although it should
193             // be safe in this case: it would be difficult to find a way to
194             // corrupt the private array
195             _buffer[_writeptr] = (T) _base.next();
196             
197             _cnt++;
198             _writeptr = advance(_writeptr);
199         }
200 
201         return n == _cnt;
202     }
203     
204     private int advance(int n) {
205         return ++n % _size;
206     }
207 }
208
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags