libjava/classpath/javax/print/attribute/SetOfIntegerSyntax.java

   1 /* SetOfIntegerSyntax.java --
   2    Copyright (C) 2003, 2004, 2005  Free Software Foundation, Inc.
   3
   4 This file is part of GNU Classpath.
   5
   6 GNU Classpath is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU Classpath is distributed in the hope that it will be useful, but
  12 WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU Classpath; see the file COPYING.  If not, write to the
  18 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301 USA.
  20
  21 Linking this library statically or dynamically with other modules is
  22 making a combined work based on this library.  Thus, the terms and
  23 conditions of the GNU General Public License cover the whole
  24 combination.
  25
  26 As a special exception, the copyright holders of this library give you
  27 permission to link this library with independent modules to produce an
  28 executable, regardless of the license terms of these independent
  29 modules, and to copy and distribute the resulting executable under
  30 terms of your choice, provided that you also meet, for each linked
  31 independent module, the terms and conditions of the license of that
  32 module.  An independent module is a module which is not derived from
  33 or based on this library.  If you modify this library, you may extend
  34 this exception to your version of the library, but you are not
  35 obligated to do so.  If you do not wish to do so, delete this
  36 exception statement from your version. */
  37
  38 package javax.print.attribute;
  39
  40 import java.io.Serializable;
  41 import java.text.CharacterIterator;
  42 import java.text.StringCharacterIterator;
  43 import java.util.ArrayList;
  44 import java.util.Arrays;
  45 import java.util.Comparator;
  46
  47 /**
  48  * <code>SetOfIntegerSyntax</code> is the abstract base class of all attribute
  49  * classes which provide a set of non-negative integers as value (e.g. the
  50  * page ranges to print) represented as single values or ranges of values.
  51  * <p>
  52  * A <code>SetOfIntegerSyntax</code> instance consists of an integer array of
  53  * ranges. Ranges may have the same lower and upper bound representing a single
  54  * integer value. Ranges with a lower bound greater than the upper bound are
  55  * null ranges and discarded. Ranges may overlap in their values. In no case
  56  * negative integers are allowed.
  57  * </p>
  58  * <p>
  59  * There are several constructors available:
  60  * <ul>
  61  * <li><code>SetOfIntegerSyntax(int member)</code><br>
  62  * Constructor for an instance with only one integer value.
  63  * </li><br>
  64  * <li><code>SetOfIntegerSyntax(int lowerBound, int upperBound)</code><br>
  65  * Constructor for an instance with one range of integer values.
  66  * </li><br>
  67  * <li><code>SetOfIntegerSyntax(int[][] members)</code><br>
  68  * Flexible constructor for an instance with several single integer values
  69  * and/or several ranges of integer values. The allowed array form is an
  70  * array of integer arrays of length one or two. Examples are:
  71  * <code>int[0][]</code> for empty set of integers, <code>int[][] {{1}}</code>
  72  * , <code>int[][] {{1,5}}</code>, <code>int[][] {{1,5},{7,9}}</code>,
  73  * <code>int[][] {{3,7},{19}}</code>.
  74  * </li><br>
  75  * <li><code>SetOfIntegerSyntax(String s)</code><br>
  76  * Flexible constructor for an instance with several single integer values
  77  * and/or several ranges of integer values. The allowed String instance have
  78  * to be a String with comma separated ranges of integer values or single
  79  * values. Ranges are represented by two integer with a hypen (-) or colon (:)
  80  * between the lower and upper bound value. Whitespace characters are ignored.
  81  * Examples are: <code>""</code> for an empty set of integers,
  82  * <code>"1"</code>, <code>"1-5"</code>, <code>"1-5,7-9"</code>,
  83  * <code>"3-7,19"</code> and <code>"1:2,4"</code>.
  84  * </li>
  85  * </ul>
  86  * </p>
  87  * <p>
  88  * <b>Internal storage:</b><br>
  89  * The set of integers are stored internally in a normalized array form.
  90  * In the normalized array form the set of integer ranges are represented
  91  * in as few ranges as possible and overlapping ranges are merged. The ranges
  92  * are always represented as an integer array of length two with ranges
  93  * stored in {lower bound, upper bound} form. The ranges are stored in
  94  * ascending order, without any null ranges.
  95  * </p>
  96  * @author Michael Koch (konqueror@gmx.de)
  97  */
  98 public abstract class SetOfIntegerSyntax
  99   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 }