/*

 * Copyright (c) 2000, 2004, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package javax.print.attribute;

import java.io.Serializable;

import java.util.Vector;

/**

 * Class SetOfIntegerSyntax is an abstract base class providing the common

 * implementation of all attributes whose value is a set of nonnegative

 * integers. This includes attributes whose value is a single range of integers

 * and attributes whose value is a set of ranges of integers.

 * <P>

 * You can construct an instance of SetOfIntegerSyntax by giving it in "string

 * form." The string consists of zero or more comma-separated integer groups.

 * Each integer group consists of either one integer, two integers separated by

 * a hyphen (<CODE>-</CODE>), or two integers separated by a colon

 * (<CODE>:</CODE>). Each integer consists of one or more decimal digits

 * (<CODE>0</CODE> through <CODE>9</CODE>). Whitespace characters cannot

 * appear within an integer but are otherwise ignored. For example:

 * <CODE>""</CODE>, <CODE>"1"</CODE>, <CODE>"5-10"</CODE>, <CODE>"1:2,

 * 4"</CODE>.

 * <P>

 * You can also construct an instance of SetOfIntegerSyntax by giving it in

 * "array form." Array form consists of an array of zero or more integer groups

 * where each integer group is a length-1 or length-2 array of

 * <CODE>int</CODE>s; for example, <CODE>int[0][]</CODE>,

 * <CODE>int[][]{{1}}</CODE>, <CODE>int[][]{{5,10}}</CODE>,

 * <CODE>int[][]{{1,2},{4}}</CODE>.

 * <P>

 * In both string form and array form, each successive integer group gives a

 * range of integers to be included in the set. The first integer in each group

 * gives the lower bound of the range; the second integer in each group gives

 * the upper bound of the range; if there is only one integer in the group, the

 * upper bound is the same as the lower bound. If the upper bound is less than

 * the lower bound, it denotes a null range (no values). If the upper bound is

 * equal to the lower bound, it denotes a range consisting of a single value. If

 * the upper bound is greater than the lower bound, it denotes a range

 * consisting of more than one value. The ranges may appear in any order and are

 * allowed to overlap. The union of all the ranges gives the set's contents.

 * Once a SetOfIntegerSyntax instance is constructed, its value is immutable.

 * <P>

 * The SetOfIntegerSyntax object's value is actually stored in "<I>canonical</I>

 * array form." This is the same as array form, except there are no null ranges;

 * the members of the set are represented in as few ranges as possible (i.e.,

 * overlapping ranges are coalesced); the ranges appear in ascending order; and

 * each range is always represented as a length-two array of <CODE>int</CODE>s

 * in the form {lower bound, upper bound}. An empty set is represented as a

 * zero-length array.

 * <P>

 * Class SetOfIntegerSyntax has operations to return the set's members in

 * canonical array form, to test whether a given integer is a member of the

 * set, and to iterate through the members of the set.

 * <P>

 *

 * @author  David Mendenhall

 * @author  Alan Kaminsky

 */

public abstract class SetOfIntegerSyntax implements Serializable, Cloneable {

    private static final long serialVersionUID = 3666874174847632203L;

    /**

     * This set's members in canonical array form.

     * @serial

     */

    private int[][] members;

    /**

     * Construct a new set-of-integer attribute with the given members in

     * string form.

     *

     * @param  members  Set members in string form. If null, an empty set is

     *                     constructed.

     *

     * @exception  IllegalArgumentException

     *     (Unchecked exception) Thrown if <CODE>members</CODE> does not

     *    obey  the proper syntax.

     */

    protected SetOfIntegerSyntax(String members) {

        this.members = parse (members);

    }

    /**

     * Parse the given string, returning canonical array form.

     */

