1 // Protocol Buffers - Google's data interchange format 2 // Copyright 2008 Google Inc. All rights reserved. 3 // https://developers.google.com/protocol-buffers/ 4 // 5 // Redistribution and use in source and binary forms, with or without 6 // modification, are permitted provided that the following conditions are 7 // met: 8 // 9 // * Redistributions of source code must retain the above copyright 10 // notice, this list of conditions and the following disclaimer. 11 // * Redistributions in binary form must reproduce the above 12 // copyright notice, this list of conditions and the following disclaimer 13 // in the documentation and/or other materials provided with the 14 // distribution. 15 // * Neither the name of Google Inc. nor the names of its 16 // contributors may be used to endorse or promote products derived from 17 // this software without specific prior written permission. 18 // 19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 31 package com.google.protobuf; 32 33 import com.google.protobuf.Internal.IntList; 34 35 import java.util.Arrays; 36 import java.util.Collection; 37 import java.util.RandomAccess; 38 39 /** 40 * An implementation of {@link IntList} on top of a primitive array. 41 * 42 * @author dweis@google.com (Daniel Weis) 43 */ 44 final class IntArrayList extends AbstractProtobufList<Integer> implements IntList, RandomAccess { 45 46 private static final IntArrayList EMPTY_LIST = new IntArrayList(); 47 static { EMPTY_LIST.makeImmutable()48 EMPTY_LIST.makeImmutable(); 49 } 50 emptyList()51 public static IntArrayList emptyList() { 52 return EMPTY_LIST; 53 } 54 55 /** 56 * The backing store for the list. 57 */ 58 private int[] array; 59 60 /** 61 * The size of the list distinct from the length of the array. That is, it is the number of 62 * elements set in the list. 63 */ 64 private int size; 65 66 /** 67 * Constructs a new mutable {@code IntArrayList} with default capacity. 68 */ IntArrayList()69 IntArrayList() { 70 this(new int[DEFAULT_CAPACITY], 0); 71 } 72 73 /** 74 * Constructs a new mutable {@code IntArrayList} containing the same elements as {@code other}. 75 */ IntArrayList(int[] array, int size)76 private IntArrayList(int[] array, int size) { 77 this.array = array; 78 this.size = size; 79 } 80 81 @Override equals(Object o)82 public boolean equals(Object o) { 83 if (this == o) { 84 return true; 85 } 86 if (!(o instanceof IntArrayList)) { 87 return super.equals(o); 88 } 89 IntArrayList other = (IntArrayList) o; 90 if (size != other.size) { 91 return false; 92 } 93 94 final int[] arr = other.array; 95 for (int i = 0; i < size; i++) { 96 if (array[i] != arr[i]) { 97 return false; 98 } 99 } 100 101 return true; 102 } 103 104 @Override hashCode()105 public int hashCode() { 106 int result = 1; 107 for (int i = 0; i < size; i++) { 108 result = (31 * result) + array[i]; 109 } 110 return result; 111 } 112 113 @Override mutableCopyWithCapacity(int capacity)114 public IntList mutableCopyWithCapacity(int capacity) { 115 if (capacity < size) { 116 throw new IllegalArgumentException(); 117 } 118 return new IntArrayList(Arrays.copyOf(array, capacity), size); 119 } 120 121 @Override get(int index)122 public Integer get(int index) { 123 return getInt(index); 124 } 125 126 @Override getInt(int index)127 public int getInt(int index) { 128 ensureIndexInRange(index); 129 return array[index]; 130 } 131 132 @Override size()133 public int size() { 134 return size; 135 } 136 137 @Override set(int index, Integer element)138 public Integer set(int index, Integer element) { 139 return setInt(index, element); 140 } 141 142 @Override setInt(int index, int element)143 public int setInt(int index, int element) { 144 ensureIsMutable(); 145 ensureIndexInRange(index); 146 int previousValue = array[index]; 147 array[index] = element; 148 return previousValue; 149 } 150 151 @Override add(int index, Integer element)152 public void add(int index, Integer element) { 153 addInt(index, element); 154 } 155 156 /** 157 * Like {@link #add(Integer)} but more efficient in that it doesn't box the element. 158 */ 159 @Override addInt(int element)160 public void addInt(int element) { 161 addInt(size, element); 162 } 163 164 /** 165 * Like {@link #add(int, Integer)} but more efficient in that it doesn't box the element. 166 */ addInt(int index, int element)167 private void addInt(int index, int element) { 168 ensureIsMutable(); 169 if (index < 0 || index > size) { 170 throw new IndexOutOfBoundsException(makeOutOfBoundsExceptionMessage(index)); 171 } 172 173 if (size < array.length) { 174 // Shift everything over to make room 175 System.arraycopy(array, index, array, index + 1, size - index); 176 } else { 177 // Resize to 1.5x the size 178 int length = ((size * 3) / 2) + 1; 179 int[] newArray = new int[length]; 180 181 // Copy the first part directly 182 System.arraycopy(array, 0, newArray, 0, index); 183 184 // Copy the rest shifted over by one to make room 185 System.arraycopy(array, index, newArray, index + 1, size - index); 186 array = newArray; 187 } 188 189 array[index] = element; 190 size++; 191 modCount++; 192 } 193 194 @Override addAll(Collection<? extends Integer> collection)195 public boolean addAll(Collection<? extends Integer> collection) { 196 ensureIsMutable(); 197 198 if (collection == null) { 199 throw new NullPointerException(); 200 } 201 202 // We specialize when adding another IntArrayList to avoid boxing elements. 203 if (!(collection instanceof IntArrayList)) { 204 return super.addAll(collection); 205 } 206 207 IntArrayList list = (IntArrayList) collection; 208 if (list.size == 0) { 209 return false; 210 } 211 212 int overflow = Integer.MAX_VALUE - size; 213 if (overflow < list.size) { 214 // We can't actually represent a list this large. 215 throw new OutOfMemoryError(); 216 } 217 218 int newSize = size + list.size; 219 if (newSize > array.length) { 220 array = Arrays.copyOf(array, newSize); 221 } 222 223 System.arraycopy(list.array, 0, array, size, list.size); 224 size = newSize; 225 modCount++; 226 return true; 227 } 228 229 @Override remove(Object o)230 public boolean remove(Object o) { 231 ensureIsMutable(); 232 for (int i = 0; i < size; i++) { 233 if (o.equals(array[i])) { 234 System.arraycopy(array, i + 1, array, i, size - i); 235 size--; 236 modCount++; 237 return true; 238 } 239 } 240 return false; 241 } 242 243 @Override remove(int index)244 public Integer remove(int index) { 245 ensureIsMutable(); 246 ensureIndexInRange(index); 247 int value = array[index]; 248 System.arraycopy(array, index + 1, array, index, size - index); 249 size--; 250 modCount++; 251 return value; 252 } 253 254 /** 255 * Ensures that the provided {@code index} is within the range of {@code [0, size]}. Throws an 256 * {@link IndexOutOfBoundsException} if it is not. 257 * 258 * @param index the index to verify is in range 259 */ ensureIndexInRange(int index)260 private void ensureIndexInRange(int index) { 261 if (index < 0 || index >= size) { 262 throw new IndexOutOfBoundsException(makeOutOfBoundsExceptionMessage(index)); 263 } 264 } 265 makeOutOfBoundsExceptionMessage(int index)266 private String makeOutOfBoundsExceptionMessage(int index) { 267 return "Index:" + index + ", Size:" + size; 268 } 269 } 270