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 < 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 <= upperbound 299 * and lowerBound < 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}