0001: /*
0002: * GeoTools - OpenSource mapping toolkit
0003: * http://geotools.org
0004: * (C) 2003-2006, Geotools Project Managment Committee (PMC)
0005: * (C) 2001, Institut de Recherche pour le Développement
0006: *
0007: * This library is free software; you can redistribute it and/or
0008: * modify it under the terms of the GNU Lesser General Public
0009: * License as published by the Free Software Foundation; either
0010: * version 2.1 of the License, or (at your option) any later version.
0011: *
0012: * This library is distributed in the hope that it will be useful,
0013: * but WITHOUT ANY WARRANTY; without even the implied warranty of
0014: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
0015: * Lesser General Public License for more details.
0016: */
0017: package org.geotools.util;
0018:
0019: // Collections
0020: import java.io.Serializable;
0021: import java.lang.reflect.Array;
0022: import java.util.AbstractSet;
0023: import java.util.Arrays;
0024: import java.util.Comparator;
0025: import java.util.ConcurrentModificationException;
0026: import java.util.NoSuchElementException;
0027: import java.util.SortedSet;
0028:
0029: import javax.media.jai.util.Range;
0030:
0031: import org.geotools.resources.ClassChanger;
0032: import org.geotools.resources.Utilities;
0033: import org.geotools.resources.i18n.Errors;
0034: import org.geotools.resources.i18n.ErrorKeys;
0035: import org.opengis.util.Cloneable;
0036:
0037: /**
0038: * An ordered set of ranges. {@code RangeSet} objects store an arbitrary number of
0039: * {@linkplain Range ranges} in any Java's primitives ({@code int}, {@code float},
0040: * etc.) or any {@linkplain Comparable comparable} objects. Ranges may be added in any order.
0041: * When a range is added, {@code RangeSet} first looks for an existing range overlapping the
0042: * specified range. If an overlapping range is found, ranges are merged as of {@link Range#union}.
0043: * Consequently, ranges returned by {@link #iterator} may not be the same than added ranges.
0044: * <p>
0045: * All entries in this set can be seen as {@link Range} objects.
0046: * This class is not thread-safe.
0047: *
0048: * @since 2.0
0049: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/library/metadata/src/main/java/org/geotools/util/RangeSet.java $
0050: * @version $Id: RangeSet.java 22443 2006-10-27 20:47:22Z desruisseaux $
0051: * @author Martin Desruisseaux
0052: * @author Andrea Aime
0053: */
0054: public class RangeSet extends AbstractSet implements SortedSet,
0055: Cloneable, Serializable {
0056: /**
0057: * Serial number for interoperability with different versions.
0058: */
0059: private static final long serialVersionUID = 3222336180818126987L;
0060:
0061: /**
0062: * The comparator for ranges. Defined only in order to comply to {@link #comparator}
0063: * contract, but not used for internal working in this class.
0064: */
0065: private static final Comparator COMPARATOR = new Comparator() {
0066: public int compare(final Object o1, final Object o2) {
0067: final Range r1 = (Range) o1;
0068: final Range r2 = (Range) o2;
0069: int cmin = r1.getMinValue().compareTo(r2.getMinValue());
0070: int cmax = r1.getMaxValue().compareTo(r2.getMaxValue());
0071: if (cmin == 0)
0072: cmin = (r1.isMinIncluded() ? -1 : 0)
0073: - (r2.isMinIncluded() ? -1 : 0);
0074: if (cmax == 0)
0075: cmax = (r1.isMaxIncluded() ? +1 : 0)
0076: - (r2.isMaxIncluded() ? +1 : 0);
0077: if (cmin == cmax)
0078: return cmax; // Easy case: min and max are both greater, smaller or eq.
0079: if (cmin == 0)
0080: return cmax; // Easy case: only max value differ.
0081: if (cmax == 0)
0082: return cmin; // Easy case: only min value differ.
0083: // One range is included in the other.
0084: throw new IllegalArgumentException("Unordered ranges");
0085: }
0086: };
0087:
0088: /**
0089: * Tableau de correspondances entre les type primitifs
0090: * et leurs "wrappers". Les classes aux index pairs sont
0091: * les types primitifs, tandis que les classes aux index
0092: * impairs sont leurs "wrappers".
0093: */
0094: private static final Class[] PRIMITIVES = { Double.TYPE,
0095: Double.class, Float.TYPE, Float.class, Long.TYPE,
0096: Long.class, Integer.TYPE, Integer.class, Short.TYPE,
0097: Short.class, Byte.TYPE, Byte.class, Character.TYPE,
0098: Character.class };
0099:
0100: /**
0101: * The primitive types, as an index in the {@link #PRIMITIVES} array divided by 2.
0102: */
0103: private static final byte DOUBLE = 0, FLOAT = 1, LONG = 2,
0104: INTEGER = 3, SHORT = 4, BYTE = 5, CHARACTER = 6,
0105: OTHER = -1;
0106:
0107: /**
0108: * Le type des données de l'intervalle. Il s'agit du type
0109: * qui sera spécifié aux objets {@link Range} représentant
0110: * un intervalle.
0111: */
0112: private final Class type;
0113:
0114: /**
0115: * Ce champ a une valeur identique à {@code type}, sauf
0116: * si {@code elementType} est un type primitif. Dans ce
0117: * cas, il sera <code>{@link Number}.class</code>.
0118: */
0119: private final Class relaxedType;
0120:
0121: /**
0122: * Le type des données utilisé dans le tableau {@code array}.
0123: * Il s'agira souvent du même type que {@code type}, sauf si
0124: * ce dernier était le "wrapper" d'un des types primitifs du Java.
0125: * Dans ce cas, {@code elementType} sera ce type primitif.
0126: */
0127: private final Class elementType;
0128:
0129: /**
0130: * The primitive type, as one of {@code DOUBLE}, {@code FLOAT}, {@code LONG},
0131: * {@code INTEGER}, {@code SHORT}, {@code BYTE}, {@code CHARACTER} or
0132: * {@code OTHER} enumeration.
0133: */
0134: private final byte indexType;
0135:
0136: /**
0137: * Tableau d'intervalles. Il peut s'agir d'un tableau d'un des types primitifs
0138: * du Java (par exemple {@code int[]} ou {@code float[]}), ou d'un
0139: * tableau de type {@code Comparable[]}. Les éléments de ce tableau doivent
0140: * obligatoirement être en ordre strictement croissant et sans doublon.
0141: * <br><br>
0142: * La longueur de ce tableau est le double du nombre d'intervalles. Il aurait
0143: * été plus efficace d'utiliser une variable séparée (pour ne pas être obligé
0144: * d'agrandir ce tableau à chaque ajout d'un intervalle), mais malheureusement
0145: * le J2SE 1.4 ne nous fournit pas de méthode {@code Arrays.binarySearch}
0146: * qui nous permettent de spécifier les limites du tableau (voir RFE #4306897
0147: * à http://developer.java.sun.com/developer/bugParade/bugs/4306897.html).
0148: */
0149: private Object array;
0150:
0151: /**
0152: * Compte le nombre de modifications apportées au tableau des intervalles.
0153: * Ce comptage sert à vérifier si une modification survient pendant qu'un
0154: * itérateur balayait les intervalles.
0155: */
0156: private int modCount;
0157:
0158: /**
0159: * {@code true} if and only if the element class represents a primitive type.
0160: * This is equivalents to {@code elementType.isPrimitive()} and is computed
0161: * once for ever for performance reason.
0162: */
0163: private final boolean isPrimitive;
0164:
0165: /**
0166: * {@code true} if we should invoke {@link ClassChanger#toNumber}
0167: * before to store a value into the array. It will be the case if the
0168: * array {@code array} contains primitive elements and the type
0169: * {@code type} is not the corresponding wrapper.
0170: */
0171: private final boolean useClassChanger;
0172:
0173: /**
0174: * {@code true} if instances of {@link NumberRange} should be created instead
0175: * of {@link Range}.
0176: */
0177: private final boolean isNumeric;
0178:
0179: /**
0180: * Construct an empty set of range.
0181: *
0182: * @param type The class of the range elements. It must be a primitive
0183: * type or a class implementing {@link Comparable}.
0184: * @throws IllegalArgumentException if {@code type} is not a
0185: * primitive type or a class implementing {@link Comparable}.
0186: */
0187: public RangeSet(Class type) throws IllegalArgumentException {
0188: // If 'type' is a primitive type,
0189: // find the corresponding wrapper.
0190: byte indexType = OTHER;
0191: for (int i = 0; i < PRIMITIVES.length; i += 2) {
0192: if (PRIMITIVES[i].equals(type)) {
0193: type = PRIMITIVES[i + 1];
0194: indexType = (byte) (i / 2);
0195: break;
0196: }
0197: }
0198: if (!Comparable.class.isAssignableFrom(type)) {
0199: throw new IllegalArgumentException(Errors.format(
0200: ErrorKeys.NOT_COMPARABLE_CLASS_$1, Utilities
0201: .getShortClassName(type)));
0202: }
0203: Class elementType = ClassChanger.getTransformedClass(type); // e.g. change Date --> Long
0204: useClassChanger = (elementType != type);
0205: // If 'elementType' is a wrapper class,
0206: // find the corresponding primitive type.
0207: for (int i = 0; i < PRIMITIVES.length; i += 2) {
0208: if (PRIMITIVES[i + 1].equals(elementType)) {
0209: elementType = PRIMITIVES[i];
0210: indexType = (byte) (i / 2);
0211: break;
0212: }
0213: }
0214: this .type = type;
0215: this .indexType = indexType;
0216: this .elementType = elementType;
0217: this .isPrimitive = elementType.isPrimitive();
0218: this .isNumeric = Number.class.isAssignableFrom(type);
0219: this .relaxedType = isNumeric ? Number.class : type;
0220: }
0221:
0222: /**
0223: * Returns the comparator associated with this sorted set.
0224: */
0225: public Comparator comparator() {
0226: return COMPARATOR;
0227: }
0228:
0229: /**
0230: * Remove all elements from this set of ranges.
0231: */
0232: public void clear() {
0233: array = null;
0234: modCount++;
0235: }
0236:
0237: /**
0238: * Returns the number of ranges in this set.
0239: */
0240: public int size() {
0241: return (array != null) ? Array.getLength(array) / 2 : 0;
0242: }
0243:
0244: /**
0245: * Add a range to this set. Range may be added in any order.
0246: * If the specified range overlap an existing range, the two
0247: * range will be merged as of {@link Range#union}.
0248: * <br><br>
0249: * Note: current version do not support open interval (i.e.
0250: * {@code Range.is[Min/Max]Included()} must return
0251: * {@code true}). It may be fixed in a future version.
0252: *
0253: * @param r The range to add. The {@code RangeSet} class
0254: * will never modify the supplied {@link Range} object.
0255: * @return {@code true} if this set changed as a result of the call.
0256: * @throws ClassCastException if the argument is not a {@link Range} object.
0257: *
0258: * @todo support open intervals.
0259: */
0260: public boolean add(final Object r) throws ClassCastException {
0261: final Range range = (Range) r;
0262: if (!range.isMinIncluded() || !range.isMaxIncluded()) {
0263: // TODO: support open intervals.
0264: throw new UnsupportedOperationException(
0265: "Open interval not yet supported");
0266: }
0267: return add(range.getMinValue(), range.getMaxValue());
0268: }
0269:
0270: /**
0271: * Add a range of values to this set. Range may be added in any order.
0272: * If the specified range overlap an existing range, the two ranges
0273: * will be merged.
0274: *
0275: * @param lower The lower value, inclusive.
0276: * @param upper The upper value, inclusive.
0277: * @return {@code true} if this set changed as a result of the call.
0278: * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}.
0279: */
0280: public boolean add(Comparable lower, Comparable upper)
0281: throws IllegalArgumentException {
0282: if (!relaxedType.isAssignableFrom(lower.getClass())) {
0283: throw new IllegalArgumentException(String.valueOf(lower));
0284: }
0285: if (!relaxedType.isAssignableFrom(upper.getClass())) {
0286: throw new IllegalArgumentException(String.valueOf(upper));
0287: }
0288: if (lower.compareTo(upper) > 0) {
0289: throw new IllegalArgumentException(Errors.format(
0290: ErrorKeys.BAD_RANGE_$2, lower, upper));
0291: }
0292: if (useClassChanger) {
0293: try {
0294: lower = (Comparable) ClassChanger.toNumber(lower);
0295: upper = (Comparable) ClassChanger.toNumber(upper);
0296: } catch (ClassNotFoundException exception) {
0297: // Should not happen, since this operation is legal according the constructor.
0298: final ClassCastException e = new ClassCastException(
0299: exception.getLocalizedMessage());
0300: e.initCause(exception);
0301: throw e;
0302: }
0303: }
0304: if (array == null) {
0305: modCount++;
0306: array = Array.newInstance(elementType, 2);
0307: Array.set(array, 0, lower);
0308: Array.set(array, 1, upper);
0309: return true;
0310: }
0311: final int modCountChk = modCount;
0312: int i0 = binarySearch(lower);
0313: int i1;
0314: if (i0 < 0) {
0315: /*
0316: * Si le début de la plage ne correspond pas à une des dates en
0317: * mémoire, il faudra l'insérer à quelque part dans le tableau.
0318: * Si la date tombe dans une des plages déjà existantes (si son
0319: * index est impair), on étend la date de début pour prendre le
0320: * début de la plage. Visuellement, on fait:
0321: *
0322: * 0 1 2 3 4 5 6 7
0323: * ##### ######## ##### #######
0324: * <---^ ^
0325: * lower(i=3) upper(i=5)
0326: */
0327: if (((i0 = ~i0) & 1) != 0) { // Attention: c'est ~ et non -
0328: lower = (Comparable) Array.get(array, --i0);
0329: i1 = binarySearch(upper);
0330: } else {
0331: /*
0332: * Si la date de début ne tombe pas dans une plage déjà
0333: * existante, il faut étendre la valeur de début qui se
0334: * trouve dans le tableau. Visuellement, on fait:
0335: *
0336: * 0 1 2 3 4 5 6 7
0337: * ##### ***######## ##### #######
0338: * ^ ^
0339: * lower(i=2) upper(i=5)
0340: */
0341: if (i0 != Array.getLength(array)
0342: && (i1 = binarySearch(upper)) != ~i0) {
0343: modCount++;
0344: Array.set(array, i0, lower);
0345: } else {
0346: /*
0347: * Un cas particulier se produit si la nouvelle plage
0348: * est à insérer à la fin du tableau. Dans ce cas, on
0349: * n'a qu'à agrandir le tableau et écrire les valeurs
0350: * directement à la fin. Ce traitement est nécessaire
0351: * pour eviter les 'ArrayIndexOutOfBoundsException'.
0352: * Un autre cas particulier se produit si la nouvelle
0353: * plage est entièrement comprise entre deux plages
0354: * déjà existantes. Le même code ci-dessous insèrera
0355: * la nouvelle plage à l'index 'i0'.
0356: */
0357: modCount++;
0358: final Object old = array;
0359: final int length = Array.getLength(array);
0360: array = Array.newInstance(elementType, length + 2);
0361: System.arraycopy(old, 0, array, 0, i0);
0362: System.arraycopy(old, i0, array, i0 + 2, length
0363: - i0);
0364: Array.set(array, i0 + 0, lower);
0365: Array.set(array, i0 + 1, upper);
0366: return true;
0367: }
0368: }
0369: } else {
0370: i0 &= ~1;
0371: i1 = binarySearch(upper);
0372: }
0373: /*
0374: * A ce stade, on est certain que 'i0' est pair et pointe vers le début
0375: * de la plage dans le tableau. Fait maintenant le traitement pour 'i1'.
0376: */
0377: if (i1 < 0) {
0378: /*
0379: * Si la date de fin tombe dans une des plages déjà existantes
0380: * (si son index est impair), on l'étend pour pendre la fin de
0381: * la plage trouvée dans le tableau. Visuellement, on fait:
0382: *
0383: * 0 1 2 3 4 5 6 7
0384: * ##### ######## ##### #######
0385: * ^ ^-->
0386: * lower(i=2) upper(i=5)
0387: */
0388: if (((i1 = ~i1) & 1) != 0) { // Attention: c'est ~ et non -
0389: upper = (Comparable) Array.get(array, i1);
0390: } else {
0391: /*
0392: * Si la date de fin ne tombe pas dans une plage déjà
0393: * existante, il faut étendre la valeur de fin qui se
0394: * trouve dans le tableau. Visuellement, on fait:
0395: *
0396: * 0 1 2 3 4 5 6 7
0397: * ##### ######## #####** #######
0398: * ^ ^
0399: * lower(i=2) upper(i=6)
0400: */
0401: modCount++;
0402: Array.set(array, --i1, upper);
0403: }
0404: } else {
0405: i1 |= 1;
0406: }
0407: /*
0408: * A ce stade, on est certain que 'i1' est impair et pointe vers la fin
0409: * de la plage dans le tableau. On va maintenant supprimer tout ce qui
0410: * se trouve entre 'i0' et 'i1', à l'exclusion de 'i0' et 'i1'.
0411: */
0412: assert (i0 & 1) == 0 : i0;
0413: assert (i1 & 1) != 0 : i1;
0414: final int n = i1 - (++i0);
0415: if (n > 0) {
0416: modCount++;
0417: final Object old = array;
0418: final int length = Array.getLength(array);
0419: array = Array.newInstance(elementType, length - n);
0420: System.arraycopy(old, 0, array, 0, i0);
0421: System.arraycopy(old, i1, array, i0, length - i1);
0422: }
0423: assert (Array.getLength(array) & 1) == 0;
0424: return modCountChk != modCount;
0425: }
0426:
0427: /**
0428: * Add a range of values to this set. Range may be added in any order.
0429: * If the specified range overlap an existing range, the two ranges
0430: * will be merged.
0431: *
0432: * @param lower The lower value, inclusive.
0433: * @param upper The upper value, inclusive.
0434: * @return {@code true} if this set changed as a result of the call.
0435: * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}.
0436: */
0437: public boolean add(byte lower, byte upper)
0438: throws IllegalArgumentException {
0439: return add(new Byte(lower), new Byte(upper));
0440: }
0441:
0442: /**
0443: * Add a range of values to this set. Range may be added in any order.
0444: * If the specified range overlap an existing range, the two ranges
0445: * will be merged.
0446: *
0447: * @param lower The lower value, inclusive.
0448: * @param upper The upper value, inclusive.
0449: * @return {@code true} if this set changed as a result of the call.
0450: * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}.
0451: */
0452: public boolean add(short lower, short upper)
0453: throws IllegalArgumentException {
0454: return add(new Short(lower), new Short(upper));
0455: }
0456:
0457: /**
0458: * Add a range of values to this set. Range may be added in any order.
0459: * If the specified range overlap an existing range, the two ranges
0460: * will be merged.
0461: *
0462: * @param lower The lower value, inclusive.
0463: * @param upper The upper value, inclusive.
0464: * @return {@code true} if this set changed as a result of the call.
0465: * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}.
0466: */
0467: public boolean add(int lower, int upper)
0468: throws IllegalArgumentException {
0469: return add(new Integer(lower), new Integer(upper));
0470: }
0471:
0472: /**
0473: * Add a range of values to this set. Range may be added in any order.
0474: * If the specified range overlap an existing range, the two ranges
0475: * will be merged.
0476: *
0477: * @param lower The lower value, inclusive.
0478: * @param upper The upper value, inclusive.
0479: * @return {@code true} if this set changed as a result of the call.
0480: * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}.
0481: */
0482: public boolean add(long lower, long upper)
0483: throws IllegalArgumentException {
0484: return add(new Long(lower), new Long(upper));
0485: }
0486:
0487: /**
0488: * Add a range of values to this set. Range may be added in any order.
0489: * If the specified range overlap an existing range, the two ranges
0490: * will be merged.
0491: *
0492: * @param lower The lower value, inclusive.
0493: * @param upper The upper value, inclusive.
0494: * @return {@code true} if this set changed as a result of the call.
0495: * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}.
0496: */
0497: public boolean add(float lower, float upper)
0498: throws IllegalArgumentException {
0499: return add(new Float(lower), new Float(upper));
0500: }
0501:
0502: /**
0503: * Add a range of values to this set. Range may be added in any order.
0504: * If the specified range overlap an existing range, the two ranges
0505: * will be merged.
0506: *
0507: * @param lower The lower value, inclusive.
0508: * @param upper The upper value, inclusive.
0509: * @return {@code true} if this set changed as a result of the call.
0510: * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}.
0511: */
0512: public boolean add(double lower, double upper)
0513: throws IllegalArgumentException {
0514: return add(new Double(lower), new Double(upper));
0515: }
0516:
0517: /**
0518: * Remove a range of values from this set. Range may be removed in any order.
0519: *
0520: * @param lower The lower value to remove, exclusive.
0521: * @param upper The upper value to remove, exclusive.
0522: * @return {@code true} if this set changed as a result of the call.
0523: * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}.
0524: */
0525: public boolean remove(Comparable lower, Comparable upper)
0526: throws IllegalArgumentException {
0527: if (!relaxedType.isAssignableFrom(lower.getClass())) {
0528: throw new IllegalArgumentException(String.valueOf(lower));
0529: }
0530: if (!relaxedType.isAssignableFrom(upper.getClass())) {
0531: throw new IllegalArgumentException(String.valueOf(upper));
0532: }
0533: if (lower.compareTo(upper) >= 0) {
0534: throw new IllegalArgumentException(Errors.format(
0535: ErrorKeys.BAD_RANGE_$2, lower, upper));
0536: }
0537: if (useClassChanger) {
0538: try {
0539: lower = (Comparable) ClassChanger.toNumber(lower);
0540: upper = (Comparable) ClassChanger.toNumber(upper);
0541: } catch (ClassNotFoundException exception) {
0542: // Should not happen, since this operation is legal according the constructor.
0543: final ClassCastException e = new ClassCastException(
0544: exception.getLocalizedMessage());
0545: e.initCause(exception);
0546: throw e;
0547: }
0548: }
0549: // if already empty, or range outside the current set, nothing to change
0550: if (array == null) {
0551: return false;
0552: }
0553: final int modCountChk = modCount;
0554: int i0 = binarySearch(lower);
0555: int i1 = binarySearch(upper);
0556: if (i0 < 0) {
0557: if (((i0 = ~i0) & 1) != 0) { // Attention: c'est ~ et non -
0558: /*
0559: * Si le début de la plage ne correspond pas à une des dates en mémoire,
0560: * il faudra faire un trou à quelque part dans le tableau. Si la date tombe
0561: * dans une des plages déjà existantes (si son index est impair), on change
0562: * la date de fin de la plage existante. Visuellement, on fait:
0563: *
0564: * 0 1 2 3 4 5 6 7
0565: * ##### #####--- --### #######
0566: * ^ ^
0567: * lower(i=3) upper(i=5)
0568: */
0569: modCount++;
0570: if (i1 != ~i0) {
0571: Array.set(array, i0, lower);
0572: } else {
0573: /*
0574: * Special case if the upper index is inside the same range than the lower one:
0575: *
0576: * 0 1 2 3 4 5
0577: * ##### ####---------##### #####
0578: * ^ ^
0579: * lower(i=3) upper(i=3)
0580: */
0581: final Object old = array;
0582: final int length = Array.getLength(array);
0583: array = Array.newInstance(elementType, length + 2);
0584: System.arraycopy(old, 0, array, 0, i0);
0585: System.arraycopy(old, i0, array, i0 + 2, length
0586: - i0);
0587: Array.set(array, i0 + 0, lower);
0588: Array.set(array, i0 + 1, upper);
0589: return true;
0590: }
0591: } else {
0592: /*
0593: * Si la date de début ne tombe pas dans une plage déjà
0594: * existante, il faut prendre la date de fin de la plage
0595: * précédente. Visuellement, on fait:
0596: *
0597: * 0 1 2 3 4 5 6 7
0598: * ##### ######## ##### #######
0599: * <---^ ^
0600: * lower(i=2) upper(i=5)
0601: */
0602: i0--;
0603: }
0604: } else {
0605: if ((i0 & 1) == 0) {
0606: i0--;
0607: }
0608: }
0609: /*
0610: * A ce stade, on est certain que 'i0' est impair et pointe vers la fin
0611: * d'une plage dans le tableau. Fait maintenant le traitement pour 'i1'.
0612: */
0613: if (i1 < 0) {
0614: /*
0615: * Si la date de fin tombe dans une des plages déjà existantes
0616: * (si son index est impair), on change la date de début de la
0617: * plage existante. Visuellement, on fait:
0618: *
0619: * 0 1 2 3 4 5 6 7
0620: * ##### ######## --### #######
0621: * ^ ^
0622: * lower(i=3) upper(i=5)
0623: */
0624: if (((i1 = ~i1) & 1) != 0) { // Attention: c'est ~ et non -
0625: modCount++;
0626: Array.set(array, --i1, upper);
0627: } else {
0628: /*
0629: * Si la date de fin ne tombe pas dans une plage déjà existante, il
0630: * faudra (plus tard) supprimer les éventuelles plages qui le précède.
0631: *
0632: * 0 1 2 3 4 5 6 7
0633: * ##### ######## ####### ###########
0634: * ^ ^
0635: * lower(i=3) upper(i=6)
0636: */
0637: // nothing to do
0638: }
0639: } else {
0640: i1 &= ~1;
0641: }
0642: /*
0643: * A ce stade, on est certain que 'i1' est pair et pointe vers la début
0644: * de la plage dans le tableau. On va maintenant supprimer tout ce qui
0645: * se trouve entre 'i0' et 'i1', à l'exclusion de 'i0' et 'i1'.
0646: */
0647: assert (i0 & 1) != 0 : i0;
0648: assert (i1 & 1) == 0 : i1;
0649: final int n = i1 - (++i0);
0650: if (n > 0) {
0651: modCount++;
0652: final Object old = array;
0653: final int length = Array.getLength(array);
0654: array = Array.newInstance(elementType, length - n);
0655: System.arraycopy(old, 0, array, 0, i0);
0656: System.arraycopy(old, i1, array, i0, length - i1);
0657: }
0658: assert (Array.getLength(array) & 1) == 0;
0659: return modCountChk != modCount;
0660: }
0661:
0662: /**
0663: * Remove a range of values from this set. Range may be removed in any order.
0664: *
0665: * @param lower The lower value to remove, exclusive.
0666: * @param upper The upper value to remove, exclusive.
0667: * @return {@code true} if this set changed as a result of the call.
0668: * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}.
0669: */
0670: public boolean remove(byte lower, byte upper)
0671: throws IllegalArgumentException {
0672: return remove(new Byte(lower), new Byte(upper));
0673: }
0674:
0675: /**
0676: * Remove a range of values from this set. Range may be removed in any order.
0677: *
0678: * @param lower The lower value to remove, exclusive.
0679: * @param upper The upper value to remove, exclusive.
0680: * @return {@code true} if this set changed as a result of the call.
0681: * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}.
0682: */
0683: public boolean remove(short lower, short upper)
0684: throws IllegalArgumentException {
0685: return remove(new Short(lower), new Short(upper));
0686: }
0687:
0688: /**
0689: * Remove a range of values from this set. Range may be removed in any order.
0690: *
0691: * @param lower The lower value to remove, exclusive.
0692: * @param upper The upper value to remove, exclusive.
0693: * @return {@code true} if this set changed as a result of the call.
0694: * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}.
0695: */
0696: public boolean remove(int lower, int upper)
0697: throws IllegalArgumentException {
0698: return remove(new Integer(lower), new Integer(upper));
0699: }
0700:
0701: /**
0702: * Remove a range of values from this set. Range may be removed in any order.
0703: *
0704: * @param lower The lower value to remove, exclusive.
0705: * @param upper The upper value to remove, exclusive.
0706: * @return {@code true} if this set changed as a result of the call.
0707: * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}.
0708: */
0709: public boolean remove(long lower, long upper)
0710: throws IllegalArgumentException {
0711: return remove(new Long(lower), new Long(upper));
0712: }
0713:
0714: /**
0715: * Remove a range of values from this set. Range may be removed in any order.
0716: *
0717: * @param lower The lower value to remove, exclusive.
0718: * @param upper The upper value to remove, exclusive.
0719: * @return {@code true} if this set changed as a result of the call.
0720: * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}.
0721: */
0722: public boolean remove(float lower, float upper)
0723: throws IllegalArgumentException {
0724: return remove(new Float(lower), new Float(upper));
0725: }
0726:
0727: /**
0728: * Remove a range of values from this set. Range may be removed in any order.
0729: *
0730: * @param lower The lower value to remove, exclusive.
0731: * @param upper The upper value to remove, exclusive.
0732: * @return {@code true} if this set changed as a result of the call.
0733: * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}.
0734: */
0735: public boolean remove(double lower, double upper)
0736: throws IllegalArgumentException {
0737: return remove(new Double(lower), new Double(upper));
0738: }
0739:
0740: /**
0741: * Retourne l'index de l'élément {@code value} dans le tableau {@code array}.
0742: * Cette méthode interprète le tableau {@code array} comme un tableau d'un des types
0743: * intrinsèques du Java, et appelle la méthode {@code Arrays.binarySearch} appropriée.
0744: *
0745: * @param value The value to search. This value must have been converted with
0746: * {@link #toNumber} prior to call this method.
0747: */
0748: private int binarySearch(final Comparable value) {
0749: switch (indexType) {
0750: case DOUBLE:
0751: return Arrays.binarySearch((double[]) array,
0752: ((Number) value).doubleValue());
0753: case FLOAT:
0754: return Arrays.binarySearch((float[]) array,
0755: ((Number) value).floatValue());
0756: case LONG:
0757: return Arrays.binarySearch((long[]) array, ((Number) value)
0758: .longValue());
0759: case INTEGER:
0760: return Arrays.binarySearch((int[]) array, ((Number) value)
0761: .intValue());
0762: case SHORT:
0763: return Arrays.binarySearch((short[]) array,
0764: ((Number) value).shortValue());
0765: case BYTE:
0766: return Arrays.binarySearch((byte[]) array, ((Number) value)
0767: .byteValue());
0768: case CHARACTER:
0769: return Arrays.binarySearch((char[]) array,
0770: ((Character) value).charValue());
0771: default:
0772: return Arrays.binarySearch((Object[]) array, value);
0773: }
0774: }
0775:
0776: /**
0777: * Wrap the specified value in a number, if needed.
0778: */
0779: private Comparable toNumber(Comparable value) {
0780: assert type.isAssignableFrom(value.getClass()) : value;
0781: if (useClassChanger)
0782: try {
0783: value = (Comparable) ClassChanger.toNumber(value);
0784: } catch (ClassNotFoundException exception) {
0785: // Should not happen since the constructor should have make sure
0786: // that this operation is legal for value of class 'type'.
0787: final ClassCastException e = new ClassCastException(
0788: value.getClass().getName());
0789: e.initCause(exception);
0790: throw e;
0791: }
0792: return value;
0793: }
0794:
0795: /**
0796: * Returns a new {@link Range} object initialized with the given values.
0797: *
0798: * @param lower The lower value, inclusive.
0799: * @param upper The upper value, inclusive.
0800: */
0801: private Range newRange(final Comparable lower,
0802: final Comparable upper) {
0803: if (isNumeric) {
0804: return new NumberRange(type, lower, upper);
0805: } else {
0806: return new Range(type, lower, upper);
0807: }
0808: }
0809:
0810: /**
0811: * Returns the value at the specified index.
0812: * Even index are lower bounds, while odd index are upper bounds.
0813: */
0814: private Comparable get(final int index) {
0815: Comparable value = (Comparable) Array.get(array, index);
0816: if (useClassChanger)
0817: try {
0818: value = ClassChanger.toComparable((Number) value, type);
0819: } catch (ClassNotFoundException exception) {
0820: // Should not happen, since class type should
0821: // have been checked by all 'add(...)' methods
0822: final ClassCastException e = new ClassCastException(
0823: value.getClass().getName());
0824: e.initCause(exception);
0825: throw e;
0826: }
0827: return value;
0828: }
0829:
0830: /**
0831: * Returns a {@linkplain Range#getMinValue range's minimum value} as a {@code double}.
0832: * The {@code index} can be any value from 0 inclusive to the set's {@link #size size}
0833: * exclusive. The returned values always increase with {@code index}.
0834: *
0835: * @param index The range index, from 0 inclusive to {@link #size size} exclusive.
0836: * @return The minimum value for the range at the specified index.
0837: * @throws IndexOutOfBoundsException if {@code index} is out of bounds.
0838: * @throws ClassCastException if range elements are not convertible to numbers.
0839: */
0840: public final double getMinValueAsDouble(int index)
0841: throws IndexOutOfBoundsException, ClassCastException {
0842: index *= 2;
0843: return (isPrimitive) ? Array.getDouble(array, index)
0844: : ((Number) Array.get(array, index)).doubleValue();
0845: }
0846:
0847: /**
0848: * Returns a {@linkplain Range#getMaxValue range's maximum value} as a {@code double}.
0849: * The {@code index} can be any value from 0 inclusive to the set's {@link #size size}
0850: * exclusive. The returned values always increase with {@code index}.
0851: *
0852: * @param index The range index, from 0 inclusive to {@link #size size} exclusive.
0853: * @return The maximum value for the range at the specified index.
0854: * @throws IndexOutOfBoundsException if {@code index} is out of bounds.
0855: * @throws ClassCastException if range elements are not convertible to numbers.
0856: */
0857: public final double getMaxValueAsDouble(int index)
0858: throws IndexOutOfBoundsException, ClassCastException {
0859: index = 2 * index + 1;
0860: return (isPrimitive) ? Array.getDouble(array, index)
0861: : ((Number) Array.get(array, index)).doubleValue();
0862: }
0863:
0864: /**
0865: * If the specified value is inside a range, returns the index of this range.
0866: * Otherwise, returns {@code -1}.
0867: *
0868: * @param value The value to search.
0869: * @return The index of the range which contains this value, or -1 if there is no such range.
0870: */
0871: public int indexOfRange(final Comparable value) {
0872: int index = binarySearch(toNumber(value));
0873: if (index < 0) {
0874: // Found an insertion point. Make sure that the insertion
0875: // point is inside a range (i.e. before the maximum value).
0876: index = ~index; // Tild sign, not minus.
0877: if ((index & 1) == 0) {
0878: return -1;
0879: }
0880: }
0881: index /= 2; // Round toward 0 (odd index are maximum values).
0882: assert newRange(get(2 * index), get(2 * index + 1)).contains(
0883: value) : value;
0884: return index;
0885: }
0886:
0887: /**
0888: * Returns {@code true} if this set contains the specified element.
0889: */
0890: public boolean contains(final Object object) {
0891: final Range range = (Range) object;
0892: if (type.equals(range.getElementClass())) {
0893: if (range.isMinIncluded() && range.isMaxIncluded()) {
0894: final int index = binarySearch(toNumber(range
0895: .getMinValue()));
0896: if (index >= 0 && (index & 1) == 0) {
0897: return get(index + 1)
0898: .compareTo(range.getMaxValue()) == 0;
0899: }
0900: }
0901: }
0902: return false;
0903: }
0904:
0905: /**
0906: * Returns the first (lowest) range currently in this sorted set.
0907: *
0908: * @throws NoSuchElementException if the set is empty.
0909: */
0910: public Object first() throws NoSuchElementException {
0911: if (array != null && Array.getLength(array) != 0) {
0912: return newRange(get(0), get(1));
0913: }
0914: throw new NoSuchElementException();
0915: }
0916:
0917: /**
0918: * Returns the last (highest) range currently in this sorted set.
0919: *
0920: * @throws NoSuchElementException if the set is empty.
0921: */
0922: public Object last() throws NoSuchElementException {
0923: if (array != null) {
0924: final int length = Array.getLength(array);
0925: if (length != 0) {
0926: return newRange(get(length - 2), get(length - 1));
0927: }
0928: }
0929: throw new NoSuchElementException();
0930: }
0931:
0932: /**
0933: * Returns a view of the portion of this sorted set whose elements range
0934: * from {@code lower}, inclusive, to {@code upper}, exclusive.
0935: *
0936: * @param lower Low endpoint (inclusive) of the sub set.
0937: * @param upper High endpoint (exclusive) of the sub set.
0938: * @return A view of the specified range within this sorted set.
0939: */
0940: public SortedSet subSet(final Object lower, final Object upper) {
0941: throw new UnsupportedOperationException("Not yet implemented");
0942: }
0943:
0944: /**
0945: * Returns a view of the portion of this sorted set whose elements are
0946: * strictly less than {@code upper}.
0947: *
0948: * @param upper High endpoint (exclusive) of the headSet.
0949: * @return A view of the specified initial range of this sorted set.
0950: */
0951: public SortedSet headSet(final Object upper) {
0952: throw new UnsupportedOperationException("Not yet implemented");
0953: }
0954:
0955: /**
0956: * Returns a view of the portion of this sorted set whose elements are
0957: * greater than or equal to {@code lower}.
0958: *
0959: * @param lower Low endpoint (inclusive) of the tailSet.
0960: * @return A view of the specified final range of this sorted set.
0961: */
0962: public SortedSet tailSet(final Object lower) {
0963: throw new UnsupportedOperationException("Not yet implemented");
0964: }
0965:
0966: /**
0967: * Returns an iterator over the elements in this set of ranges.
0968: * All elements are {@link Range} objects.
0969: */
0970: public java.util.Iterator iterator() {
0971: return new Iterator();
0972: }
0973:
0974: /**
0975: * An iterator for iterating through ranges in a {@link RangeSet}.
0976: * All elements are {@link Range} objects.
0977: *
0978: * @version $Id: RangeSet.java 22443 2006-10-27 20:47:22Z desruisseaux $
0979: * @author Martin Desruisseaux
0980: */
0981: private final class Iterator implements java.util.Iterator {
0982: /**
0983: * Modification count at construction time.
0984: */
0985: private int modCount = RangeSet.this .modCount;
0986:
0987: /**
0988: * The array length.
0989: */
0990: private int length = (array != null) ? Array.getLength(array)
0991: : 0;
0992:
0993: /**
0994: * Current position in {@link RangeSet#array}.
0995: */
0996: private int position;
0997:
0998: /**
0999: * Returns {@code true} if the iteration has more elements.
1000: */
1001: public boolean hasNext() {
1002: return position < length;
1003: }
1004:
1005: /**
1006: * Returns the next element in the iteration.
1007: */
1008: public Object next() {
1009: if (hasNext()) {
1010: final Comparable lower = get(position++);
1011: final Comparable upper = get(position++);
1012: if (RangeSet.this .modCount != modCount) {
1013: // Check it last, in case a change occured
1014: // while we was constructing the element.
1015: throw new ConcurrentModificationException();
1016: }
1017: return newRange(lower, upper);
1018: }
1019: throw new NoSuchElementException();
1020: }
1021:
1022: /**
1023: * Removes from the underlying collection the
1024: * last element returned by the iterator.
1025: */
1026: public void remove() {
1027: if (position != 0) {
1028: if (RangeSet.this .modCount == modCount) {
1029: final Object newArray = Array.newInstance(
1030: elementType, length -= 2);
1031: System.arraycopy(array, position, newArray,
1032: position -= 2, length - position);
1033: System.arraycopy(array, 0, newArray, 0, position);
1034: array = newArray;
1035: modCount = ++RangeSet.this .modCount;
1036: } else {
1037: throw new ConcurrentModificationException();
1038: }
1039: } else {
1040: throw new IllegalStateException();
1041: }
1042: }
1043: }
1044:
1045: /**
1046: * Returns a hash value for this set of ranges.
1047: * This value need not remain consistent between
1048: * different implementations of the same class.
1049: */
1050: public int hashCode() {
1051: int code = type.hashCode();
1052: if (array != null) {
1053: for (int i = Array.getLength(array); (i -= 8) >= 0;) {
1054: code = code * 37 + Array.get(array, i).hashCode();
1055: }
1056: }
1057: return code;
1058: }
1059:
1060: /**
1061: * Compares the specified object with
1062: * this set of ranges for equality.
1063: */
1064: public boolean equals(final Object object) {
1065: if (object != null && object.getClass().equals(getClass())) {
1066: final RangeSet that = (RangeSet) object;
1067: if (Utilities.equals(this .type, that.type)) {
1068: switch (indexType) {
1069: case DOUBLE:
1070: return Arrays.equals((double[]) this .array,
1071: (double[]) that.array);
1072: case FLOAT:
1073: return Arrays.equals((float[]) this .array,
1074: (float[]) that.array);
1075: case LONG:
1076: return Arrays.equals((long[]) this .array,
1077: (long[]) that.array);
1078: case INTEGER:
1079: return Arrays.equals((int[]) this .array,
1080: (int[]) that.array);
1081: case SHORT:
1082: return Arrays.equals((short[]) this .array,
1083: (short[]) that.array);
1084: case BYTE:
1085: return Arrays.equals((byte[]) this .array,
1086: (byte[]) that.array);
1087: case CHARACTER:
1088: return Arrays.equals((char[]) this .array,
1089: (char[]) that.array);
1090: default:
1091: return Arrays.equals((Object[]) this .array,
1092: (Object[]) that.array);
1093: }
1094: }
1095: }
1096: return false;
1097: }
1098:
1099: /**
1100: * Returns a clone of this range set.
1101: */
1102: public Object clone() {
1103: try {
1104: final RangeSet set = (RangeSet) super .clone();
1105: switch (set.indexType) {
1106: case DOUBLE:
1107: set.array = ((double[]) set.array).clone();
1108: break;
1109: case FLOAT:
1110: set.array = ((float[]) set.array).clone();
1111: break;
1112: case LONG:
1113: set.array = ((long[]) set.array).clone();
1114: break;
1115: case INTEGER:
1116: set.array = ((int[]) set.array).clone();
1117: break;
1118: case SHORT:
1119: set.array = ((short[]) set.array).clone();
1120: break;
1121: case BYTE:
1122: set.array = ((byte[]) set.array).clone();
1123: break;
1124: case CHARACTER:
1125: set.array = ((char[]) set.array).clone();
1126: break;
1127: default:
1128: set.array = ((Object[]) set.array).clone();
1129: break;
1130: }
1131: return set;
1132: } catch (CloneNotSupportedException exception) {
1133: // Should not happen, since we are cloneable.
1134: throw new AssertionError(exception);
1135: }
1136: }
1137:
1138: /**
1139: * Returns a string representation of this set of ranges.
1140: * The returned string is implementation dependent.
1141: * It is usually provided for debugging purposes.
1142: */
1143: public String toString() {
1144: final StringBuffer buffer = new StringBuffer(Utilities
1145: .getShortClassName(this ));
1146: buffer.append('[');
1147: boolean first = true;
1148: for (java.util.Iterator it = iterator(); it.hasNext();) {
1149: final Range range = (Range) it.next();
1150: if (!first) {
1151: buffer.append(',');
1152: }
1153: buffer.append('{');
1154: buffer.append(range.getMinValue());
1155: buffer.append("..");
1156: buffer.append(range.getMaxValue());
1157: buffer.append('}');
1158: first = false;
1159: }
1160: buffer.append(']');
1161: return buffer.toString();
1162: }
1163: }
|