001/* SetOfIntegerSyntax.java --
002   Copyright (C) 2003, 2004, 2005  Free Software Foundation, Inc.
003
004This file is part of GNU Classpath.
005
006GNU Classpath is free software; you can redistribute it and/or modify
007it under the terms of the GNU General Public License as published by
008the Free Software Foundation; either version 2, or (at your option)
009any later version.
010
011GNU Classpath is distributed in the hope that it will be useful, but
012WITHOUT ANY WARRANTY; without even the implied warranty of
013MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014General Public License for more details.
015
016You should have received a copy of the GNU General Public License
017along with GNU Classpath; see the file COPYING.  If not, write to the
018Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
01902110-1301 USA.
020
021Linking this library statically or dynamically with other modules is
022making a combined work based on this library.  Thus, the terms and
023conditions of the GNU General Public License cover the whole
024combination.
025
026As a special exception, the copyright holders of this library give you
027permission to link this library with independent modules to produce an
028executable, regardless of the license terms of these independent
029modules, and to copy and distribute the resulting executable under
030terms of your choice, provided that you also meet, for each linked
031independent module, the terms and conditions of the license of that
032module.  An independent module is a module which is not derived from
033or based on this library.  If you modify this library, you may extend
034this exception to your version of the library, but you are not
035obligated to do so.  If you do not wish to do so, delete this
036exception statement from your version. */
037
038package javax.print.attribute;
039
040import java.io.Serializable;
041import java.text.CharacterIterator;
042import java.text.StringCharacterIterator;
043import java.util.ArrayList;
044import java.util.Arrays;
045import java.util.Comparator;
046
047/**
048 * <code>SetOfIntegerSyntax</code> is the abstract base class of all attribute
049 * classes which provide a set of non-negative integers as value (e.g. the
050 * page ranges to print) represented as single values or ranges of values.
051 * <p>
052 * A <code>SetOfIntegerSyntax</code> instance consists of an integer array of
053 * ranges. Ranges may have the same lower and upper bound representing a single
054 * integer value. Ranges with a lower bound greater than the upper bound are
055 * null ranges and discarded. Ranges may overlap in their values. In no case
056 * negative integers are allowed.
057 * </p>
058 * <p>
059 * There are several constructors available:
060 * <ul>
061 * <li><code>SetOfIntegerSyntax(int member)</code><br>
062 * Constructor for an instance with only one integer value.
063 * </li><br>
064 * <li><code>SetOfIntegerSyntax(int lowerBound, int upperBound)</code><br>
065 * Constructor for an instance with one range of integer values.
066 * </li><br>
067 * <li><code>SetOfIntegerSyntax(int[][] members)</code><br>
068 * Flexible constructor for an instance with several single integer values
069 * and/or several ranges of integer values. The allowed array form is an
070 * array of integer arrays of length one or two. Examples are:
071 * <code>int[0][]</code> for empty set of integers, <code>int[][] {{1}}</code>
072 * , <code>int[][] {{1,5}}</code>, <code>int[][] {{1,5},{7,9}}</code>,
073 * <code>int[][] {{3,7},{19}}</code>.
074 * </li><br>
075 * <li><code>SetOfIntegerSyntax(String s)</code><br>
076 * Flexible constructor for an instance with several single integer values
077 * and/or several ranges of integer values. The allowed String instance have
078 * to be a String with comma separated ranges of integer values or single
079 * values. Ranges are represented by two integer with a hypen (-) or colon (:)
080 * between the lower and upper bound value. Whitespace characters are ignored.
081 * Examples are: <code>""</code> for an empty set of integers,
082 * <code>"1"</code>, <code>"1-5"</code>, <code>"1-5,7-9"</code>,
083 * <code>"3-7,19"</code> and <code>"1:2,4"</code>.
084 * </li>
085 * </ul>
086 * </p>
087 * <p>
088 * <b>Internal storage:</b><br>
089 * The set of integers are stored internally in a normalized array form.
090 * In the normalized array form the set of integer ranges are represented
091 * in as few ranges as possible and overlapping ranges are merged. The ranges
092 * are always represented as an integer array of length two with ranges
093 * stored in {lower bound, upper bound} form. The ranges are stored in
094 * ascending order, without any null ranges.
095 * </p>
096 * @author Michael Koch (konqueror@gmx.de)
097 */
098public abstract class SetOfIntegerSyntax
099  implements Cloneable, Serializable
100{
101  private static final long serialVersionUID = 3666874174847632203L;
102
103  private int[][] members;
104
105  private static int[][] normalize(int[][] values, int size)
106  {
107    // Sort into increasing order.  First the first index is
108    // compared, then the second.
109    Arrays.sort(values, 0, size, new Comparator()
110                {
111                  public int compare(Object o1, Object o2)
112                  {
113                    int[] v1 = (int[]) o1;
114                    int[] v2 = (int[]) o2;
115                    if (v1[0] == v2[0])
116                      return v1[1] - v2[1];
117                    return v1[0] - v2[0];
118                  }
119                });
120
121    // Now coalesce overlapping ranges.
122    int outIndex = 0;
123    for (int i = 0; i < size; ++i)
124      {
125        // Note that we compare with values[i][1]+1, since
126        // we can coalesce {0,1} with {2,x}.
127        int save = i;
128        while (i + 1 < size && values[i + 1][0] <= values[i][1] + 1)
129          {
130            values[i][1] = Math.max(values[i][1], values[i + 1][1]);
131            ++i;
132          }
133        values[outIndex++] = values[save];
134      }
135
136    int[][] result = new int[outIndex][];
137    System.arraycopy(values, 0, result, 0, outIndex);
138
139    return result;
140  }
141
142  /**
143   * Creates a <code>SetOfIntegerSyntax</code> object.
144   *
145   * @param member the member value
146   *
147   * @exception IllegalArgumentException if member is &lt; 0
148   */
149  protected SetOfIntegerSyntax(int member)
150  {
151    if (member < 0)
152      throw new IllegalArgumentException("member may not be less than 0");
153
154    this.members = new int[][]{{member, member}};
155  }
156
157  /**
158   * Creates a <code>SetOfIntegerSyntax</code> object.
159   *
160   * @param members the members to use in this set. If
161   * <code>null</code> an empty set is created.
162   *
163   * @exception IllegalArgumentException if any element is invalid
164   * @exception NullPointerException if any element of members is null
165   */
166  protected SetOfIntegerSyntax(int[][] members)
167  {
168    int[][] newMembers;
169    int outIndex = 0;
170    if (members == null)
171      newMembers = new int[0][];
172    else
173      {
174        newMembers = new int[members.length][];
175        for (int index = 0; index < members.length; index++)
176          {
177            int lower;
178            int upper;
179
180            if (members[index].length == 1)
181              {
182                lower = members[index][0];
183                upper = members[index][0];
184              }
185            else if (members[index].length == 2)
186              {
187                lower = members[index][0];
188                upper = members[index][1];
189              }
190            else
191              throw new IllegalArgumentException("invalid member element");
192
193            // We only want to reject non-null ranges where lower<0.
194            if (lower <= upper && lower < 0)
195              throw new IllegalArgumentException("invalid member element");
196
197            if (lower <= upper)
198              {
199                int[] range = new int[2];
200                range[0] = lower;
201                range[1] = upper;
202                newMembers[outIndex++] = range;
203              }
204          }
205      }
206
207    this.members = normalize(newMembers, outIndex);
208  }
209
210  private boolean skipWhitespace(StringCharacterIterator i)
211  {
212    while (Character.isWhitespace(i.current()))
213      i.next();
214    return i.current() == CharacterIterator.DONE;
215  }
216
217  private boolean skipNumber(StringCharacterIterator i)
218  {
219    boolean readAny = false;
220    while (Character.isDigit(i.current()))
221      {
222        readAny = true;
223        i.next();
224      }
225    return readAny;
226  }
227
228  /**
229   * Creates a <code>SetOfIntegerSyntax</code> object.
230   *
231   * @param s the members to use in this set in string form. If
232   * <code>null</code> an empty set is created.
233   *
234   * @exception IllegalArgumentException if any element is invalid
235   */
236  protected SetOfIntegerSyntax(String s)
237  {
238    if (s == null)
239      this.members = normalize(new int[0][], 0);
240    else
241      {
242        ArrayList vals = new ArrayList();
243
244        StringCharacterIterator it = new StringCharacterIterator(s);
245
246        while (true)
247          {
248            // Skip whitespace.
249            if (skipWhitespace(it))
250              break;
251
252            // Parse integer.
253            int index = it.getIndex();
254            if (! skipNumber(it))
255              throw new IllegalArgumentException();
256            int[] item = new int[2];
257            item[0] = Integer.parseInt(s.substring(index, it.getIndex()));
258
259            if (! skipWhitespace(it))
260              {
261                char c = it.current();
262                if (c == ':' || c == '-')
263                  {
264                  it.next();
265                  if (skipWhitespace(it))
266                    throw new IllegalArgumentException();
267                  index = it.getIndex();
268                  if (! skipNumber(it))
269                    throw new IllegalArgumentException();
270                  item[1] = Integer.parseInt(s.substring(index, it.getIndex()));
271                  }
272                else
273                  item[1] = item[0];
274              }
275            else
276              item[1] = item[0];
277
278            if (item[0] <= item[1])
279              vals.add(item);
280
281            if (skipWhitespace(it))
282              break;
283            if (it.current() != ',')
284              throw new IllegalArgumentException();
285            it.next();
286          }
287
288        members = normalize((int[][]) vals.toArray(new int[0][]), vals.size());
289      }
290  }
291
292  /**
293   * Creates a <code>SetOfIntegerSyntax</code> object.
294   *
295   * @param lowerBound the lower bound value
296   * @param upperBound the upper bound value
297   *
298   * @exception IllegalArgumentException if lowerBound &lt;= upperbound
299   * and lowerBound &lt; 0
300   */
301  protected SetOfIntegerSyntax(int lowerBound, int upperBound)
302  {
303    // We only want to reject non-null ranges where lower<0.
304    if (lowerBound <= upperBound
305        && lowerBound < 0)
306      throw new IllegalArgumentException();
307
308    members = (lowerBound <= upperBound ? new int[][]{{lowerBound, upperBound}}
309                                        : new int[0][]);
310  }
311
312  /**
313   * Checks if this set contains the given value.
314   *
315   * @param value the value to test for
316   *
317   * @return true if this set contains value, false otherwise
318   */
319  public boolean contains(int value)
320  {
321    // This only works on a normalized member array.
322    for (int index = 0; index < members.length; index++)
323      {
324        if (value < members[index][0])
325          return false;
326        else if (value <= members[index][1])
327          return true;
328      }
329
330    return false;
331  }
332
333  /**
334   * Checks if this set contains the given value.
335   *
336   * @param value the value to test for
337   *
338   * @return true if this set contains value, false otherwise
339   */
340  public boolean contains(IntegerSyntax value)
341  {
342    return contains(value.getValue());
343  }
344
345  /**
346   * Tests if the given object is equal to this object.
347   *
348   * @param obj the object to test
349   *
350   * @return true if both objects are equal, false otherwise.
351   */
352  public boolean equals(Object obj)
353  {
354    if (! (obj instanceof SetOfIntegerSyntax))
355      return false;
356    SetOfIntegerSyntax other = (SetOfIntegerSyntax) obj;
357    if (other.members.length != members.length)
358      return false;
359    for (int i = 0; i < members.length; ++i)
360      {
361        if (members[i][0] != other.members[i][0]
362            || members[i][1] != other.members[i][1])
363          return false;
364      }
365    return true;
366  }
367
368  /**
369   * Returns an array describing the members included in this set.
370   *
371   * @return The members in normalized array form.
372   */
373  public int[][] getMembers()
374  {
375    return (int[][]) members.clone();
376  }
377
378  /**
379   * Returns the hashcode for this object.
380   *
381   * @return The hashcode.
382   */
383  public int hashCode()
384  {
385    int result = 0;
386    for (int i = 0; i < members.length; ++i)
387      result += members[i][0] + members[i][1];
388    return result;
389  }
390
391  /**
392   * Returns the smallest value that is greater than x which is in this set.
393   *
394   * @param x an integer value
395   *
396   * @return The next smallest integer value, or <code>-1</code> if there
397   * is no greater integer in the set.
398   */
399  public int next(int x)
400  {
401    for (int i = 0; i < members.length; ++i)
402      {
403        if (x >= members[i][1])
404          continue;
405        if (x < members[i][0])
406          return members[i][0];
407        // X is in this range.
408        return x + 1;
409      }
410    return -1;
411  }
412
413  /**
414   * Returns the string representation for this object.
415   * The value is a zero length string for an empty set, or a comma seperated
416   * list of ranges and single values in the form <code>"1-2,5-7,10"</code>.
417   *
418   * @return The string representation.
419   */
420  public String toString()
421  {
422    StringBuilder sb = new StringBuilder();
423    for (int i = 0; i < members.length; ++i)
424      {
425        if (i > 0)
426          sb.append(',');
427        sb.append(members[i][0]);
428        if (members[i][0] != members[i][1])
429          {
430            sb.append('-');
431            sb.append(members[i][1]);
432          }
433      }
434    return sb.toString();
435  }
436}