001    /* SetOfIntegerSyntax.java -- 
002       Copyright (C) 2003, 2004, 2005  Free Software Foundation, Inc.
003    
004    This file is part of GNU Classpath.
005    
006    GNU Classpath is free software; you can redistribute it and/or modify
007    it under the terms of the GNU General Public License as published by
008    the Free Software Foundation; either version 2, or (at your option)
009    any later version.
010    
011    GNU Classpath is distributed in the hope that it will be useful, but
012    WITHOUT ANY WARRANTY; without even the implied warranty of
013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014    General Public License for more details.
015    
016    You should have received a copy of the GNU General Public License
017    along with GNU Classpath; see the file COPYING.  If not, write to the
018    Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
019    02110-1301 USA.
020    
021    Linking this library statically or dynamically with other modules is
022    making a combined work based on this library.  Thus, the terms and
023    conditions of the GNU General Public License cover the whole
024    combination.
025    
026    As a special exception, the copyright holders of this library give you
027    permission to link this library with independent modules to produce an
028    executable, regardless of the license terms of these independent
029    modules, and to copy and distribute the resulting executable under
030    terms of your choice, provided that you also meet, for each linked
031    independent module, the terms and conditions of the license of that
032    module.  An independent module is a module which is not derived from
033    or based on this library.  If you modify this library, you may extend
034    this exception to your version of the library, but you are not
035    obligated to do so.  If you do not wish to do so, delete this
036    exception statement from your version. */
037    
038    package javax.print.attribute;
039    
040    import java.io.Serializable;
041    import java.text.CharacterIterator;
042    import java.text.StringCharacterIterator;
043    import java.util.ArrayList;
044    import java.util.Arrays;
045    import 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     */
098    public 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 &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    }