| OLD | NEW |
| 1 // Protocol Buffers - Google's data interchange format | 1 // Protocol Buffers - Google's data interchange format |
| 2 // Copyright 2008 Google Inc. All rights reserved. | 2 // Copyright 2008 Google Inc. All rights reserved. |
| 3 // https://developers.google.com/protocol-buffers/ | 3 // https://developers.google.com/protocol-buffers/ |
| 4 // | 4 // |
| 5 // Redistribution and use in source and binary forms, with or without | 5 // Redistribution and use in source and binary forms, with or without |
| 6 // modification, are permitted provided that the following conditions are | 6 // modification, are permitted provided that the following conditions are |
| 7 // met: | 7 // met: |
| 8 // | 8 // |
| 9 // * Redistributions of source code must retain the above copyright | 9 // * Redistributions of source code must retain the above copyright |
| 10 // notice, this list of conditions and the following disclaimer. | 10 // notice, this list of conditions and the following disclaimer. |
| (...skipping 20 matching lines...) Expand all Loading... |
| 31 package com.google.protobuf; | 31 package com.google.protobuf; |
| 32 | 32 |
| 33 import com.google.protobuf.Internal.IntList; | 33 import com.google.protobuf.Internal.IntList; |
| 34 | 34 |
| 35 import java.util.Arrays; | 35 import java.util.Arrays; |
| 36 import java.util.Collection; | 36 import java.util.Collection; |
| 37 import java.util.RandomAccess; | 37 import java.util.RandomAccess; |
| 38 | 38 |
| 39 /** | 39 /** |
| 40 * An implementation of {@link IntList} on top of a primitive array. | 40 * An implementation of {@link IntList} on top of a primitive array. |
| 41 * | 41 * |
| 42 * @author dweis@google.com (Daniel Weis) | 42 * @author dweis@google.com (Daniel Weis) |
| 43 */ | 43 */ |
| 44 final class IntArrayList | 44 final class IntArrayList extends AbstractProtobufList<Integer> implements IntLis
t, RandomAccess { |
| 45 extends AbstractProtobufList<Integer> | 45 |
| 46 implements IntList, RandomAccess { | |
| 47 | |
| 48 private static final IntArrayList EMPTY_LIST = new IntArrayList(); | 46 private static final IntArrayList EMPTY_LIST = new IntArrayList(); |
| 49 static { | 47 static { |
| 50 EMPTY_LIST.makeImmutable(); | 48 EMPTY_LIST.makeImmutable(); |
| 51 } | 49 } |
| 52 | 50 |
| 53 public static IntArrayList emptyList() { | 51 public static IntArrayList emptyList() { |
| 54 return EMPTY_LIST; | 52 return EMPTY_LIST; |
| 55 } | 53 } |
| 56 | 54 |
| 57 /** | 55 /** |
| 58 * The backing store for the list. | 56 * The backing store for the list. |
| 59 */ | 57 */ |
| 60 private int[] array; | 58 private int[] array; |
| 61 | 59 |
| 62 /** | 60 /** |
| 63 * The size of the list distinct from the length of the array. That is, it is
the number of | 61 * The size of the list distinct from the length of the array. That is, it is
the number of |
| 64 * elements set in the list. | 62 * elements set in the list. |
| 65 */ | 63 */ |
| 66 private int size; | 64 private int size; |
| 67 | 65 |
| 68 /** | 66 /** |
| 69 * Constructs a new mutable {@code IntArrayList} with default capacity. | 67 * Constructs a new mutable {@code IntArrayList} with default capacity. |
| 70 */ | 68 */ |
| 71 IntArrayList() { | 69 IntArrayList() { |
| 72 this(new int[DEFAULT_CAPACITY], 0); | 70 this(new int[DEFAULT_CAPACITY], 0); |
| 73 } | 71 } |
| 74 | 72 |
| 75 /** | 73 /** |
| 76 * Constructs a new mutable {@code IntArrayList} | 74 * Constructs a new mutable {@code IntArrayList} containing the same elements
as {@code other}. |
| 77 * containing the same elements as {@code other}. | |
| 78 */ | 75 */ |
| 79 private IntArrayList(int[] other, int size) { | 76 private IntArrayList(int[] array, int size) { |
| 80 array = other; | 77 this.array = array; |
| 81 this.size = size; | 78 this.size = size; |
| 82 } | 79 } |
| 83 | 80 |
| 84 @Override | 81 @Override |
| 85 public boolean equals(Object o) { | 82 public boolean equals(Object o) { |
| 86 if (this == o) { | 83 if (this == o) { |
| 87 return true; | 84 return true; |
| 88 } | 85 } |
| 89 if (!(o instanceof IntArrayList)) { | 86 if (!(o instanceof IntArrayList)) { |
| 90 return super.equals(o); | 87 return super.equals(o); |
| 91 } | 88 } |
| 92 IntArrayList other = (IntArrayList) o; | 89 IntArrayList other = (IntArrayList) o; |
| 93 if (size != other.size) { | 90 if (size != other.size) { |
| 94 return false; | 91 return false; |
| 95 } | 92 } |
| 96 | 93 |
| 97 final int[] arr = other.array; | 94 final int[] arr = other.array; |
| 98 for (int i = 0; i < size; i++) { | 95 for (int i = 0; i < size; i++) { |
| 99 if (array[i] != arr[i]) { | 96 if (array[i] != arr[i]) { |
| 100 return false; | 97 return false; |
| 101 } | 98 } |
| 102 } | 99 } |
| 103 | 100 |
| 104 return true; | 101 return true; |
| 105 } | 102 } |
| 106 | 103 |
| 107 @Override | 104 @Override |
| 108 public int hashCode() { | 105 public int hashCode() { |
| 109 int result = 1; | 106 int result = 1; |
| 110 for (int i = 0; i < size; i++) { | 107 for (int i = 0; i < size; i++) { |
| 111 result = (31 * result) + array[i]; | 108 result = (31 * result) + array[i]; |
| 112 } | 109 } |
| 113 return result; | 110 return result; |
| 114 } | 111 } |
| 115 | 112 |
| 116 @Override | 113 @Override |
| 117 public IntList mutableCopyWithCapacity(int capacity) { | 114 public IntList mutableCopyWithCapacity(int capacity) { |
| 118 if (capacity < size) { | 115 if (capacity < size) { |
| 119 throw new IllegalArgumentException(); | 116 throw new IllegalArgumentException(); |
| 120 } | 117 } |
| 121 return new IntArrayList(Arrays.copyOf(array, capacity), size); | 118 return new IntArrayList(Arrays.copyOf(array, capacity), size); |
| 122 } | 119 } |
| 123 | 120 |
| 124 @Override | 121 @Override |
| 125 public Integer get(int index) { | 122 public Integer get(int index) { |
| 126 return getInt(index); | 123 return getInt(index); |
| 127 } | 124 } |
| 128 | 125 |
| 129 @Override | 126 @Override |
| 130 public int getInt(int index) { | 127 public int getInt(int index) { |
| 131 ensureIndexInRange(index); | 128 ensureIndexInRange(index); |
| 132 return array[index]; | 129 return array[index]; |
| 133 } | 130 } |
| (...skipping 31 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 165 } | 162 } |
| 166 | 163 |
| 167 /** | 164 /** |
| 168 * Like {@link #add(int, Integer)} but more efficient in that it doesn't box t
he element. | 165 * Like {@link #add(int, Integer)} but more efficient in that it doesn't box t
he element. |
| 169 */ | 166 */ |
| 170 private void addInt(int index, int element) { | 167 private void addInt(int index, int element) { |
| 171 ensureIsMutable(); | 168 ensureIsMutable(); |
| 172 if (index < 0 || index > size) { | 169 if (index < 0 || index > size) { |
| 173 throw new IndexOutOfBoundsException(makeOutOfBoundsExceptionMessage(index)
); | 170 throw new IndexOutOfBoundsException(makeOutOfBoundsExceptionMessage(index)
); |
| 174 } | 171 } |
| 175 | 172 |
| 176 if (size < array.length) { | 173 if (size < array.length) { |
| 177 // Shift everything over to make room | 174 // Shift everything over to make room |
| 178 System.arraycopy(array, index, array, index + 1, size - index); | 175 System.arraycopy(array, index, array, index + 1, size - index); |
| 179 } else { | 176 } else { |
| 180 // Resize to 1.5x the size | 177 // Resize to 1.5x the size |
| 181 int length = ((size * 3) / 2) + 1; | 178 int length = ((size * 3) / 2) + 1; |
| 182 int[] newArray = new int[length]; | 179 int[] newArray = new int[length]; |
| 183 | 180 |
| 184 // Copy the first part directly | 181 // Copy the first part directly |
| 185 System.arraycopy(array, 0, newArray, 0, index); | 182 System.arraycopy(array, 0, newArray, 0, index); |
| 186 | 183 |
| 187 // Copy the rest shifted over by one to make room | 184 // Copy the rest shifted over by one to make room |
| 188 System.arraycopy(array, index, newArray, index + 1, size - index); | 185 System.arraycopy(array, index, newArray, index + 1, size - index); |
| 189 array = newArray; | 186 array = newArray; |
| 190 } | 187 } |
| 191 | 188 |
| 192 array[index] = element; | 189 array[index] = element; |
| 193 size++; | 190 size++; |
| 194 modCount++; | 191 modCount++; |
| 195 } | 192 } |
| 196 | 193 |
| 197 @Override | 194 @Override |
| 198 public boolean addAll(Collection<? extends Integer> collection) { | 195 public boolean addAll(Collection<? extends Integer> collection) { |
| 199 ensureIsMutable(); | 196 ensureIsMutable(); |
| 200 | 197 |
| 201 if (collection == null) { | 198 if (collection == null) { |
| 202 throw new NullPointerException(); | 199 throw new NullPointerException(); |
| 203 } | 200 } |
| 204 | 201 |
| 205 // We specialize when adding another IntArrayList to avoid boxing elements. | 202 // We specialize when adding another IntArrayList to avoid boxing elements. |
| 206 if (!(collection instanceof IntArrayList)) { | 203 if (!(collection instanceof IntArrayList)) { |
| 207 return super.addAll(collection); | 204 return super.addAll(collection); |
| 208 } | 205 } |
| 209 | 206 |
| 210 IntArrayList list = (IntArrayList) collection; | 207 IntArrayList list = (IntArrayList) collection; |
| 211 if (list.size == 0) { | 208 if (list.size == 0) { |
| 212 return false; | 209 return false; |
| 213 } | 210 } |
| 214 | 211 |
| 215 int overflow = Integer.MAX_VALUE - size; | 212 int overflow = Integer.MAX_VALUE - size; |
| 216 if (overflow < list.size) { | 213 if (overflow < list.size) { |
| 217 // We can't actually represent a list this large. | 214 // We can't actually represent a list this large. |
| 218 throw new OutOfMemoryError(); | 215 throw new OutOfMemoryError(); |
| 219 } | 216 } |
| 220 | 217 |
| 221 int newSize = size + list.size; | 218 int newSize = size + list.size; |
| 222 if (newSize > array.length) { | 219 if (newSize > array.length) { |
| 223 array = Arrays.copyOf(array, newSize); | 220 array = Arrays.copyOf(array, newSize); |
| 224 } | 221 } |
| 225 | 222 |
| 226 System.arraycopy(list.array, 0, array, size, list.size); | 223 System.arraycopy(list.array, 0, array, size, list.size); |
| 227 size = newSize; | 224 size = newSize; |
| 228 modCount++; | 225 modCount++; |
| 229 return true; | 226 return true; |
| 230 } | 227 } |
| 231 | 228 |
| 232 @Override | 229 @Override |
| 233 public boolean remove(Object o) { | 230 public boolean remove(Object o) { |
| 234 ensureIsMutable(); | 231 ensureIsMutable(); |
| 235 for (int i = 0; i < size; i++) { | 232 for (int i = 0; i < size; i++) { |
| 236 if (o.equals(array[i])) { | 233 if (o.equals(array[i])) { |
| 237 System.arraycopy(array, i + 1, array, i, size - i); | 234 System.arraycopy(array, i + 1, array, i, size - i); |
| 238 size--; | 235 size--; |
| 239 modCount++; | 236 modCount++; |
| 240 return true; | 237 return true; |
| 241 } | 238 } |
| 242 } | 239 } |
| 243 return false; | 240 return false; |
| 244 } | 241 } |
| 245 | 242 |
| 246 @Override | 243 @Override |
| 247 public Integer remove(int index) { | 244 public Integer remove(int index) { |
| 248 ensureIsMutable(); | 245 ensureIsMutable(); |
| 249 ensureIndexInRange(index); | 246 ensureIndexInRange(index); |
| 250 int value = array[index]; | 247 int value = array[index]; |
| 251 System.arraycopy(array, index + 1, array, index, size - index); | 248 System.arraycopy(array, index + 1, array, index, size - index); |
| 252 size--; | 249 size--; |
| 253 modCount++; | 250 modCount++; |
| 254 return value; | 251 return value; |
| 255 } | 252 } |
| 256 | 253 |
| 257 /** | 254 /** |
| 258 * Ensures that the provided {@code index} is within the range of {@code [0, s
ize]}. Throws an | 255 * Ensures that the provided {@code index} is within the range of {@code [0, s
ize]}. Throws an |
| 259 * {@link IndexOutOfBoundsException} if it is not. | 256 * {@link IndexOutOfBoundsException} if it is not. |
| 260 * | 257 * |
| 261 * @param index the index to verify is in range | 258 * @param index the index to verify is in range |
| 262 */ | 259 */ |
| 263 private void ensureIndexInRange(int index) { | 260 private void ensureIndexInRange(int index) { |
| 264 if (index < 0 || index >= size) { | 261 if (index < 0 || index >= size) { |
| 265 throw new IndexOutOfBoundsException(makeOutOfBoundsExceptionMessage(index)
); | 262 throw new IndexOutOfBoundsException(makeOutOfBoundsExceptionMessage(index)
); |
| 266 } | 263 } |
| 267 } | 264 } |
| 268 | 265 |
| 269 private String makeOutOfBoundsExceptionMessage(int index) { | 266 private String makeOutOfBoundsExceptionMessage(int index) { |
| 270 return "Index:" + index + ", Size:" + size; | 267 return "Index:" + index + ", Size:" + size; |
| 271 } | 268 } |
| 272 } | 269 } |
| OLD | NEW |