|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object de.uni_tuebingen.sfb.lichtenstein.combinatorics.CombinatoricOperator<T>
T
- The type of the objects to operate on.public abstract class CombinatoricOperator<T>
A common superclass for all combinatoric operators. Makes use of the template method pattern to define all others.
Given an array of objects of type T, it returns all results of a certain combinatoric operation.
For efficiency, I changed this class to use ints for the counters. This means that e.g. for permutations, the maximal size of the array is about 20. If larger arrays are needed, BigInteger should be used (reintroduced). TODO: make simultaneous iteration possible.
Field Summary | |
---|---|
protected T[] |
elements
The elements the operator works upon. |
protected int[] |
indices
An integer array backing up the original one to keep track of the indices. |
private int |
numLeft
The variations still to go. |
private int |
total
The total number of variations to be computed. |
Constructor Summary | |
---|---|
protected |
CombinatoricOperator(T[] elements,
int r)
Initialize a new operator, with given elements and size of the arrays to be returned. |
Method Summary | ||
---|---|---|
static
|
collectionToArray(java.util.Collection<T> coll,
java.lang.Class<T> type)
Return an array that contains all the elements of the given collection. |
|
protected abstract void |
computeNext()
Compute the next array of indices. |
|
static int |
factorial(int n)
Compute the factorial of n. |
|
int |
getNumLeft()
Return number of variations not yet generated. |
|
private T[] |
getResult(int[] indexes)
Compute the result, based on the given array of indices. |
|
int |
getTotal()
Return the total number of variations. |
|
boolean |
hasNext()
Returns true if the iteration has more elements. |
|
protected void |
initializeIndices()
Initialize the array of indices. |
|
protected abstract int |
initializeTotal(int n,
int r)
Compute the total number of elements to return. |
|
java.util.Iterator<T[]> |
iterator()
A combinatoric operator is itself an iterator. |
|
T[] |
next()
Compute the next combination. |
|
void |
remove()
Not supported. |
|
void |
reset()
Reset the iteration. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
protected T[] elements
protected int[] indices
private int numLeft
private final int total
Constructor Detail |
---|
protected CombinatoricOperator(T[] elements, int r)
elements
- The elements on which this combinatoric operator has to act.r
- The size of the arrays to compute.| 0 <= r
| new.getTotal() == initializeTotal();
| new.getNumLeft() == new.getTotal()
Method Detail |
---|
protected void initializeIndices()
protected abstract int initializeTotal(int n, int r)
n
- The number of elements the operator works on.r
- The size of the arrays to return.| result >= 0
public void reset()
| new.getNumLeft() ==
getTotal()
public int getNumLeft()
public int getTotal()
public boolean hasNext()
hasNext
in interface java.util.Iterator<T[]>
| result == getNumLeft() > 0;
public T[] next()
next
in interface java.util.Iterator<T[]>
protected abstract void computeNext()
private T[] getResult(int[] indexes)
indexes
- An array of indices into the element array.| result[i] == elements[indexes[i]]
public void remove()
remove
in interface java.util.Iterator<T[]>
public java.util.Iterator<T[]> iterator()
iterator
in interface java.lang.Iterable<T[]>
| result == this
public static int factorial(int n)
n
- The number of which the factorial is to be computed. Should be less than 20, otherwise integer overflow
occurs.
public static <T> T[] collectionToArray(java.util.Collection<T> coll, java.lang.Class<T> type)
T
- The type of the elements of the collection.coll
- The collection to transform.type
- The type of the elements in the collection. Unfortunately, this method argument is necessary to create an
array of the appropriate type. Blame Java generics.| for each element in result | coll.contains(element)
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |