diff options
4 files changed, 328 insertions, 166 deletions
diff --git a/java/src/com/android/inputmethod/compat/ArraysCompatUtils.java b/java/src/com/android/inputmethod/compat/ArraysCompatUtils.java new file mode 100644 index 000000000..f6afbcfe2 --- /dev/null +++ b/java/src/com/android/inputmethod/compat/ArraysCompatUtils.java @@ -0,0 +1,50 @@ +/* + * Copyright (C) 2011 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.inputmethod.compat; + +import java.lang.reflect.Method; +import java.util.Arrays; + +public class ArraysCompatUtils { + private static final Method METHOD_Arrays_binarySearch = CompatUtils + .getMethod(Arrays.class, "binarySearch", int[].class, int.class, int.class, int.class); + + public static int binarySearch(int[] array, int startIndex, int endIndex, int value) { + if (METHOD_Arrays_binarySearch != null) { + final Object index = CompatUtils.invoke(null, 0, METHOD_Arrays_binarySearch, + array, startIndex, endIndex, value); + return (Integer)index; + } else { + return compatBinarySearch(array, startIndex, endIndex, value); + } + } + + /* package */ static int compatBinarySearch(int[] array, int startIndex, int endIndex, + int value) { + if (startIndex > endIndex) throw new IllegalArgumentException(); + if (startIndex < 0 || endIndex > array.length) throw new ArrayIndexOutOfBoundsException(); + + final int work[] = new int[endIndex - startIndex]; + System.arraycopy(array, startIndex, work, 0, work.length); + final int index = Arrays.binarySearch(work, value); + if (index >= 0) { + return index + startIndex; + } else { + return ~(~index + startIndex); + } + } +} diff --git a/java/src/com/android/inputmethod/latin/spellcheck/SpellChecker.java b/java/src/com/android/inputmethod/latin/spellcheck/SpellChecker.java index e3407a269..63c6d69d7 100644 --- a/java/src/com/android/inputmethod/latin/spellcheck/SpellChecker.java +++ b/java/src/com/android/inputmethod/latin/spellcheck/SpellChecker.java @@ -19,6 +19,7 @@ package com.android.inputmethod.latin.spellcheck; import android.content.Context; import android.content.res.Resources; +import com.android.inputmethod.compat.ArraysCompatUtils; import com.android.inputmethod.latin.Dictionary; import com.android.inputmethod.latin.Dictionary.DataType; import com.android.inputmethod.latin.Dictionary.WordCallback; @@ -26,7 +27,6 @@ import com.android.inputmethod.latin.DictionaryFactory; import com.android.inputmethod.latin.Utils; import com.android.inputmethod.latin.WordComposer; -import java.util.Arrays; import java.util.LinkedList; import java.util.List; import java.util.Locale; @@ -64,13 +64,14 @@ public class SpellChecker { private int[] mScores = new int[DEFAULT_SUGGESTION_LENGTH]; private int mLength = 0; + @Override synchronized public boolean addWord(char[] word, int wordOffset, int wordLength, int score, int dicTypeId, DataType dataType) { if (mLength >= mScores.length) { final int newLength = mScores.length * 2; mScores = new int[newLength]; } - final int positionIndex = Arrays.binarySearch(mScores, 0, mLength, score); + final int positionIndex = ArraysCompatUtils.binarySearch(mScores, 0, mLength, score); // binarySearch returns the index if the element exists, and -<insertion index> - 1 // if it doesn't. See documentation for binarySearch. final int insertionIndex = positionIndex >= 0 ? positionIndex : -positionIndex - 1; diff --git a/native/src/unigram_dictionary.cpp b/native/src/unigram_dictionary.cpp index ef52ceb7c..36233b741 100644 --- a/native/src/unigram_dictionary.cpp +++ b/native/src/unigram_dictionary.cpp @@ -518,47 +518,6 @@ inline static int calcFreqForSplitTwoWords( return totalFreq; } -bool UnigramDictionary::getSplitTwoWordsSuggestion(const int inputLength, - const int firstWordStartPos, const int firstWordLength, const int secondWordStartPos, - const int secondWordLength, const bool isSpaceProximity) { - if (inputLength >= MAX_WORD_LENGTH) return false; - if (0 >= firstWordLength || 0 >= secondWordLength || firstWordStartPos >= secondWordStartPos - || firstWordStartPos < 0 || secondWordStartPos + secondWordLength > inputLength) - return false; - const int newWordLength = firstWordLength + secondWordLength + 1; - // Allocating variable length array on stack - unsigned short word[newWordLength]; - const int firstFreq = getBestWordFreq(firstWordStartPos, firstWordLength, mWord); - if (DEBUG_DICT) { - LOGI("First freq: %d", firstFreq); - } - if (firstFreq <= 0) return false; - - for (int i = 0; i < firstWordLength; ++i) { - word[i] = mWord[i]; - } - - const int secondFreq = getBestWordFreq(secondWordStartPos, secondWordLength, mWord); - if (DEBUG_DICT) { - LOGI("Second freq: %d", secondFreq); - } - if (secondFreq <= 0) return false; - - word[firstWordLength] = SPACE; - for (int i = (firstWordLength + 1); i < newWordLength; ++i) { - word[i] = mWord[i - firstWordLength - 1]; - } - - int pairFreq = calcFreqForSplitTwoWords(TYPED_LETTER_MULTIPLIER, firstWordLength, - secondWordLength, firstFreq, secondFreq, isSpaceProximity); - if (DEBUG_DICT) { - LOGI("Split two words: %d, %d, %d, %d, %d", firstFreq, secondFreq, pairFreq, inputLength, - TYPED_LETTER_MULTIPLIER); - } - addWord(word, newWordLength, pairFreq); - return true; -} - bool UnigramDictionary::getMissingSpaceWords(const int inputLength, const int missingSpacePos) { return getSplitTwoWordsSuggestion( inputLength, 0, missingSpacePos, missingSpacePos, inputLength - missingSpacePos, false); @@ -570,48 +529,6 @@ bool UnigramDictionary::getMistypedSpaceWords(const int inputLength, const int s inputLength - spaceProximityPos - 1, true); } -// Keep this for comparing spec to new getWords -void UnigramDictionary::getWordsOld(const int initialPos, const int inputLength, const int skipPos, - const int excessivePos, const int transposedPos,int *nextLetters, - const int nextLettersSize) { - int initialPosition = initialPos; - const int count = Dictionary::getCount(DICT_ROOT, &initialPosition); - getWordsRec(count, initialPosition, 0, - min(inputLength * MAX_DEPTH_MULTIPLIER, MAX_WORD_LENGTH), - mInputLength <= 0, 1, 0, 0, skipPos, excessivePos, transposedPos, nextLetters, - nextLettersSize); -} - -void UnigramDictionary::getWordsRec(const int childrenCount, const int pos, const int depth, - const int maxDepth, const bool traverseAllNodes, const int matchWeight, - const int inputIndex, const int diffs, const int skipPos, const int excessivePos, - const int transposedPos, int *nextLetters, const int nextLettersSize) { - int siblingPos = pos; - for (int i = 0; i < childrenCount; ++i) { - int newCount; - int newChildPosition; - bool newTraverseAllNodes; - int newMatchRate; - int newInputIndex; - int newDiffs; - int newSiblingPos; - int newOutputIndex; - const bool needsToTraverseChildrenNodes = processCurrentNode(siblingPos, depth, maxDepth, - traverseAllNodes, matchWeight, inputIndex, diffs, - skipPos, excessivePos, transposedPos, - nextLetters, nextLettersSize, - &newCount, &newChildPosition, &newTraverseAllNodes, &newMatchRate, - &newInputIndex, &newDiffs, &newSiblingPos, &newOutputIndex); - siblingPos = newSiblingPos; - - if (needsToTraverseChildrenNodes) { - getWordsRec(newCount, newChildPosition, newOutputIndex, maxDepth, newTraverseAllNodes, - newMatchRate, newInputIndex, newDiffs, skipPos, excessivePos, transposedPos, - nextLetters, nextLettersSize); - } - } -} - inline int UnigramDictionary::calculateFinalFreq(const int inputIndex, const int depth, const int matchWeight, const int skipPos, const int excessivePos, const int transposedPos, const int freq, const bool sameLength) const { @@ -763,92 +680,49 @@ inline void UnigramDictionary::onTerminal(unsigned short int* word, const int de } } -inline bool UnigramDictionary::processCurrentNode(const int pos, const int depth, - const int maxDepth, const bool traverseAllNodes, int matchWeight, int inputIndex, - const int diffs, const int skipPos, const int excessivePos, const int transposedPos, - int *nextLetters, const int nextLettersSize, int *newCount, int *newChildPosition, - bool *newTraverseAllNodes, int *newMatchRate, int *newInputIndex, int *newDiffs, - int *nextSiblingPosition, int *nextOutputIndex) { - if (DEBUG_DICT) { - int inputCount = 0; - if (skipPos >= 0) ++inputCount; - if (excessivePos >= 0) ++inputCount; - if (transposedPos >= 0) ++inputCount; - assert(inputCount <= 1); - } - unsigned short c; - int childPosition; - bool terminal; - int freq; - bool isSameAsUserTypedLength = false; - - const uint8_t flags = 0; // No flags for now - - if (excessivePos == depth && inputIndex < mInputLength - 1) ++inputIndex; +#ifndef NEW_DICTIONARY_FORMAT +// TODO: Don't forget to bring inline functions back to over where they are used. - *nextSiblingPosition = Dictionary::setDictionaryValues(DICT_ROOT, IS_LATEST_DICT_VERSION, pos, - &c, &childPosition, &terminal, &freq); - *nextOutputIndex = depth + 1; - - const bool needsToTraverseChildrenNodes = childPosition != 0; - - // If we are only doing traverseAllNodes, no need to look at the typed characters. - if (traverseAllNodes || needsToSkipCurrentNode(c, inputIndex, skipPos, depth)) { - mWord[depth] = c; - if (traverseAllNodes && terminal) { - onTerminal(mWord, depth, DICT_ROOT, flags, pos, inputIndex, matchWeight, skipPos, - excessivePos, transposedPos, freq, false, nextLetters, nextLettersSize); - } - if (!needsToTraverseChildrenNodes) return false; - *newTraverseAllNodes = traverseAllNodes; - *newMatchRate = matchWeight; - *newDiffs = diffs; - *newInputIndex = inputIndex; - } else { - const int *currentChars = getInputCharsAt(inputIndex); +// The following functions will be entirely replaced with new implementations. +void UnigramDictionary::getWordsOld(const int initialPos, const int inputLength, const int skipPos, + const int excessivePos, const int transposedPos,int *nextLetters, + const int nextLettersSize) { + int initialPosition = initialPos; + const int count = Dictionary::getCount(DICT_ROOT, &initialPosition); + getWordsRec(count, initialPosition, 0, + min(inputLength * MAX_DEPTH_MULTIPLIER, MAX_WORD_LENGTH), + mInputLength <= 0, 1, 0, 0, skipPos, excessivePos, transposedPos, nextLetters, + nextLettersSize); +} - if (transposedPos >= 0) { - if (inputIndex == transposedPos) currentChars += MAX_PROXIMITY_CHARS; - if (inputIndex == (transposedPos + 1)) currentChars -= MAX_PROXIMITY_CHARS; - } +void UnigramDictionary::getWordsRec(const int childrenCount, const int pos, const int depth, + const int maxDepth, const bool traverseAllNodes, const int matchWeight, + const int inputIndex, const int diffs, const int skipPos, const int excessivePos, + const int transposedPos, int *nextLetters, const int nextLettersSize) { + int siblingPos = pos; + for (int i = 0; i < childrenCount; ++i) { + int newCount; + int newChildPosition; + bool newTraverseAllNodes; + int newMatchRate; + int newInputIndex; + int newDiffs; + int newSiblingPos; + int newOutputIndex; + const bool needsToTraverseChildrenNodes = processCurrentNode(siblingPos, depth, maxDepth, + traverseAllNodes, matchWeight, inputIndex, diffs, + skipPos, excessivePos, transposedPos, + nextLetters, nextLettersSize, + &newCount, &newChildPosition, &newTraverseAllNodes, &newMatchRate, + &newInputIndex, &newDiffs, &newSiblingPos, &newOutputIndex); + siblingPos = newSiblingPos; - int matchedProximityCharId = getMatchedProximityId(currentChars, c, skipPos, excessivePos, - transposedPos); - if (UNRELATED_CHAR == matchedProximityCharId) return false; - mWord[depth] = c; - // If inputIndex is greater than mInputLength, that means there is no - // proximity chars. So, we don't need to check proximity. - if (SAME_OR_ACCENTED_OR_CAPITALIZED_CHAR == matchedProximityCharId) { - multiplyIntCapped(TYPED_LETTER_MULTIPLIER, &matchWeight); - } - bool isSameAsUserTypedLength = mInputLength == inputIndex + 1 - || (excessivePos == mInputLength - 1 && inputIndex == mInputLength - 2); - if (isSameAsUserTypedLength && terminal) { - onTerminal(mWord, depth, DICT_ROOT, flags, pos, inputIndex, matchWeight, skipPos, - excessivePos, transposedPos, freq, true, nextLetters, nextLettersSize); + if (needsToTraverseChildrenNodes) { + getWordsRec(newCount, newChildPosition, newOutputIndex, maxDepth, newTraverseAllNodes, + newMatchRate, newInputIndex, newDiffs, skipPos, excessivePos, transposedPos, + nextLetters, nextLettersSize); } - if (!needsToTraverseChildrenNodes) return false; - // Start traversing all nodes after the index exceeds the user typed length - *newTraverseAllNodes = isSameAsUserTypedLength; - *newMatchRate = matchWeight; - *newDiffs = diffs + ((NEAR_PROXIMITY_CHAR == matchedProximityCharId) ? 1 : 0); - *newInputIndex = inputIndex + 1; } - // Optimization: Prune out words that are too long compared to how much was typed. - if (depth >= maxDepth || *newDiffs > mMaxEditDistance) { - return false; - } - - // If inputIndex is greater than mInputLength, that means there are no proximity chars. - // TODO: Check if this can be isSameAsUserTypedLength only. - if (isSameAsUserTypedLength || mInputLength <= *newInputIndex) { - *newTraverseAllNodes = true; - } - // get the count of nodes and increment childAddress. - *newCount = Dictionary::getCount(DICT_ROOT, &childPosition); - *newChildPosition = childPosition; - if (DEBUG_DICT) assert(needsToTraverseChildrenNodes); - return needsToTraverseChildrenNodes; } inline int UnigramDictionary::getBestWordFreq(const int startInputIndex, const int inputLength, @@ -986,4 +860,138 @@ int UnigramDictionary::getBigramPosition(int pos, unsigned short *word, int offs return NOT_VALID_WORD; } + +// The following functions will be modified. +bool UnigramDictionary::getSplitTwoWordsSuggestion(const int inputLength, + const int firstWordStartPos, const int firstWordLength, const int secondWordStartPos, + const int secondWordLength, const bool isSpaceProximity) { + if (inputLength >= MAX_WORD_LENGTH) return false; + if (0 >= firstWordLength || 0 >= secondWordLength || firstWordStartPos >= secondWordStartPos + || firstWordStartPos < 0 || secondWordStartPos + secondWordLength > inputLength) + return false; + const int newWordLength = firstWordLength + secondWordLength + 1; + // Allocating variable length array on stack + unsigned short word[newWordLength]; + const int firstFreq = getBestWordFreq(firstWordStartPos, firstWordLength, mWord); + if (DEBUG_DICT) { + LOGI("First freq: %d", firstFreq); + } + if (firstFreq <= 0) return false; + + for (int i = 0; i < firstWordLength; ++i) { + word[i] = mWord[i]; + } + + const int secondFreq = getBestWordFreq(secondWordStartPos, secondWordLength, mWord); + if (DEBUG_DICT) { + LOGI("Second freq: %d", secondFreq); + } + if (secondFreq <= 0) return false; + + word[firstWordLength] = SPACE; + for (int i = (firstWordLength + 1); i < newWordLength; ++i) { + word[i] = mWord[i - firstWordLength - 1]; + } + + int pairFreq = calcFreqForSplitTwoWords(TYPED_LETTER_MULTIPLIER, firstWordLength, + secondWordLength, firstFreq, secondFreq, isSpaceProximity); + if (DEBUG_DICT) { + LOGI("Split two words: %d, %d, %d, %d, %d", firstFreq, secondFreq, pairFreq, inputLength, + TYPED_LETTER_MULTIPLIER); + } + addWord(word, newWordLength, pairFreq); + return true; +} + +inline bool UnigramDictionary::processCurrentNode(const int pos, const int depth, + const int maxDepth, const bool traverseAllNodes, int matchWeight, int inputIndex, + const int diffs, const int skipPos, const int excessivePos, const int transposedPos, + int *nextLetters, const int nextLettersSize, int *newCount, int *newChildPosition, + bool *newTraverseAllNodes, int *newMatchRate, int *newInputIndex, int *newDiffs, + int *nextSiblingPosition, int *nextOutputIndex) { + if (DEBUG_DICT) { + int inputCount = 0; + if (skipPos >= 0) ++inputCount; + if (excessivePos >= 0) ++inputCount; + if (transposedPos >= 0) ++inputCount; + assert(inputCount <= 1); + } + unsigned short c; + int childPosition; + bool terminal; + int freq; + bool isSameAsUserTypedLength = false; + + const uint8_t flags = 0; // No flags for now + + if (excessivePos == depth && inputIndex < mInputLength - 1) ++inputIndex; + + *nextSiblingPosition = Dictionary::setDictionaryValues(DICT_ROOT, IS_LATEST_DICT_VERSION, pos, + &c, &childPosition, &terminal, &freq); + *nextOutputIndex = depth + 1; + + const bool needsToTraverseChildrenNodes = childPosition != 0; + + // If we are only doing traverseAllNodes, no need to look at the typed characters. + if (traverseAllNodes || needsToSkipCurrentNode(c, inputIndex, skipPos, depth)) { + mWord[depth] = c; + if (traverseAllNodes && terminal) { + onTerminal(mWord, depth, DICT_ROOT, flags, pos, inputIndex, matchWeight, skipPos, + excessivePos, transposedPos, freq, false, nextLetters, nextLettersSize); + } + if (!needsToTraverseChildrenNodes) return false; + *newTraverseAllNodes = traverseAllNodes; + *newMatchRate = matchWeight; + *newDiffs = diffs; + *newInputIndex = inputIndex; + } else { + const int *currentChars = getInputCharsAt(inputIndex); + + if (transposedPos >= 0) { + if (inputIndex == transposedPos) currentChars += MAX_PROXIMITY_CHARS; + if (inputIndex == (transposedPos + 1)) currentChars -= MAX_PROXIMITY_CHARS; + } + + int matchedProximityCharId = getMatchedProximityId(currentChars, c, skipPos, excessivePos, + transposedPos); + if (UNRELATED_CHAR == matchedProximityCharId) return false; + mWord[depth] = c; + // If inputIndex is greater than mInputLength, that means there is no + // proximity chars. So, we don't need to check proximity. + if (SAME_OR_ACCENTED_OR_CAPITALIZED_CHAR == matchedProximityCharId) { + multiplyIntCapped(TYPED_LETTER_MULTIPLIER, &matchWeight); + } + bool isSameAsUserTypedLength = mInputLength == inputIndex + 1 + || (excessivePos == mInputLength - 1 && inputIndex == mInputLength - 2); + if (isSameAsUserTypedLength && terminal) { + onTerminal(mWord, depth, DICT_ROOT, flags, pos, inputIndex, matchWeight, skipPos, + excessivePos, transposedPos, freq, true, nextLetters, nextLettersSize); + } + if (!needsToTraverseChildrenNodes) return false; + // Start traversing all nodes after the index exceeds the user typed length + *newTraverseAllNodes = isSameAsUserTypedLength; + *newMatchRate = matchWeight; + *newDiffs = diffs + ((NEAR_PROXIMITY_CHAR == matchedProximityCharId) ? 1 : 0); + *newInputIndex = inputIndex + 1; + } + // Optimization: Prune out words that are too long compared to how much was typed. + if (depth >= maxDepth || *newDiffs > mMaxEditDistance) { + return false; + } + + // If inputIndex is greater than mInputLength, that means there are no proximity chars. + // TODO: Check if this can be isSameAsUserTypedLength only. + if (isSameAsUserTypedLength || mInputLength <= *newInputIndex) { + *newTraverseAllNodes = true; + } + // get the count of nodes and increment childAddress. + *newCount = Dictionary::getCount(DICT_ROOT, &childPosition); + *newChildPosition = childPosition; + if (DEBUG_DICT) assert(needsToTraverseChildrenNodes); + return needsToTraverseChildrenNodes; +} + +#else // NEW_DICTIONARY_FORMAT +#endif // NEW_DICTIONARY_FORMAT + } // namespace latinime diff --git a/tests/src/com/android/inputmethod/compat/ArraysCompatUtilsTests.java b/tests/src/com/android/inputmethod/compat/ArraysCompatUtilsTests.java new file mode 100644 index 000000000..93681b616 --- /dev/null +++ b/tests/src/com/android/inputmethod/compat/ArraysCompatUtilsTests.java @@ -0,0 +1,103 @@ +/* + * Copyright (C) 2011 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); you may not + * use this file except in compliance with the License. You may obtain a copy of + * the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT + * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the + * License for the specific language governing permissions and limitations under + * the License. + */ + +package com.android.inputmethod.compat; + +import android.test.AndroidTestCase; + +public class ArraysCompatUtilsTests extends AndroidTestCase { + // See {@link tests.api.java.util.ArraysTest}. + private static final int ARRAY_SIZE = 100; + private final int[] mIntArray = new int[ARRAY_SIZE]; + + @Override + protected void setUp() throws Exception { + super.setUp(); + for (int counter = 0; counter < ARRAY_SIZE; counter++) { + mIntArray[counter] = counter; + } + } + + public void testEmptyArray() { + final int index = ArraysCompatUtils.binarySearch(mIntArray, 0, 0, 0); + assertEquals("empty", ~0, index); + final int compat = ArraysCompatUtils.compatBinarySearch(mIntArray, 0, 0, 0); + assertEquals("empty compat", ~0, compat); + } + + public void testEmptyRangeArray() { + final int mid = ARRAY_SIZE / 3; + final int index = ArraysCompatUtils.binarySearch(mIntArray, mid, mid, 1); + assertEquals("empty", ~mid, index); + final int compat = ArraysCompatUtils.compatBinarySearch(mIntArray, mid, mid, 1); + assertEquals("empty compat", ~mid, compat); + } + + public void testFind() { + for (int counter = 0; counter < ARRAY_SIZE; counter++) { + final int index = ArraysCompatUtils.binarySearch(mIntArray, 0, ARRAY_SIZE, counter); + assertEquals("found", counter, index); + } + for (int counter = 0; counter < ARRAY_SIZE; counter++) { + final int compat = ArraysCompatUtils.compatBinarySearch( + mIntArray, 0, ARRAY_SIZE, counter); + assertEquals("found compat", counter, compat); + } + } + + public void testFindNegative() { + final int offset = ARRAY_SIZE / 2; + for (int counter = 0; counter < ARRAY_SIZE; counter++) { + mIntArray[counter] -= offset; + } + for (int counter = 0; counter < ARRAY_SIZE; counter++) { + final int index = ArraysCompatUtils.binarySearch( + mIntArray, 0, ARRAY_SIZE, counter - offset); + assertEquals("found", counter, index); + } + for (int counter = 0; counter < ARRAY_SIZE; counter++) { + final int compat = ArraysCompatUtils.compatBinarySearch( + mIntArray, 0, ARRAY_SIZE, counter - offset); + assertEquals("found compat", counter, compat); + } + } + + public void testNotFountAtTop() { + final int index = ArraysCompatUtils.binarySearch(mIntArray, 0, ARRAY_SIZE, -1); + assertEquals("not found top", ~0, index); + final int compat = ArraysCompatUtils.compatBinarySearch( + mIntArray, 0, ARRAY_SIZE, -1); + assertEquals("not found top compat", ~0, compat); + } + + public void testNotFountAtEnd() { + final int index = ArraysCompatUtils.binarySearch(mIntArray, 0, ARRAY_SIZE, ARRAY_SIZE); + assertEquals("not found end", ~ARRAY_SIZE, index); + final int compat = ArraysCompatUtils.compatBinarySearch( + mIntArray, 0, ARRAY_SIZE, ARRAY_SIZE); + assertEquals("not found end compat", ~ARRAY_SIZE, compat); + } + + public void testNotFountAtMid() { + final int mid = ARRAY_SIZE / 3; + mIntArray[mid] = mIntArray[mid + 1]; + final int index = ArraysCompatUtils.binarySearch(mIntArray, 0, ARRAY_SIZE, mid); + assertEquals("not found mid", ~mid, index); + final int compat = ArraysCompatUtils.compatBinarySearch( + mIntArray, 0, ARRAY_SIZE, mid); + assertEquals("not found mid compat", ~mid, compat); + } +} |