1 /*
2 * Copyright (c) 2000, 2014, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26
27 package javax.print.attribute;
28
29 import java.io.Serializable;
30 import java.util.Vector;
31
32 /**
33 * Class SetOfIntegerSyntax is an abstract base class providing the common
34 * implementation of all attributes whose value is a set of nonnegative
35 * integers. This includes attributes whose value is a single range of integers
36 * and attributes whose value is a set of ranges of integers.
37 * <P>
38 * You can construct an instance of SetOfIntegerSyntax by giving it in "string
39 * form." The string consists of zero or more comma-separated integer groups.
40 * Each integer group consists of either one integer, two integers separated by
41 * a hyphen ({@code -}), or two integers separated by a colon
42 * ({@code :}). Each integer consists of one or more decimal digits
43 * ({@code 0} through {@code 9}). Whitespace characters cannot
44 * appear within an integer but are otherwise ignored. For example:
45 * {@code ""}, {@code "1"}, {@code "5-10"}, {@code "1:2, 4"}.
46 * <P>
47 * You can also construct an instance of SetOfIntegerSyntax by giving it in
48 * "array form." Array form consists of an array of zero or more integer groups
49 * where each integer group is a length-1 or length-2 array of
50 * {@code int}s; for example, {@code int[0][]},
51 * {@code int[][]{{1}}}, {@code int[][]{{5,10}}},
52 * {@code int[][]{{1,2},{4}}}.
53 * <P>
54 * In both string form and array form, each successive integer group gives a
55 * range of integers to be included in the set. The first integer in each group
56 * gives the lower bound of the range; the second integer in each group gives
57 * the upper bound of the range; if there is only one integer in the group, the
58 * upper bound is the same as the lower bound. If the upper bound is less than
59 * the lower bound, it denotes a null range (no values). If the upper bound is
60 * equal to the lower bound, it denotes a range consisting of a single value. If
61 * the upper bound is greater than the lower bound, it denotes a range
62 * consisting of more than one value. The ranges may appear in any order and are
63 * allowed to overlap. The union of all the ranges gives the set's contents.
64 * Once a SetOfIntegerSyntax instance is constructed, its value is immutable.
65 * <P>
66 * The SetOfIntegerSyntax object's value is actually stored in "<I>canonical</I>
67 * array form." This is the same as array form, except there are no null ranges;
68 * the members of the set are represented in as few ranges as possible (i.e.,
69 * overlapping ranges are coalesced); the ranges appear in ascending order; and
70 * each range is always represented as a length-two array of {@code int}s
71 * in the form {lower bound, upper bound}. An empty set is represented as a
72 * zero-length array.
73 * <P>
74 * Class SetOfIntegerSyntax has operations to return the set's members in
75 * canonical array form, to test whether a given integer is a member of the
76 * set, and to iterate through the members of the set.
77 *
78 * @author David Mendenhall
79 * @author Alan Kaminsky
80 */
81 public abstract class SetOfIntegerSyntax implements Serializable, Cloneable {
82
83 private static final long serialVersionUID = 3666874174847632203L;
84
85 /**
86 * This set's members in canonical array form.
87 * @serial
88 */
89 private int[][] members;
90
91
92 /**
93 * Construct a new set-of-integer attribute with the given members in
94 * string form.
95 *
96 * @param members Set members in string form. If null, an empty set is
97 * constructed.
98 *
99 * @exception IllegalArgumentException
100 * (Unchecked exception) Thrown if {@code members} does not
101 * obey the proper syntax.
102 */
103 protected SetOfIntegerSyntax(String members) {
104 this.members = parse (members);
105 }
106
107 /**
108 * Parse the given string, returning canonical array form.
109 */
110 private static int[][] parse(String members) {
111 // Create vector to hold int[] elements, each element being one range
112 // parsed out of members.
113 Vector<int[]> theRanges = new Vector<>();
114
115 // Run state machine over members.
116 int n = (members == null ? 0 : members.length());
117 int i = 0;
118 int state = 0;
119 int lb = 0;
120 int ub = 0;
121 char c;
122 int digit;
123 while (i < n) {
124 c = members.charAt(i ++);
125 switch (state) {
126
127 case 0: // Before first integer in first group
128 if (Character.isWhitespace(c)) {
129 state = 0;
130 }
131 else if ((digit = Character.digit(c, 10)) != -1) {
132 lb = digit;
133 state = 1;
134 } else {
135 throw new IllegalArgumentException();
136 }
137 break;
138
139 case 1: // In first integer in a group
140 if (Character.isWhitespace(c)){
141 state = 2;
142 } else if ((digit = Character.digit(c, 10)) != -1) {
143 lb = 10 * lb + digit;
144 state = 1;
145 } else if (c == '-' || c == ':') {
146 state = 3;
147 } else if (c == ',') {
148 accumulate (theRanges, lb, lb);
149 state = 6;
150 } else {
151 throw new IllegalArgumentException();
152 }
153 break;
154
155 case 2: // After first integer in a group
156 if (Character.isWhitespace(c)) {
157 state = 2;
158 }
159 else if (c == '-' || c == ':') {
160 state = 3;
161 }
162 else if (c == ',') {
163 accumulate(theRanges, lb, lb);
164 state = 6;
165 } else {
166 throw new IllegalArgumentException();
167 }
168 break;
169
170 case 3: // Before second integer in a group
171 if (Character.isWhitespace(c)) {
172 state = 3;
173 } else if ((digit = Character.digit(c, 10)) != -1) {
174 ub = digit;
175 state = 4;
176 } else {
177 throw new IllegalArgumentException();
178 }
179 break;
180
181 case 4: // In second integer in a group
182 if (Character.isWhitespace(c)) {
183 state = 5;
184 } else if ((digit = Character.digit(c, 10)) != -1) {
185 ub = 10 * ub + digit;
186 state = 4;
187 } else if (c == ',') {
188 accumulate(theRanges, lb, ub);
189 state = 6;
190 } else {
191 throw new IllegalArgumentException();
192 }
193 break;
194
195 case 5: // After second integer in a group
196 if (Character.isWhitespace(c)) {
197 state = 5;
198 } else if (c == ',') {
199 accumulate(theRanges, lb, ub);
200 state = 6;
201 } else {
202 throw new IllegalArgumentException();
203 }
204 break;
205
206 case 6: // Before first integer in second or later group
207 if (Character.isWhitespace(c)) {
208 state = 6;
209 } else if ((digit = Character.digit(c, 10)) != -1) {
210 lb = digit;
211 state = 1;
212 } else {
213 throw new IllegalArgumentException();
214 }
215 break;
216 }
217 }
218
219 // Finish off the state machine.
220 switch (state) {
221 case 0: // Before first integer in first group
222 break;
223 case 1: // In first integer in a group
224 case 2: // After first integer in a group
225 accumulate(theRanges, lb, lb);
226 break;
227 case 4: // In second integer in a group
228 case 5: // After second integer in a group
229 accumulate(theRanges, lb, ub);
230 break;
231 case 3: // Before second integer in a group
232 case 6: // Before first integer in second or later group
233 throw new IllegalArgumentException();
234 }
235
236 // Return canonical array form.
237 return canonicalArrayForm (theRanges);
238 }
239
240 /**
241 * Accumulate the given range (lb .. ub) into the canonical array form
242 * into the given vector of int[] objects.
243 */
244 private static void accumulate(Vector<int[]> ranges, int lb,int ub) {
245 // Make sure range is non-null.
246 if (lb <= ub) {
247 // Stick range at the back of the vector.
248 ranges.add(new int[] {lb, ub});
249
250 // Work towards the front of the vector to integrate the new range
251 // with the existing ranges.
252 for (int j = ranges.size()-2; j >= 0; -- j) {
253 // Get lower and upper bounds of the two ranges being compared.
254 int[] rangea = ranges.elementAt (j);
255 int lba = rangea[0];
256 int uba = rangea[1];
257 int[] rangeb = ranges.elementAt (j+1);
258 int lbb = rangeb[0];
259 int ubb = rangeb[1];
260
261 /* If the two ranges overlap or are adjacent, coalesce them.
262 * The two ranges overlap if the larger lower bound is less
263 * than or equal to the smaller upper bound. The two ranges
264 * are adjacent if the larger lower bound is one greater
265 * than the smaller upper bound.
266 */
267 if (Math.max(lba, lbb) - Math.min(uba, ubb) <= 1) {
268 // The coalesced range is from the smaller lower bound to
269 // the larger upper bound.
270 ranges.setElementAt(new int[]
271 {Math.min(lba, lbb),
272 Math.max(uba, ubb)}, j);
273 ranges.remove (j+1);
274 } else if (lba > lbb) {
275
276 /* If the two ranges don't overlap and aren't adjacent but
277 * are out of order, swap them.
278 */
279 ranges.setElementAt (rangeb, j);
280 ranges.setElementAt (rangea, j+1);
281 } else {
282 /* If the two ranges don't overlap and aren't adjacent and
283 * aren't out of order, we're done early.
284 */
285 break;
286 }
287 }
288 }
289 }
290
291 /**
292 * Convert the given vector of int[] objects to canonical array form.
293 */
294 private static int[][] canonicalArrayForm(Vector<int[]> ranges) {
295 return ranges.toArray (new int[ranges.size()][]);
296 }
297
298 /**
299 * Construct a new set-of-integer attribute with the given members in
300 * array form.
301 *
302 * @param members Set members in array form. If null, an empty set is
303 * constructed.
304 *
305 * @exception NullPointerException
306 * (Unchecked exception) Thrown if any element of
307 * {@code members} is null.
308 * @exception IllegalArgumentException
309 * (Unchecked exception) Thrown if any element of
310 * {@code members} is not a length-one or length-two array or if
311 * any non-null range in {@code members} has a lower bound less
312 * than zero.
313 */
314 protected SetOfIntegerSyntax(int[][] members) {
315 this.members = parse (members);
316 }
317
318 /**
319 * Parse the given array form, returning canonical array form.
320 */
321 private static int[][] parse(int[][] members) {
322 // Create vector to hold int[] elements, each element being one range
323 // parsed out of members.
324 Vector<int[]> ranges = new Vector<>();
325
326 // Process all integer groups in members.
327 int n = (members == null ? 0 : members.length);
328 for (int i = 0; i < n; ++ i) {
329 // Get lower and upper bounds of the range.
330 int lb, ub;
331 if (members[i].length == 1) {
332 lb = ub = members[i][0];
333 } else if (members[i].length == 2) {
334 lb = members[i][0];
335 ub = members[i][1];
336 } else {
337 throw new IllegalArgumentException();
338 }
339
340 // Verify valid bounds.
341 if (lb <= ub && lb < 0) {
342 throw new IllegalArgumentException();
343 }
344
345 // Accumulate the range.
346 accumulate(ranges, lb, ub);
347 }
348
349 // Return canonical array form.
350 return canonicalArrayForm (ranges);
351 }
352
353 /**
354 * Construct a new set-of-integer attribute containing a single integer.
355 *
356 * @param member Set member.
357 *
358 * @exception IllegalArgumentException
359 * (Unchecked exception) Thrown if {@code member} is less than
360 * zero.
361 */
362 protected SetOfIntegerSyntax(int member) {
363 if (member < 0) {
364 throw new IllegalArgumentException();
365 }
366 members = new int[][] {{member, member}};
367 }
368
369 /**
370 * Construct a new set-of-integer attribute containing a single range of
371 * integers. If the lower bound is greater than the upper bound (a null
372 * range), an empty set is constructed.
373 *
374 * @param lowerBound Lower bound of the range.
375 * @param upperBound Upper bound of the range.
376 *
377 * @exception IllegalArgumentException
378 * (Unchecked exception) Thrown if the range is non-null and
379 * {@code lowerBound} is less than zero.
380 */
381 protected SetOfIntegerSyntax(int lowerBound, int upperBound) {
382 if (lowerBound <= upperBound && lowerBound < 0) {
383 throw new IllegalArgumentException();
384 }
385 members = lowerBound <=upperBound ?
386 new int[][] {{lowerBound, upperBound}} :
387 new int[0][];
388 }
389
390
391 /**
392 * Obtain this set-of-integer attribute's members in canonical array form.
393 * The returned array is "safe;" the client may alter it without affecting
394 * this set-of-integer attribute.
395 *
396 * @return This set-of-integer attribute's members in canonical array form.
397 */
398 public int[][] getMembers() {
399 int n = members.length;
400 int[][] result = new int[n][];
401 for (int i = 0; i < n; ++ i) {
402 result[i] = new int[] {members[i][0], members[i][1]};
403 }
404 return result;
405 }
406
407 /**
408 * Determine if this set-of-integer attribute contains the given value.
409 *
410 * @param x Integer value.
411 *
412 * @return True if this set-of-integer attribute contains the value
413 * {@code x}, false otherwise.
414 */
415 public boolean contains(int x) {
416 // Do a linear search to find the range that contains x, if any.
417 int n = members.length;
418 for (int i = 0; i < n; ++ i) {
419 if (x < members[i][0]) {
420 return false;
421 } else if (x <= members[i][1]) {
422 return true;
423 }
424 }
425 return false;
426 }
427
428 /**
429 * Determine if this set-of-integer attribute contains the given integer
430 * attribute's value.
431 *
432 * @param attribute Integer attribute.
433 *
434 * @return True if this set-of-integer attribute contains
435 * {@code theAttribute}'s value, false otherwise.
436 */
437 public boolean contains(IntegerSyntax attribute) {
438 return contains (attribute.getValue());
439 }
440
441 /**
442 * Determine the smallest integer in this set-of-integer attribute that is
443 * greater than the given value. If there are no integers in this
444 * set-of-integer attribute greater than the given value, {@code -1} is
445 * returned. (Since a set-of-integer attribute can only contain nonnegative
446 * values, {@code -1} will never appear in the set.) You can use the
447 * {@code next()} method to iterate through the integer values in a
448 * set-of-integer attribute in ascending order, like this:
449 * <PRE>
450 * SetOfIntegerSyntax attribute = . . .;
451 * int i = -1;
452 * while ((i = attribute.next (i)) != -1)
453 * {
454 * foo (i);
455 * }
456 * </PRE>
457 *
458 * @param x Integer value.
459 *
460 * @return The smallest integer in this set-of-integer attribute that is
461 * greater than {@code x}, or {@code -1} if no integer in
462 * this set-of-integer attribute is greater than {@code x}.
463 */
464 public int next(int x) {
465 // Do a linear search to find the range that contains x, if any.
466 int n = members.length;
467 for (int i = 0; i < n; ++ i) {
468 if (x < members[i][0]) {
469 return members[i][0];
470 } else if (x < members[i][1]) {
471 return x + 1;
472 }
473 }
474 return -1;
475 }
476
477 /**
478 * Returns whether this set-of-integer attribute is equivalent to the passed
479 * in object. To be equivalent, all of the following conditions must be
480 * true:
481 * <OL TYPE=1>
482 * <LI>
483 * {@code object} is not null.
484 * <LI>
485 * {@code object} is an instance of class SetOfIntegerSyntax.
486 * <LI>
487 * This set-of-integer attribute's members and {@code object}'s
488 * members are the same.
489 * </OL>
490 *
491 * @param object Object to compare to.
492 *
493 * @return True if {@code object} is equivalent to this
494 * set-of-integer attribute, false otherwise.
495 */
496 public boolean equals(Object object) {
497 if (object != null && object instanceof SetOfIntegerSyntax) {
498 int[][] myMembers = this.members;
499 int[][] otherMembers = ((SetOfIntegerSyntax) object).members;
500 int m = myMembers.length;
501 int n = otherMembers.length;
502 if (m == n) {
503 for (int i = 0; i < m; ++ i) {
504 if (myMembers[i][0] != otherMembers[i][0] ||
505 myMembers[i][1] != otherMembers[i][1]) {
506 return false;
507 }
508 }
509 return true;
510 } else {
511 return false;
512 }
513 } else {
514 return false;
515 }
516 }
517
518 /**
519 * Returns a hash code value for this set-of-integer attribute. The hash
520 * code is the sum of the lower and upper bounds of the ranges in the
521 * canonical array form, or 0 for an empty set.
522 */
523 public int hashCode() {
524 int result = 0;
525 int n = members.length;
526 for (int i = 0; i < n; ++ i) {
527 result += members[i][0] + members[i][1];
528 }
529 return result;
530 }
531
532 /**
533 * Returns a string value corresponding to this set-of-integer attribute.
534 * The string value is a zero-length string if this set is empty. Otherwise,
535 * the string value is a comma-separated list of the ranges in the canonical
536 * array form, where each range is represented as <code>"<I>i</I>"</code> if
537 * the lower bound equals the upper bound or
538 * <code>"<I>i</I>-<I>j</I>"</code> otherwise.
539 */
540 public String toString() {
541 StringBuilder result = new StringBuilder();
542 int n = members.length;
543 for (int i = 0; i < n; i++) {
544 if (i > 0) {
545 result.append (',');
546 }
547 result.append (members[i][0]);
548 if (members[i][0] != members[i][1]) {
549 result.append ('-');
550 result.append (members[i][1]);
551 }
552 }
553 return result.toString();
554 }
555
556 }