Merge


1   // ============================================================================
2   // $Id: Merge.java,v 1.5 2006/12/16 16:48:58 davidahall Exp $
3   // Copyright (c) 2006  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.algorithms;
34  
35  import java.util.Collection  ;
36  import java.util.Comparator  ;
37  import java.util.Iterator  ;
38  import java.util.NoSuchElementException  ;
39  import net.sf.jga.fn.BinaryFunctor;
40  import net.sf.jga.fn.adaptor.ConstantBinary;
41  import net.sf.jga.fn.comparison.LessEqual;
42  import net.sf.jga.util.CollectionUtils;
43  import net.sf.jga.util.ComparableComparator;
44  import net.sf.jga.util.LookAheadIterator;
45  
46  import static net.sf.jga.util.ArrayUtils.*;
47  
48  /**
49   * Algorithms that combine the contents of two inputs.  The inputs may arrays, collections, or
50   * iterations.
51   * <p>
52   * Copyright &copy; 2006  David A. Hall
53   */
54  
55  public class Merge {
56  
57      // ============
58      // Arrays
59      // ============
60      
61      /**
62       * Returns all elements of the first array followed by all the elements of the second array
63       */
64      static public <T> Iterable  <T> append(T[] ts1, T[] ts2) {
65          return new MergeIterable<T>(iterable(ts1), iterable(ts2),
66                                      new ConstantBinary<T,T,Boolean  >(Boolean.TRUE));
67      }
68  
69      
70      /**
71       * Returns all elements of both arrays, always choosing the lesser of the two current elements.
72       */
73      static public <T extends Comparable  <? super T>> Iterable  <T> merge(T[] ts1, T[] ts2) {
74          return new MergeIterable<T>(iterable(ts1), iterable(ts2), new ComparableComparator<T>());
75      }
76  
77      
78      /**
79       * Returns all elements of both arrays, always choosing the lesser of the two current elements
80       * using the given comparator.
81       */
82      static public <T> Iterable  <T> merge(T[] ts1, T[] ts2, Comparator  <T> comp) {
83          return new MergeIterable<T>(iterable(ts1), iterable(ts2), comp);
84      }
85  
86      
87      /**
88       * Returns all elements of both arrays, always choosing the lesser of the two current elements
89       * by using the given predicate.  When the predicate returns TRUE, an element is taken from the
90       * first array: when FALSE, an element is taken from the second array.
91       */
92      static public <T> Iterable  <T> merge(T[] ts1, T[] ts2, BinaryFunctor<T,T,Boolean  > pred){
93          return new MergeIterable<T>(iterable(ts1), iterable(ts2), pred); 
94      }
95  
96  
97      // ============
98      // Iterables
99      // ============
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, Iterable  <? extends T> i2) {
106         return merge(i1, i2, new ConstantBinary<T,T,Boolean  >(Boolean.TRUE));
107     }
108 
109     
110     /**
111      * Returns an Iterable implementation that 'contains' all elements of both iterables, always
112      * choosing the lesser of the two current elements.
113      */
114     static public <T extends Comparable  <? super T>> Iterable  <T>
115     merge(Iterable  <? extends T> i1, Iterable  <? extends T> i2)
116     {
117         return merge(i1, i2, new ComparableComparator<T>());
118     }
119 
120     
121     /**
122      * Returns all elements of both iterables, always choosing the lesser of the two current
123      * elements.
124      */
125     static public <T> Iterable  <T>
126     merge(Iterable  <? extends T> i1, Iterable  <? extends T> i2, Comparator  <T> comp)
127     {
128         return new MergeIterable<T>(i1, i2, comp);
129     }
130 
131     
132     /**
133      * Returns all elements of both iterables, always choosing the lesser of the two current
134      * elements by using the given predicate.  When the predicate returns TRUE, an element is
135      * taken from the first array: when FALSE, an element is taken from the second array.
136      */
137     static public <T> Iterable  <T>
138     merge(Iterable  <? extends T> i1, Iterable  <? extends T> i2, BinaryFunctor<T,T,Boolean  > pred)
139     {
140         return new MergeIterable<T>(i1, i2, pred);
141     }
142     
143     // ============
144     // Iterators
145     // ============
146     
147     /**
148      * Returns an Iterator that will return elements from the first input iterator followed by
149      * elements from the second input iterator.
150      */
151     static public <T> Iterator  <T> append(Iterator  <? extends T> iter1, Iterator  <? extends T> iter2) {
152         return new net.sf.jga.util.MergeIterator<T>(iter1, iter2,
153                                                     new ConstantBinary<T,T,Boolean  >(Boolean.TRUE));
154     }
155 
156     
157     /**
158      * Returns an Iterator that will return elements from both input iterators, choosing the
159      * lesser of the two current values.  Neither input iterator is advanced in this method.
160      */
161     static public <T extends Comparable  <? super T>> Iterator  <T>
162     merge(Iterator  <? extends T> iter1, Iterator  <? extends T> iter2) {
163         return new net.sf.jga.util.MergeIterator<T>(iter1, iter2, new ComparableComparator<T>());
164     }
165 
166     
167     /**
168      * Returns an Iterator that will return elements from both input iterators, choosing the
169      * lesser of the two current values using the given comparator.  Neither input iterator
170      * is advanced in this method.
171      */
172     static public <T> Iterator  <T>
173     merge(Iterator  <? extends T> iter1, Iterator  <? extends T> iter2, Comparator  <T> comp) {
174         return new net.sf.jga.util.MergeIterator<T>(iter1,iter2,comp);
175     }
176 
177     
178     /**
179      * Returns an Iterator that will return elements from both input iterators, choosing the
180      * lesser of the two current values by using the given predicate.  When the predicate
181      * returns TRUE, an element is taken from the first array: when FALSE, an element is taken
182      * from the second iterator.  Neither input iterator is advanced in this method.
183      */
184     static public <T> Iterator  <T>
185     merge(Iterator  <? extends T> iter1, Iterator  <? extends T> iter2, BinaryFunctor<T,T,Boolean  > pred){
186         return new net.sf.jga.util.MergeIterator<T>(iter1,iter2,pred);
187     }
188     
189     // ============
190     // IterableCopy
191     // ============
192     
193     /**
194      * Appends the values of the first and second collection to the output collection
195      * @return the output collection
196      */
197     static public <T, TCollection extends Collection  <? super T>> TCollection
198     append(Iterable  <? extends T> cin1, Iterable  <? extends T> cin2, TCollection cout) {
199         return merge(cin1, cin2, new ConstantBinary<T,T,Boolean  >(Boolean.TRUE), cout);
200     }
201 
202     
203     /**
204      * Merges two collections, appending values to the output collection.
205      * @return the output collection
206      */
207     static public <T extends Comparable  <? super T>, TCollection extends Collection  <? super T>> TCollection
208     merge(Iterable  <? extends T> cin1, Iterable  <? extends T> cin2, TCollection cout) {
209         return merge(cin1, cin2, new ComparableComparator<T>(), cout);
210     }
211 
212     
213     /**
214      * Merges two collections using the given comparator, appending values to the output collection.
215      * @return the output collection
216      */
217     static public <T, TCollection extends Collection  <? super T>> TCollection
218     merge(Iterable  <? extends T> cin1, Iterable  <? extends T> cin2, Comparator  <T> comp,
219           TCollection cout)
220     {
221         return CollectionUtils.append(cout, merge(cin1.iterator(), cin2.iterator(), comp));
222     }
223 
224     
225     /**
226      * Merges two collections using the given comparator, appending values to the output collection.
227      * @return the output collection
228      */
229 
230     static public <T, TCollection extends Collection  <? super T>> TCollection
231     merge(Iterable  <? extends T> cin1, Iterable  <? extends T> cin2, BinaryFunctor<T,T,Boolean  > pred,
232           TCollection cout)
233     {
234         return CollectionUtils.append(cout, merge(cin1.iterator(), cin2.iterator(), pred));
235     }
236 
237 
238     /**
239      * Produces iterators that return all of the merged contents of two inputs
240      */
241     static public class MergeIterable<T> implements Iterable  <T> {
242 
243         // The contents
244         private Iterable  <? extends T> _delegate1;
245         private Iterable  <? extends T> _delegate2;
246     
247         // The test
248         private BinaryFunctor<T,T,Boolean  > _pred;
249 
250         /**
251          * Builds a Merge for the given base iterators that uses the given Comparator to compare
252          * corresponding elements.  The Comparator will be used with a LessEqualComp predicate.
253          * @throws IllegalArgumentException if either argument is null
254          */
255       
256         public MergeIterable(Iterable  <? extends T> base1, Iterable  <? extends T> base2,
257                              Comparator  <T> comp)
258         {
259             this(base1, base2, new LessEqual<T>(comp));
260         }
261 
262         /**
263          * Builds a Merge for the given base iterators that uses the given predicate to compare
264          * corresponding elements.  The predicate should return TRUE if its first argument is less
265          * than or equal to the second.
266          * @throws IllegalArgumentException if either base iterable is null
267          */
268     
269         public MergeIterable(Iterable  <? extends T> base1, Iterable  <? extends T> base2,
270                              BinaryFunctor<T,T,Boolean  > pred)
271         {
272             if (base1 == null || base2 == null) {
273                 String   msg = "two base iterables are required";
274                 throw new IllegalArgumentException  (msg);
275             }
276         
277             if (pred == null) {
278                 String   msg = "functor is required";
279                 throw new IllegalArgumentException  (msg);
280             }
281         
282             _delegate1 = base1;
283             _delegate2 = base2;
284             _pred = pred;
285         }
286 
287         // - - - - - - - - - - -
288         // Iterable<T> interface
289         // - - - - - - - - - - -
290 
291         public Iterator  <T> iterator() {
292             return new net.sf.jga.util.MergeIterator<T>(_delegate1.iterator(),
293                                                         _delegate2.iterator(), _pred);
294         }
295     }
296     
297     /**
298      * Iterator that merges the contents of two input iterators.
299      */
300     static public class MergeIterator<T> implements Iterator  <T> {
301         // The base iterators
302         private LookAheadIterator<? extends T> _base1;
303         private LookAheadIterator<? extends T> _base2;
304 
305         // The test
306         private BinaryFunctor<T,T,Boolean  > _pred;
307 
308         /**
309          * Builds a Merge.Iterator for the given base iterators that uses the given
310          * Comparator to compare corresponding elements.  The Comparator will be
311          * used with a LessEqualComp predicate.
312          * @throws IllegalArgumentException if either argument is null
313          */
314 
315         public MergeIterator(Iterator  <? extends T> base1, Iterator  <? extends T> base2,
316                              Comparator  <T> comp)
317         {
318             this(base1, base2, new LessEqual<T>(comp));
319         }
320         
321         /**
322          * Builds a Merge.Iterator for the given base iterators that uses the given
323          * predicate to compare corresponding elements.  The predicate should return
324          * TRUE if its first argument is less than or equal to the second.
325          * @throws IllegalArgumentException if either argument is null
326          */
327         
328         public MergeIterator(Iterator  <? extends T> base1, Iterator  <? extends T> base2,
329                              BinaryFunctor<T,T,Boolean  > pred)
330         {
331             if (base1 == null || base2 == null) {
332                 String   msg = "two base iterators are required";
333                 throw new IllegalArgumentException  (msg);
334             }
335             if (pred == null) {
336                 String   msg = "functor is required";
337                 throw new IllegalArgumentException  (msg);
338             }
339 
340             _base1 = new LookAheadIterator<T>(base1, 1);
341             _base2 = new LookAheadIterator<T>(base2, 1);
342             _pred = pred;
343         }
344 
345     
346         // - - - - - - - - - - -
347         // Iterator<T> interface
348         // - - - - - - - - - - -
349     
350         public boolean hasNext() {
351             return _base1.hasNextPlus(1) || _base2.hasNextPlus(1);
352         }
353 
354         public T next() {
355             if (_base1.hasNextPlus(1)) 
356                 if (_base2.hasNextPlus(1))
357                     if (_pred.fn(_base1.peek(1), _base2.peek(1)))
358                         return _base1.next();           
359                     else
360                         return _base2.next();
361                 else
362                     return _base1.next();
363             else
364                 if (_base2.hasNextPlus(1)) 
365                     return _base2.next();
366                 else
367                     throw new NoSuchElementException  ();
368         }
369 
370         public void remove() { throw new UnsupportedOperationException  (); }
371     }
372 }
373
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags