diff options
Diffstat (limited to 'native/jni/src/proximity_info_state_utils.cpp')
| -rw-r--r-- | native/jni/src/proximity_info_state_utils.cpp | 1029 |
1 files changed, 1029 insertions, 0 deletions
diff --git a/native/jni/src/proximity_info_state_utils.cpp b/native/jni/src/proximity_info_state_utils.cpp new file mode 100644 index 000000000..be6cde17b --- /dev/null +++ b/native/jni/src/proximity_info_state_utils.cpp @@ -0,0 +1,1029 @@ +/* + * Copyright (C) 2013 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 <cmath> +#include <sstream> // for debug prints +#include <vector> + +#include "defines.h" +#include "geometry_utils.h" +#include "proximity_info.h" +#include "proximity_info_params.h" +#include "proximity_info_state_utils.h" + +namespace latinime { + +/* static */ int ProximityInfoStateUtils::updateTouchPoints(const int mostCommonKeyWidth, + const ProximityInfo *const proximityInfo, const int maxPointToKeyLength, + const int *const inputProximities, const int *const inputXCoordinates, + const int *const inputYCoordinates, const int *const times, const int *const pointerIds, + const int inputSize, const bool isGeometric, const int pointerId, + const int pushTouchPointStartIndex, std::vector<int> *sampledInputXs, + std::vector<int> *sampledInputYs, std::vector<int> *sampledInputTimes, + std::vector<int> *sampledLengthCache, std::vector<int> *sampledInputIndice) { + if (DEBUG_SAMPLING_POINTS) { + if (times) { + for (int i = 0; i < inputSize; ++i) { + AKLOGI("(%d) x %d, y %d, time %d", + i, inputXCoordinates[i], inputYCoordinates[i], times[i]); + } + } + } +#ifdef DO_ASSERT_TEST + if (times) { + for (int i = 0; i < inputSize; ++i) { + if (i > 0) { + if (times[i] < times[i - 1]) { + AKLOGI("Invalid time sequence. %d, %d", times[i], times[i - 1]); + ASSERT(false); + } + } + } + } +#endif + const bool proximityOnly = !isGeometric + && (inputXCoordinates[0] < 0 || inputYCoordinates[0] < 0); + int lastInputIndex = pushTouchPointStartIndex; + for (int i = lastInputIndex; i < inputSize; ++i) { + const int pid = pointerIds ? pointerIds[i] : 0; + if (pointerId == pid) { + lastInputIndex = i; + } + } + if (DEBUG_GEO_FULL) { + AKLOGI("Init ProximityInfoState: last input index = %d", lastInputIndex); + } + // Working space to save near keys distances for current, prev and prevprev input point. + NearKeysDistanceMap nearKeysDistances[3]; + // These pointers are swapped for each inputs points. + NearKeysDistanceMap *currentNearKeysDistances = &nearKeysDistances[0]; + NearKeysDistanceMap *prevNearKeysDistances = &nearKeysDistances[1]; + NearKeysDistanceMap *prevPrevNearKeysDistances = &nearKeysDistances[2]; + // "sumAngle" is accumulated by each angle of input points. And when "sumAngle" exceeds + // the threshold we save that point, reset sumAngle. This aims to keep the figure of + // the curve. + float sumAngle = 0.0f; + + for (int i = pushTouchPointStartIndex; i <= lastInputIndex; ++i) { + // Assuming pointerId == 0 if pointerIds is null. + const int pid = pointerIds ? pointerIds[i] : 0; + if (DEBUG_GEO_FULL) { + AKLOGI("Init ProximityInfoState: (%d)PID = %d", i, pid); + } + if (pointerId == pid) { + const int c = isGeometric ? + NOT_A_COORDINATE : getPrimaryCodePointAt(inputProximities, i); + const int x = proximityOnly ? NOT_A_COORDINATE : inputXCoordinates[i]; + const int y = proximityOnly ? NOT_A_COORDINATE : inputYCoordinates[i]; + const int time = times ? times[i] : -1; + + if (i > 1) { + const float prevAngle = getAngle( + inputXCoordinates[i - 2], inputYCoordinates[i - 2], + inputXCoordinates[i - 1], inputYCoordinates[i - 1]); + const float currentAngle = + getAngle(inputXCoordinates[i - 1], inputYCoordinates[i - 1], x, y); + sumAngle += getAngleDiff(prevAngle, currentAngle); + } + + if (pushTouchPoint(mostCommonKeyWidth, proximityInfo, maxPointToKeyLength, + i, c, x, y, time, isGeometric /* doSampling */, + i == lastInputIndex, sumAngle, currentNearKeysDistances, + prevNearKeysDistances, prevPrevNearKeysDistances, + sampledInputXs, sampledInputYs, sampledInputTimes, sampledLengthCache, + sampledInputIndice)) { + // Previous point information was popped. + NearKeysDistanceMap *tmp = prevNearKeysDistances; + prevNearKeysDistances = currentNearKeysDistances; + currentNearKeysDistances = tmp; + } else { + NearKeysDistanceMap *tmp = prevPrevNearKeysDistances; + prevPrevNearKeysDistances = prevNearKeysDistances; + prevNearKeysDistances = currentNearKeysDistances; + currentNearKeysDistances = tmp; + sumAngle = 0.0f; + } + } + } + return sampledInputXs->size(); +} + +/* static */ const int *ProximityInfoStateUtils::getProximityCodePointsAt( + const int *const inputProximities, const int index) { + return inputProximities + (index * MAX_PROXIMITY_CHARS_SIZE); +} + +/* static */ int ProximityInfoStateUtils::getPrimaryCodePointAt( + const int *const inputProximities, const int index) { + return getProximityCodePointsAt(inputProximities, index)[0]; +} + +/* static */ void ProximityInfoStateUtils::initPrimaryInputWord( + const int inputSize, const int *const inputProximities, int *primaryInputWord) { + for (int i = 0; i < inputSize; ++i) { + primaryInputWord[i] = getPrimaryCodePointAt(inputProximities, i); + } +} + +/* static */ float ProximityInfoStateUtils::calculateSquaredDistanceFromSweetSpotCenter( + const ProximityInfo *const proximityInfo, const std::vector<int> *const sampledInputXs, + const std::vector<int> *const sampledInputYs, const int keyIndex, + const int inputIndex) { + const float sweetSpotCenterX = proximityInfo->getSweetSpotCenterXAt(keyIndex); + const float sweetSpotCenterY = proximityInfo->getSweetSpotCenterYAt(keyIndex); + const float inputX = static_cast<float>((*sampledInputXs)[inputIndex]); + const float inputY = static_cast<float>((*sampledInputYs)[inputIndex]); + return SQUARE_FLOAT(inputX - sweetSpotCenterX) + SQUARE_FLOAT(inputY - sweetSpotCenterY); +} + +/* static */ float ProximityInfoStateUtils::calculateNormalizedSquaredDistance( + const ProximityInfo *const proximityInfo, const std::vector<int> *const sampledInputXs, + const std::vector<int> *const sampledInputYs, + const int keyIndex, const int inputIndex) { + if (keyIndex == NOT_AN_INDEX) { + return ProximityInfoParams::NOT_A_DISTANCE_FLOAT; + } + if (!proximityInfo->hasSweetSpotData(keyIndex)) { + return ProximityInfoParams::NOT_A_DISTANCE_FLOAT; + } + if (NOT_A_COORDINATE == (*sampledInputXs)[inputIndex]) { + return ProximityInfoParams::NOT_A_DISTANCE_FLOAT; + } + const float squaredDistance = calculateSquaredDistanceFromSweetSpotCenter(proximityInfo, + sampledInputXs, sampledInputYs, keyIndex, inputIndex); + const float squaredRadius = SQUARE_FLOAT(proximityInfo->getSweetSpotRadiiAt(keyIndex)); + return squaredDistance / squaredRadius; +} + +/* static */ void ProximityInfoStateUtils::initNormalizedSquaredDistances( + const ProximityInfo *const proximityInfo, const int inputSize, + const int *inputXCoordinates, const int *inputYCoordinates, + const int *const inputProximities, const bool hasInputCoordinates, + const std::vector<int> *const sampledInputXs, + const std::vector<int> *const sampledInputYs, + int *normalizedSquaredDistances) { + for (int i = 0; i < inputSize; ++i) { + const int *proximityCodePoints = getProximityCodePointsAt(inputProximities, i); + const int primaryKey = proximityCodePoints[0]; + const int x = inputXCoordinates[i]; + const int y = inputYCoordinates[i]; + if (DEBUG_PROXIMITY_CHARS) { + int a = x + y + primaryKey; + a += 0; + AKLOGI("--- Primary = %c, x = %d, y = %d", primaryKey, x, y); + } + for (int j = 0; j < MAX_PROXIMITY_CHARS_SIZE && proximityCodePoints[j] > 0; + ++j) { + const int currentCodePoint = proximityCodePoints[j]; + const float squaredDistance = + hasInputCoordinates ? calculateNormalizedSquaredDistance( + proximityInfo, sampledInputXs, sampledInputYs, + proximityInfo->getKeyIndexOf(currentCodePoint), i) : + ProximityInfoParams::NOT_A_DISTANCE_FLOAT; + if (squaredDistance >= 0.0f) { + normalizedSquaredDistances[i * MAX_PROXIMITY_CHARS_SIZE + j] = + (int) (squaredDistance + * ProximityInfoParams::NORMALIZED_SQUARED_DISTANCE_SCALING_FACTOR); + } else { + normalizedSquaredDistances[i * MAX_PROXIMITY_CHARS_SIZE + j] = + (j == 0) ? EQUIVALENT_CHAR_WITHOUT_DISTANCE_INFO : + PROXIMITY_CHAR_WITHOUT_DISTANCE_INFO; + } + if (DEBUG_PROXIMITY_CHARS) { + AKLOGI("--- Proximity (%d) = %c", j, currentCodePoint); + } + } + } + +} + +/* static */ void ProximityInfoStateUtils::initGeometricDistanceInfos( + const ProximityInfo *const proximityInfo, const int keyCount, + const int sampledInputSize, const int lastSavedInputSize, + const std::vector<int> *const sampledInputXs, + const std::vector<int> *const sampledInputYs, + std::vector<NearKeycodesSet> *nearKeysVector, + std::vector<NearKeycodesSet> *searchKeysVector, + std::vector<float> *distanceCache_G) { + nearKeysVector->resize(sampledInputSize); + searchKeysVector->resize(sampledInputSize); + distanceCache_G->resize(sampledInputSize * keyCount); + for (int i = lastSavedInputSize; i < sampledInputSize; ++i) { + (*nearKeysVector)[i].reset(); + (*searchKeysVector)[i].reset(); + static const float NEAR_KEY_NORMALIZED_SQUARED_THRESHOLD = 4.0f; + for (int k = 0; k < keyCount; ++k) { + const int index = i * keyCount + k; + const int x = (*sampledInputXs)[i]; + const int y = (*sampledInputYs)[i]; + const float normalizedSquaredDistance = + proximityInfo->getNormalizedSquaredDistanceFromCenterFloatG(k, x, y); + (*distanceCache_G)[index] = normalizedSquaredDistance; + if (normalizedSquaredDistance < NEAR_KEY_NORMALIZED_SQUARED_THRESHOLD) { + (*nearKeysVector)[i][k] = true; + } + } + } +} + +/* static */ void ProximityInfoStateUtils::popInputData(std::vector<int> *sampledInputXs, + std::vector<int> *sampledInputYs, std::vector<int> *sampledInputTimes, + std::vector<int> *sampledLengthCache, std::vector<int> *sampledInputIndice) { + sampledInputXs->pop_back(); + sampledInputYs->pop_back(); + sampledInputTimes->pop_back(); + sampledLengthCache->pop_back(); + sampledInputIndice->pop_back(); +} + +/* static */ float ProximityInfoStateUtils::refreshSpeedRates(const int inputSize, + const int *const xCoordinates, const int *const yCoordinates, const int *const times, + const int lastSavedInputSize, const int sampledInputSize, + const std::vector<int> *const sampledInputXs, + const std::vector<int> *const sampledInputYs, + const std::vector<int> *const sampledInputTimes, + const std::vector<int> *const sampledLengthCache, + const std::vector<int> *const sampledInputIndice, std::vector<float> *sampledSpeedRates, + std::vector<float> *sampledDirections) { + // Relative speed calculation. + const int sumDuration = sampledInputTimes->back() - sampledInputTimes->front(); + const int sumLength = sampledLengthCache->back() - sampledLengthCache->front(); + const float averageSpeed = static_cast<float>(sumLength) / static_cast<float>(sumDuration); + sampledSpeedRates->resize(sampledInputSize); + for (int i = lastSavedInputSize; i < sampledInputSize; ++i) { + const int index = (*sampledInputIndice)[i]; + int length = 0; + int duration = 0; + + // Calculate velocity by using distances and durations of + // NUM_POINTS_FOR_SPEED_CALCULATION points for both forward and backward. + static const int NUM_POINTS_FOR_SPEED_CALCULATION = 2; + for (int j = index; j < min(inputSize - 1, index + NUM_POINTS_FOR_SPEED_CALCULATION); + ++j) { + if (i < sampledInputSize - 1 && j >= (*sampledInputIndice)[i + 1]) { + break; + } + length += getDistanceInt(xCoordinates[j], yCoordinates[j], + xCoordinates[j + 1], yCoordinates[j + 1]); + duration += times[j + 1] - times[j]; + } + for (int j = index - 1; j >= max(0, index - NUM_POINTS_FOR_SPEED_CALCULATION); --j) { + if (i > 0 && j < (*sampledInputIndice)[i - 1]) { + break; + } + // TODO: use mSampledLengthCache instead? + length += getDistanceInt(xCoordinates[j], yCoordinates[j], + xCoordinates[j + 1], yCoordinates[j + 1]); + duration += times[j + 1] - times[j]; + } + if (duration == 0 || sumDuration == 0) { + // Cannot calculate speed; thus, it gives an average value (1.0); + (*sampledSpeedRates)[i] = 1.0f; + } else { + const float speed = static_cast<float>(length) / static_cast<float>(duration); + (*sampledSpeedRates)[i] = speed / averageSpeed; + } + } + + // Direction calculation. + sampledDirections->resize(sampledInputSize - 1); + for (int i = max(0, lastSavedInputSize - 1); i < sampledInputSize - 1; ++i) { + (*sampledDirections)[i] = getDirection(sampledInputXs, sampledInputYs, i, i + 1); + } + return averageSpeed; +} + +/* static */ void ProximityInfoStateUtils::refreshBeelineSpeedRates(const int mostCommonKeyWidth, + const float averageSpeed, const int inputSize, const int *const xCoordinates, + const int *const yCoordinates, const int *times, const int sampledInputSize, + const std::vector<int> *const sampledInputXs, + const std::vector<int> *const sampledInputYs, const std::vector<int> *const inputIndice, + std::vector<int> *beelineSpeedPercentiles) { + if (DEBUG_SAMPLING_POINTS) { + AKLOGI("--- refresh beeline speed rates"); + } + beelineSpeedPercentiles->resize(sampledInputSize); + for (int i = 0; i < sampledInputSize; ++i) { + (*beelineSpeedPercentiles)[i] = static_cast<int>(calculateBeelineSpeedRate( + mostCommonKeyWidth, averageSpeed, i, inputSize, xCoordinates, yCoordinates, times, + sampledInputSize, sampledInputXs, sampledInputYs, inputIndice) * MAX_PERCENTILE); + } +} + +/* static */float ProximityInfoStateUtils::getDirection( + const std::vector<int> *const sampledInputXs, + const std::vector<int> *const sampledInputYs, const int index0, const int index1) { + ASSERT(sampledInputXs && sampledInputYs); + const int sampledInputSize =sampledInputXs->size(); + if (index0 < 0 || index0 > sampledInputSize - 1) { + return 0.0f; + } + if (index1 < 0 || index1 > sampledInputSize - 1) { + return 0.0f; + } + const int x1 = (*sampledInputXs)[index0]; + const int y1 = (*sampledInputYs)[index0]; + const int x2 = (*sampledInputXs)[index1]; + const int y2 = (*sampledInputYs)[index1]; + return getAngle(x1, y1, x2, y2); +} + +// Calculating point to key distance for all near keys and returning the distance between +// the given point and the nearest key position. +/* static */ float ProximityInfoStateUtils::updateNearKeysDistances( + const ProximityInfo *const proximityInfo, const float maxPointToKeyLength, const int x, + const int y, NearKeysDistanceMap *const currentNearKeysDistances) { + static const float NEAR_KEY_THRESHOLD = 2.0f; + + currentNearKeysDistances->clear(); + const int keyCount = proximityInfo->getKeyCount(); + float nearestKeyDistance = maxPointToKeyLength; + for (int k = 0; k < keyCount; ++k) { + const float dist = proximityInfo->getNormalizedSquaredDistanceFromCenterFloatG(k, x, y); + if (dist < NEAR_KEY_THRESHOLD) { + currentNearKeysDistances->insert(std::pair<int, float>(k, dist)); + } + if (nearestKeyDistance > dist) { + nearestKeyDistance = dist; + } + } + return nearestKeyDistance; +} + +// Check if previous point is at local minimum position to near keys. +/* static */ bool ProximityInfoStateUtils::isPrevLocalMin( + const NearKeysDistanceMap *const currentNearKeysDistances, + const NearKeysDistanceMap *const prevNearKeysDistances, + const NearKeysDistanceMap *const prevPrevNearKeysDistances) { + static const float MARGIN = 0.01f; + + for (NearKeysDistanceMap::const_iterator it = prevNearKeysDistances->begin(); + it != prevNearKeysDistances->end(); ++it) { + NearKeysDistanceMap::const_iterator itPP = prevPrevNearKeysDistances->find(it->first); + NearKeysDistanceMap::const_iterator itC = currentNearKeysDistances->find(it->first); + if ((itPP == prevPrevNearKeysDistances->end() || itPP->second > it->second + MARGIN) + && (itC == currentNearKeysDistances->end() || itC->second > it->second + MARGIN)) { + return true; + } + } + return false; +} + +// Calculating a point score that indicates usefulness of the point. +/* static */ float ProximityInfoStateUtils::getPointScore(const int mostCommonKeyWidth, + const int x, const int y, const int time, const bool lastPoint, const float nearest, + const float sumAngle, const NearKeysDistanceMap *const currentNearKeysDistances, + const NearKeysDistanceMap *const prevNearKeysDistances, + const NearKeysDistanceMap *const prevPrevNearKeysDistances, + std::vector<int> *sampledInputXs, std::vector<int> *sampledInputYs) { + static const int DISTANCE_BASE_SCALE = 100; + static const float NEAR_KEY_THRESHOLD = 0.6f; + static const int CORNER_CHECK_DISTANCE_THRESHOLD_SCALE = 25; + static const float NOT_LOCALMIN_DISTANCE_SCORE = -1.0f; + static const float LOCALMIN_DISTANCE_AND_NEAR_TO_KEY_SCORE = 1.0f; + static const float CORNER_ANGLE_THRESHOLD = M_PI_F * 2.0f / 3.0f; + static const float CORNER_SUM_ANGLE_THRESHOLD = M_PI_F / 4.0f; + static const float CORNER_SCORE = 1.0f; + + const size_t size = sampledInputXs->size(); + // If there is only one point, add this point. Besides, if the previous point's distance map + // is empty, we re-compute nearby keys distances from the current point. + // Note that the current point is the first point in the incremental input that needs to + // be re-computed. + if (size <= 1 || prevNearKeysDistances->empty()) { + return 0.0f; + } + + const int baseSampleRate = mostCommonKeyWidth; + const int distPrev = getDistanceInt(sampledInputXs->back(), sampledInputYs->back(), + (*sampledInputXs)[size - 2], (*sampledInputYs)[size - 2]) * DISTANCE_BASE_SCALE; + float score = 0.0f; + + // Location + if (!isPrevLocalMin(currentNearKeysDistances, prevNearKeysDistances, + prevPrevNearKeysDistances)) { + score += NOT_LOCALMIN_DISTANCE_SCORE; + } else if (nearest < NEAR_KEY_THRESHOLD) { + // Promote points nearby keys + score += LOCALMIN_DISTANCE_AND_NEAR_TO_KEY_SCORE; + } + // Angle + const float angle1 = getAngle(x, y, sampledInputXs->back(), sampledInputYs->back()); + const float angle2 = getAngle(sampledInputXs->back(), sampledInputYs->back(), + (*sampledInputXs)[size - 2], (*sampledInputYs)[size - 2]); + const float angleDiff = getAngleDiff(angle1, angle2); + + // Save corner + if (distPrev > baseSampleRate * CORNER_CHECK_DISTANCE_THRESHOLD_SCALE + && (sumAngle > CORNER_SUM_ANGLE_THRESHOLD || angleDiff > CORNER_ANGLE_THRESHOLD)) { + score += CORNER_SCORE; + } + return score; +} + +// Sampling touch point and pushing information to vectors. +// Returning if previous point is popped or not. +/* static */ bool ProximityInfoStateUtils::pushTouchPoint(const int mostCommonKeyWidth, + const ProximityInfo *const proximityInfo, const int maxPointToKeyLength, + const int inputIndex, const int nodeCodePoint, int x, int y, + const int time, const bool doSampling, const bool isLastPoint, const float sumAngle, + NearKeysDistanceMap *const currentNearKeysDistances, + const NearKeysDistanceMap *const prevNearKeysDistances, + const NearKeysDistanceMap *const prevPrevNearKeysDistances, + std::vector<int> *sampledInputXs, std::vector<int> *sampledInputYs, + std::vector<int> *sampledInputTimes, std::vector<int> *sampledLengthCache, + std::vector<int> *sampledInputIndice) { + static const int LAST_POINT_SKIP_DISTANCE_SCALE = 4; + + size_t size = sampledInputXs->size(); + bool popped = false; + if (nodeCodePoint < 0 && doSampling) { + const float nearest = updateNearKeysDistances( + proximityInfo, maxPointToKeyLength, x, y, currentNearKeysDistances); + const float score = getPointScore(mostCommonKeyWidth, x, y, time, isLastPoint, nearest, + sumAngle, currentNearKeysDistances, prevNearKeysDistances, + prevPrevNearKeysDistances, sampledInputXs, sampledInputYs); + if (score < 0) { + // Pop previous point because it would be useless. + popInputData(sampledInputXs, sampledInputYs, sampledInputTimes, sampledLengthCache, + sampledInputIndice); + size = sampledInputXs->size(); + popped = true; + } else { + popped = false; + } + // Check if the last point should be skipped. + if (isLastPoint && size > 0) { + if (getDistanceInt(x, y, sampledInputXs->back(), + sampledInputYs->back()) * LAST_POINT_SKIP_DISTANCE_SCALE + < mostCommonKeyWidth) { + // This point is not used because it's too close to the previous point. + if (DEBUG_GEO_FULL) { + AKLOGI("p0: size = %zd, x = %d, y = %d, lx = %d, ly = %d, dist = %d, " + "width = %d", size, x, y, sampledInputXs->back(), + sampledInputYs->back(), getDistanceInt( + x, y, sampledInputXs->back(), sampledInputYs->back()), + mostCommonKeyWidth / LAST_POINT_SKIP_DISTANCE_SCALE); + } + return popped; + } + } + } + + if (nodeCodePoint >= 0 && (x < 0 || y < 0)) { + const int keyId = proximityInfo->getKeyIndexOf(nodeCodePoint); + if (keyId >= 0) { + x = proximityInfo->getKeyCenterXOfKeyIdG(keyId); + y = proximityInfo->getKeyCenterYOfKeyIdG(keyId); + } + } + + // Pushing point information. + if (size > 0) { + sampledLengthCache->push_back( + sampledLengthCache->back() + getDistanceInt( + x, y, sampledInputXs->back(), sampledInputYs->back())); + } else { + sampledLengthCache->push_back(0); + } + sampledInputXs->push_back(x); + sampledInputYs->push_back(y); + sampledInputTimes->push_back(time); + sampledInputIndice->push_back(inputIndex); + if (DEBUG_GEO_FULL) { + AKLOGI("pushTouchPoint: x = %03d, y = %03d, time = %d, index = %d, popped ? %01d", + x, y, time, inputIndex, popped); + } + return popped; +} + +/* static */ float ProximityInfoStateUtils::calculateBeelineSpeedRate(const int mostCommonKeyWidth, + const float averageSpeed, const int id, const int inputSize, const int *const xCoordinates, + const int *const yCoordinates, const int *times, const int sampledInputSize, + const std::vector<int> *const sampledInputXs, + const std::vector<int> *const sampledInputYs, + const std::vector<int> *const sampledInputIndices) { + if (sampledInputSize <= 0 || averageSpeed < 0.001f) { + if (DEBUG_SAMPLING_POINTS) { + AKLOGI("--- invalid state: cancel. size = %d, ave = %f", + sampledInputSize, averageSpeed); + } + return 1.0f; + } + const int lookupRadius = mostCommonKeyWidth + * ProximityInfoParams::LOOKUP_RADIUS_PERCENTILE / MAX_PERCENTILE; + const int x0 = (*sampledInputXs)[id]; + const int y0 = (*sampledInputYs)[id]; + const int actualInputIndex = (*sampledInputIndices)[id]; + int tempTime = 0; + int tempBeelineDistance = 0; + int start = actualInputIndex; + // lookup forward + while (start > 0 && tempBeelineDistance < lookupRadius) { + tempTime += times[start] - times[start - 1]; + --start; + tempBeelineDistance = getDistanceInt(x0, y0, xCoordinates[start], yCoordinates[start]); + } + // Exclusive unless this is an edge point + if (start > 0 && start < actualInputIndex) { + ++start; + } + tempTime= 0; + tempBeelineDistance = 0; + int end = actualInputIndex; + // lookup backward + while (end < (inputSize - 1) && tempBeelineDistance < lookupRadius) { + tempTime += times[end + 1] - times[end]; + ++end; + tempBeelineDistance = getDistanceInt(x0, y0, xCoordinates[end], yCoordinates[end]); + } + // Exclusive unless this is an edge point + if (end > actualInputIndex && end < (inputSize - 1)) { + --end; + } + + if (start >= end) { + if (DEBUG_DOUBLE_LETTER) { + AKLOGI("--- double letter: start == end %d", start); + } + return 1.0f; + } + + const int x2 = xCoordinates[start]; + const int y2 = yCoordinates[start]; + const int x3 = xCoordinates[end]; + const int y3 = yCoordinates[end]; + const int beelineDistance = getDistanceInt(x2, y2, x3, y3); + int adjustedStartTime = times[start]; + if (start == 0 && actualInputIndex == 0 && inputSize > 1) { + adjustedStartTime += ProximityInfoParams::FIRST_POINT_TIME_OFFSET_MILLIS; + } + int adjustedEndTime = times[end]; + if (end == (inputSize - 1) && inputSize > 1) { + adjustedEndTime -= ProximityInfoParams::FIRST_POINT_TIME_OFFSET_MILLIS; + } + const int time = adjustedEndTime - adjustedStartTime; + if (time <= 0) { + return 1.0f; + } + + if (time >= ProximityInfoParams::STRONG_DOUBLE_LETTER_TIME_MILLIS){ + return 0.0f; + } + if (DEBUG_DOUBLE_LETTER) { + AKLOGI("--- (%d, %d) double letter: start = %d, end = %d, dist = %d, time = %d," + " speed = %f, ave = %f, val = %f, start time = %d, end time = %d", + id, (*sampledInputIndices)[id], start, end, beelineDistance, time, + (static_cast<float>(beelineDistance) / static_cast<float>(time)), averageSpeed, + ((static_cast<float>(beelineDistance) / static_cast<float>(time)) + / averageSpeed), adjustedStartTime, adjustedEndTime); + } + // Offset 1% + // TODO: Detect double letter more smartly + return 0.01f + static_cast<float>(beelineDistance) / static_cast<float>(time) / averageSpeed; +} + +/* static */ float ProximityInfoStateUtils::getPointAngle( + const std::vector<int> *const sampledInputXs, + const std::vector<int> *const sampledInputYs, const int index) { + if (!sampledInputXs || !sampledInputYs) { + return 0.0f; + } + const int sampledInputSize = sampledInputXs->size(); + if (index <= 0 || index >= sampledInputSize - 1) { + return 0.0f; + } + const float previousDirection = getDirection(sampledInputXs, sampledInputYs, index - 1, index); + const float nextDirection = getDirection(sampledInputXs, sampledInputYs, index, index + 1); + const float directionDiff = getAngleDiff(previousDirection, nextDirection); + return directionDiff; +} + +/* static */ float ProximityInfoStateUtils::getPointsAngle( + const std::vector<int> *const sampledInputXs, + const std::vector<int> *const sampledInputYs, + const int index0, const int index1, const int index2) { + if (!sampledInputXs || !sampledInputYs) { + return 0.0f; + } + const int sampledInputSize = sampledInputXs->size(); + if (index0 < 0 || index0 > sampledInputSize - 1) { + return 0.0f; + } + if (index1 < 0 || index1 > sampledInputSize - 1) { + return 0.0f; + } + if (index2 < 0 || index2 > sampledInputSize - 1) { + return 0.0f; + } + const float previousDirection = getDirection(sampledInputXs, sampledInputYs, index0, index1); + const float nextDirection = getDirection(sampledInputXs, sampledInputYs, index1, index2); + return getAngleDiff(previousDirection, nextDirection); +} + +// TODO: Remove the "scale" parameter +// This function basically converts from a length to an edit distance. Accordingly, it's obviously +// wrong to compare with mMaxPointToKeyLength. +/* static */ float ProximityInfoStateUtils::getPointToKeyByIdLength(const float maxPointToKeyLength, + const std::vector<float> *const distanceCache_G, const int keyCount, + const int inputIndex, const int keyId, const float scale) { + if (keyId != NOT_AN_INDEX) { + const int index = inputIndex * keyCount + keyId; + return min((*distanceCache_G)[index] * scale, maxPointToKeyLength); + } + // If the char is not a key on the keyboard then return the max length. + return static_cast<float>(MAX_POINT_TO_KEY_LENGTH); +} + +/* static */ float ProximityInfoStateUtils::getPointToKeyByIdLength(const float maxPointToKeyLength, + const std::vector<float> *const distanceCache_G, const int keyCount, + const int inputIndex, const int keyId) { + return getPointToKeyByIdLength(maxPointToKeyLength, distanceCache_G, keyCount, inputIndex, + keyId, 1.0f); +} + +// Updates probabilities of aligning to some keys and skipping. +// Word suggestion should be based on this probabilities. +/* static */ void ProximityInfoStateUtils::updateAlignPointProbabilities( + const float maxPointToKeyLength, const int mostCommonKeyWidth, const int keyCount, + const int start, const int sampledInputSize, const std::vector<int> *const sampledInputXs, + const std::vector<int> *const sampledInputYs, + const std::vector<float> *const sampledSpeedRates, + const std::vector<int> *const sampledLengthCache, + const std::vector<float> *const distanceCache_G, + std::vector<NearKeycodesSet> *nearKeysVector, + std::vector<hash_map_compat<int, float> > *charProbabilities) { + static const float MIN_PROBABILITY = 0.000001f; + static const float MAX_SKIP_PROBABILITY = 0.95f; + static const float SKIP_FIRST_POINT_PROBABILITY = 0.01f; + static const float SKIP_LAST_POINT_PROBABILITY = 0.1f; + static const float MIN_SPEED_RATE_FOR_SKIP_PROBABILITY = 0.15f; + static const float SPEED_WEIGHT_FOR_SKIP_PROBABILITY = 0.9f; + static const float SLOW_STRAIGHT_WEIGHT_FOR_SKIP_PROBABILITY = 0.6f; + static const float NEAREST_DISTANCE_WEIGHT = 0.5f; + static const float NEAREST_DISTANCE_BIAS = 0.5f; + static const float NEAREST_DISTANCE_WEIGHT_FOR_LAST = 0.6f; + static const float NEAREST_DISTANCE_BIAS_FOR_LAST = 0.4f; + + static const float ANGLE_WEIGHT = 0.90f; + static const float DEEP_CORNER_ANGLE_THRESHOLD = M_PI_F * 60.0f / 180.0f; + static const float SKIP_DEEP_CORNER_PROBABILITY = 0.1f; + static const float CORNER_ANGLE_THRESHOLD = M_PI_F * 30.0f / 180.0f; + static const float STRAIGHT_ANGLE_THRESHOLD = M_PI_F * 15.0f / 180.0f; + static const float SKIP_CORNER_PROBABILITY = 0.4f; + static const float SPEED_MARGIN = 0.1f; + static const float CENTER_VALUE_OF_NORMALIZED_DISTRIBUTION = 0.0f; + + charProbabilities->resize(sampledInputSize); + // Calculates probabilities of using a point as a correlated point with the character + // for each point. + for (int i = start; i < sampledInputSize; ++i) { + (*charProbabilities)[i].clear(); + // First, calculates skip probability. Starts form MIN_SKIP_PROBABILITY. + // Note that all values that are multiplied to this probability should be in [0.0, 1.0]; + float skipProbability = MAX_SKIP_PROBABILITY; + + const float currentAngle = getPointAngle(sampledInputXs, sampledInputYs, i); + const float speedRate = (*sampledSpeedRates)[i]; + + float nearestKeyDistance = static_cast<float>(MAX_POINT_TO_KEY_LENGTH); + for (int j = 0; j < keyCount; ++j) { + if ((*nearKeysVector)[i].test(j)) { + const float distance = getPointToKeyByIdLength( + maxPointToKeyLength, distanceCache_G, keyCount, i, j); + if (distance < nearestKeyDistance) { + nearestKeyDistance = distance; + } + } + } + + if (i == 0) { + skipProbability *= min(1.0f, nearestKeyDistance * NEAREST_DISTANCE_WEIGHT + + NEAREST_DISTANCE_BIAS); + // Promote the first point + skipProbability *= SKIP_FIRST_POINT_PROBABILITY; + } else if (i == sampledInputSize - 1) { + skipProbability *= min(1.0f, nearestKeyDistance * NEAREST_DISTANCE_WEIGHT_FOR_LAST + + NEAREST_DISTANCE_BIAS_FOR_LAST); + // Promote the last point + skipProbability *= SKIP_LAST_POINT_PROBABILITY; + } else { + // If the current speed is relatively slower than adjacent keys, we promote this point. + if ((*sampledSpeedRates)[i - 1] - SPEED_MARGIN > speedRate + && speedRate < (*sampledSpeedRates)[i + 1] - SPEED_MARGIN) { + if (currentAngle < CORNER_ANGLE_THRESHOLD) { + skipProbability *= min(1.0f, speedRate + * SLOW_STRAIGHT_WEIGHT_FOR_SKIP_PROBABILITY); + } else { + // If the angle is small enough, we promote this point more. (e.g. pit vs put) + skipProbability *= min(1.0f, speedRate * SPEED_WEIGHT_FOR_SKIP_PROBABILITY + + MIN_SPEED_RATE_FOR_SKIP_PROBABILITY); + } + } + + skipProbability *= min(1.0f, speedRate * nearestKeyDistance * + NEAREST_DISTANCE_WEIGHT + NEAREST_DISTANCE_BIAS); + + // Adjusts skip probability by a rate depending on angle. + // ANGLE_RATE of skipProbability is adjusted by current angle. + skipProbability *= (M_PI_F - currentAngle) / M_PI_F * ANGLE_WEIGHT + + (1.0f - ANGLE_WEIGHT); + if (currentAngle > DEEP_CORNER_ANGLE_THRESHOLD) { + skipProbability *= SKIP_DEEP_CORNER_PROBABILITY; + } + // We assume the angle of this point is the angle for point[i], point[i - 2] + // and point[i - 3]. The reason why we don't use the angle for point[i], point[i - 1] + // and point[i - 2] is this angle can be more affected by the noise. + const float prevAngle = getPointsAngle(sampledInputXs, sampledInputYs, i, i - 2, i - 3); + if (i >= 3 && prevAngle < STRAIGHT_ANGLE_THRESHOLD + && currentAngle > CORNER_ANGLE_THRESHOLD) { + skipProbability *= SKIP_CORNER_PROBABILITY; + } + } + + // probabilities must be in [0.0, MAX_SKIP_PROBABILITY]; + ASSERT(skipProbability >= 0.0f); + ASSERT(skipProbability <= MAX_SKIP_PROBABILITY); + (*charProbabilities)[i][NOT_AN_INDEX] = skipProbability; + + // Second, calculates key probabilities by dividing the rest probability + // (1.0f - skipProbability). + const float inputCharProbability = 1.0f - skipProbability; + + // TODO: The variance is critical for accuracy; thus, adjusting these parameter by machine + // learning or something would be efficient. + static const float SPEEDxANGLE_WEIGHT_FOR_STANDARD_DIVIATION = 0.3f; + static const float MAX_SPEEDxANGLE_RATE_FOR_STANDERD_DIVIATION = 0.25f; + static const float SPEEDxNEAREST_WEIGHT_FOR_STANDARD_DIVIATION = 0.5f; + static const float MAX_SPEEDxNEAREST_RATE_FOR_STANDERD_DIVIATION = 0.15f; + static const float MIN_STANDERD_DIVIATION = 0.37f; + + const float speedxAngleRate = min(speedRate * currentAngle / M_PI_F + * SPEEDxANGLE_WEIGHT_FOR_STANDARD_DIVIATION, + MAX_SPEEDxANGLE_RATE_FOR_STANDERD_DIVIATION); + const float speedxNearestKeyDistanceRate = min(speedRate * nearestKeyDistance + * SPEEDxNEAREST_WEIGHT_FOR_STANDARD_DIVIATION, + MAX_SPEEDxNEAREST_RATE_FOR_STANDERD_DIVIATION); + const float sigma = speedxAngleRate + speedxNearestKeyDistanceRate + MIN_STANDERD_DIVIATION; + + ProximityInfoUtils::NormalDistribution + distribution(CENTER_VALUE_OF_NORMALIZED_DISTRIBUTION, sigma); + static const float PREV_DISTANCE_WEIGHT = 0.5f; + static const float NEXT_DISTANCE_WEIGHT = 0.6f; + // Summing up probability densities of all near keys. + float sumOfProbabilityDensities = 0.0f; + for (int j = 0; j < keyCount; ++j) { + if ((*nearKeysVector)[i].test(j)) { + float distance = sqrtf(getPointToKeyByIdLength( + maxPointToKeyLength, distanceCache_G, 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, distanceCache_G, 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 * NEXT_DISTANCE_WEIGHT) + / (1.0f + 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, distanceCache_G, 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 * PREV_DISTANCE_WEIGHT) + / (1.0f + 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); + } + } + + // Split the probability of an input point to keys that are close to the input point. + for (int j = 0; j < keyCount; ++j) { + if ((*nearKeysVector)[i].test(j)) { + float distance = sqrtf(getPointToKeyByIdLength( + maxPointToKeyLength, distanceCache_G, 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, distanceCache_G, keyCount, i + 1, j)); + if (prevDistance < distance) { + distance = (distance + prevDistance * NEXT_DISTANCE_WEIGHT) + / (1.0f + 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, distanceCache_G, keyCount, i - 1, j)); + if (prevDistance < distance) { + distance = (distance + prevDistance * PREV_DISTANCE_WEIGHT) + / (1.0f + PREV_DISTANCE_WEIGHT); + } + } + const float probabilityDensity = distribution.getProbabilityDensity(distance); + const float probability = inputCharProbability * probabilityDensity + / sumOfProbabilityDensities; + (*charProbabilities)[i][j] = probability; + } + } + } + + if (DEBUG_POINTS_PROBABILITY) { + for (int i = 0; i < sampledInputSize; ++i) { + std::stringstream sstream; + sstream << i << ", "; + sstream << "(" << (*sampledInputXs)[i] << ", " << (*sampledInputYs)[i] << "), "; + sstream << "Speed: "<< (*sampledSpeedRates)[i] << ", "; + sstream << "Angle: "<< getPointAngle(sampledInputXs, sampledInputYs, i) << ", \n"; + + for (hash_map_compat<int, float>::iterator it = (*charProbabilities)[i].begin(); + it != (*charProbabilities)[i].end(); ++it) { + if (it->first == NOT_AN_INDEX) { + sstream << it->first + << "(skip):" + << it->second + << "\n"; + } else { + sstream << it->first + << "(" + //<< static_cast<char>(mProximityInfo->getCodePointOf(it->first)) + << "):" + << it->second + << "\n"; + } + } + AKLOGI("%s", sstream.str().c_str()); + } + } + + // Decrease key probabilities of points which don't have the highest probability of that key + // among nearby points. Probabilities of the first point and the last point are not suppressed. + for (int i = max(start, 1); i < sampledInputSize; ++i) { + for (int j = i + 1; j < sampledInputSize; ++j) { + if (!suppressCharProbabilities( + mostCommonKeyWidth, sampledInputSize, sampledLengthCache, i, j, + charProbabilities)) { + break; + } + } + for (int j = i - 1; j >= max(start, 0); --j) { + if (!suppressCharProbabilities( + mostCommonKeyWidth, sampledInputSize, sampledLengthCache, i, j, + charProbabilities)) { + break; + } + } + } + + // Converting from raw probabilities to log probabilities to calculate spatial distance. + for (int i = start; i < sampledInputSize; ++i) { + for (int j = 0; j < keyCount; ++j) { + hash_map_compat<int, float>::iterator it = (*charProbabilities)[i].find(j); + if (it == (*charProbabilities)[i].end()){ + (*nearKeysVector)[i].reset(j); + } else if(it->second < MIN_PROBABILITY) { + // Erases from near keys vector because it has very low probability. + (*nearKeysVector)[i].reset(j); + (*charProbabilities)[i].erase(j); + } else { + it->second = -logf(it->second); + } + } + (*charProbabilities)[i][NOT_AN_INDEX] = -logf((*charProbabilities)[i][NOT_AN_INDEX]); + } +} + +/* static */ void ProximityInfoStateUtils::updateSearchKeysVector( + const ProximityInfo *const proximityInfo, const int sampledInputSize, + const int lastSavedInputSize, + const std::vector<int> *const sampledLengthCache, + const std::vector<NearKeycodesSet> *const nearKeysVector, + std::vector<NearKeycodesSet> *searchKeysVector) { + const int readForwordLength = static_cast<int>( + hypotf(proximityInfo->getKeyboardWidth(), proximityInfo->getKeyboardHeight()) + * ProximityInfoParams::SEARCH_KEY_RADIUS_RATIO); + for (int i = 0; i < sampledInputSize; ++i) { + if (i >= lastSavedInputSize) { + (*searchKeysVector)[i].reset(); + } + for (int j = max(i, lastSavedInputSize); j < sampledInputSize; ++j) { + // TODO: Investigate if this is required. This may not fail. + if ((*sampledLengthCache)[j] - (*sampledLengthCache)[i] >= readForwordLength) { + break; + } + (*searchKeysVector)[i] |= (*nearKeysVector)[j]; + } + } +} + +// Decreases char probabilities of index0 by checking probabilities of a near point (index1) and +// increases char probabilities of index1 by checking probabilities of index0. +/* static */ bool ProximityInfoStateUtils::suppressCharProbabilities(const int mostCommonKeyWidth, + const int sampledInputSize, const std::vector<int> *const lengthCache, + const int index0, const int index1, + std::vector<hash_map_compat<int, float> > *charProbabilities) { + ASSERT(0 <= index0 && index0 < sampledInputSize); + ASSERT(0 <= index1 && index1 < sampledInputSize); + + static const float SUPPRESSION_LENGTH_WEIGHT = 1.5f; + static const float MIN_SUPPRESSION_RATE = 0.1f; + static const float SUPPRESSION_WEIGHT = 0.5f; + static const float SUPPRESSION_WEIGHT_FOR_PROBABILITY_GAIN = 0.1f; + static const float SKIP_PROBABALITY_WEIGHT_FOR_PROBABILITY_GAIN = 0.3f; + + const float keyWidthFloat = static_cast<float>(mostCommonKeyWidth); + const float diff = fabsf(static_cast<float>((*lengthCache)[index0] - (*lengthCache)[index1])); + if (diff > keyWidthFloat * SUPPRESSION_LENGTH_WEIGHT) { + return false; + } + const float suppressionRate = MIN_SUPPRESSION_RATE + + diff / keyWidthFloat / SUPPRESSION_LENGTH_WEIGHT * SUPPRESSION_WEIGHT; + for (hash_map_compat<int, float>::iterator it = (*charProbabilities)[index0].begin(); + it != (*charProbabilities)[index0].end(); ++it) { + hash_map_compat<int, float>::iterator it2 = (*charProbabilities)[index1].find(it->first); + if (it2 != (*charProbabilities)[index1].end() && it->second < it2->second) { + const float newProbability = it->second * suppressionRate; + const float suppression = it->second - newProbability; + it->second = newProbability; + // mCharProbabilities[index0][NOT_AN_INDEX] is the probability of skipping this point. + (*charProbabilities)[index0][NOT_AN_INDEX] += suppression; + + // Add the probability of the same key nearby index1 + const float probabilityGain = min(suppression * SUPPRESSION_WEIGHT_FOR_PROBABILITY_GAIN, + (*charProbabilities)[index1][NOT_AN_INDEX] + * SKIP_PROBABALITY_WEIGHT_FOR_PROBABILITY_GAIN); + it2->second += probabilityGain; + (*charProbabilities)[index1][NOT_AN_INDEX] -= probabilityGain; + } + } + return true; +} + +/* static */ void ProximityInfoStateUtils::dump(const bool isGeometric, const int inputSize, + const int *const inputXCoordinates, const int *const inputYCoordinates, + const int sampledInputSize, const std::vector<int> *const sampledInputXs, + const std::vector<int> *const sampledInputYs, + const std::vector<int> *const sampledTimes, + const std::vector<float> *const sampledSpeedRates, + const std::vector<int> *const sampledBeelineSpeedPercentiles) { + if (DEBUG_GEO_FULL) { + for (int i = 0; i < sampledInputSize; ++i) { + AKLOGI("Sampled(%d): x = %d, y = %d, time = %d", i, (*sampledInputXs)[i], + (*sampledInputYs)[i], sampledTimes ? (*sampledTimes)[i] : -1); + } + } + + std::stringstream originalX, originalY, sampledX, sampledY; + for (int i = 0; i < inputSize; ++i) { + originalX << inputXCoordinates[i]; + originalY << inputYCoordinates[i]; + if (i != inputSize - 1) { + originalX << ";"; + originalY << ";"; + } + } + AKLOGI("===== sampled points ====="); + for (int i = 0; i < sampledInputSize; ++i) { + if (isGeometric) { + AKLOGI("%d: x = %d, y = %d, time = %d, relative speed = %.4f, beeline speed = %d", + i, (*sampledInputXs)[i], (*sampledInputYs)[i], (*sampledTimes)[i], + (*sampledSpeedRates)[i], (*sampledBeelineSpeedPercentiles)[i]); + } + sampledX << (*sampledInputXs)[i]; + sampledY << (*sampledInputYs)[i]; + if (i != sampledInputSize - 1) { + sampledX << ";"; + sampledY << ";"; + } + } + AKLOGI("original points:\n%s, %s,\nsampled points:\n%s, %s,\n", + originalX.str().c_str(), originalY.str().c_str(), sampledX.str().c_str(), + sampledY.str().c_str()); +} +} // namespace latinime |