001: // ============================================================================
002: // $Id: Merge.java,v 1.5 2006/12/16 16:48:58 davidahall Exp $
003: // Copyright (c) 2006 David A. Hall
004: // ============================================================================
005: // The contents of this file are subject to the Common Development and
006: // Distribution License (CDDL), Version 1.0 (the License); you may not use this
007: // file except in compliance with the License. You should have received a copy
008: // of the the License along with this file: if not, a copy of the License is
009: // available from Sun Microsystems, Inc.
010: //
011: // http://www.sun.com/cddl/cddl.html
012: //
013: // From time to time, the license steward (initially Sun Microsystems, Inc.) may
014: // publish revised and/or new versions of the License. You may not use,
015: // distribute, or otherwise make this file available under subsequent versions
016: // of the License.
017: //
018: // Alternatively, the contents of this file may be used under the terms of the
019: // GNU Lesser General Public License Version 2.1 or later (the "LGPL"), in which
020: // case the provisions of the LGPL are applicable instead of those above. If you
021: // wish to allow use of your version of this file only under the terms of the
022: // LGPL, and not to allow others to use your version of this file under the
023: // terms of the CDDL, indicate your decision by deleting the provisions above
024: // and replace them with the notice and other provisions required by the LGPL.
025: // If you do not delete the provisions above, a recipient may use your version
026: // of this file under the terms of either the CDDL or the LGPL.
027: //
028: // This library is distributed in the hope that it will be useful,
029: // but WITHOUT ANY WARRANTY; without even the implied warranty of
030: // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
031: // ============================================================================
032:
033: package net.sf.jga.algorithms;
034:
035: import java.util.Collection;
036: import java.util.Comparator;
037: import java.util.Iterator;
038: import java.util.NoSuchElementException;
039: import net.sf.jga.fn.BinaryFunctor;
040: import net.sf.jga.fn.adaptor.ConstantBinary;
041: import net.sf.jga.fn.comparison.LessEqual;
042: import net.sf.jga.util.CollectionUtils;
043: import net.sf.jga.util.ComparableComparator;
044: import net.sf.jga.util.LookAheadIterator;
045:
046: import static net.sf.jga.util.ArrayUtils.*;
047:
048: /**
049: * Algorithms that combine the contents of two inputs. The inputs may arrays, collections, or
050: * iterations.
051: * <p>
052: * Copyright © 2006 David A. Hall
053: */
054:
055: public class Merge {
056:
057: // ============
058: // Arrays
059: // ============
060:
061: /**
062: * Returns all elements of the first array followed by all the elements of the second array
063: */
064: static public <T> Iterable<T> append(T[] ts1, T[] ts2) {
065: return new MergeIterable<T>(iterable(ts1), iterable(ts2),
066: new ConstantBinary<T, T, Boolean>(Boolean.TRUE));
067: }
068:
069: /**
070: * Returns all elements of both arrays, always choosing the lesser of the two current elements.
071: */
072: static public <T extends Comparable<? super T>> Iterable<T> merge(
073: T[] ts1, T[] ts2) {
074: return new MergeIterable<T>(iterable(ts1), iterable(ts2),
075: new ComparableComparator<T>());
076: }
077:
078: /**
079: * Returns all elements of both arrays, always choosing the lesser of the two current elements
080: * using the given comparator.
081: */
082: static public <T> Iterable<T> merge(T[] ts1, T[] ts2,
083: Comparator<T> comp) {
084: return new MergeIterable<T>(iterable(ts1), iterable(ts2), comp);
085: }
086:
087: /**
088: * Returns all elements of both arrays, always choosing the lesser of the two current elements
089: * by using the given predicate. When the predicate returns TRUE, an element is taken from the
090: * first array: when FALSE, an element is taken from the second array.
091: */
092: static public <T> Iterable<T> merge(T[] ts1, T[] ts2,
093: BinaryFunctor<T, T, Boolean> pred) {
094: return new MergeIterable<T>(iterable(ts1), iterable(ts2), pred);
095: }
096:
097: // ============
098: // Iterables
099: // ============
100:
101: /**
102: * Returns an Iterable implementation that 'contains' all elements of first iterable followed by
103: * all elements of the second iterable
104: */
105: static public <T> Iterable<T> append(Iterable<? extends T> i1,
106: Iterable<? extends T> i2) {
107: return merge(i1, i2, new ConstantBinary<T, T, Boolean>(
108: Boolean.TRUE));
109: }
110:
111: /**
112: * Returns an Iterable implementation that 'contains' all elements of both iterables, always
113: * choosing the lesser of the two current elements.
114: */
115: static public <T extends Comparable<? super T>> Iterable<T> merge(
116: Iterable<? extends T> i1, Iterable<? extends T> i2) {
117: return merge(i1, i2, new ComparableComparator<T>());
118: }
119:
120: /**
121: * Returns all elements of both iterables, always choosing the lesser of the two current
122: * elements.
123: */
124: static public <T> Iterable<T> merge(Iterable<? extends T> i1,
125: Iterable<? extends T> i2, Comparator<T> comp) {
126: return new MergeIterable<T>(i1, i2, comp);
127: }
128:
129: /**
130: * Returns all elements of both iterables, always choosing the lesser of the two current
131: * elements by using the given predicate. When the predicate returns TRUE, an element is
132: * taken from the first array: when FALSE, an element is taken from the second array.
133: */
134: static public <T> Iterable<T> merge(Iterable<? extends T> i1,
135: Iterable<? extends T> i2, BinaryFunctor<T, T, Boolean> pred) {
136: return new MergeIterable<T>(i1, i2, pred);
137: }
138:
139: // ============
140: // Iterators
141: // ============
142:
143: /**
144: * Returns an Iterator that will return elements from the first input iterator followed by
145: * elements from the second input iterator.
146: */
147: static public <T> Iterator<T> append(Iterator<? extends T> iter1,
148: Iterator<? extends T> iter2) {
149: return new net.sf.jga.util.MergeIterator<T>(iter1, iter2,
150: new ConstantBinary<T, T, Boolean>(Boolean.TRUE));
151: }
152:
153: /**
154: * Returns an Iterator that will return elements from both input iterators, choosing the
155: * lesser of the two current values. Neither input iterator is advanced in this method.
156: */
157: static public <T extends Comparable<? super T>> Iterator<T> merge(
158: Iterator<? extends T> iter1, Iterator<? extends T> iter2) {
159: return new net.sf.jga.util.MergeIterator<T>(iter1, iter2,
160: new ComparableComparator<T>());
161: }
162:
163: /**
164: * Returns an Iterator that will return elements from both input iterators, choosing the
165: * lesser of the two current values using the given comparator. Neither input iterator
166: * is advanced in this method.
167: */
168: static public <T> Iterator<T> merge(Iterator<? extends T> iter1,
169: Iterator<? extends T> iter2, Comparator<T> comp) {
170: return new net.sf.jga.util.MergeIterator<T>(iter1, iter2, comp);
171: }
172:
173: /**
174: * Returns an Iterator that will return elements from both input iterators, choosing the
175: * lesser of the two current values by using the given predicate. When the predicate
176: * returns TRUE, an element is taken from the first array: when FALSE, an element is taken
177: * from the second iterator. Neither input iterator is advanced in this method.
178: */
179: static public <T> Iterator<T> merge(Iterator<? extends T> iter1,
180: Iterator<? extends T> iter2,
181: BinaryFunctor<T, T, Boolean> pred) {
182: return new net.sf.jga.util.MergeIterator<T>(iter1, iter2, pred);
183: }
184:
185: // ============
186: // IterableCopy
187: // ============
188:
189: /**
190: * Appends the values of the first and second collection to the output collection
191: * @return the output collection
192: */
193: static public <T, TCollection extends Collection<? super T>> TCollection append(
194: Iterable<? extends T> cin1, Iterable<? extends T> cin2,
195: TCollection cout) {
196: return merge(cin1, cin2, new ConstantBinary<T, T, Boolean>(
197: Boolean.TRUE), cout);
198: }
199:
200: /**
201: * Merges two collections, appending values to the output collection.
202: * @return the output collection
203: */
204: static public <T extends Comparable<? super T>, TCollection extends Collection<? super T>> TCollection merge(
205: Iterable<? extends T> cin1, Iterable<? extends T> cin2,
206: TCollection cout) {
207: return merge(cin1, cin2, new ComparableComparator<T>(), cout);
208: }
209:
210: /**
211: * Merges two collections using the given comparator, appending values to the output collection.
212: * @return the output collection
213: */
214: static public <T, TCollection extends Collection<? super T>> TCollection merge(
215: Iterable<? extends T> cin1, Iterable<? extends T> cin2,
216: Comparator<T> comp, TCollection cout) {
217: return CollectionUtils.append(cout, merge(cin1.iterator(), cin2
218: .iterator(), comp));
219: }
220:
221: /**
222: * Merges two collections using the given comparator, appending values to the output collection.
223: * @return the output collection
224: */
225:
226: static public <T, TCollection extends Collection<? super T>> TCollection merge(
227: Iterable<? extends T> cin1, Iterable<? extends T> cin2,
228: BinaryFunctor<T, T, Boolean> pred, TCollection cout) {
229: return CollectionUtils.append(cout, merge(cin1.iterator(), cin2
230: .iterator(), pred));
231: }
232:
233: /**
234: * Produces iterators that return all of the merged contents of two inputs
235: */
236: static public class MergeIterable<T> implements Iterable<T> {
237:
238: // The contents
239: private Iterable<? extends T> _delegate1;
240: private Iterable<? extends T> _delegate2;
241:
242: // The test
243: private BinaryFunctor<T, T, Boolean> _pred;
244:
245: /**
246: * Builds a Merge for the given base iterators that uses the given Comparator to compare
247: * corresponding elements. The Comparator will be used with a LessEqualComp predicate.
248: * @throws IllegalArgumentException if either argument is null
249: */
250:
251: public MergeIterable(Iterable<? extends T> base1,
252: Iterable<? extends T> base2, Comparator<T> comp) {
253: this (base1, base2, new LessEqual<T>(comp));
254: }
255:
256: /**
257: * Builds a Merge for the given base iterators that uses the given predicate to compare
258: * corresponding elements. The predicate should return TRUE if its first argument is less
259: * than or equal to the second.
260: * @throws IllegalArgumentException if either base iterable is null
261: */
262:
263: public MergeIterable(Iterable<? extends T> base1,
264: Iterable<? extends T> base2,
265: BinaryFunctor<T, T, Boolean> pred) {
266: if (base1 == null || base2 == null) {
267: String msg = "two base iterables are required";
268: throw new IllegalArgumentException(msg);
269: }
270:
271: if (pred == null) {
272: String msg = "functor is required";
273: throw new IllegalArgumentException(msg);
274: }
275:
276: _delegate1 = base1;
277: _delegate2 = base2;
278: _pred = pred;
279: }
280:
281: // - - - - - - - - - - -
282: // Iterable<T> interface
283: // - - - - - - - - - - -
284:
285: public Iterator<T> iterator() {
286: return new net.sf.jga.util.MergeIterator<T>(_delegate1
287: .iterator(), _delegate2.iterator(), _pred);
288: }
289: }
290:
291: /**
292: * Iterator that merges the contents of two input iterators.
293: */
294: static public class MergeIterator<T> implements Iterator<T> {
295: // The base iterators
296: private LookAheadIterator<? extends T> _base1;
297: private LookAheadIterator<? extends T> _base2;
298:
299: // The test
300: private BinaryFunctor<T, T, Boolean> _pred;
301:
302: /**
303: * Builds a Merge.Iterator for the given base iterators that uses the given
304: * Comparator to compare corresponding elements. The Comparator will be
305: * used with a LessEqualComp predicate.
306: * @throws IllegalArgumentException if either argument is null
307: */
308:
309: public MergeIterator(Iterator<? extends T> base1,
310: Iterator<? extends T> base2, Comparator<T> comp) {
311: this (base1, base2, new LessEqual<T>(comp));
312: }
313:
314: /**
315: * Builds a Merge.Iterator for the given base iterators that uses the given
316: * predicate to compare corresponding elements. The predicate should return
317: * TRUE if its first argument is less than or equal to the second.
318: * @throws IllegalArgumentException if either argument is null
319: */
320:
321: public MergeIterator(Iterator<? extends T> base1,
322: Iterator<? extends T> base2,
323: BinaryFunctor<T, T, Boolean> pred) {
324: if (base1 == null || base2 == null) {
325: String msg = "two base iterators are required";
326: throw new IllegalArgumentException(msg);
327: }
328: if (pred == null) {
329: String msg = "functor is required";
330: throw new IllegalArgumentException(msg);
331: }
332:
333: _base1 = new LookAheadIterator<T>(base1, 1);
334: _base2 = new LookAheadIterator<T>(base2, 1);
335: _pred = pred;
336: }
337:
338: // - - - - - - - - - - -
339: // Iterator<T> interface
340: // - - - - - - - - - - -
341:
342: public boolean hasNext() {
343: return _base1.hasNextPlus(1) || _base2.hasNextPlus(1);
344: }
345:
346: public T next() {
347: if (_base1.hasNextPlus(1))
348: if (_base2.hasNextPlus(1))
349: if (_pred.fn(_base1.peek(1), _base2.peek(1)))
350: return _base1.next();
351: else
352: return _base2.next();
353: else
354: return _base1.next();
355: else if (_base2.hasNextPlus(1))
356: return _base2.next();
357: else
358: throw new NoSuchElementException();
359: }
360:
361: public void remove() {
362: throw new UnsupportedOperationException();
363: }
364: }
365: }
|