001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.apache.commons.compress.harmony.pack200; 018 019import java.util.Arrays; 020 021/** 022 * IntList is based on <code>java.util.ArrayList</code>, but is written specifically for ints in order to reduce boxing 023 * and unboxing to Integers, reduce the memory required and improve performance of pack200. 024 */ 025public class IntList { 026 027 private int[] array; 028 private int firstIndex; 029 private int lastIndex; 030 private int modCount; 031 032 /** 033 * Constructs a new instance of IntList with capacity for ten elements. 034 */ 035 public IntList() { 036 this(10); 037 } 038 039 /** 040 * Constructs a new instance of IntList with the specified capacity. 041 * 042 * @param capacity the initial capacity of this IntList 043 */ 044 public IntList(final int capacity) { 045 if (capacity < 0) { 046 throw new IllegalArgumentException(); 047 } 048 firstIndex = lastIndex = 0; 049 array = new int[capacity]; 050 } 051 052 /** 053 * Adds the specified object at the end of this IntList. 054 * 055 * @param object the object to add 056 * @return true 057 */ 058 public boolean add(final int object) { 059 if (lastIndex == array.length) { 060 growAtEnd(1); 061 } 062 array[lastIndex++] = object; 063 modCount++; 064 return true; 065 } 066 067 public void add(final int location, final int object) { 068 final int size = lastIndex - firstIndex; 069 if (0 < location && location < size) { 070 if (firstIndex == 0 && lastIndex == array.length) { 071 growForInsert(location, 1); 072 } else if ((location < size / 2 && firstIndex > 0) || lastIndex == array.length) { 073 System.arraycopy(array, firstIndex, array, --firstIndex, location); 074 } else { 075 final int index = location + firstIndex; 076 System.arraycopy(array, index, array, index + 1, size - location); 077 lastIndex++; 078 } 079 array[location + firstIndex] = object; 080 } else if (location == 0) { 081 if (firstIndex == 0) { 082 growAtFront(1); 083 } 084 array[--firstIndex] = object; 085 } else if (location == size) { 086 if (lastIndex == array.length) { 087 growAtEnd(1); 088 } 089 array[lastIndex++] = object; 090 } else { 091 throw new IndexOutOfBoundsException(); 092 } 093 094 modCount++; 095 } 096 097 public void clear() { 098 if (firstIndex != lastIndex) { 099 Arrays.fill(array, firstIndex, lastIndex, -1); 100 firstIndex = lastIndex = 0; 101 modCount++; 102 } 103 } 104 105 public int get(final int location) { 106 if (0 <= location && location < (lastIndex - firstIndex)) { 107 return array[firstIndex + location]; 108 } 109 throw new IndexOutOfBoundsException("" + location); 110 } 111 112 private void growAtEnd(final int required) { 113 final int size = lastIndex - firstIndex; 114 if (firstIndex >= required - (array.length - lastIndex)) { 115 final int newLast = lastIndex - firstIndex; 116 if (size > 0) { 117 System.arraycopy(array, firstIndex, array, 0, size); 118 } 119 firstIndex = 0; 120 lastIndex = newLast; 121 } else { 122 int increment = size / 2; 123 if (required > increment) { 124 increment = required; 125 } 126 if (increment < 12) { 127 increment = 12; 128 } 129 final int[] newArray = new int[size + increment]; 130 if (size > 0) { 131 System.arraycopy(array, firstIndex, newArray, 0, size); 132 firstIndex = 0; 133 lastIndex = size; 134 } 135 array = newArray; 136 } 137 } 138 139 private void growAtFront(final int required) { 140 final int size = lastIndex - firstIndex; 141 if (array.length - lastIndex + firstIndex >= required) { 142 final int newFirst = array.length - size; 143 if (size > 0) { 144 System.arraycopy(array, firstIndex, array, newFirst, size); 145 } 146 firstIndex = newFirst; 147 lastIndex = array.length; 148 } else { 149 int increment = size / 2; 150 if (required > increment) { 151 increment = required; 152 } 153 if (increment < 12) { 154 increment = 12; 155 } 156 final int[] newArray = new int[size + increment]; 157 if (size > 0) { 158 System.arraycopy(array, firstIndex, newArray, newArray.length - size, size); 159 } 160 firstIndex = newArray.length - size; 161 lastIndex = newArray.length; 162 array = newArray; 163 } 164 } 165 166 private void growForInsert(final int location, final int required) { 167 final int size = lastIndex - firstIndex; 168 int increment = size / 2; 169 if (required > increment) { 170 increment = required; 171 } 172 if (increment < 12) { 173 increment = 12; 174 } 175 final int[] newArray = new int[size + increment]; 176 final int newFirst = increment - required; 177 // Copy elements after location to the new array skipping inserted 178 // elements 179 System.arraycopy(array, location + firstIndex, newArray, newFirst + location + required, size - location); 180 // Copy elements before location to the new array from firstIndex 181 System.arraycopy(array, firstIndex, newArray, newFirst, location); 182 firstIndex = newFirst; 183 lastIndex = size + increment; 184 185 array = newArray; 186 } 187 188 public void increment(final int location) { 189 if ((0 > location) || (location >= (lastIndex - firstIndex))) { 190 throw new IndexOutOfBoundsException("" + location); 191 } 192 array[firstIndex + location]++; 193 } 194 195 public boolean isEmpty() { 196 return lastIndex == firstIndex; 197 } 198 199 public int remove(final int location) { 200 int result; 201 final int size = lastIndex - firstIndex; 202 if ((0 > location) || (location >= size)) { 203 throw new IndexOutOfBoundsException(); 204 } 205 if (location == size - 1) { 206 result = array[--lastIndex]; 207 array[lastIndex] = 0; 208 } else if (location == 0) { 209 result = array[firstIndex]; 210 array[firstIndex++] = 0; 211 } else { 212 final int elementIndex = firstIndex + location; 213 result = array[elementIndex]; 214 if (location < size / 2) { 215 System.arraycopy(array, firstIndex, array, firstIndex + 1, location); 216 array[firstIndex++] = 0; 217 } else { 218 System.arraycopy(array, elementIndex + 1, array, elementIndex, size - location - 1); 219 array[--lastIndex] = 0; 220 } 221 } 222 if (firstIndex == lastIndex) { 223 firstIndex = lastIndex = 0; 224 } 225 226 modCount++; 227 return result; 228 } 229 230 public int size() { 231 return lastIndex - firstIndex; 232 } 233 234 public int[] toArray() { 235 final int size = lastIndex - firstIndex; 236 final int[] result = new int[size]; 237 System.arraycopy(array, firstIndex, result, 0, size); 238 return result; 239 } 240 241 public void addAll(final IntList list) { 242 growAtEnd(list.size()); 243 for (int i = 0; i < list.size(); i++) { 244 add(list.get(i)); 245 } 246 } 247 248}