001/*
002 * $Id$
003 */
004
005package edu.jas.ps;
006
007
008import java.util.Iterator;
009import java.util.NoSuchElementException;
010import java.util.List;
011import java.util.ArrayList;
012
013
014import edu.jas.poly.ExpVector;
015import edu.jas.util.CartesianProductLong;
016import edu.jas.util.LongIterable;
017
018
019/**
020 * Iterable for ExpVector, using total degree enumeration.
021 * @author Heinz Kredel
022 */
023public class ExpVectorIterable implements Iterable<ExpVector> {
024
025
026    protected long upperBound;
027
028
029    final boolean infinite;
030
031
032    final int nvar;
033
034
035    /**
036     * Constructor.
037     * @param nv number of variables.
038     */
039    public ExpVectorIterable(int nv) {
040        this(nv,true,Long.MAX_VALUE);
041    }
042
043
044    /**
045     * Constructor.
046     * @param nv number of variables.
047     * @param ub upper bound for the components.
048     */
049    public ExpVectorIterable(int nv, long ub) {
050        this(nv,false,ub);
051    }
052
053
054    /**
055     * Constructor.
056     * @param nv number of variables.
057     * @param all true, if all elements between 0 and upper bound are enumerated, 
058                  false, if only elements of exact upper bund are to be processed.
059     * @param ub upper bound for the components.
060     */
061    public ExpVectorIterable(int nv, boolean all, long ub) {
062        upperBound = ub;
063        infinite = all;
064        nvar = nv;
065    }
066
067
068    /** Set the upper bound for the iterator.
069     * @param ub an upper bound for the iterator elements. 
070     */
071    public void setUpperBound(long ub) {
072        upperBound = ub;
073    }
074
075
076    /** Get the upper bound for the iterator.
077     * @return the upper bound for the iterator elements. 
078     */
079    public long getUpperBound() {
080        return upperBound;
081    }
082
083
084    /**
085     * Get an iterator over ExpVector.
086     * @return an iterator.
087     */
088    public Iterator<ExpVector> iterator() {
089        return new ExpVectorIterator(nvar,infinite,upperBound);
090    }
091
092}
093
094
095/**
096 * ExpVector iterator using CartesianProductLongIterator.
097 * @author Heinz Kredel
098 */
099class ExpVectorIterator implements Iterator<ExpVector> {
100
101
102    /**
103     * data structure.
104     */
105    ExpVector current;
106
107
108    Iterator<List<Long>> liter;
109
110
111    protected int totalDegree;
112
113
114    protected boolean empty;
115
116
117    final long upperBound;
118
119
120    final boolean infinite;
121
122
123    final int nvar;
124
125
126    /**
127     * ExpVector iterator constructor.
128     * @param nv number of variables.
129     */
130    public ExpVectorIterator(int nv) {
131        this(nv,true,Long.MAX_VALUE);
132    }
133
134
135    /**
136     * ExpVector iterator constructor.
137     * @param nv number of variables.
138     * @param ub upper bound for the components.
139     */
140    public ExpVectorIterator(int nv,long ub) {
141        this(nv,false,ub);
142    }
143
144
145    /**
146     * ExpVector iterator constructor.
147     * @param nv number of variables.
148     * @param inf true, if all elements between 0 and upper bound are enumerated, 
149                  false, if only elements of exact upper bund are to be processed.
150     * @param ub an upper bound for the entries.
151     */
152    protected ExpVectorIterator(int nv, boolean inf, long ub) {
153        infinite = inf; 
154        upperBound = ub;
155        if (upperBound < 0L) {
156            throw new IllegalArgumentException("negative upper bound not allowed");
157        }
158        totalDegree = 0;
159        if ( !infinite ) {
160            totalDegree = (int)upperBound;
161        }
162        //System.out.println("totalDegree = " + totalDegree + ", upperBound = " + upperBound);
163        LongIterable li = new LongIterable();
164        li.setNonNegativeIterator();
165        li.setUpperBound(totalDegree);
166        List<LongIterable> tlist = new ArrayList<LongIterable>(nv);
167        for (int i = 0; i < nv; i++) {
168            tlist.add(li); // can reuse li
169        }
170        Iterable<List<Long>> ib = new CartesianProductLong(tlist,totalDegree);
171        liter = ib.iterator();
172        empty = (totalDegree > upperBound) || !liter.hasNext();
173        current = ExpVector.create(nv);
174        if ( !empty ) {
175            List<Long> el = liter.next();
176            current = ExpVector.create(el);
177            //System.out.println("current = " + current);
178        }
179        nvar = nv;
180    }
181
182
183    /**
184     * Test for availability of a next long.
185     * @return true if the iteration has more ExpVectors, else false.
186     */
187    public synchronized boolean hasNext() {
188        return !empty;
189    }
190
191
192    /**
193     * Get next ExpVector.
194     * @return next ExpVector.
195     */
196    public synchronized ExpVector next() {
197        ExpVector res = current;
198        if ( liter.hasNext() ) {
199            List<Long> el = liter.next();
200            current = ExpVector.create(el);
201            //System.out.println("current, liter = " + current);
202            return res;
203        } 
204        if ( totalDegree >= upperBound ) {
205            empty = true;
206            return res;
207        }
208        totalDegree++;
209        //System.out.println("totalDegree,b = " + totalDegree);
210        if ( totalDegree >= upperBound && !infinite ) {
211            throw new NoSuchElementException("invalid call of next()");
212        }
213        LongIterable li = new LongIterable();
214        li.setNonNegativeIterator();
215        li.setUpperBound(totalDegree);
216        List<LongIterable> tlist = new ArrayList<LongIterable>(nvar);
217        for (int i = 0; i < nvar; i++) {
218            tlist.add(li); // can reuse li
219        }
220        Iterable<List<Long>> ib = new CartesianProductLong(tlist,totalDegree);
221        liter = ib.iterator();
222        List<Long> el = liter.next();
223        current = ExpVector.create(el);
224        return res;
225    }
226
227
228    /**
229     * Remove a tuple if allowed.
230     */
231    public void remove() {
232        throw new UnsupportedOperationException("cannot remove elements");
233    }
234
235}