aboutsummaryrefslogtreecommitdiffstats
path: root/native
diff options
context:
space:
mode:
Diffstat (limited to 'native')
-rw-r--r--native/jni/NativeFileList.mk4
-rw-r--r--native/jni/src/defines.h8
-rw-r--r--native/jni/src/suggest/core/dictionary/bloom_filter.h39
-rw-r--r--native/jni/src/suggest/core/layout/normal_distribution_2d.h59
-rw-r--r--native/jni/src/suggest/core/layout/proximity_info_params.cpp8
-rw-r--r--native/jni/src/suggest/core/layout/proximity_info_params.h9
-rw-r--r--native/jni/src/suggest/core/layout/proximity_info_state.cpp2
-rw-r--r--native/jni/src/suggest/core/layout/proximity_info_state_utils.cpp113
-rw-r--r--native/jni/src/suggest/core/layout/proximity_info_state_utils.h1
-rw-r--r--native/jni/tests/defines_test.cpp (renamed from native/jni/src/suggest/core/dictionary/bloom_filter.cpp)23
-rw-r--r--native/jni/tests/suggest/core/dictionary/bloom_filter_test.cpp80
-rw-r--r--native/jni/tests/suggest/core/layout/normal_distribution_2d_test.cpp68
12 files changed, 306 insertions, 108 deletions
diff --git a/native/jni/NativeFileList.mk b/native/jni/NativeFileList.mk
index 1031903f8..70a6638fb 100644
--- a/native/jni/NativeFileList.mk
+++ b/native/jni/NativeFileList.mk
@@ -27,7 +27,6 @@ LATIN_IME_CORE_SRC_FILES := \
dic_nodes_cache.cpp) \
$(addprefix suggest/core/dictionary/, \
bigram_dictionary.cpp \
- bloom_filter.cpp \
dictionary.cpp \
digraph_utils.cpp \
error_type_utils.cpp \
@@ -101,4 +100,7 @@ LATIN_IME_CORE_SRC_FILES := \
time_keeper.cpp)
LATIN_IME_CORE_TEST_FILES := \
+ defines_test.cpp \
+ suggest/core/layout/normal_distribution_2d_test.cpp \
+ suggest/core/dictionary/bloom_filter_test.cpp \
utils/autocorrection_threshold_utils_test.cpp
diff --git a/native/jni/src/defines.h b/native/jni/src/defines.h
index 1719b1c60..3becc79e8 100644
--- a/native/jni/src/defines.h
+++ b/native/jni/src/defines.h
@@ -35,7 +35,13 @@
// Must be equal to ProximityInfo.MAX_PROXIMITY_CHARS_SIZE in Java
#define MAX_PROXIMITY_CHARS_SIZE 16
#define ADDITIONAL_PROXIMITY_CHAR_DELIMITER_CODE 2
-#define NELEMS(x) (sizeof(x) / sizeof((x)[0]))
+
+// TODO: Use size_t instead of int.
+// Disclaimer: You will see a compile error if you use this macro against a variable-length array.
+// Sorry for the inconvenience. It isn't supported.
+template <typename T, int N>
+char (&ArraySizeHelper(T (&array)[N]))[N];
+#define NELEMS(x) (sizeof(ArraySizeHelper(x)))
AK_FORCE_INLINE static int intArrayToCharArray(const int *const source, const int sourceSize,
char *dest, const int destSize) {
diff --git a/native/jni/src/suggest/core/dictionary/bloom_filter.h b/native/jni/src/suggest/core/dictionary/bloom_filter.h
index 85b8fc397..1e60f49ed 100644
--- a/native/jni/src/suggest/core/dictionary/bloom_filter.h
+++ b/native/jni/src/suggest/core/dictionary/bloom_filter.h
@@ -17,8 +17,7 @@
#ifndef LATINIME_BLOOM_FILTER_H
#define LATINIME_BLOOM_FILTER_H
-#include <cstdint>
-#include <cstring>
+#include <bitset>
#include "defines.h"
@@ -34,41 +33,37 @@ namespace latinime {
// Total 148603.14 (sum of others 148579.90)
class BloomFilter {
public:
- BloomFilter() {
- ASSERT(BIGRAM_FILTER_BYTE_SIZE * 8 >= BIGRAM_FILTER_MODULO);
- memset(mFilter, 0, sizeof(mFilter));
- }
+ BloomFilter() : mFilter() {}
- // TODO: uint32_t position
- AK_FORCE_INLINE void setInFilter(const int32_t position) {
- const uint32_t bucket = static_cast<uint32_t>(position % BIGRAM_FILTER_MODULO);
- mFilter[bucket >> 3] |= static_cast<uint8_t>(1 << (bucket & 0x7));
+ AK_FORCE_INLINE void setInFilter(const int position) {
+ mFilter.set(getIndex(position));
}
- // TODO: uint32_t position
- AK_FORCE_INLINE bool isInFilter(const int32_t position) const {
- const uint32_t bucket = static_cast<uint32_t>(position % BIGRAM_FILTER_MODULO);
- return (mFilter[bucket >> 3] & static_cast<uint8_t>(1 << (bucket & 0x7))) != 0;
+ AK_FORCE_INLINE bool isInFilter(const int position) const {
+ return mFilter.test(getIndex(position));
}
private:
DISALLOW_ASSIGNMENT_OPERATOR(BloomFilter);
- // Size, in bytes, of the bloom filter index for bigrams
- // 128 gives us 1024 buckets. The probability of false positive is (1 - e ** (-kn/m))**k,
+ AK_FORCE_INLINE size_t getIndex(const int position) const {
+ return static_cast<size_t>(position) % BIGRAM_FILTER_MODULO;
+ }
+
+ // Size, in bits, of the bloom filter index for bigrams
+ // The probability of false positive is (1 - e ** (-kn/m))**k,
// where k is the number of hash functions, n the number of bigrams, and m the number of
// bits we can test.
- // At the moment 100 is the maximum number of bigrams for a word with the current
+ // At the moment 100 is the maximum number of bigrams for a word with the current main
// dictionaries, so n = 100. 1024 buckets give us m = 1024.
// With 1 hash function, our false positive rate is about 9.3%, which should be enough for
// our uses since we are only using this to increase average performance. For the record,
// k = 2 gives 3.1% and k = 3 gives 1.6%. With k = 1, making m = 2048 gives 4.8%,
// and m = 4096 gives 2.4%.
- // This is assigned here because it is used for array size.
- static const int BIGRAM_FILTER_BYTE_SIZE = 128;
- static const int BIGRAM_FILTER_MODULO;
-
- uint8_t mFilter[BIGRAM_FILTER_BYTE_SIZE];
+ // This is assigned here because it is used for bitset size.
+ // 1021 is the largest prime under 1024.
+ static const size_t BIGRAM_FILTER_MODULO = 1021;
+ std::bitset<BIGRAM_FILTER_MODULO> mFilter;
};
} // namespace latinime
#endif // LATINIME_BLOOM_FILTER_H
diff --git a/native/jni/src/suggest/core/layout/normal_distribution_2d.h b/native/jni/src/suggest/core/layout/normal_distribution_2d.h
new file mode 100644
index 000000000..3bc0a0153
--- /dev/null
+++ b/native/jni/src/suggest/core/layout/normal_distribution_2d.h
@@ -0,0 +1,59 @@
+/*
+ * Copyright (C) 2014 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.
+ */
+
+#ifndef LATINIME_NORMAL_DISTRIBUTION_2D_H
+#define LATINIME_NORMAL_DISTRIBUTION_2D_H
+
+#include <cmath>
+
+#include "defines.h"
+#include "suggest/core/layout/geometry_utils.h"
+#include "suggest/core/layout/normal_distribution.h"
+
+namespace latinime {
+
+// Normal distribution on a 2D plane. The covariance is always zero, but the distribution can be
+// rotated.
+class NormalDistribution2D {
+ public:
+ NormalDistribution2D(const float uX, const float sigmaX, const float uY, const float sigmaY,
+ const float theta)
+ : mXDistribution(0.0f, sigmaX), mYDistribution(0.0f, sigmaY), mUX(uX), mUY(uY),
+ mSinTheta(sinf(theta)), mCosTheta(cosf(theta)) {}
+
+ float getProbabilityDensity(const float x, const float y) const {
+ // Shift
+ const float shiftedX = x - mUX;
+ const float shiftedY = y - mUY;
+ // Rotate
+ const float rotatedShiftedX = mCosTheta * shiftedX + mSinTheta * shiftedY;
+ const float rotatedShiftedY = -mSinTheta * shiftedX + mCosTheta * shiftedY;
+ return mXDistribution.getProbabilityDensity(rotatedShiftedX)
+ * mYDistribution.getProbabilityDensity(rotatedShiftedY);
+ }
+
+ private:
+ DISALLOW_IMPLICIT_CONSTRUCTORS(NormalDistribution2D);
+
+ const NormalDistribution mXDistribution;
+ const NormalDistribution mYDistribution;
+ const float mUX;
+ const float mUY;
+ const float mSinTheta;
+ const float mCosTheta;
+};
+} // namespace latinime
+#endif // LATINIME_NORMAL_DISTRIBUTION_2D_H
diff --git a/native/jni/src/suggest/core/layout/proximity_info_params.cpp b/native/jni/src/suggest/core/layout/proximity_info_params.cpp
index 597518a4c..a70dd7e34 100644
--- a/native/jni/src/suggest/core/layout/proximity_info_params.cpp
+++ b/native/jni/src/suggest/core/layout/proximity_info_params.cpp
@@ -76,8 +76,12 @@ const float ProximityInfoParams::MAX_SPEEDxANGLE_RATE_FOR_STANDARD_DEVIATION = 0
const float ProximityInfoParams::SPEEDxNEAREST_WEIGHT_FOR_STANDARD_DEVIATION = 0.5f;
const float ProximityInfoParams::MAX_SPEEDxNEAREST_RATE_FOR_STANDARD_DEVIATION = 0.15f;
const float ProximityInfoParams::MIN_STANDARD_DEVIATION = 0.37f;
-const float ProximityInfoParams::PREV_DISTANCE_WEIGHT = 0.5f;
-const float ProximityInfoParams::NEXT_DISTANCE_WEIGHT = 0.6f;
+const float ProximityInfoParams::STANDARD_DEVIATION_X_WEIGHT_FOR_FIRST = 1.25f;
+const float ProximityInfoParams::STANDARD_DEVIATION_Y_WEIGHT_FOR_FIRST = 0.85f;
+const float ProximityInfoParams::STANDARD_DEVIATION_X_WEIGHT_FOR_LAST = 1.4f;
+const float ProximityInfoParams::STANDARD_DEVIATION_Y_WEIGHT_FOR_LAST = 0.95f;
+const float ProximityInfoParams::STANDARD_DEVIATION_X_WEIGHT = 1.1f;
+const float ProximityInfoParams::STANDARD_DEVIATION_Y_WEIGHT = 0.95f;
// Used by ProximityInfoStateUtils::suppressCharProbabilities()
const float ProximityInfoParams::SUPPRESSION_LENGTH_WEIGHT = 1.5f;
diff --git a/native/jni/src/suggest/core/layout/proximity_info_params.h b/native/jni/src/suggest/core/layout/proximity_info_params.h
index ae1f82c22..b8e9f5daf 100644
--- a/native/jni/src/suggest/core/layout/proximity_info_params.h
+++ b/native/jni/src/suggest/core/layout/proximity_info_params.h
@@ -78,8 +78,13 @@ class ProximityInfoParams {
static const float SPEEDxNEAREST_WEIGHT_FOR_STANDARD_DEVIATION;
static const float MAX_SPEEDxNEAREST_RATE_FOR_STANDARD_DEVIATION;
static const float MIN_STANDARD_DEVIATION;
- static const float PREV_DISTANCE_WEIGHT;
- static const float NEXT_DISTANCE_WEIGHT;
+ // X means gesture's direction. Y means gesture's orthogonal direction.
+ static const float STANDARD_DEVIATION_X_WEIGHT_FOR_FIRST;
+ static const float STANDARD_DEVIATION_Y_WEIGHT_FOR_FIRST;
+ static const float STANDARD_DEVIATION_X_WEIGHT_FOR_LAST;
+ static const float STANDARD_DEVIATION_Y_WEIGHT_FOR_LAST;
+ static const float STANDARD_DEVIATION_X_WEIGHT;
+ static const float STANDARD_DEVIATION_Y_WEIGHT;
// Used by ProximityInfoStateUtils::suppressCharProbabilities()
static const float SUPPRESSION_LENGTH_WEIGHT;
diff --git a/native/jni/src/suggest/core/layout/proximity_info_state.cpp b/native/jni/src/suggest/core/layout/proximity_info_state.cpp
index 2919904e5..b75c2ef67 100644
--- a/native/jni/src/suggest/core/layout/proximity_info_state.cpp
+++ b/native/jni/src/suggest/core/layout/proximity_info_state.cpp
@@ -134,7 +134,7 @@ void ProximityInfoState::initInputParams(const int pointerId, const float maxPoi
mProximityInfo->getKeyCount(), lastSavedInputSize, mSampledInputSize,
&mSampledInputXs, &mSampledInputYs, &mSpeedRates, &mSampledLengthCache,
&mSampledNormalizedSquaredLengthCache, &mSampledNearKeySets,
- &mCharProbabilities);
+ mProximityInfo, &mCharProbabilities);
ProximityInfoStateUtils::updateSampledSearchKeySets(mProximityInfo,
mSampledInputSize, lastSavedInputSize, &mSampledLengthCache,
&mSampledNearKeySets, &mSampledSearchKeySets,
diff --git a/native/jni/src/suggest/core/layout/proximity_info_state_utils.cpp b/native/jni/src/suggest/core/layout/proximity_info_state_utils.cpp
index 5a3ff7384..638297eb1 100644
--- a/native/jni/src/suggest/core/layout/proximity_info_state_utils.cpp
+++ b/native/jni/src/suggest/core/layout/proximity_info_state_utils.cpp
@@ -24,7 +24,7 @@
#include "defines.h"
#include "suggest/core/layout/geometry_utils.h"
-#include "suggest/core/layout/normal_distribution.h"
+#include "suggest/core/layout/normal_distribution_2d.h"
#include "suggest/core/layout/proximity_info.h"
#include "suggest/core/layout/proximity_info_params.h"
@@ -627,6 +627,7 @@ namespace latinime {
const std::vector<int> *const sampledLengthCache,
const std::vector<float> *const sampledNormalizedSquaredLengthCache,
std::vector<NearKeycodesSet> *sampledNearKeySets,
+ const ProximityInfo *const proximityInfo,
std::vector<hash_map_compat<int, float> > *charProbabilities) {
charProbabilities->resize(sampledInputSize);
// Calculates probabilities of using a point as a correlated point with the character
@@ -709,89 +710,57 @@ namespace latinime {
// (1.0f - skipProbability).
const float inputCharProbability = 1.0f - skipProbability;
- const float speedxAngleRate = std::min(speedRate * currentAngle / M_PI_F
+ const float speedMultipliedByAngleRate = std::min(speedRate * currentAngle / M_PI_F
* ProximityInfoParams::SPEEDxANGLE_WEIGHT_FOR_STANDARD_DEVIATION,
ProximityInfoParams::MAX_SPEEDxANGLE_RATE_FOR_STANDARD_DEVIATION);
- const float speedxNearestKeyDistanceRate = std::min(speedRate * nearestKeyDistance
- * ProximityInfoParams::SPEEDxNEAREST_WEIGHT_FOR_STANDARD_DEVIATION,
- ProximityInfoParams::MAX_SPEEDxNEAREST_RATE_FOR_STANDARD_DEVIATION);
- const float sigma = speedxAngleRate + speedxNearestKeyDistanceRate
- + ProximityInfoParams::MIN_STANDARD_DEVIATION;
-
- NormalDistribution distribution(
- ProximityInfoParams::CENTER_VALUE_OF_NORMALIZED_DISTRIBUTION, sigma);
+ const float speedMultipliedByNearestKeyDistanceRate = std::min(
+ speedRate * nearestKeyDistance
+ * ProximityInfoParams::SPEEDxNEAREST_WEIGHT_FOR_STANDARD_DEVIATION,
+ ProximityInfoParams::MAX_SPEEDxNEAREST_RATE_FOR_STANDARD_DEVIATION);
+ const float sigma = (speedMultipliedByAngleRate + speedMultipliedByNearestKeyDistanceRate
+ + ProximityInfoParams::MIN_STANDARD_DEVIATION) * mostCommonKeyWidth;
+ float theta = 0.0f;
+ // TODO: Use different metrics to compute sigmas.
+ float sigmaX = sigma;
+ float sigmaY = sigma;
+ if (i == 0 && i != sampledInputSize - 1) {
+ // First point
+ theta = getDirection(sampledInputXs, sampledInputYs, i + 1, i);
+ sigmaX *= ProximityInfoParams::STANDARD_DEVIATION_X_WEIGHT_FOR_FIRST;
+ sigmaY *= ProximityInfoParams::STANDARD_DEVIATION_Y_WEIGHT_FOR_FIRST;
+ } else {
+ if (i == sampledInputSize - 1) {
+ // Last point
+ sigmaX *= ProximityInfoParams::STANDARD_DEVIATION_X_WEIGHT_FOR_LAST;
+ sigmaY *= ProximityInfoParams::STANDARD_DEVIATION_Y_WEIGHT_FOR_LAST;
+ } else {
+ sigmaX *= ProximityInfoParams::STANDARD_DEVIATION_X_WEIGHT;
+ sigmaY *= ProximityInfoParams::STANDARD_DEVIATION_Y_WEIGHT;
+ }
+ theta = getDirection(sampledInputXs, sampledInputYs, i, i - 1);
+ }
+ NormalDistribution2D distribution((*sampledInputXs)[i], sigmaX, (*sampledInputYs)[i],
+ sigmaY, theta);
// Summing up probability densities of all near keys.
float sumOfProbabilityDensities = 0.0f;
for (int j = 0; j < keyCount; ++j) {
if ((*sampledNearKeySets)[i].test(j)) {
- float distance = sqrtf(getPointToKeyByIdLength(
- maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount, i, j));
- if (i == 0 && i != sampledInputSize - 1) {
- // For the first point, weighted average of distances from first point and the
- // next point to the key is used as a point to key distance.
- const float nextDistance = sqrtf(getPointToKeyByIdLength(
- maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount,
- i + 1, j));
- if (nextDistance < distance) {
- // The distance of the first point tends to bigger than continuing
- // points because the first touch by the user can be sloppy.
- // So we promote the first point if the distance of that point is larger
- // than the distance of the next point.
- distance = (distance
- + nextDistance * ProximityInfoParams::NEXT_DISTANCE_WEIGHT)
- / (1.0f + ProximityInfoParams::NEXT_DISTANCE_WEIGHT);
- }
- } else if (i != 0 && i == sampledInputSize - 1) {
- // For the first point, weighted average of distances from last point and
- // the previous point to the key is used as a point to key distance.
- const float previousDistance = sqrtf(getPointToKeyByIdLength(
- maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount,
- i - 1, j));
- if (previousDistance < distance) {
- // The distance of the last point tends to bigger than continuing points
- // because the last touch by the user can be sloppy. So we promote the
- // last point if the distance of that point is larger than the distance of
- // the previous point.
- distance = (distance
- + previousDistance * ProximityInfoParams::PREV_DISTANCE_WEIGHT)
- / (1.0f + ProximityInfoParams::PREV_DISTANCE_WEIGHT);
- }
- }
- // TODO: Promote the first point when the extended line from the next input is near
- // from a key. Also, promote the last point as well.
- sumOfProbabilityDensities += distribution.getProbabilityDensity(distance);
+ sumOfProbabilityDensities += distribution.getProbabilityDensity(
+ proximityInfo->getKeyCenterXOfKeyIdG(j,
+ NOT_A_COORDINATE /* referencePointX */, true /* isGeometric */),
+ proximityInfo->getKeyCenterYOfKeyIdG(j,
+ NOT_A_COORDINATE /* referencePointY */, true /* isGeometric */));
}
}
// Split the probability of an input point to keys that are close to the input point.
for (int j = 0; j < keyCount; ++j) {
if ((*sampledNearKeySets)[i].test(j)) {
- float distance = sqrtf(getPointToKeyByIdLength(
- maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount, i, j));
- if (i == 0 && i != sampledInputSize - 1) {
- // For the first point, weighted average of distances from the first point and
- // the next point to the key is used as a point to key distance.
- const float prevDistance = sqrtf(getPointToKeyByIdLength(
- maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount,
- i + 1, j));
- if (prevDistance < distance) {
- distance = (distance
- + prevDistance * ProximityInfoParams::NEXT_DISTANCE_WEIGHT)
- / (1.0f + ProximityInfoParams::NEXT_DISTANCE_WEIGHT);
- }
- } else if (i != 0 && i == sampledInputSize - 1) {
- // For the first point, weighted average of distances from last point and
- // the previous point to the key is used as a point to key distance.
- const float prevDistance = sqrtf(getPointToKeyByIdLength(
- maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount,
- i - 1, j));
- if (prevDistance < distance) {
- distance = (distance
- + prevDistance * ProximityInfoParams::PREV_DISTANCE_WEIGHT)
- / (1.0f + ProximityInfoParams::PREV_DISTANCE_WEIGHT);
- }
- }
- const float probabilityDensity = distribution.getProbabilityDensity(distance);
+ const float probabilityDensity = distribution.getProbabilityDensity(
+ proximityInfo->getKeyCenterXOfKeyIdG(j,
+ NOT_A_COORDINATE /* referencePointX */, true /* isGeometric */),
+ proximityInfo->getKeyCenterYOfKeyIdG(j,
+ NOT_A_COORDINATE /* referencePointY */, true /* isGeometric */));
const float probability = inputCharProbability * probabilityDensity
/ sumOfProbabilityDensities;
(*charProbabilities)[i][j] = probability;
diff --git a/native/jni/src/suggest/core/layout/proximity_info_state_utils.h b/native/jni/src/suggest/core/layout/proximity_info_state_utils.h
index ea0cd1149..5d7a9c589 100644
--- a/native/jni/src/suggest/core/layout/proximity_info_state_utils.h
+++ b/native/jni/src/suggest/core/layout/proximity_info_state_utils.h
@@ -72,6 +72,7 @@ class ProximityInfoStateUtils {
const std::vector<int> *const sampledLengthCache,
const std::vector<float> *const sampledNormalizedSquaredLengthCache,
std::vector<NearKeycodesSet> *sampledNearKeySets,
+ const ProximityInfo *const proximityInfo,
std::vector<hash_map_compat<int, float> > *charProbabilities);
static void updateSampledSearchKeySets(const ProximityInfo *const proximityInfo,
const int sampledInputSize, const int lastSavedInputSize,
diff --git a/native/jni/src/suggest/core/dictionary/bloom_filter.cpp b/native/jni/tests/defines_test.cpp
index 4ae474e0c..f7b80b2b5 100644
--- a/native/jni/src/suggest/core/dictionary/bloom_filter.cpp
+++ b/native/jni/tests/defines_test.cpp
@@ -1,11 +1,11 @@
/*
- * Copyright (C) 2013, The Android Open Source Project
+ * Copyright (C) 2014 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
+ * 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,
@@ -14,12 +14,21 @@
* limitations under the License.
*/
-#include "suggest/core/dictionary/bloom_filter.h"
+#include "defines.h"
+
+#include <gtest/gtest.h>
namespace latinime {
+namespace {
-// Must be smaller than BIGRAM_FILTER_BYTE_SIZE * 8, and preferably prime. 1021 is the largest
-// prime under 128 * 8.
-const int BloomFilter::BIGRAM_FILTER_MODULO = 1021;
+TEST(DefinesTest, NELEMSForFixedLengthArray) {
+ const size_t SMALL_ARRAY_SIZE = 1;
+ const size_t LARGE_ARRAY_SIZE = 100;
+ int smallArray[SMALL_ARRAY_SIZE];
+ int largeArray[LARGE_ARRAY_SIZE];
+ EXPECT_EQ(SMALL_ARRAY_SIZE, NELEMS(smallArray));
+ EXPECT_EQ(LARGE_ARRAY_SIZE, NELEMS(largeArray));
+}
-} // namespace latinime
+} // namespace
+} // namespace latinime
diff --git a/native/jni/tests/suggest/core/dictionary/bloom_filter_test.cpp b/native/jni/tests/suggest/core/dictionary/bloom_filter_test.cpp
new file mode 100644
index 000000000..b62021784
--- /dev/null
+++ b/native/jni/tests/suggest/core/dictionary/bloom_filter_test.cpp
@@ -0,0 +1,80 @@
+/*
+ * Copyright (C) 2014 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.
+ */
+
+#include "suggest/core/dictionary/bloom_filter.h"
+
+#include <gtest/gtest.h>
+
+#include <algorithm>
+#include <cstdlib>
+#include <functional>
+#include <random>
+#include <unordered_set>
+#include <vector>
+
+namespace latinime {
+namespace {
+
+TEST(BloomFilterTest, TestFilter) {
+ static const int TEST_RANDOM_DATA_MAX = 65536;
+ static const int ELEMENT_COUNT = 1000;
+ std::vector<int> elements;
+
+ // Initialize data set with random integers.
+ {
+ // Use the uniform integer distribution [0, TEST_RANDOM_DATA_MAX].
+ std::uniform_int_distribution<int> distribution(0, TEST_RANDOM_DATA_MAX);
+ auto randomNumberGenerator = std::bind(distribution, std::mt19937());
+ for (int i = 0; i < ELEMENT_COUNT; ++i) {
+ elements.push_back(randomNumberGenerator());
+ }
+ }
+
+ // Make sure BloomFilter contains nothing by default.
+ BloomFilter bloomFilter;
+ for (const int elem : elements) {
+ ASSERT_FALSE(bloomFilter.isInFilter(elem));
+ }
+
+ // Copy some of the test vector into bloom filter.
+ std::unordered_set<int> elementsThatHaveBeenSetInFilter;
+ {
+ // Use the uniform integer distribution [0, 1].
+ std::uniform_int_distribution<int> distribution(0, 1);
+ auto randomBitGenerator = std::bind(distribution, std::mt19937());
+ for (const int elem : elements) {
+ if (randomBitGenerator() == 0) {
+ bloomFilter.setInFilter(elem);
+ elementsThatHaveBeenSetInFilter.insert(elem);
+ }
+ }
+ }
+
+ for (const int elem : elements) {
+ const bool existsInFilter = bloomFilter.isInFilter(elem);
+ const bool hasBeenSetInFilter =
+ elementsThatHaveBeenSetInFilter.find(elem) != elementsThatHaveBeenSetInFilter.end();
+ if (hasBeenSetInFilter) {
+ EXPECT_TRUE(existsInFilter) << "elem: " << elem;
+ }
+ if (!existsInFilter) {
+ EXPECT_FALSE(hasBeenSetInFilter) << "elem: " << elem;
+ }
+ }
+}
+
+} // namespace
+} // namespace latinime
diff --git a/native/jni/tests/suggest/core/layout/normal_distribution_2d_test.cpp b/native/jni/tests/suggest/core/layout/normal_distribution_2d_test.cpp
new file mode 100644
index 000000000..1d6a27c4f
--- /dev/null
+++ b/native/jni/tests/suggest/core/layout/normal_distribution_2d_test.cpp
@@ -0,0 +1,68 @@
+/*
+ * Copyright (C) 2014 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.
+ */
+
+#include "suggest/core/layout/normal_distribution_2d.h"
+
+#include <gtest/gtest.h>
+
+#include <vector>
+
+namespace latinime {
+namespace {
+
+static const float ORIGIN_X = 0.0f;
+static const float ORIGIN_Y = 0.0f;
+static const float LARGE_STANDARD_DEVIATION = 100.0f;
+static const float SMALL_STANDARD_DEVIATION = 10.0f;
+static const float ZERO_RADIAN = 0.0f;
+
+TEST(NormalDistribution2DTest, ProbabilityDensity) {
+ const NormalDistribution2D distribution(ORIGIN_X, LARGE_STANDARD_DEVIATION, ORIGIN_Y,
+ SMALL_STANDARD_DEVIATION, ZERO_RADIAN);
+
+ static const float SMALL_COORDINATE = 10.0f;
+ static const float LARGE_COORDINATE = 20.0f;
+ // The probability density of the point near the distribution center is larger than the
+ // probability density of the point that is far from distribution center.
+ EXPECT_GE(distribution.getProbabilityDensity(SMALL_COORDINATE, SMALL_COORDINATE),
+ distribution.getProbabilityDensity(LARGE_COORDINATE, LARGE_COORDINATE));
+ // The probability density of the point shifted toward the direction that has larger standard
+ // deviation is larger than the probability density of the point shifted towards another
+ // direction.
+ EXPECT_GE(distribution.getProbabilityDensity(LARGE_COORDINATE, SMALL_COORDINATE),
+ distribution.getProbabilityDensity(SMALL_COORDINATE, LARGE_COORDINATE));
+}
+
+TEST(NormalDistribution2DTest, Rotate) {
+ static const float COORDINATES[] = {0.0f, 10.0f, 100.0f, -20.0f};
+ static const float EPSILON = 0.01f;
+ const NormalDistribution2D distribution(ORIGIN_X, LARGE_STANDARD_DEVIATION, ORIGIN_Y,
+ SMALL_STANDARD_DEVIATION, ZERO_RADIAN);
+ const NormalDistribution2D rotatedDistribution(ORIGIN_X, LARGE_STANDARD_DEVIATION, ORIGIN_Y,
+ SMALL_STANDARD_DEVIATION, M_PI_4);
+ for (const float x : COORDINATES) {
+ for (const float y : COORDINATES) {
+ // The probability density of the rotated distribution at the point and the probability
+ // density of the original distribution at the rotated point are the same.
+ const float probabilityDensity0 = distribution.getProbabilityDensity(x, y);
+ const float probabilityDensity1 = rotatedDistribution.getProbabilityDensity(-y, x);
+ EXPECT_NEAR(probabilityDensity0, probabilityDensity1, EPSILON);
+ }
+ }
+}
+
+} // namespace
+} // namespace latinime