001: /*
002: * $Id: CollatingRowIterator.java,v 1.19 2005/12/20 18:32:40 ahimanikya Exp $
003: * =======================================================================
004: * Copyright (c) 2002-2005 Axion Development Team. All rights reserved.
005: *
006: * Redistribution and use in source and binary forms, with or without
007: * modification, are permitted provided that the following conditions
008: * are met:
009: *
010: * 1. Redistributions of source code must retain the above
011: * copyright notice, this list of conditions and the following
012: * disclaimer.
013: *
014: * 2. Redistributions in binary form must reproduce the above copyright
015: * notice, this list of conditions and the following disclaimer in
016: * the documentation and/or other materials provided with the
017: * distribution.
018: *
019: * 3. The names "Tigris", "Axion", nor the names of its contributors may
020: * not be used to endorse or promote products derived from this
021: * software without specific prior written permission.
022: *
023: * 4. Products derived from this software may not be called "Axion", nor
024: * may "Tigris" or "Axion" appear in their names without specific prior
025: * written permission.
026: *
027: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
028: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
029: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
030: * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
031: * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
032: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
033: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
034: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
035: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
036: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
037: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
038: * =======================================================================
039: */
040:
041: package org.axiondb.engine.rowiterators;
042:
043: import java.util.ArrayList;
044: import java.util.NoSuchElementException;
045:
046: import org.axiondb.AxionException;
047: import org.axiondb.Row;
048: import org.axiondb.RowComparator;
049: import org.axiondb.RowIterator;
050:
051: /**
052: * Collates the results of two or more sorted {@link RowIterator}s according to the given
053: * {@link RowComparator}. It is assumed that each iterator is already ordered (ascending)
054: * according to the given {@link RowComparator}.
055: *
056: * @version $Revision: 1.19 $ $Date: 2005/12/20 18:32:40 $
057: * @author Rodney Waldhoff
058: * @author Ahimanikya Satapathy
059: */
060: public class CollatingRowIterator extends BaseRowIterator {
061:
062: public CollatingRowIterator(RowComparator comparator) {
063: _comparator = comparator;
064: _iterators = new ArrayList(3);
065: }
066:
067: public void addRowIterator(RowIterator iter)
068: throws IllegalStateException {
069: assertNotStarted();
070: _iterators.add(iter);
071: }
072:
073: public Row current() {
074: if (!hasCurrent()) {
075: throw new NoSuchElementException("No current row");
076: }
077: return _currentRow;
078: }
079:
080: public int currentIndex() {
081: return _currentIndex;
082: }
083:
084: public boolean hasCurrent() {
085: return _hasCurrent;
086: }
087:
088: public boolean hasNext() {
089: start();
090: return anyNextAvailable() || anyIteratorHasNext();
091: }
092:
093: public boolean hasPrevious() {
094: start();
095: return anyPreviousAvailable() || anyIteratorHasPrevious();
096: }
097:
098: public Row last() throws AxionException {
099: if (_started) {
100: clearPreviousPeeked();
101: clearNextPeeked();
102: }
103: for (int i = 0, I = _iterators.size(); i < I; i++) {
104: ((RowIterator) (_iterators.get(i))).last();
105: }
106: _nextIndex = size();
107: _currentIndex = _nextIndex - 1;
108: _hasCurrent = true;
109: return _currentRow = peekPrevious();
110: }
111:
112: public Row next() throws AxionException {
113: if (!hasNext()) {
114: throw new NoSuchElementException("No next row");
115: }
116: _currentIndex = _nextIndex;
117: _nextIndex++;
118: _hasCurrent = true;
119: return _currentRow = peekNextRow();
120: }
121:
122: public int nextIndex() {
123: return _nextIndex;
124: }
125:
126: public Row previous() throws AxionException {
127: if (!hasPrevious()) {
128: throw new NoSuchElementException("No previous row");
129: }
130: _currentIndex = _nextIndex - 1;
131: _nextIndex--;
132: _hasCurrent = true;
133: return _currentRow = peekPreviousRow();
134: }
135:
136: public int previousIndex() {
137: return _nextIndex - 1;
138: }
139:
140: public void remove() throws AxionException {
141: if (!hasCurrent()) {
142: throw new NoSuchElementException("No current row");
143: }
144: RowIterator iter = getLastReturnedFrom();
145: iter.remove();
146: _currentRow = null;
147: _currentIndex = -1;
148: _hasCurrent = false;
149: }
150:
151: public void reset() throws AxionException {
152: start();
153: for (int i = 0, I = _iterators.size(); i < I; i++) {
154: clearNextPeeked(i);
155: clearPreviousPeeked(i);
156: ((RowIterator) _iterators.get(i)).reset();
157: }
158: _currentRow = null;
159: _currentIndex = -1;
160: _hasCurrent = false;
161: _nextIndex = 0;
162: _lastReturnedFrom = -1;
163: }
164:
165: public void set(Row row) throws AxionException {
166: if (!hasCurrent()) {
167: throw new NoSuchElementException("No current row");
168: }
169:
170: RowIterator iter = getLastReturnedFrom();
171: iter.set(row);
172: _currentRow = row;
173: }
174:
175: public String toString() {
176: return "Collating(" + _iterators + ")";
177: }
178:
179: public int size() throws AxionException {
180: int size = 0;
181: for (int i = 0, I = _iterators.size(); i < I; i++) {
182: size += ((RowIterator) (_iterators.get(i))).size();
183: }
184: return size;
185: }
186:
187: private boolean anyIteratorHasNext() {
188: for (int i = 0, I = _iterators.size(); i < I; i++) {
189: RowIterator it = (RowIterator) _iterators.get(i);
190: if (it.hasNext()) {
191: return true;
192: }
193: }
194: return false;
195: }
196:
197: private boolean anyIteratorHasPrevious() {
198: for (int i = 0, I = _iterators.size(); i < I; i++) {
199: RowIterator it = (RowIterator) _iterators.get(i);
200: if (it.hasPrevious()) {
201: return true;
202: }
203: }
204: return false;
205: }
206:
207: private boolean anyNextAvailable() {
208: for (int i = 0, I = _iterators.size(); i < I; i++) {
209: if (isValueSet(_nextValues[i])) {
210: return true;
211: }
212: }
213: return false;
214: }
215:
216: private boolean anyPreviousAvailable() {
217: for (int i = 0, I = _iterators.size(); i < I; i++) {
218: if (isValueSet(_previousValues[i])) {
219: return true;
220: }
221: }
222: return false;
223: }
224:
225: private void assertNotStarted() throws IllegalStateException {
226: if (_started) {
227: throw new IllegalStateException("Already started");
228: }
229: }
230:
231: private void clearNextPeeked() throws AxionException {
232: for (int i = 0, m = _iterators.size(); i < m; i++) {
233: if (isValueSet(_nextValues[i])) {
234: ((RowIterator) _iterators.get(i)).previous();
235: clearNextPeeked(i);
236: }
237: }
238: _nextAvailable = false;
239: }
240:
241: private void clearNextPeeked(int i) {
242: _nextValues[i] = null;
243: }
244:
245: private void clearPreviousPeeked() throws AxionException {
246: for (int i = 0, I = _iterators.size(); i < I; i++) {
247: if (isValueSet(_previousValues[i])) {
248: ((RowIterator) _iterators.get(i)).next();
249: clearPreviousPeeked(i);
250: }
251: }
252: _previousAvailable = false;
253: }
254:
255: private void clearPreviousPeeked(int i) {
256: _previousValues[i] = null;
257: }
258:
259: private RowIterator getLastReturnedFrom()
260: throws IllegalStateException {
261: return (RowIterator) (_iterators.get(_lastReturnedFrom));
262: }
263:
264: private boolean isValueSet(Object val) {
265: return (val != null);
266: }
267:
268: private Row peekNextRow() throws AxionException {
269: _nextAvailable = true;
270: if (_previousAvailable) {
271: clearPreviousPeeked();
272: }
273:
274: int nextIndex = -1;
275: Row nextValue = null;
276: for (int i = 0, I = _iterators.size(); i < I; i++) {
277: if (_nextValues[i] == null) {
278: RowIterator iter = (RowIterator) (_iterators.get(i));
279: if (iter.hasNext()) {
280: // peek ahead to the next value
281: _nextValues[i] = iter.next();
282: } else {
283: continue;
284: }
285: }
286: if (-1 == nextIndex) {
287: nextIndex = i;
288: nextValue = _nextValues[i];
289: } else if (_comparator.compare(nextValue, _nextValues[i]) > 0) {
290: nextIndex = i;
291: nextValue = _nextValues[i];
292: }
293: }
294:
295: _lastReturnedFrom = nextIndex;
296: clearNextPeeked(nextIndex);
297: return nextValue;
298: }
299:
300: private Row peekPreviousRow() throws AxionException {
301: _previousAvailable = true;
302: if (_nextAvailable) {
303: clearNextPeeked();
304: }
305:
306: int previousIndex = -1;
307: Row previousValue = null;
308: for (int i = 0, I = _iterators.size(); i < I; i++) {
309: if (_previousValues[i] == null) {
310: RowIterator iter = (RowIterator) (_iterators.get(i));
311: if (iter.hasPrevious()) {
312: // peek ahead to the previous value
313: _previousValues[i] = iter.previous();
314: } else {
315: continue;
316: }
317: }
318: if (-1 == previousIndex) {
319: previousIndex = i;
320: previousValue = _previousValues[i];
321: } else if (_comparator.compare(previousValue,
322: _previousValues[i]) <= 0) {
323: previousIndex = i;
324: previousValue = _previousValues[i];
325: }
326: }
327:
328: _lastReturnedFrom = previousIndex;
329: clearPreviousPeeked(previousIndex);
330: return previousValue;
331: }
332:
333: /**
334: * Initializes the collating state if it hasn't been already.
335: */
336: private void start() {
337: if (!_started) {
338: int isize = _iterators.size();
339: _nextValues = new Row[isize];
340: _previousValues = new Row[isize];
341: _started = true;
342: }
343: }
344:
345: /** My {@link RowComparator}to use for collating. */
346: private RowComparator _comparator;
347:
348: /** The index of {@link #_currentRow}within my iteration. */
349: private int _currentIndex = -1;
350: /** The last {@link Row}returned by {@link #next}or {@link #previous}. */
351: private Row _currentRow;
352: /** Whether or not {@link #_currentRow}has been set. */
353: private boolean _hasCurrent = false;
354:
355: /** The list of {@link RowIterator}s to collate over. */
356: private ArrayList _iterators;
357: /** The {@link #_iterators iterator}I last returned from. */
358: private int _lastReturnedFrom = -1;
359:
360: /** next {@link Row}value picked up and not used yet */
361: private boolean _nextAvailable = false;
362: /** The next index within my iteration. */
363: private int _nextIndex = 0;
364: /** next {@link Row}values peeked from my {@link #_iterators}. */
365: private Row[] _nextValues;
366:
367: /** previous {@link Row}value picked up and not used yet */
368: private boolean _previousAvailable = false;
369: /** previous {@link Row}values peeked from my {@link #_iterators}. */
370: private Row[] _previousValues;
371:
372: private boolean _started = false;
373: }
|