    private static int[][] parse(String members) {

        // Create vector to hold int[] elements, each element being one range

        // parsed out of members.

        Vector<int[]> theRanges = new Vector<>();

        // Run state machine over members.

        int n = (members == null ? 0 : members.length());

        int i = 0;

        int state = 0;

        int lb = 0;

        int ub = 0;

        char c;

        int digit;

        while (i < n) {

            c = members.charAt(i ++);

            switch (state) {

            case 0: // Before first integer in first group

                if (Character.isWhitespace(c)) {

                    state = 0;

                }

                else if ((digit = Character.digit(c, 10)) != -1) {

                    lb = digit;

                    state = 1;

                } else {

                    throw new IllegalArgumentException();

                }

                break;

            case 1: // In first integer in a group

                if (Character.isWhitespace(c)){

                        state = 2;

                } else if ((digit = Character.digit(c, 10)) != -1) {

                    lb = 10 * lb + digit;

                    state = 1;

                } else if (c == '-' || c == ':') {

                    state = 3;

                } else if (c == ',') {

                    accumulate (theRanges, lb, lb);

                    state = 6;

                } else {

                    throw new IllegalArgumentException();

                }

                break;

            case 2: // After first integer in a group

                if (Character.isWhitespace(c)) {

                    state = 2;

                }

                else if (c == '-' || c == ':') {

                    state = 3;

                }

                else if (c == ',') {

                    accumulate(theRanges, lb, lb);

                    state = 6;

                } else {

                    throw new IllegalArgumentException();

                }

                break;

            case 3: // Before second integer in a group

                if (Character.isWhitespace(c)) {

                    state = 3;

                } else if ((digit = Character.digit(c, 10)) != -1) {

                    ub = digit;

                    state = 4;

                } else {

                    throw new IllegalArgumentException();

                }

                break;

            case 4: // In second integer in a group

                if (Character.isWhitespace(c)) {

                    state = 5;

                } else if ((digit = Character.digit(c, 10)) != -1) {

                    ub = 10 * ub + digit;

                    state = 4;

                } else if (c == ',') {

                    accumulate(theRanges, lb, ub);

                    state = 6;

                } else {

                    throw new IllegalArgumentException();

                }

                break;

            case 5: // After second integer in a group

                if (Character.isWhitespace(c)) {

                    state = 5;

                } else if (c == ',') {

                    accumulate(theRanges, lb, ub);

                    state = 6;

                } else {

                    throw new IllegalArgumentException();

                }

                break;

            case 6: // Before first integer in second or later group

                if (Character.isWhitespace(c)) {

                    state = 6;

                } else if ((digit = Character.digit(c, 10)) != -1) {

                    lb = digit;

                    state = 1;

                } else {

                    throw new IllegalArgumentException();

                }

                break;

            }

        }

        // Finish off the state machine.

        switch (state) {

        case 0: // Before first integer in first group

            break;

        case 1: // In first integer in a group

        case 2: // After first integer in a group

            accumulate(theRanges, lb, lb);

            break;

        case 4: // In second integer in a group

        case 5: // After second integer in a group

            accumulate(theRanges, lb, ub);

            break;

        case 3: // Before second integer in a group

        case 6: // Before first integer in second or later group

            throw new IllegalArgumentException();

        }

        // Return canonical array form.

        return canonicalArrayForm (theRanges);

    }

    /**

     * Accumulate the given range (lb .. ub) into the canonical array form

     * into the given vector of int[] objects.

     */

    private static void accumulate(Vector<int[]> ranges, int lb,int ub) {

        // Make sure range is non-null.

        if (lb <= ub) {

            // Stick range at the back of the vector.

            ranges.add(new int[] {lb, ub});

            // Work towards the front of the vector to integrate the new range

            // with the existing ranges.

            for (int j = ranges.size()-2; j >= 0; -- j) {

            // Get lower and upper bounds of the two ranges being compared.

                int[] rangea = ranges.elementAt (j);

                int lba = rangea[0];

                int uba = rangea[1];

                int[] rangeb = ranges.elementAt (j+1);

                int lbb = rangeb[0];

                int ubb = rangeb[1];

                /* If the two ranges overlap or are adjacent, coalesce them.

                 * The two ranges overlap if the larger lower bound is less

                 * than or equal to the smaller upper bound. The two ranges

                 * are adjacent if the larger lower bound is one greater

                 * than the smaller upper bound.

                 */

                if (Math.max(lba, lbb) - Math.min(uba, ubb) <= 1) {

                    // The coalesced range is from the smaller lower bound to

                    // the larger upper bound.

                    ranges.setElementAt(new int[]

                                           {Math.min(lba, lbb),

                                                Math.max(uba, ubb)}, j);

                    ranges.remove (j+1);

                } else if (lba > lbb) {

                    /* If the two ranges don't overlap and aren't adjacent but

                     * are out of order, swap them.

                     */

                    ranges.setElementAt (rangeb, j);

                    ranges.setElementAt (rangea, j+1);

                } else {

                /* If the two ranges don't overlap and aren't adjacent and

                 * aren't out of order, we're done early.

                 */

                    break;

                }

            }

        }

    }

