[cvs] / jsr166 / src / main / java / util / Vector.java Repository:
ViewVC logotype

Diff of /jsr166/src/main/java/util/Vector.java

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 1.9, Sun Mar 19 17:59:39 2006 UTC revision 1.10, Wed Apr 19 15:07:14 2006 UTC
# Line 1  Line 1 
1  /*  /*
2   * %W% %E%   * @(#)Vector.java      1.103 05/12/06
3   *   *
4   * Copyright 2006 Sun Microsystems, Inc. All rights reserved.   * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
5   * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.   * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
# Line 49  Line 49 
49   *   *
50   * @author  Lee Boynton   * @author  Lee Boynton
51   * @author  Jonathan Payne   * @author  Jonathan Payne
52   * @version %I%, %G%   * @version 1.103, 12/06/05
53   * @see Collection   * @see Collection
54   * @see List   * @see List
55   * @see ArrayList   * @see ArrayList
# Line 952  Line 952 
952      }      }
953    
954      /**      /**
      * Returns a view of the portion of this List between fromIndex,  
      * inclusive, and toIndex, exclusive.  (If fromIndex and toIndex are  
      * equal, the returned List is empty.)  The returned List is backed by this  
      * List, so changes in the returned List are reflected in this List, and  
      * vice-versa.  The returned List supports all of the optional List  
      * operations supported by this List.<p>  
      *  
      * This method eliminates the need for explicit range operations (of  
      * the sort that commonly exist for arrays).   Any operation that expects  
      * a List can be used as a range operation by operating on a subList view  
      * instead of a whole List.  For example, the following idiom  
      * removes a range of elements from a List:  
      * <pre>  
      *      list.subList(from, to).clear();  
      * </pre>  
      * Similar idioms may be constructed for indexOf and lastIndexOf,  
      * and all of the algorithms in the Collections class can be applied to  
      * a subList.<p>  
      *  
      * The semantics of the List returned by this method become undefined if  
      * the backing list (i.e., this List) is <i>structurally modified</i> in  
      * any way other than via the returned List.  (Structural modifications are  
      * those that change the size of the List, or otherwise perturb it in such  
      * a fashion that iterations in progress may yield incorrect results.)  
      *  
      * @param fromIndex low endpoint (inclusive) of the subList  
      * @param toIndex high endpoint (exclusive) of the subList  
      * @return a view of the specified range within this List  
      * @throws IndexOutOfBoundsException endpoint index value out of range  
      *         <code>(fromIndex &lt; 0 || toIndex &gt; size)</code>  
      * @throws IllegalArgumentException endpoint indices out of order  
      *         <code>(fromIndex &gt; toIndex)</code>  
      */  
     public synchronized List<E> subList(int fromIndex, int toIndex) {  
         return Collections.synchronizedList(super.subList(fromIndex, toIndex),  
                                             this);  
     }  
   
     /**  
955       * Removes from this List all of the elements whose index is between       * Removes from this List all of the elements whose index is between
956       * fromIndex, inclusive and toIndex, exclusive.  Shifts any succeeding       * fromIndex, inclusive and toIndex, exclusive.  Shifts any succeeding
957       * elements to the left (reduces their index).       * elements to the left (reduces their index).
958       * This call shortens the ArrayList by (toIndex - fromIndex) elements.  (If       * This call shortens the Vector by (toIndex - fromIndex) elements.  (If
959       * toIndex==fromIndex, this operation has no effect.)       * toIndex==fromIndex, this operation has no effect.)
960       *       *
961       * @param fromIndex index of first element to be removed       * @param fromIndex index of first element to be removed
# Line 1026  Line 987 
987      /**      /**
988       * Returns a list-iterator of the elements in this list (in proper       * Returns a list-iterator of the elements in this list (in proper
989       * sequence), starting at the specified position in the list.       * sequence), starting at the specified position in the list.
990       * Obeys the general contract of <tt>List.listIterator(int)</tt>.<p>       * Obeys the general contract of {@link List#listIterator(int)}.
991       *       *
992       * The list-iterator is <i>fail-fast</i>: if the list is structurally       * <p>The list-iterator is <i>fail-fast</i>: if the list is structurally
993       * modified at any time after the Iterator is created, in any way except       * modified at any time after the Iterator is created, in any way except
994       * through the list-iterator's own <tt>remove</tt> or <tt>add</tt>       * through the list-iterator's own {@code remove} or {@code add}
995       * methods, the list-iterator will throw a       * methods, the list-iterator will throw a
996       * <tt>ConcurrentModificationException</tt>.  Thus, in the face of       * {@code ConcurrentModificationException}.  Thus, in the face of
997       * concurrent modification, the iterator fails quickly and cleanly, rather       * concurrent modification, the iterator fails quickly and cleanly, rather
998       * than risking arbitrary, non-deterministic behavior at an undetermined       * than risking arbitrary, non-deterministic behavior at an undetermined
999       * time in the future.       * time in the future.
1000       *       *
1001       * @param index index of the first element to be returned from the       * @param index index of the first element to be returned from the
1002       *              list-iterator (by a call to <tt>next</tt>)       *        list-iterator (by a call to {@link ListIterator#next})
1003       * @return a ListIterator of the elements in this list (in proper       * @return a list-iterator of the elements in this list (in proper
1004       *         sequence), starting at the specified position in the list       *         sequence), starting at the specified position in the list
1005       * @throws IndexOutOfBoundsException {@inheritDoc}       * @throws IndexOutOfBoundsException {@inheritDoc}
      * @see List#listIterator(int)  
1006       */       */
1007      public synchronized ListIterator<E> listIterator(int index) {      public synchronized ListIterator<E> listIterator(int index) {
1008          if (index < 0 || index > elementCount)          if (index < 0 || index > elementCount)
1009              throw new IndexOutOfBoundsException("Index: "+index);              throw new IndexOutOfBoundsException("Index: "+index);
1010          return new VectorIterator(index);          return new VectorIterator(index, elementCount);
1011      }      }
1012    
1013      /**      /**
1014       * {@inheritDoc}       * {@inheritDoc}
1015       */       */
1016      public synchronized ListIterator<E> listIterator() {      public synchronized ListIterator<E> listIterator() {
1017          return new VectorIterator(0);          return new VectorIterator(0, elementCount);
1018      }      }
1019    
1020      /**      /**
# Line 1063  Line 1023 
1023       * @return an iterator over the elements in this list in proper sequence       * @return an iterator over the elements in this list in proper sequence
1024       */       */
1025      public synchronized Iterator<E> iterator() {      public synchronized Iterator<E> iterator() {
1026          return new VectorIterator(0);          return new VectorIterator(0, elementCount);
1027        }
1028    
1029        /**
1030         * Helper method to access array elements under synchronization by
1031         * iterators. The caller performs index check with respect to
1032         * expected bounds, so errors accessing the element are reported
1033         * as ConcurrentModificationExceptions.
1034         */
1035        final synchronized Object iteratorGet(int index, int expectedModCount) {
1036            if (modCount == expectedModCount) {
1037                try {
1038                    return elementData[index];
1039                } catch(IndexOutOfBoundsException fallThrough) {
1040                }
1041            }
1042            throw new ConcurrentModificationException();
1043      }      }
1044    
1045      /**      /**
1046       * A streamlined version of AbstractList.ListItr.       * Streamlined specialization of AbstractList version of iterator.
1047         * Locally perfroms bounds checks, but relies on outer Vector
1048         * to access elements under synchronization.
1049       */       */
1050      private final class VectorIterator implements ListIterator<E> {      private final class VectorIterator implements ListIterator<E> {
1051          int cursor;                // current position          int cursor;              // Index of next element to return;
1052          int lastRet;               // index of last returned element          int fence;               // Upper bound on cursor (cache of size())
1053          int expectedModCount;      // to check for CME          int lastRet;             // Index of last element, or -1 if no such
1054            int expectedModCount;    // To check for CME
1055          VectorIterator(int index) {  
1056              cursor = index;          VectorIterator(int index, int fence) {
1057              expectedModCount = modCount;              this.cursor = index;
1058              lastRet = -1;              this.fence = fence;
1059                this.lastRet = -1;
1060                this.expectedModCount = Vector.this.modCount;
1061          }          }
1062    
1063          public boolean hasNext() {          public boolean hasNext() {
1064              // Racy but within spec, since modifications are checked              return cursor < fence;
             // within or after synchronization in next/previous  
             return cursor != elementCount;  
1065          }          }
1066    
1067          public boolean hasPrevious() {          public boolean hasPrevious() {
1068              return cursor != 0;              return cursor > 0;
1069          }          }
1070    
1071          public int nextIndex() {          public int nextIndex() {
# Line 1099  Line 1077 
1077          }          }
1078    
1079          public E next() {          public E next() {
             try {  
1080                  int i = cursor;                  int i = cursor;
1081                  E next = get(i);              if (i >= fence)
1082                    throw new NoSuchElementException();
1083                Object next = Vector.this.iteratorGet(i, expectedModCount);
1084                  lastRet = i;                  lastRet = i;
1085                  cursor = i + 1;                  cursor = i + 1;
1086                  return next;              return (E)next;
             } catch (IndexOutOfBoundsException ex) {  
                 throw new NoSuchElementException();  
             } finally {  
                 if (expectedModCount != modCount)  
                     throw new ConcurrentModificationException();  
             }  
1087          }          }
1088    
1089          public E previous() {          public E previous() {
             try {  
1090                  int i = cursor - 1;                  int i = cursor - 1;
1091                  E prev = get(i);              if (i < 0)
1092                    throw new NoSuchElementException();
1093                Object prev = Vector.this.iteratorGet(i, expectedModCount);
1094                  lastRet = i;                  lastRet = i;
1095                  cursor = i;                  cursor = i;
1096                  return prev;              return (E)prev;
1097            }
1098    
1099            public void set(E e) {
1100                if (lastRet < 0)
1101                    throw new IllegalStateException();
1102                if (Vector.this.modCount != expectedModCount)
1103                    throw new ConcurrentModificationException();
1104                try {
1105                    Vector.this.set(lastRet, e);
1106                    expectedModCount = Vector.this.modCount;
1107              } catch (IndexOutOfBoundsException ex) {              } catch (IndexOutOfBoundsException ex) {
                 throw new NoSuchElementException();  
             } finally {  
                 if (expectedModCount != modCount)  
1108                      throw new ConcurrentModificationException();                      throw new ConcurrentModificationException();
1109              }              }
1110          }          }
1111    
1112          public void remove() {          public void remove() {
1113              if (lastRet == -1)              int i = lastRet;
1114                if (i < 0)
1115                  throw new IllegalStateException();                  throw new IllegalStateException();
1116              if (expectedModCount != modCount)              if (Vector.this.modCount != expectedModCount)
1117                  throw new ConcurrentModificationException();                  throw new ConcurrentModificationException();
1118              try {              try {
1119                  Vector.this.remove(lastRet);                  Vector.this.remove(i);
1120                  if (lastRet < cursor)                  if (i < cursor)
1121                      cursor--;                      cursor--;
1122                  lastRet = -1;                  lastRet = -1;
1123                  expectedModCount = modCount;                  fence = Vector.this.size();
1124                    expectedModCount = Vector.this.modCount;
1125              } catch (IndexOutOfBoundsException ex) {              } catch (IndexOutOfBoundsException ex) {
1126                  throw new ConcurrentModificationException();                  throw new ConcurrentModificationException();
1127              }              }
1128          }          }
1129    
1130            public void add(E e) {
1131                if (Vector.this.modCount != expectedModCount)
1132                    throw new ConcurrentModificationException();
1133                try {
1134                    int i = cursor;
1135                    Vector.this.add(i, e);
1136                    cursor = i + 1;
1137                    lastRet = -1;
1138                    fence = Vector.this.size();
1139                    expectedModCount = Vector.this.modCount;
1140                } catch (IndexOutOfBoundsException ex) {
1141                    throw new ConcurrentModificationException();
1142                }
1143            }
1144        }
1145    
1146        /**
1147         * Returns a view of the portion of this List between fromIndex,
1148         * inclusive, and toIndex, exclusive.  (If fromIndex and toIndex are
1149         * equal, the returned List is empty.)  The returned List is backed by this
1150         * List, so changes in the returned List are reflected in this List, and
1151         * vice-versa.  The returned List supports all of the optional List
1152         * operations supported by this List.<p>
1153         *
1154         * This method eliminates the need for explicit range operations (of
1155         * the sort that commonly exist for arrays).   Any operation that expects
1156         * a List can be used as a range operation by operating on a subList view
1157         * instead of a whole List.  For example, the following idiom
1158         * removes a range of elements from a List:
1159         * <pre>
1160         *      list.subList(from, to).clear();
1161         * </pre>
1162         * Similar idioms may be constructed for indexOf and lastIndexOf,
1163         * and all of the algorithms in the Collections class can be applied to
1164         * a subList.<p>
1165         *
1166         * The semantics of the List returned by this method become undefined if
1167         * the backing list (i.e., this List) is <i>structurally modified</i> in
1168         * any way other than via the returned List.  (Structural modifications are
1169         * those that change the size of the List, or otherwise perturb it in such
1170         * a fashion that iterations in progress may yield incorrect results.)
1171         *
1172         * @param fromIndex low endpoint (inclusive) of the subList
1173         * @param toIndex high endpoint (exclusive) of the subList
1174         * @return a view of the specified range within this List
1175         * @throws IndexOutOfBoundsException endpoint index value out of range
1176         *         <code>(fromIndex &lt; 0 || toIndex &gt; size)</code>
1177         * @throws IllegalArgumentException endpoint indices out of order
1178         *         <code>(fromIndex &gt; toIndex)</code>
1179         */
1180        public synchronized List<E> subList(int fromIndex, int toIndex) {
1181            return new VectorSubList(this, this, fromIndex, fromIndex, toIndex);
1182        }
1183    
1184        /**
1185         * This class specializes the AbstractList version of SubList to
1186         * avoid the double-indirection penalty that would arise using a
1187         * synchronized wrapper, as well as to avoid some unnecessary
1188         * checks in sublist iterators.
1189         */
1190        private static final class VectorSubList<E> extends AbstractList<E> implements RandomAccess {
1191            final Vector<E> base;             // base list
1192            final AbstractList<E> parent;     // Creating list
1193            final int baseOffset;             // index wrt Vector
1194            final int parentOffset;           // index wrt parent
1195            int length;                       // length of sublist
1196    
1197            VectorSubList(Vector<E> base, AbstractList<E> parent, int baseOffset,
1198                         int fromIndex, int toIndex) {
1199                if (fromIndex < 0)
1200                    throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
1201                if (toIndex > parent.size())
1202                    throw new IndexOutOfBoundsException("toIndex = " + toIndex);
1203                if (fromIndex > toIndex)
1204                    throw new IllegalArgumentException("fromIndex(" + fromIndex +
1205                                                       ") > toIndex(" + toIndex + ")");
1206    
1207                this.base = base;
1208                this.parent = parent;
1209                this.baseOffset = baseOffset;
1210                this.parentOffset = fromIndex;
1211                this.length = toIndex - fromIndex;
1212                modCount = base.modCount;
1213            }
1214    
1215            /**
1216             * Returns an IndexOutOfBoundsException with nicer message
1217             */
1218            private IndexOutOfBoundsException indexError(int index) {
1219                return new IndexOutOfBoundsException("Index: " + index +
1220                                                     ", Size: " + length);
1221            }
1222    
1223            public E set(int index, E element) {
1224                synchronized(base) {
1225                    if (index < 0 || index >= length)
1226                        throw indexError(index);
1227                    if (base.modCount != modCount)
1228                        throw new ConcurrentModificationException();
1229                    return base.set(index + baseOffset, element);
1230                }
1231            }
1232    
1233            public E get(int index) {
1234                synchronized(base) {
1235                    if (index < 0 || index >= length)
1236                        throw indexError(index);
1237                    if (base.modCount != modCount)
1238                        throw new ConcurrentModificationException();
1239                    return base.get(index + baseOffset);
1240                }
1241            }
1242    
1243            public int size() {
1244                synchronized(base) {
1245                    if (base.modCount != modCount)
1246                        throw new ConcurrentModificationException();
1247                    return length;
1248                }
1249            }
1250    
1251            public void add(int index, E element) {
1252                synchronized(base) {
1253                    if (index < 0 || index > length)
1254                        throw indexError(index);
1255                    if (base.modCount != modCount)
1256                        throw new ConcurrentModificationException();
1257                    parent.add(index + parentOffset, element);
1258                    length++;
1259                    modCount = base.modCount;
1260                }
1261            }
1262    
1263            public E remove(int index) {
1264                synchronized(base) {
1265                    if (index < 0 || index >= length)
1266                        throw indexError(index);
1267                    if (base.modCount != modCount)
1268                        throw new ConcurrentModificationException();
1269                    E result = parent.remove(index + parentOffset);
1270                    length--;
1271                    modCount = base.modCount;
1272                    return result;
1273                }
1274            }
1275    
1276            protected void removeRange(int fromIndex, int toIndex) {
1277                synchronized(base) {
1278                    if (base.modCount != modCount)
1279                        throw new ConcurrentModificationException();
1280                    parent.removeRange(fromIndex + parentOffset,
1281                                       toIndex + parentOffset);
1282                    length -= (toIndex-fromIndex);
1283                    modCount = base.modCount;
1284                }
1285            }
1286    
1287            public boolean addAll(Collection<? extends E> c) {
1288                return addAll(length, c);
1289            }
1290    
1291            public boolean addAll(int index, Collection<? extends E> c) {
1292                synchronized(base) {
1293                    if (index < 0 || index > length)
1294                        throw indexError(index);
1295                    int cSize = c.size();
1296                    if (cSize==0)
1297                        return false;
1298    
1299                    if (base.modCount != modCount)
1300                        throw new ConcurrentModificationException();
1301                    parent.addAll(parentOffset + index, c);
1302                    modCount = base.modCount;
1303                    length += cSize;
1304                    return true;
1305                }
1306            }
1307    
1308            public boolean equals(Object o) {
1309                synchronized(base) {return super.equals(o);}
1310            }
1311    
1312            public int hashCode() {
1313                synchronized(base) {return super.hashCode();}
1314            }
1315    
1316            public int indexOf(Object o) {
1317                synchronized(base) {return super.indexOf(o);}
1318            }
1319    
1320            public int lastIndexOf(Object o) {
1321                synchronized(base) {return super.lastIndexOf(o);}
1322            }
1323    
1324            public List<E> subList(int fromIndex, int toIndex) {
1325                return new VectorSubList(base, this, fromIndex + baseOffset,
1326                                         fromIndex, toIndex);
1327            }
1328    
1329            public Iterator<E> iterator() {
1330                synchronized(base) {
1331                    return new VectorSubListIterator(this, 0);
1332                }
1333            }
1334    
1335            public synchronized ListIterator<E> listIterator() {
1336                synchronized(base) {
1337                    return new VectorSubListIterator(this, 0);
1338                }
1339            }
1340    
1341            public ListIterator<E> listIterator(int index) {
1342                synchronized(base) {
1343                    if (index < 0 || index > length)
1344                        throw indexError(index);
1345                    return new VectorSubListIterator(this, index);
1346                }
1347            }
1348    
1349            /**
1350             * Same idea as VectorIterator, except routing structural
1351             * change operations through the sublist.
1352             */
1353            private static final class VectorSubListIterator<E> implements ListIterator<E> {
1354                final Vector<E> base;         // base list
1355                final VectorSubList<E> outer; // Sublist creating this iteraor
1356                final int offset;             // cursor offset wrt base
1357                int cursor;                   // Current index
1358                int fence;                    // Upper bound on cursor
1359                int lastRet;                  // Index of returned element, or -1
1360                int expectedModCount;         // Expected modCount of base Vector
1361    
1362                VectorSubListIterator(VectorSubList<E> list, int index) {
1363                    this.lastRet = -1;
1364                    this.cursor = index;
1365                    this.outer = list;
1366                    this.offset = list.baseOffset;
1367                    this.fence = list.length;
1368                    this.base = list.base;
1369                    this.expectedModCount = base.modCount;
1370                }
1371    
1372                public boolean hasNext() {
1373                    return cursor < fence;
1374                }
1375    
1376                public boolean hasPrevious() {
1377                    return cursor > 0;
1378                }
1379    
1380                public int nextIndex() {
1381                    return cursor;
1382                }
1383    
1384                public int previousIndex() {
1385                    return cursor - 1;
1386                }
1387    
1388                public E next() {
1389                    int i = cursor;
1390                    if (cursor >= fence)
1391                        throw new NoSuchElementException();
1392                    Object next = base.iteratorGet(i + offset, expectedModCount);
1393                    lastRet = i;
1394                    cursor = i + 1;
1395                    return (E)next;
1396                }
1397    
1398                public E previous() {
1399                    int i = cursor - 1;
1400                    if (i < 0)
1401                        throw new NoSuchElementException();
1402                    Object prev = base.iteratorGet(i + offset, expectedModCount);
1403                    lastRet = i;
1404                    cursor = i;
1405                    return (E)prev;
1406                }
1407    
1408          public void set(E e) {          public void set(E e) {
1409              if (lastRet == -1)                  if (lastRet < 0)
1410                  throw new IllegalStateException();                  throw new IllegalStateException();
1411              if (expectedModCount != modCount)                  if (base.modCount != expectedModCount)
1412                  throw new ConcurrentModificationException();                  throw new ConcurrentModificationException();
1413              try {              try {
1414                  Vector.this.set(lastRet, e);                      outer.set(lastRet, e);
1415                  expectedModCount = modCount;                      expectedModCount = base.modCount;
1416                    } catch (IndexOutOfBoundsException ex) {
1417                        throw new ConcurrentModificationException();
1418                    }
1419                }
1420    
1421                public void remove() {
1422                    int i = lastRet;
1423                    if (i < 0)
1424                        throw new IllegalStateException();
1425                    if (base.modCount != expectedModCount)
1426                        throw new ConcurrentModificationException();
1427                    try {
1428                        outer.remove(i);
1429                        if (i < cursor)
1430                            cursor--;
1431                        lastRet = -1;
1432                        fence = outer.length;
1433                        expectedModCount = base.modCount;
1434              } catch (IndexOutOfBoundsException ex) {              } catch (IndexOutOfBoundsException ex) {
1435                  throw new ConcurrentModificationException();                  throw new ConcurrentModificationException();
1436              }              }
1437          }          }
1438    
1439          public void add(E e) {          public void add(E e) {
1440              if (expectedModCount != modCount)                  if (base.modCount != expectedModCount)
1441                  throw new ConcurrentModificationException();                  throw new ConcurrentModificationException();
1442              try {              try {
1443                  int i = cursor;                  int i = cursor;
1444                  Vector.this.add(i, e);                      outer.add(i, e);
1445                  cursor = i + 1;                  cursor = i + 1;
1446                  lastRet = -1;                  lastRet = -1;
1447                  expectedModCount = modCount;                      fence = outer.length;
1448                        expectedModCount = base.modCount;
1449              } catch (IndexOutOfBoundsException ex) {              } catch (IndexOutOfBoundsException ex) {
1450                  throw new ConcurrentModificationException();                  throw new ConcurrentModificationException();
1451              }              }
1452          }          }
1453      }      }
1454  }  }
1455    }
1456    
1457    
1458    

Legend:
Removed from v.1.9  
changed lines
  Added in v.1.10

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8