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.LongList; | 33 import com.google.protobuf.Internal.LongList; |
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 LongList} on top of a primitive array. | 40 * An implementation of {@link LongList} 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 LongArrayList | 44 final class LongArrayList extends AbstractProtobufList<Long> implements LongList
, RandomAccess { |
45 extends AbstractProtobufList<Long> | 45 |
46 implements LongList, RandomAccess { | |
47 | |
48 private static final LongArrayList EMPTY_LIST = new LongArrayList(); | 46 private static final LongArrayList EMPTY_LIST = new LongArrayList(); |
49 static { | 47 static { |
50 EMPTY_LIST.makeImmutable(); | 48 EMPTY_LIST.makeImmutable(); |
51 } | 49 } |
52 | 50 |
53 public static LongArrayList emptyList() { | 51 public static LongArrayList 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 long[] array; | 58 private long[] 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 LongArrayList} with default capacity. | 67 * Constructs a new mutable {@code LongArrayList} with default capacity. |
70 */ | 68 */ |
71 LongArrayList() { | 69 LongArrayList() { |
72 this(new long[DEFAULT_CAPACITY], 0); | 70 this(new long[DEFAULT_CAPACITY], 0); |
73 } | 71 } |
74 | 72 |
75 /** | 73 /** |
76 * Constructs a new mutable {@code LongArrayList} | 74 * Constructs a new mutable {@code LongArrayList} containing the same elements
as {@code other}. |
77 * containing the same elements as {@code other}. | |
78 */ | 75 */ |
79 private LongArrayList(long[] other, int size) { | 76 private LongArrayList(long[] 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 LongArrayList)) { | 86 if (!(o instanceof IntArrayList)) { |
90 return super.equals(o); | 87 return super.equals(o); |
91 } | 88 } |
92 LongArrayList other = (LongArrayList) o; | 89 LongArrayList other = (LongArrayList) o; |
93 if (size != other.size) { | 90 if (size != other.size) { |
94 return false; | 91 return false; |
95 } | 92 } |
96 | 93 |
97 final long[] arr = other.array; | 94 final long[] 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) + Internal.hashLong(array[i]); | 108 result = (31 * result) + Internal.hashLong(array[i]); |
112 } | 109 } |
113 return result; | 110 return result; |
114 } | 111 } |
115 | 112 |
116 @Override | 113 @Override |
117 public LongList mutableCopyWithCapacity(int capacity) { | 114 public LongList mutableCopyWithCapacity(int capacity) { |
118 if (capacity < size) { | 115 if (capacity < size) { |
119 throw new IllegalArgumentException(); | 116 throw new IllegalArgumentException(); |
120 } | 117 } |
121 return new LongArrayList(Arrays.copyOf(array, capacity), size); | 118 return new LongArrayList(Arrays.copyOf(array, capacity), size); |
122 } | 119 } |
123 | 120 |
124 @Override | 121 @Override |
125 public Long get(int index) { | 122 public Long get(int index) { |
126 return getLong(index); | 123 return getLong(index); |
127 } | 124 } |
128 | 125 |
129 @Override | 126 @Override |
130 public long getLong(int index) { | 127 public long getLong(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, Long)} but more efficient in that it doesn't box the
element. | 165 * Like {@link #add(int, Long)} but more efficient in that it doesn't box the
element. |
169 */ | 166 */ |
170 private void addLong(int index, long element) { | 167 private void addLong(int index, long 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 long[] newArray = new long[length]; | 179 long[] newArray = new long[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 Long> collection) { | 195 public boolean addAll(Collection<? extends Long> 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 LongArrayList to avoid boxing elements. | 202 // We specialize when adding another LongArrayList to avoid boxing elements. |
206 if (!(collection instanceof LongArrayList)) { | 203 if (!(collection instanceof LongArrayList)) { |
207 return super.addAll(collection); | 204 return super.addAll(collection); |
208 } | 205 } |
209 | 206 |
210 LongArrayList list = (LongArrayList) collection; | 207 LongArrayList list = (LongArrayList) 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 Long remove(int index) { | 244 public Long remove(int index) { |
248 ensureIsMutable(); | 245 ensureIsMutable(); |
249 ensureIndexInRange(index); | 246 ensureIndexInRange(index); |
250 long value = array[index]; | 247 long 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 |