|
Saturday, 25 February 2012 18:55 |
// Copied from https://gist.github.com/1911614
// Similar to http://snippets.dzone.com/posts/show/11959 but type safe.
/* Copyright 2012 LinkedIn Corp.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/
import com.google.common.base.Function;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
/**
* @author
This e-mail address is being protected from spambots. You need JavaScript enabled to view it
*/
public class Cartesian
{
/**
* Generate the Cartesian
* product of the given axes. For axes [[a1, a2 ...], [b1, b2 ...], [c1, c2 ...]
* ...] the product is [[a1, b1, c1 ...] ... [a1, b1, c2 ...] ... [a1, b2, c1 ...] ...
* [aN, bN, cN ...]]. In other words, the results are generated in same order as these
* nested loops:
*
*
* for (A a : [a1, a2 ...])
* for (A b : [b1, b2 ...])
* for (A c : [c1, c2 ...])
* ...
* result = new R[]{ a, b, c ... };
*
*
* Each result is a new array of R, whose elements refer to the elements of the axes. If
* you prefer a List, call asLists(product(axes)).
*
* Don't change the axes while iterating over their product, as a rule. Changes to the
* axes can affect the product or cause iteration to fail (which is usually bad). To
* prevent this, you can clone the axes.
*
* The implementation is lazy. This method iterates over the axes. The returned Iterable
* contains references to each axis. Iterating over the product causes iteration over
* each axis. Methods of each axis are called as late as practical.
*/
public static Iterable product(Class resultType, Iterable> axes)
{
return new Product(resultType, axes);
}
/**
* Wrap the given arrays in fixed-size Lists. Changes to the lists write through to the
* arrays.
*/
public static Iterable> asLists(Iterable sources)
{
return Iterables.transform(sources, new AsList());
}
/** Arrays.asList, represented as a Function (as used in Google collections). */
public static class AsList implements Function>
{
@Override
public List apply(T[] x)
{
return Arrays.asList(x);
}
}
private static class Product implements Iterable
{
private final Class _resultType;
private final ArrayList> _axes;
Product(Class resultType, Iterable> axes)
{
_resultType = resultType;
_axes = Lists.newArrayList(axes);
}
@Override
public Iterator iterator()
{
if (!_axes.isEmpty())
return new ProductIterator(_resultType, _axes);
Object newArray = Array.newInstance(_resultType, 0);
@SuppressWarnings("unchecked")
R[] emptyArray = (R[]) newArray;
return Collections.singleton(emptyArray).iterator();
}
@Override
public String toString()
{
return "Cartesian.product(" + _axes + ")";
}
private static class ProductIterator implements Iterator
{
private final Class _resultType;
private final List> _axes;
private final List> _iterators; // one per axis
/**
* The minimum index such that this.next() will return an array that contains
* _iterators.get(index).next(). There are some special sentinel values:
* _iterators.size() means the value is unknown (to be determined by this.hasNext),
* and -1 means all combinations have been exhausted (so this.hasNext() == false).
*/
private int _nextIndex;
private final List _result; // a copy of the last result
ProductIterator(Class resultType, ArrayList> axes)
{
_resultType = resultType;
_axes = axes; // contained by reference
_iterators = new ArrayList>(_axes.size());
for (Iterable s : _axes)
{
_iterators.add(s.iterator());
}
_nextIndex = _iterators.size();
_result = new ArrayList(_nextIndex);
}
private void close()
{
_nextIndex = -1;
// Release references, to encourage garbage collection:
_iterators.clear();
_result.clear();
}
@Override
public boolean hasNext()
{
if (_nextIndex >= _iterators.size())
{
// Determine the _nextIndex to be used by next():
if (_result.isEmpty()) // This is the first call to hasNext().
{
_nextIndex = 0; // start here
for (Iterator iter : _iterators)
{
if (!iter.hasNext())
{
close(); // no combinations
break;
}
_result.add(null); // to increase its size
}
}
else
// This is the first call to hasNext() after next() returned a result.
{
for (_nextIndex = _iterators.size() - 1; _nextIndex >= 0; --_nextIndex)
{
Iterator iter = _iterators.get(_nextIndex);
if (iter.hasNext())
{
break; // start here
}
if (_nextIndex == 0) // All combinations have been generated.
{
close();
break;
}
// Repeat this axis, with the next value from the previous axis.
iter = _axes.get(_nextIndex).iterator();
_iterators.set(_nextIndex, iter);
if (!iter.hasNext()) // Oops; this axis can't be repeated.
{
close(); // no more combinations
break;
}
}
}
}
return _nextIndex >= 0;
}
@Override
public R[] next()
{
if (!hasNext())
throw new NoSuchElementException("!hasNext");
for (; _nextIndex < _iterators.size(); ++_nextIndex)
{
_result.set(_nextIndex, _iterators.get(_nextIndex).next());
}
Object newArray = Array.newInstance(_resultType, _result.size());
@SuppressWarnings("unchecked")
R[] result = (R[]) newArray;
return _result.toArray(result);
}
@Override
public void remove()
{
for (Iterator iter : _iterators)
{
iter.remove();
}
}
@Override
public String toString()
{
return "Cartesian.product(" + _axes + ").iterator()";
}
}
}
}
 Read more: |
|
|
