SetOfIntegerSyntax


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