Coverage Report - com.sun.javafx.runtime.sequence.SequenceMutator
 
Classes in this File Line Coverage Branch Coverage Complexity
SequenceMutator
96%
122/127
91%
93/102
0
SequenceMutator$Listener
N/A
N/A
0
 
 1  
 /*
 2  
  * Copyright 2007 Sun Microsystems, Inc.  All Rights Reserved.
 3  
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 4  
  *
 5  
  * This code is free software; you can redistribute it and/or modify it
 6  
  * under the terms of the GNU General Public License version 2 only, as
 7  
  * published by the Free Software Foundation.  Sun designates this
 8  
  * particular file as subject to the "Classpath" exception as provided
 9  
  * by Sun in the LICENSE file that accompanied this code.
 10  
  *
 11  
  * This code is distributed in the hope that it will be useful, but WITHOUT
 12  
  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 13  
  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 14  
  * version 2 for more details (a copy is included in the LICENSE file that
 15  
  * accompanied this code).
 16  
  *
 17  
  * You should have received a copy of the GNU General Public License version
 18  
  * 2 along with this work; if not, write to the Free Software Foundation,
 19  
  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 20  
  *
 21  
  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
 22  
  * CA 95054 USA or visit www.sun.com if you need additional information or
 23  
  * have any questions.
 24  
  */
 25  
 
 26  
 package com.sun.javafx.runtime.sequence;
 27  
 
 28  
 import java.util.BitSet;
 29  
 
 30  
 /**
 31  
  * Helper methods for modifying sequences and notifying sequence change listeners.  The helper methods only call the
 32  
  * sequence trigger methods; if the underlying sequence is modified then the caller is responsible for
 33  
  * calling the onChanged() method.
 34  
  *
 35  
  * @author Brian Goetz
 36  
  */
 37  91
 public class SequenceMutator {
 38  
 
 39  
     public interface Listener<T> {
 40  
         public void onReplaceSlice(int startPos, int endPos, Sequence<? extends T> newElements, Sequence<T> oldValue, Sequence<T> newValue);
 41  
     }
 42  
 
 43  
     // Inhibit instantiation
 44  0
     private SequenceMutator() {
 45  0
     }
 46  
 
 47  
     /**
 48  
      * The core sequence mutation operation is slice replacement.  A slice is represented by (start, end) indexes, which
 49  
      * are _inclusive_.  The length of a slice is end-start+1.
 50  
      *
 51  
      * A one-element slice at position p is represented (p, p).   The empty slice before element p is represented
 52  
      * by (p, p-1).  The empty slice after the last element is represented by (len, len-1) where len is the length
 53  
      * of the sequence.
 54  
      *
 55  
      * Inserting elements into the sequence is performed by replacing an empty slice with a non-empty slice.
 56  
      * Deleting elements from the sequence is performed by replacing a non-empty slice with an empty slice.
 57  
      * Replacing elements in the sequence is performed by replacing a non-empty slice with another non-empty one.
 58  
      *
 59  
      * @param target The sequence in which the slice is being replaced
 60  
      * @param listener A sequence listener which will be notified, may be null
 61  
      * @param startPos Starting position of the slice, inclusive, may be 0..size
 62  
      * @param endPos Ending position of the slice, inclusive, may be start-1..size
 63  
      * @param newValues Values to be inserted, may be null
 64  
      * @return The new sequence.
 65  
      */
 66  
     public static <T> Sequence<T> replaceSlice(Sequence<T> target, Listener<T> listener,
 67  
                                                int startPos, int endPos, Sequence<? extends T> newValues) {
 68  
         Sequence<T> result;
 69  7343
         Class<T> elementType = target.getElementType();
 70  7343
         int size = Sequences.size(target);
 71  
 
 72  7343
         if (startPos > size || startPos < 0)
 73  587
             return target;
 74  
 
 75  6756
         if (endPos < startPos-1)
 76  1
             endPos = startPos-1;
 77  6755
         else if (endPos > size)
 78  41
             endPos = size;
 79  
 
 80  6756
         if (startPos == endPos + 1) {
 81  
             // Insertion at startPos
 82  3945
             if (Sequences.size(newValues) == 0)
 83  420
                 result = target;
 84  3525
             else if (startPos == 0)
 85  903
                 result = Sequences.concatenate(elementType, newValues, target);
 86  2622
             else if (startPos == size)
 87  2361
                 result = Sequences.concatenate(elementType, target, newValues);
 88  
             else
 89  261
                 result = Sequences.concatenate(elementType,
 90  
                         target.subsequence(0, startPos), newValues, target.subsequence(startPos, size));
 91  
         }
 92  2811
         else if (Sequences.size(newValues) == 0) {
 93  1136
             if (newValues == null)
 94  83
                 newValues = Sequences.emptySequence(target.getElementType());
 95  
             // Deletion from startPos to endPos inclusive
 96  1136
             if (endPos == startPos-1)
 97  0
                 result = target;
 98  1136
             else if (endPos >= size-1)
 99  363
                 result = target.subsequence(0, startPos);
 100  773
             else if (startPos == 0)
 101  400
                 result = target.subsequence(endPos+1, size);
 102  
             else {
 103  
                 // @@@ OPT: Consider a range-delete sequence type
 104  373
                 BitSet bits = new BitSet(size);
 105  373
                 bits.set(0, size);
 106  373
                 bits.clear(startPos, endPos+1);
 107  373
                 result = Sequences.filter(target, bits);
 108  373
             }
 109  
         }
 110  1675
         else if (startPos <= endPos) {
 111  
             // Replacement
 112  
             // @@@ OPT: Special-case for replacing leading or trailing slices
 113  1675
             result = Sequences.concatenate(elementType, target.subsequence(0, startPos), newValues, target.subsequence(endPos+1, size));
 114  
         }
 115  
         else
 116  0
             throw new IllegalArgumentException();
 117  
 
 118  6756
         if (result != target && shouldFlatten(result))
 119  4052
             result = result.flatten();
 120  
 
 121  6756
         if (result != target && listener != null)
 122  4831
             listener.onReplaceSlice(startPos, endPos, newValues, target, result);
 123  6756
         return result;
 124  
     }
 125  
 
 126  
     /**
 127  
      * Optimized version of replaceSlice where sizeof newValues == 1.
 128  
      */
 129  
     public static <T> Sequence<T> replaceSlice(Sequence<T> target, Listener<T> listener,
 130  
                                                int startPos, int endPos, T newValue) {
 131  4313
         int size = Sequences.size(target);
 132  4313
         if (startPos > size || startPos < 0)
 133  13
             return target;
 134  4300
         if (newValue == null)
 135  2
             return replaceSlice(target, listener, startPos, endPos, Sequences.emptySequence(target.getElementType()));
 136  
 
 137  
         Sequence<T> result;
 138  4298
         Sequence<T> singleton = Sequences.singleton(target.getElementType(), newValue);
 139  
 
 140  
         // @@@ OPT: Consider a single-element insert sequence type
 141  4298
         if (startPos == endPos) {
 142  2132
             result = new ReplacementSequence<T>(target, startPos, newValue);
 143  2132
             if (shouldFlatten(result)) {
 144  376
                 result = result.flatten();
 145  
             }
 146  2132
             if (listener != null) {
 147  2122
                 listener.onReplaceSlice(startPos, endPos, singleton, target, result);
 148  
             }
 149  
         } else {
 150  2166
             result = replaceSlice(target, listener, startPos, endPos, singleton);
 151  
         }
 152  4298
         return result;
 153  
     }
 154  
 
 155  
     /**
 156  
      * Modify the element at the specified position.  If the position is out of range, the sequence is not
 157  
      * modified.
 158  
      */
 159  
     public static <T> Sequence<T> set(Sequence<T> target, Listener<T> listener, int position, T value) {
 160  2138
         return replaceSlice(target, listener, position, position, value);
 161  
     }
 162  
 
 163  
     /**
 164  
      * Delete the element at the specified position.  If the position is out of range, the sequence is not modified.
 165  
      */
 166  
     public static <T> Sequence<T> delete(Sequence<T> target, Listener<T> listener, int position) {
 167  572
         return replaceSlice(target, listener, position, position, Sequences.emptySequence(target.getElementType()));
 168  
     }
 169  
 
 170  
     /**
 171  
      * Insert the specified value at the end of the sequence
 172  
      */
 173  
     public static <T> Sequence<T> insert(Sequence<T> target, Listener<T> listener, T value) {
 174  2026
         return replaceSlice(target, listener, target.size(), target.size()-1, value);
 175  
     }
 176  
 
 177  
     /**
 178  
      * Insert the specified values at the end of the sequence
 179  
      */
 180  
     public static <T> Sequence<T> insert(Sequence<T> target, Listener<T> listener, Sequence<? extends T> values) {
 181  36
         return replaceSlice(target, listener, target.size(), target.size()-1, values);
 182  
     }
 183  
 
 184  
     /**
 185  
      * Insert the specified value at the beginning of the sequence
 186  
      */
 187  
     public static <T> Sequence<T> insertFirst(Sequence<T> target, Listener<T> listener, T value) {
 188  52
         return replaceSlice(target, listener, 0, -1, value);
 189  
     }
 190  
 
 191  
     /**
 192  
      * Insert the specified values at the beginning of the sequence
 193  
      */
 194  
     public static <T> Sequence<T> insertFirst(Sequence<T> target, Listener<T> listener, Sequence<? extends T> values) {
 195  32
         return replaceSlice(target, listener, 0, -1, values);
 196  
     }
 197  
 
 198  
     /**
 199  
      * Insert the specified value before the specified position.  If the position is negative, it is inserted before
 200  
      * element zero; if it is greater than or equal to the size of the sequence, it is inserted at the end.
 201  
      */
 202  
     public static <T> Sequence<T> insertBefore(Sequence<T> target, Listener<T> listener,
 203  
                                                T value, int position) {
 204  
         // Extra validity check needed for insertBefore
 205  53
         if (position > target.size())
 206  0
             return target;
 207  
         else
 208  53
             return replaceSlice(target, listener, position, position-1, value);
 209  
     }
 210  
 
 211  
     /**
 212  
      * Insert the specified values before the specified position.  If the position is negative, they are inserted before
 213  
      * element zero; if it is greater than or equal to the size of the sequence, they are inserted at the end.
 214  
      */
 215  
     public static <T> Sequence<T> insertBefore(Sequence<T> target, Listener<T> listener,
 216  
                                                Sequence<? extends T> values, int position) {
 217  
         // Extra validity check needed for insertBefore
 218  244
         if (position > target.size())
 219  80
             return target;
 220  
         else
 221  164
             return replaceSlice(target, listener, position, position-1, values);
 222  
     }
 223  
 
 224  
     /**
 225  
      * Insert the specified value after the specified position.  If the position is negative, it is inserted before
 226  
      * element zero; if it is greater than or equal to the size of the sequence, it is inserted at the end.
 227  
      */
 228  
     public static <T> Sequence<T> insertAfter(Sequence<T> target, Listener<T> listener,
 229  
                                               T value, int position) {
 230  54
         if (position < 0 || position >= target.size())
 231  10
             return target;
 232  
         else
 233  44
             return replaceSlice(target, listener, position+1, position, value);
 234  
     }
 235  
 
 236  
     /**
 237  
      * Insert the specified values after the specified position.  If the position is negative, they are inserted before
 238  
      * element zero; if it is greater than or equal to the size of the sequence, they are inserted at the end.
 239  
      */
 240  
     public static <T> Sequence<T> insertAfter(Sequence<T> target, Listener<T> listener,
 241  
                                               Sequence<? extends T> values, int position) {
 242  244
         return replaceSlice(target, listener, position+1, position, values);
 243  
     }
 244  
 
 245  
     /**
 246  
      * Delete the elements matching the specified predicate.
 247  
      */
 248  
     public static <T> Sequence<T> delete(Sequence<T> target, Listener<T> listener,
 249  
                                          SequencePredicate<? super T> predicate) {
 250  661
         BitSet bits = target.getBits(predicate);
 251  661
         if (bits.cardinality() == 0)
 252  467
             return target;
 253  194
         bits.flip(0, target.size());
 254  194
         Sequence<T> result = Sequences.filter(target, bits);
 255  194
         if (listener != null) {
 256  135
             Sequence<T> lastValue = target;
 257  135
             BitSet partialBits = new BitSet(target.size());
 258  135
             partialBits.flip(0, target.size());
 259  1507
             for (int i = target.size() - 1; i >= 0; i--) {
 260  
                 // @@@ OPT: Collapse adjacent bits into ranges
 261  1372
                 if (!bits.get(i)) {
 262  309
                     partialBits.flip(i);
 263  309
                     Sequence<T> nextValue = Sequences.filter(target, partialBits);
 264  309
                     listener.onReplaceSlice(i, i, Sequences.emptySequence(target.getElementType()), lastValue, nextValue);
 265  309
                     lastValue = nextValue;
 266  
                 }
 267  
             }
 268  
         }
 269  194
         return result;
 270  
     }
 271  
 
 272  
     /**
 273  
      * Insert the specified value before the position(s) matching the specified predicate.
 274  
      */
 275  
     public static <T> Sequence<T> insertBefore(Sequence<T> target, Listener<T> listener,
 276  
                                                T value, SequencePredicate<? super T> predicate) {
 277  38
         BitSet bits = target.getBits(predicate);
 278  38
         if (bits.cardinality() == 0)
 279  8
             return target;
 280  30
         else if (bits.cardinality() == 1)
 281  17
             return insertBefore(target, listener, value, bits.nextSetBit(0));
 282  
         else
 283  13
             return multiInsertBefore(target, listener, bits, Sequences.singleton(target.getElementType(), value));
 284  
     }
 285  
 
 286  
     /**
 287  
      * Insert the specified values before the position(s) matching the specified predicate.
 288  
      */
 289  
     public static <T> Sequence<T> insertBefore(Sequence<T> target, Listener<T> listener,
 290  
                                                Sequence<? extends T> values, SequencePredicate<? super T> predicate) {
 291  33
         BitSet bits = target.getBits(predicate);
 292  33
         if (bits.cardinality() == 0)
 293  8
             return target;
 294  25
         else if (bits.cardinality() == 1)
 295  16
             return insertBefore(target, listener, values, bits.nextSetBit(0));
 296  
         else
 297  9
             return multiInsertBefore(target, listener, bits, values);
 298  
     }
 299  
 
 300  
     /**
 301  
      * Insert the specified value after the position(s) matching the specified predicate.
 302  
      */
 303  
     public static <T> Sequence<T> insertAfter(Sequence<T> target, Listener<T> listener,
 304  
                                               T value, SequencePredicate<? super T> predicate) {
 305  38
         BitSet bits = target.getBits(predicate);
 306  38
         if (bits.cardinality() == 0)
 307  8
             return target;
 308  30
         else if (bits.cardinality() == 1)
 309  17
             return insertAfter(target, listener, value, bits.nextSetBit(0));
 310  
         else
 311  13
             return multiInsertAfter(target, listener, bits, Sequences.singleton(target.getElementType(), value));
 312  
     }
 313  
 
 314  
     /**
 315  
      * Insert the specified values after the position(s) matching the specified predicate.
 316  
      */
 317  
     public static <T> Sequence<T> insertAfter(Sequence<T> target, Listener<T> listener,
 318  
                                               Sequence<? extends T> values, SequencePredicate<? super T> predicate) {
 319  33
         BitSet bits = target.getBits(predicate);
 320  33
         if (bits.cardinality() == 0)
 321  8
             return target;
 322  25
         else if (bits.cardinality() == 1)
 323  16
             return insertAfter(target, listener, values, bits.nextSetBit(0));
 324  
         else
 325  9
             return multiInsertAfter(target, listener, bits, values);
 326  
     }
 327  
 
 328  
     /*
 329  
     * Precondition: bits.cardinality() > 1
 330  
     */
 331  
     private static <T> Sequence<T> multiInsertBefore(Sequence<T> target, Listener<T> listener,
 332  
                                                      BitSet bits, Sequence<? extends T> values) {
 333  22
         assert (bits.cardinality() > 1);
 334  22
         Sequence<T> nextValue = target;
 335  22
         int firstBit = bits.nextSetBit(0);
 336  22
         int curPos = firstBit > 0 ? firstBit : 0;
 337  77
         for (int i = firstBit, j = bits.nextSetBit(i + 1); i >= 0; i = j, j = bits.nextSetBit(j + 1)) {
 338  55
             nextValue = replaceSlice(nextValue, listener, curPos, curPos-1, values);
 339  55
             curPos += ((j > 0) ? (j - i) : (target.size() - i)) + Sequences.size(values);
 340  
         }
 341  22
         return nextValue;
 342  
     }
 343  
 
 344  
     /*
 345  
      * Precondition: bits.cardinality() > 1
 346  
      */
 347  
     private static <T> Sequence<T> multiInsertAfter(Sequence<T> target, Listener<T> listener,
 348  
                                                     BitSet bits, Sequence<? extends T> values) {
 349  22
         assert (bits.cardinality() > 1);
 350  22
         Sequence<T> nextValue = target;
 351  74
         for (int j = bits.nextSetBit(0), iteration=0; j >= 0; j = bits.nextSetBit(j + 1), iteration++) {
 352  52
             int curPos = j + (iteration * Sequences.size(values)) + 1;
 353  52
             nextValue = replaceSlice(nextValue, listener, curPos, curPos-1, values);
 354  
         }
 355  22
         return nextValue;
 356  
     }
 357  
 
 358  
     private static<T> boolean shouldFlatten(Sequence<T> sequence) {
 359  
         // If the sequence is short or if the sequence is is too thin,
 360  
         // then copy it.
 361  8401
         int size = Sequences.size(sequence);
 362  8401
         return ((0 < size) && (size <= Sequences.FLATTENING_THRESHOLD))
 363  
                 || (sequence.getDepth() > Math.log((double) size));
 364  
     }
 365  
 
 366  
 }