    /**

     * Convert the given vector of int[] objects to canonical array form.

     */

    private static int[][] canonicalArrayForm(Vector<int[]> ranges) {

        return ranges.toArray (new int[ranges.size()][]);

    }

    /**

     * Construct a new set-of-integer attribute with the given members in

     * array form.

     *

     * @param  members  Set members in array form. If null, an empty set is

     *                     constructed.

     *

     * @exception  NullPointerException

     *     (Unchecked exception) Thrown if any element of

     *     <CODE>members</CODE> is null.

     * @exception  IllegalArgumentException

     *     (Unchecked exception) Thrown if any element of

     *     <CODE>members</CODE> is not a length-one or length-two array or if

     *     any non-null range in <CODE>members</CODE> has a lower bound less

     *     than zero.

     */

    protected SetOfIntegerSyntax(int[][] members) {

        this.members = parse (members);

    }

    /**

     * Parse the given array form, returning canonical array form.

     */

    private static int[][] parse(int[][] members) {

        // Create vector to hold int[] elements, each element being one range

        // parsed out of members.

        Vector<int[]> ranges = new Vector<>();

        // Process all integer groups in members.

        int n = (members == null ? 0 : members.length);

        for (int i = 0; i < n; ++ i) {

            // Get lower and upper bounds of the range.

            int lb, ub;

            if (members[i].length == 1) {

                lb = ub = members[i][0];

            } else if (members[i].length == 2) {

                lb = members[i][0];

                ub = members[i][1];

            } else {

                throw new IllegalArgumentException();

            }

            // Verify valid bounds.

            if (lb <= ub && lb < 0) {

                throw new IllegalArgumentException();

            }

            // Accumulate the range.

            accumulate(ranges, lb, ub);

        }

                // Return canonical array form.

                return canonicalArrayForm (ranges);

                }

    /**

     * Construct a new set-of-integer attribute containing a single integer.

     *

     * @param  member  Set member.

     *

     * @exception  IllegalArgumentException

     *     (Unchecked exception) Thrown if <CODE>member</CODE> is less than

     *     zero.

     */

    protected SetOfIntegerSyntax(int member) {

        if (member < 0) {

            throw new IllegalArgumentException();

        }

        members = new int[][] {{member, member}};

    }

    /**

     * Construct a new set-of-integer attribute containing a single range of

     * integers. If the lower bound is greater than the upper bound (a null

     * range), an empty set is constructed.

     *

     * @param  lowerBound  Lower bound of the range.

     * @param  upperBound  Upper bound of the range.

     *

     * @exception  IllegalArgumentException

     *     (Unchecked exception) Thrown if the range is non-null and

     *     <CODE>lowerBound</CODE> is less than zero.

     */

    protected SetOfIntegerSyntax(int lowerBound, int upperBound) {

        if (lowerBound <= upperBound && lowerBound < 0) {

            throw new IllegalArgumentException();

        }

        members = lowerBound <=upperBound ?

            new int[][] {{lowerBound, upperBound}} :

            new int[0][];

    }

    /**

     * Obtain this set-of-integer attribute's members in canonical array form.

     * The returned array is "safe;" the client may alter it without affecting

     * this set-of-integer attribute.

     *

     * @return  This set-of-integer attribute's members in canonical array form.

     */

