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.ProtobufList; 34 import java.util.Arrays; 35 import java.util.RandomAccess; 36 37 /** Implements {@link ProtobufList} for non-primitive and {@link String} types. */ 38 final class ProtobufArrayList<E> extends AbstractProtobufList<E> implements RandomAccess { 39 40 private static final ProtobufArrayList<Object> EMPTY_LIST = 41 new ProtobufArrayList<Object>(new Object[0], 0); 42 43 static { EMPTY_LIST.makeImmutable()44 EMPTY_LIST.makeImmutable(); 45 } 46 47 @SuppressWarnings("unchecked") // Guaranteed safe by runtime. emptyList()48 public static <E> ProtobufArrayList<E> emptyList() { 49 return (ProtobufArrayList<E>) EMPTY_LIST; 50 } 51 52 private E[] array; 53 private int size; 54 55 @SuppressWarnings("unchecked") ProtobufArrayList()56 ProtobufArrayList() { 57 this((E[]) new Object[DEFAULT_CAPACITY], 0); 58 } 59 ProtobufArrayList(E[] array, int size)60 private ProtobufArrayList(E[] array, int size) { 61 this.array = array; 62 this.size = size; 63 } 64 65 @Override mutableCopyWithCapacity(int capacity)66 public ProtobufArrayList<E> mutableCopyWithCapacity(int capacity) { 67 if (capacity < size) { 68 throw new IllegalArgumentException(); 69 } 70 71 E[] newArray = Arrays.copyOf(array, capacity); 72 73 return new ProtobufArrayList<E>(newArray, size); 74 } 75 76 @Override add(E element)77 public boolean add(E element) { 78 ensureIsMutable(); 79 80 if (size == array.length) { 81 // Resize to 1.5x the size 82 int length = ((size * 3) / 2) + 1; 83 E[] newArray = Arrays.copyOf(array, length); 84 85 array = newArray; 86 } 87 88 array[size++] = element; 89 modCount++; 90 91 return true; 92 } 93 94 @Override add(int index, E element)95 public void add(int index, E element) { 96 ensureIsMutable(); 97 98 if (index < 0 || index > size) { 99 throw new IndexOutOfBoundsException(makeOutOfBoundsExceptionMessage(index)); 100 } 101 102 if (size < array.length) { 103 // Shift everything over to make room 104 System.arraycopy(array, index, array, index + 1, size - index); 105 } else { 106 // Resize to 1.5x the size 107 int length = ((size * 3) / 2) + 1; 108 E[] newArray = createArray(length); 109 110 // Copy the first part directly 111 System.arraycopy(array, 0, newArray, 0, index); 112 113 // Copy the rest shifted over by one to make room 114 System.arraycopy(array, index, newArray, index + 1, size - index); 115 array = newArray; 116 } 117 118 array[index] = element; 119 size++; 120 modCount++; 121 } 122 123 @Override get(int index)124 public E get(int index) { 125 ensureIndexInRange(index); 126 return array[index]; 127 } 128 129 @Override remove(int index)130 public E remove(int index) { 131 ensureIsMutable(); 132 ensureIndexInRange(index); 133 134 E value = array[index]; 135 if (index < size - 1) { 136 System.arraycopy(array, index + 1, array, index, size - index - 1); 137 } 138 139 size--; 140 modCount++; 141 return value; 142 } 143 144 @Override set(int index, E element)145 public E set(int index, E element) { 146 ensureIsMutable(); 147 ensureIndexInRange(index); 148 149 E toReturn = array[index]; 150 array[index] = element; 151 152 modCount++; 153 return toReturn; 154 } 155 156 @Override size()157 public int size() { 158 return size; 159 } 160 161 @SuppressWarnings("unchecked") createArray(int capacity)162 private static <E> E[] createArray(int capacity) { 163 return (E[]) new Object[capacity]; 164 } 165 ensureIndexInRange(int index)166 private void ensureIndexInRange(int index) { 167 if (index < 0 || index >= size) { 168 throw new IndexOutOfBoundsException(makeOutOfBoundsExceptionMessage(index)); 169 } 170 } 171 makeOutOfBoundsExceptionMessage(int index)172 private String makeOutOfBoundsExceptionMessage(int index) { 173 return "Index:" + index + ", Size:" + size; 174 } 175 } 176