1 /*
2 * Copyright (c) 2000, 2017, 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 package javax.print.attribute;
27
28 import java.io.Serializable;
29 import java.util.Vector;
30
31 /**
32 * Class {@code SetOfIntegerSyntax} is an abstract base class providing the
33 * common implementation of all attributes whose value is a set of nonnegative
34 * integers. This includes attributes whose value is a single range of integers
35 * and attributes whose value is a set of ranges of integers.
36 * <p>
37 * You can construct an instance of {@code SetOfIntegerSyntax} by giving it in
38 * "string form." The string consists of zero or more comma-separated integer
39 * groups. Each integer group consists of either one integer, two integers
40 * separated by a hyphen ({@code -}), or two integers separated by a colon
41 * ({@code :}). Each integer consists of one or more decimal digits ({@code 0}
42 * through {@code 9}). Whitespace characters cannot appear within an integer but
43 * are otherwise ignored. For example: {@code ""}, {@code "1"}, {@code "5-10"},
44 * {@code "1:2, 4"}.
45 * <p>
46 * You can also construct an instance of {@code SetOfIntegerSyntax} by giving it
47 * in "array form." Array form consists of an array of zero or more integer
48 * groups where each integer group is a length-1 or length-2 array of
49 * {@code int}s; for example, {@code int[0][]}, {@code int[][]{{1}}},
50 * {@code int[][]{{5,10}}}, {@code int[][]{{1,2},{4}}}.
51 * <p>
52 * In both string form and array form, each successive integer group gives a
53 * range of integers to be included in the set. The first integer in each group
54 * gives the lower bound of the range; the second integer in each group gives
55 * the upper bound of the range; if there is only one integer in the group, the
56 * upper bound is the same as the lower bound. If the upper bound is less than
57 * the lower bound, it denotes a {@code null} range (no values). If the upper
58 * bound is equal to the lower bound, it denotes a range consisting of a single
59 * value. If the upper bound is greater than the lower bound, it denotes a range
60 * consisting of more than one value. The ranges may appear in any order and are
61 * allowed to overlap. The union of all the ranges gives the set's contents.
62 * Once a {@code SetOfIntegerSyntax} instance is constructed, its value is
63 * immutable.
64 * <p>
65 * The {@code SetOfIntegerSyntax} object's value is actually stored in
66 * "<i>canonical</i> array form." This is the same as array form, except there
67 * are no {@code null} ranges; the members of the set are represented in as few
68 * ranges as possible (i.e., overlapping ranges are coalesced); the ranges
69 * appear in ascending order; and each range is always represented as a
70 * length-two array of {@code int}s in the form {lower bound, upper bound}. An
71 * empty set is represented as a zero-length array.
72 * <p>
73 * Class {@code SetOfIntegerSyntax} has operations to return the set's members
74 * in canonical array form, to test whether a given integer is a member of the
75 * set, and to iterate through the members of the set.
76 *
77 * @author David Mendenhall
78 * @author Alan Kaminsky
79 */
80 public abstract class SetOfIntegerSyntax implements Serializable, Cloneable {
81
82 /**
83 * Use serialVersionUID from JDK 1.4 for interoperability.
84 */
85 private static final long serialVersionUID = 3666874174847632203L;
86
87 /**
88 * This set's members in canonical array form.
89 *
90 * @serial
91 */
92 private int[][] members;
93
94 /**
95 * Construct a new set-of-integer attribute with the given members in string
96 * form.
97 *
98 * @param members set members in string form. If {@code null}, an empty set
99 * is constructed.
100 * @throws IllegalArgumentException if {@code members} does not obey the
101 * 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 * @param members the string
111 * @return the canonical array form
112 */
113 private static int[][] parse(String members) {
114 // Create vector to hold int[] elements, each element being one range
115 // parsed out of members.
116 Vector<int[]> theRanges = new Vector<>();
117
118 // Run state machine over members.
119 int n = (members == null ? 0 : members.length());
120 int i = 0;
121 int state = 0;
122 int lb = 0;
123 int ub = 0;
124 char c;
125 int digit;
126 while (i < n) {
127 c = members.charAt(i ++);
128 switch (state) {
129
130 case 0: // Before first integer in first group
131 if (Character.isWhitespace(c)) {
132 state = 0;
133 }
134 else if ((digit = Character.digit(c, 10)) != -1) {
135 lb = digit;
136 state = 1;
137 } else {
138 throw new IllegalArgumentException();
139 }
140 break;
141
142 case 1: // In first integer in a group
143 if (Character.isWhitespace(c)){
144 state = 2;
145 } else if ((digit = Character.digit(c, 10)) != -1) {
146 lb = 10 * lb + digit;
147 state = 1;
148 } else if (c == '-' || c == ':') {
149 state = 3;
150 } else if (c == ',') {
151 accumulate (theRanges, lb, lb);
152 state = 6;
153 } else {
154 throw new IllegalArgumentException();
155 }
156 break;
157
158 case 2: // After first integer in a group
159 if (Character.isWhitespace(c)) {
160 state = 2;
161 }
162 else if (c == '-' || c == ':') {
163 state = 3;
164 }
165 else if (c == ',') {
166 accumulate(theRanges, lb, lb);
167 state = 6;
168 } else {
169 throw new IllegalArgumentException();
170 }
171 break;
172
173 case 3: // Before second integer in a group
174 if (Character.isWhitespace(c)) {
175 state = 3;
176 } else if ((digit = Character.digit(c, 10)) != -1) {
177 ub = digit;
178 state = 4;
179 } else {
180 throw new IllegalArgumentException();
181 }
182 break;
183
184 case 4: // In second integer in a group
185 if (Character.isWhitespace(c)) {
186 state = 5;
187 } else if ((digit = Character.digit(c, 10)) != -1) {
188 ub = 10 * ub + digit;
189 state = 4;
190 } else if (c == ',') {
191 accumulate(theRanges, lb, ub);
192 state = 6;
193 } else {
194 throw new IllegalArgumentException();
195 }
196 break;
197
198 case 5: // After second integer in a group
199 if (Character.isWhitespace(c)) {
200 state = 5;
201 } else if (c == ',') {
202 accumulate(theRanges, lb, ub);
203 state = 6;
204 } else {
205 throw new IllegalArgumentException();
206 }
207 break;
208
209 case 6: // Before first integer in second or later group
210 if (Character.isWhitespace(c)) {
211 state = 6;
212 } else if ((digit = Character.digit(c, 10)) != -1) {
213 lb = digit;
214 state = 1;
215 } else {
216 throw new IllegalArgumentException();
217 }
218 break;
219 }
220 }
221
222 // Finish off the state machine.
223 switch (state) {
224 case 0: // Before first integer in first group
225 break;
226 case 1: // In first integer in a group
227 case 2: // After first integer in a group
228 accumulate(theRanges, lb, lb);
229 break;
230 case 4: // In second integer in a group
231 case 5: // After second integer in a group
232 accumulate(theRanges, lb, ub);
233 break;
234 case 3: // Before second integer in a group
235 case 6: // Before first integer in second or later group
236 throw new IllegalArgumentException();
237 }
238
239 // Return canonical array form.
240 return canonicalArrayForm (theRanges);
241 }
242
243 /**
244 * Accumulate the given range (lb .. ub) into the canonical array form into
245 * the given vector of int[] objects.
246 */
247 private static void accumulate(Vector<int[]> ranges, int lb,int ub) {
248 // Make sure range is non-null.
249 if (lb <= ub) {
250 // Stick range at the back of the vector.
251 ranges.add(new int[] {lb, ub});
252
253 // Work towards the front of the vector to integrate the new range
254 // with the existing ranges.
255 for (int j = ranges.size()-2; j >= 0; -- j) {
256 // Get lower and upper bounds of the two ranges being compared.
257 int[] rangea = ranges.elementAt (j);
258 int lba = rangea[0];
259 int uba = rangea[1];
260 int[] rangeb = ranges.elementAt (j+1);
261 int lbb = rangeb[0];
262 int ubb = rangeb[1];
263 /*
264 * If the two ranges overlap or are adjacent, coalesce them. The
265 * two ranges overlap if the larger lower bound is less than or
266 * equal to the smaller upper bound. The two ranges are adjacent
267 * if the larger lower bound is one greater than the smaller
268 * upper bound.
269 */
270 if (Math.max(lba, lbb) - Math.min(uba, ubb) <= 1) {
271 // The coalesced range is from the smaller lower bound to
272 // the larger upper bound.
273 ranges.setElementAt(new int[]
274 {Math.min(lba, lbb),
275 Math.max(uba, ubb)}, j);
276 ranges.remove (j+1);
277 } else if (lba > lbb) {
278
279 /* If the two ranges don't overlap and aren't adjacent but
280 * are out of order, swap them.
281 */
282 ranges.setElementAt (rangeb, j);
283 ranges.setElementAt (rangea, j+1);
284 } else {
285 /*
286 * If the two ranges don't overlap and aren't adjacent and
287 * aren't out of order, we're done early.
288 */
289 break;
290 }
291 }
292 }
293 }
294
295 /**
296 * Convert the given vector of int[] objects to canonical array form.
297 */
298 private static int[][] canonicalArrayForm(Vector<int[]> ranges) {
299 return ranges.toArray (new int[ranges.size()][]);
300 }
301
302 /**
303 * Construct a new set-of-integer attribute with the given members in array
304 * form.
305 *
306 * @param members set members in array form. If {@code null}, an empty set
307 * is constructed.
308 * @throws NullPointerException if any element of {@code members} is
309 * {@code null}
310 * @throws IllegalArgumentException if any element of {@code members} is not
311 * a length-one or length-two array or if any {@code non-null} range
312 * in {@code members} has a lower bound less 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 * @throws IllegalArgumentException if {@code member} is negative
358 */
359 protected SetOfIntegerSyntax(int member) {
360 if (member < 0) {
361 throw new IllegalArgumentException();
362 }
363 members = new int[][] {{member, member}};
364 }
365
366 /**
367 * Construct a new set-of-integer attribute containing a single range of
368 * integers. If the lower bound is greater than the upper bound (a null
369 * range), an empty set is constructed.
370 *
371 * @param lowerBound Lower bound of the range
372 * @param upperBound Upper bound of the range
373 * @throws IllegalArgumentException if the range is {@code non-null} and
374 * {@code lowerBound} is less than zero
375 */
376 protected SetOfIntegerSyntax(int lowerBound, int upperBound) {
377 if (lowerBound <= upperBound && lowerBound < 0) {
378 throw new IllegalArgumentException();
379 }
380 members = lowerBound <=upperBound ?
381 new int[][] {{lowerBound, upperBound}} :
382 new int[0][];
383 }
384
385 /**
386 * Obtain this set-of-integer attribute's members in canonical array form.
387 * The returned array is "safe;" the client may alter it without affecting
388 * this set-of-integer attribute.
389 *
390 * @return this set-of-integer attribute's members in canonical array form
391 */
392 public int[][] getMembers() {
393 int n = members.length;
394 int[][] result = new int[n][];
395 for (int i = 0; i < n; ++ i) {
396 result[i] = new int[] {members[i][0], members[i][1]};
397 }
398 return result;
399 }
400
401 /**
402 * Determine if this set-of-integer attribute contains the given value.
403 *
404 * @param x the Integer value
405 * @return {@code true} if this set-of-integer attribute contains the value
406 * {@code x}, {@code false} otherwise
407 */
408 public boolean contains(int x) {
409 // Do a linear search to find the range that contains x, if any.
410 int n = members.length;
411 for (int i = 0; i < n; ++ i) {
412 if (x < members[i][0]) {
413 return false;
414 } else if (x <= members[i][1]) {
415 return true;
416 }
417 }
418 return false;
419 }
420
421 /**
422 * Determine if this set-of-integer attribute contains the given integer
423 * attribute's value.
424 *
425 * @param attribute the Integer attribute
426 * @return {@code true} if this set-of-integer attribute contains
427 * {@code attribute}'s value, {@code false} otherwise
428 */
429 public boolean contains(IntegerSyntax attribute) {
430 return contains (attribute.getValue());
431 }
432
433 /**
434 * Determine the smallest integer in this set-of-integer attribute that is
435 * greater than the given value. If there are no integers in this
436 * set-of-integer attribute greater than the given value, {@code -1} is
437 * returned. (Since a set-of-integer attribute can only contain nonnegative
438 * values, {@code -1} will never appear in the set.) You can use the
439 * {@code next()} method to iterate through the integer values in a
440 * set-of-integer attribute in ascending order, like this:
441 * <pre>
442 * SetOfIntegerSyntax attribute = . . .;
443 * int i = -1;
444 * while ((i = attribute.next (i)) != -1)
445 * {
446 * foo (i);
447 * }
448 * </pre>
449 *
450 * @param x the Integer value
451 * @return the smallest integer in this set-of-integer attribute that is
452 * greater than {@code x}, or {@code -1} if no integer in this
453 * set-of-integer attribute is greater than {@code x}.
454 */
455 public int next(int x) {
456 // Do a linear search to find the range that contains x, if any.
457 int n = members.length;
458 for (int i = 0; i < n; ++ i) {
459 if (x < members[i][0]) {
460 return members[i][0];
461 } else if (x < members[i][1]) {
462 return x + 1;
463 }
464 }
465 return -1;
466 }
467
468 /**
469 * Returns whether this set-of-integer attribute is equivalent to the passed
470 * in object. To be equivalent, all of the following conditions must be
471 * true:
472 * <ol type=1>
473 * <li>{@code object} is not {@code null}.
474 * <li>{@code object} is an instance of class {@code SetOfIntegerSyntax}.
475 * <li>This set-of-integer attribute's members and {@code object}'s
476 * members are the same.
477 * </ol>
478 *
479 * @param object {@code Object} to compare to
480 * @return {@code true} if {@code object} is equivalent to this
481 * set-of-integer attribute, {@code false} otherwise
482 */
483 public boolean equals(Object object) {
484 if (object != null && object instanceof SetOfIntegerSyntax) {
485 int[][] myMembers = this.members;
486 int[][] otherMembers = ((SetOfIntegerSyntax) object).members;
487 int m = myMembers.length;
488 int n = otherMembers.length;
489 if (m == n) {
490 for (int i = 0; i < m; ++ i) {
491 if (myMembers[i][0] != otherMembers[i][0] ||
492 myMembers[i][1] != otherMembers[i][1]) {
493 return false;
494 }
495 }
496 return true;
497 } else {
498 return false;
499 }
500 } else {
501 return false;
502 }
503 }
504
505 /**
506 * Returns a hash code value for this set-of-integer attribute. The hash
507 * code is the sum of the lower and upper bounds of the ranges in the
508 * canonical array form, or 0 for an empty set.
509 */
510 public int hashCode() {
511 int result = 0;
512 int n = members.length;
513 for (int i = 0; i < n; ++ i) {
514 result += members[i][0] + members[i][1];
515 }
516 return result;
517 }
518
519 /**
520 * Returns a string value corresponding to this set-of-integer attribute.
521 * The string value is a zero-length string if this set is empty. Otherwise,
522 * the string value is a comma-separated list of the ranges in the canonical
523 * array form, where each range is represented as <code>"<i>i</i>"</code> if
524 * the lower bound equals the upper bound or
525 * <code>"<i>i</i>-<i>j</i>"</code> otherwise.
526 */
527 public String toString() {
528 StringBuilder result = new StringBuilder();
529 int n = members.length;
530 for (int i = 0; i < n; i++) {
531 if (i > 0) {
532 result.append (',');
533 }
534 result.append (members[i][0]);
535 if (members[i][0] != members[i][1]) {
536 result.append ('-');
537 result.append (members[i][1]);
538 }
539 }
540 return result.toString();
541 }
542 }