    public int[][] getMembers() {

        int n = members.length;

        int[][] result = new int[n][];

        for (int i = 0; i < n; ++ i) {

            result[i] = new int[] {members[i][0], members[i][1]};

        }

        return result;

    }

    /**

     * Determine if this set-of-integer attribute contains the given value.

     *

     * @param  x  Integer value.

     *

     * @return  True if this set-of-integer attribute contains the value

     *          <CODE>x</CODE>, false otherwise.

     */

    public boolean contains(int x) {

        // Do a linear search to find the range that contains x, if any.

        int n = members.length;

        for (int i = 0; i < n; ++ i) {

            if (x < members[i][0]) {

                return false;

            } else if (x <= members[i][1]) {

                return true;

            }

        }

        return false;

    }

    /**

     * Determine if this set-of-integer attribute contains the given integer

     * attribute's value.

     *

     * @param  attribute  Integer attribute.

     *

     * @return  True if this set-of-integer attribute contains

     *          <CODE>theAttribute</CODE>'s value, false otherwise.

     */

    public boolean contains(IntegerSyntax attribute) {

        return contains (attribute.getValue());

    }

    /**

     * Determine the smallest integer in this set-of-integer attribute that is

     * greater than the given value. If there are no integers in this

     * set-of-integer attribute greater than the given value, <CODE>-1</CODE> is

     * returned. (Since a set-of-integer attribute can only contain nonnegative

     * values, <CODE>-1</CODE> will never appear in the set.) You can use the

     * <CODE>next()</CODE> method to iterate through the integer values in a

     * set-of-integer attribute in ascending order, like this:

     * <PRE>

     *     SetOfIntegerSyntax attribute = . . .;

     *     int i = -1;

     *     while ((i = attribute.next (i)) != -1)

     *         {

     *         foo (i);

     *         }

     * </PRE>

     *

     * @param  x  Integer value.

     *

     * @return  The smallest integer in this set-of-integer attribute that is

     *          greater than <CODE>x</CODE>, or <CODE>-1</CODE> if no integer in

     *          this set-of-integer attribute is greater than <CODE>x</CODE>.

     */

    public int next(int x) {

        // Do a linear search to find the range that contains x, if any.

        int n = members.length;

        for (int i = 0; i < n; ++ i) {

            if (x < members[i][0]) {

                return members[i][0];

            } else if (x < members[i][1]) {

                return x + 1;

            }

        }

        return -1;

    }

    /**

     * Returns whether this set-of-integer attribute is equivalent to the passed

     * in object. To be equivalent, all of the following conditions must be

     * true:

     * <OL TYPE=1>

     * <LI>

     * <CODE>object</CODE> is not null.

     * <LI>

     * <CODE>object</CODE> is an instance of class SetOfIntegerSyntax.

     * <LI>

     * This set-of-integer attribute's members and <CODE>object</CODE>'s

     * members are the same.

     * </OL>

     *

     * @param  object  Object to compare to.

     *

     * @return  True if <CODE>object</CODE> is equivalent to this

     *          set-of-integer attribute, false otherwise.

     */

    public boolean equals(Object object) {

        if (object != null && object instanceof SetOfIntegerSyntax) {

            int[][] myMembers = this.members;

            int[][] otherMembers = ((SetOfIntegerSyntax) object).members;

            int m = myMembers.length;

            int n = otherMembers.length;

            if (m == n) {

                for (int i = 0; i < m; ++ i) {

                    if (myMembers[i][0] != otherMembers[i][0] ||

                        myMembers[i][1] != otherMembers[i][1]) {

                        return false;

                    }

                }

                return true;

            } else {

                return false;

            }

        } else {

            return false;

        }

    }

    /**

     * Returns a hash code value for this set-of-integer attribute. The hash

     * code is the sum of the lower and upper bounds of the ranges in the

     * canonical array form, or 0 for an empty set.

     */

    public int hashCode() {

        int result = 0;