ResizableIntArray.java revision ad78058a93492d4f114c6a6eb56177be9231a9eb
19370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka/* 29370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka * Copyright (C) 2012 The Android Open Source Project 39370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka * 48aa9963a895f9dd5bb1bc92ab2e4f461e058f87aTadashi G. Takaoka * Licensed under the Apache License, Version 2.0 (the "License"); 58aa9963a895f9dd5bb1bc92ab2e4f461e058f87aTadashi G. Takaoka * you may not use this file except in compliance with the License. 68aa9963a895f9dd5bb1bc92ab2e4f461e058f87aTadashi G. Takaoka * You may obtain a copy of the License at 79370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka * 88aa9963a895f9dd5bb1bc92ab2e4f461e058f87aTadashi G. Takaoka * http://www.apache.org/licenses/LICENSE-2.0 99370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka * 109370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka * Unless required by applicable law or agreed to in writing, software 118aa9963a895f9dd5bb1bc92ab2e4f461e058f87aTadashi G. Takaoka * distributed under the License is distributed on an "AS IS" BASIS, 128aa9963a895f9dd5bb1bc92ab2e4f461e058f87aTadashi G. Takaoka * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 138aa9963a895f9dd5bb1bc92ab2e4f461e058f87aTadashi G. Takaoka * See the License for the specific language governing permissions and 148aa9963a895f9dd5bb1bc92ab2e4f461e058f87aTadashi G. Takaoka * limitations under the License. 159370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka */ 169370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka 17e28eba5074664d5716b8e58b8d0a235746b261ebKen Wakasapackage com.android.inputmethod.latin.utils; 189370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka 199370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaokaimport java.util.Arrays; 209370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka 219370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka// TODO: This class is not thread-safe. 22a28a05e971cc242b338331a3b78276fa95188d19Tadashi G. Takaokapublic final class ResizableIntArray { 239370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka private int[] mArray; 249370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka private int mLength; 259370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka 26c49c85f835ecd14d09abb6d88c85a3303c566741Tadashi G. Takaoka public ResizableIntArray(final int capacity) { 279370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka reset(capacity); 289370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka } 299370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka 30c49c85f835ecd14d09abb6d88c85a3303c566741Tadashi G. Takaoka public int get(final int index) { 317abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka if (index < mLength) { 327abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka return mArray[index]; 33c49c85f835ecd14d09abb6d88c85a3303c566741Tadashi G. Takaoka } 347abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka throw new ArrayIndexOutOfBoundsException("length=" + mLength + "; index=" + index); 35c49c85f835ecd14d09abb6d88c85a3303c566741Tadashi G. Takaoka } 36c49c85f835ecd14d09abb6d88c85a3303c566741Tadashi G. Takaoka 37ad78058a93492d4f114c6a6eb56177be9231a9ebTadashi G. Takaoka public void addAt(final int index, final int val) { 387abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka if (index < mLength) { 397abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka mArray[index] = val; 407abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka } else { 419370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka mLength = index; 429370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka add(val); 439370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka } 449370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka } 459370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka 46c49c85f835ecd14d09abb6d88c85a3303c566741Tadashi G. Takaoka public void add(final int val) { 477abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka final int currentLength = mLength; 487abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka ensureCapacity(currentLength + 1); 497abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka mArray[currentLength] = val; 507abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka mLength = currentLength + 1; 517abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka } 527abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka 537abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka /** 547abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka * Calculate the new capacity of {@code mArray}. 557abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka * @param minimumCapacity the minimum capacity that the {@code mArray} should have. 567abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka * @return the new capacity that the {@code mArray} should have. Returns zero when there is no 577abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka * need to expand {@code mArray}. 587abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka */ 597abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka private int calculateCapacity(final int minimumCapacity) { 607abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka final int currentCapcity = mArray.length; 617abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka if (currentCapcity < minimumCapacity) { 627abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka final int nextCapacity = currentCapcity * 2; 637abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka // The following is the same as return Math.max(minimumCapacity, nextCapacity); 647abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka return minimumCapacity > nextCapacity ? minimumCapacity : nextCapacity; 657abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka } 667abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka return 0; 679370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka } 689370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka 69c49c85f835ecd14d09abb6d88c85a3303c566741Tadashi G. Takaoka private void ensureCapacity(final int minimumCapacity) { 707abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka final int newCapacity = calculateCapacity(minimumCapacity); 717abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka if (newCapacity > 0) { 729370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka // TODO: Implement primitive array pool. 737abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka mArray = Arrays.copyOf(mArray, newCapacity); 749370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka } 759370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka } 769370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka 779370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka public int getLength() { 789370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka return mLength; 799370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka } 809370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka 81c49c85f835ecd14d09abb6d88c85a3303c566741Tadashi G. Takaoka public void setLength(final int newLength) { 82c49c85f835ecd14d09abb6d88c85a3303c566741Tadashi G. Takaoka ensureCapacity(newLength); 83c49c85f835ecd14d09abb6d88c85a3303c566741Tadashi G. Takaoka mLength = newLength; 84c49c85f835ecd14d09abb6d88c85a3303c566741Tadashi G. Takaoka } 859370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka 86c49c85f835ecd14d09abb6d88c85a3303c566741Tadashi G. Takaoka public void reset(final int capacity) { 879370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka // TODO: Implement primitive array pool. 889370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka mArray = new int[capacity]; 899370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka mLength = 0; 909370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka } 919370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka 929370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka public int[] getPrimitiveArray() { 939370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka return mArray; 949370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka } 959370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka 96c49c85f835ecd14d09abb6d88c85a3303c566741Tadashi G. Takaoka public void set(final ResizableIntArray ip) { 979370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka // TODO: Implement primitive array pool. 989370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka mArray = ip.mArray; 999370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka mLength = ip.mLength; 1009370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka } 1019370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka 102c49c85f835ecd14d09abb6d88c85a3303c566741Tadashi G. Takaoka public void copy(final ResizableIntArray ip) { 1037abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka final int newCapacity = calculateCapacity(ip.mLength); 1047abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka if (newCapacity > 0) { 1057abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka // TODO: Implement primitive array pool. 1067abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka mArray = new int[newCapacity]; 1077abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka } 1089370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka System.arraycopy(ip.mArray, 0, mArray, 0, ip.mLength); 1099370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka mLength = ip.mLength; 1109370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka } 1119370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka 112c49c85f835ecd14d09abb6d88c85a3303c566741Tadashi G. Takaoka public void append(final ResizableIntArray src, final int startPos, final int length) { 1137abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka if (length == 0) { 1147abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka return; 1157abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka } 1169370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka final int currentLength = mLength; 1179370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka final int newLength = currentLength + length; 1189370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka ensureCapacity(newLength); 1199370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka System.arraycopy(src.mArray, startPos, mArray, currentLength, length); 1209370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka mLength = newLength; 1219370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka } 1227abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka 1237abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka public void fill(final int value, final int startPos, final int length) { 1247abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka if (startPos < 0 || length < 0) { 1257abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka throw new IllegalArgumentException("startPos=" + startPos + "; length=" + length); 1267abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka } 1277abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka final int endPos = startPos + length; 1287abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka ensureCapacity(endPos); 1297abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka Arrays.fill(mArray, startPos, endPos, value); 1307abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka if (mLength < endPos) { 1317abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka mLength = endPos; 1327abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka } 1337abdcf1ed3113d3c121f6ff1b87a7464f079e141Tadashi G. Takaoka } 13464ee09610024eb1436c51f9c9ef9fc3f77239d73Tadashi G. Takaoka 135e8754aba1c8f217e7ca828de25e0506ac58daa99Keisuke Kuroyanagi /** 136e8754aba1c8f217e7ca828de25e0506ac58daa99Keisuke Kuroyanagi * Shift to the left by elementCount, discarding elementCount pointers at the start. 137e8754aba1c8f217e7ca828de25e0506ac58daa99Keisuke Kuroyanagi * @param elementCount how many elements to shift. 138e8754aba1c8f217e7ca828de25e0506ac58daa99Keisuke Kuroyanagi */ 139e8754aba1c8f217e7ca828de25e0506ac58daa99Keisuke Kuroyanagi public void shift(final int elementCount) { 140e8754aba1c8f217e7ca828de25e0506ac58daa99Keisuke Kuroyanagi System.arraycopy(mArray, elementCount, mArray, 0, mLength - elementCount); 141e8754aba1c8f217e7ca828de25e0506ac58daa99Keisuke Kuroyanagi mLength -= elementCount; 142e8754aba1c8f217e7ca828de25e0506ac58daa99Keisuke Kuroyanagi } 143e8754aba1c8f217e7ca828de25e0506ac58daa99Keisuke Kuroyanagi 14464ee09610024eb1436c51f9c9ef9fc3f77239d73Tadashi G. Takaoka @Override 14564ee09610024eb1436c51f9c9ef9fc3f77239d73Tadashi G. Takaoka public String toString() { 14664ee09610024eb1436c51f9c9ef9fc3f77239d73Tadashi G. Takaoka final StringBuilder sb = new StringBuilder(); 14764ee09610024eb1436c51f9c9ef9fc3f77239d73Tadashi G. Takaoka for (int i = 0; i < mLength; i++) { 14864ee09610024eb1436c51f9c9ef9fc3f77239d73Tadashi G. Takaoka if (i != 0) { 14964ee09610024eb1436c51f9c9ef9fc3f77239d73Tadashi G. Takaoka sb.append(","); 15064ee09610024eb1436c51f9c9ef9fc3f77239d73Tadashi G. Takaoka } 15164ee09610024eb1436c51f9c9ef9fc3f77239d73Tadashi G. Takaoka sb.append(mArray[i]); 15264ee09610024eb1436c51f9c9ef9fc3f77239d73Tadashi G. Takaoka } 15364ee09610024eb1436c51f9c9ef9fc3f77239d73Tadashi G. Takaoka return "[" + sb + "]"; 15464ee09610024eb1436c51f9c9ef9fc3f77239d73Tadashi G. Takaoka } 1559370ab9adad3b4bc3af8bde52b6422b8d2b873e7Tadashi G. Takaoka} 156