xref: /packages/inputmethods/LatinIME/native/jni/src/proximity_info_state_utils.cpp

/*
 * 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 <cstring> // for memset()
#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::trimLastTwoTouchPoints(std::vector<int> *sampledInputXs,
        std::vector<int> *sampledInputYs, std::vector<int> *sampledInputTimes,
        std::vector<int> *sampledLengthCache, std::vector<int> *sampledInputIndice) {
    const int nextStartIndex = (*sampledInputIndice)[sampledInputIndice->size() - 2];
    popInputData(sampledInputXs, sampledInputYs, sampledInputTimes, sampledLengthCache,
            sampledInputIndice);
    popInputData(sampledInputXs, sampledInputYs, sampledInputTimes, sampledLengthCache,
            sampledInputIndice);
    return nextStartIndex;
}

/* static */ int ProximityInfoStateUtils::updateTouchPoints(
        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 float verticalSweetSpotScale, 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 - 1], times[i]);
                    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(proximityInfo, maxPointToKeyLength, i, c, x, y, time,
                    verticalSweetSpotScale, 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) {
    memset(primaryInputWord, 0, sizeof(primaryInputWord[0]) * MAX_WORD_LENGTH);
    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 std::vector<int> *const sampledInputXs, const std::vector<int> *const sampledInputYs,
        int *normalizedSquaredDistances) {
    memset(normalizedSquaredDistances, NOT_A_DISTANCE,
            sizeof(normalizedSquaredDistances[0]) * MAX_PROXIMITY_CHARS_SIZE * MAX_WORD_LENGTH);
    const bool hasInputCoordinates = sampledInputXs->size() > 0 && sampledInputYs->size() > 0;
    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] =
                        static_cast<int>(squaredDistance
                                * ProximityInfoParams::NORMALIZED_SQUARED_DISTANCE_SCALING_FACTOR);
            } else {
                normalizedSquaredDistances[i * MAX_PROXIMITY_CHARS_SIZE + j] =
                        (j == 0) ? MATCH_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 sampledInputSize,
        const int lastSavedInputSize, const float verticalSweetSpotScale,
        const std::vector<int> *const sampledInputXs,
        const std::vector<int> *const sampledInputYs,
        std::vector<NearKeycodesSet> *sampledNearKeySets,
        std::vector<float> *sampledNormalizedSquaredLengthCache) {
    sampledNearKeySets->resize(sampledInputSize);
    const int keyCount = proximityInfo->getKeyCount();
    sampledNormalizedSquaredLengthCache->resize(sampledInputSize * keyCount);
    for (int i = lastSavedInputSize; i < sampledInputSize; ++i) {
        (*sampledNearKeySets)[i].reset();
        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, verticalSweetSpotScale);
            (*sampledNormalizedSquaredLengthCache)[index] = normalizedSquaredDistance;
            if (normalizedSquaredDistance
                    < ProximityInfoParams::NEAR_KEY_NORMALIZED_SQUARED_THRESHOLD) {
                (*sampledNearKeySets)[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
        // ProximityInfoParams::NUM_POINTS_FOR_SPEED_CALCULATION points for both forward and
        // backward.
        const int forwardNumPoints = min(inputSize - 1,
                index + ProximityInfoParams::NUM_POINTS_FOR_SPEED_CALCULATION);
        for (int j = index; j < forwardNumPoints; ++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];
        }
        const int backwardNumPoints = max(0,
                index - ProximityInfoParams::NUM_POINTS_FOR_SPEED_CALCULATION);
        for (int j = index - 1; j >= backwardNumPoints; --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, const float verticalSweetspotScale,
        NearKeysDistanceMap *const currentNearKeysDistances) {
    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,
                verticalSweetspotScale);
        if (dist < ProximityInfoParams::NEAR_KEY_THRESHOLD_FOR_DISTANCE) {
            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) {
    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);
        const bool isPrevPrevNear = (itPP == prevPrevNearKeysDistances->end()
                || itPP->second > it->second + ProximityInfoParams::MARGIN_FOR_PREV_LOCAL_MIN);
        const bool isCurrentNear = (itC == currentNearKeysDistances->end()
                || itC->second > it->second + ProximityInfoParams::MARGIN_FOR_PREV_LOCAL_MIN);
        if (isPrevPrevNear && isCurrentNear) {
            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) {
    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])
                    * ProximityInfoParams::DISTANCE_BASE_SCALE;
    float score = 0.0f;

    // Location
    if (!isPrevLocalMin(currentNearKeysDistances, prevNearKeysDistances,
        prevPrevNearKeysDistances)) {
        score += ProximityInfoParams::NOT_LOCALMIN_DISTANCE_SCORE;
    } else if (nearest < ProximityInfoParams::NEAR_KEY_THRESHOLD_FOR_POINT_SCORE) {
        // Promote points nearby keys
        score += ProximityInfoParams::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 * ProximityInfoParams::CORNER_CHECK_DISTANCE_THRESHOLD_SCALE
            && (sumAngle > ProximityInfoParams::CORNER_SUM_ANGLE_THRESHOLD
                    || angleDiff > ProximityInfoParams::CORNER_ANGLE_THRESHOLD_FOR_POINT_SCORE)) {
        score += ProximityInfoParams::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 ProximityInfo *const proximityInfo,
        const int maxPointToKeyLength, const int inputIndex, const int nodeCodePoint, int x, int y,
        const int time, const float verticalSweetSpotScale, 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) {
    const int mostCommonKeyWidth = proximityInfo->getMostCommonKeyWidth();

    size_t size = sampledInputXs->size();
    bool popped = false;
    if (nodeCodePoint < 0 && doSampling) {
        const float nearest = updateNearKeysDistances(proximityInfo, maxPointToKeyLength, x, y,
                verticalSweetSpotScale, 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())
                    * ProximityInfoParams::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
                                   / ProximityInfoParams::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);
}

// 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 sampledNormalizedSquaredLengthCache, const int keyCount,
        const int inputIndex, const int keyId) {
    if (keyId != NOT_AN_INDEX) {
        const int index = inputIndex * keyCount + keyId;
        return min((*sampledNormalizedSquaredLengthCache)[index], maxPointToKeyLength);
    }
    // If the char is not a key on the keyboard then return the max length.
    return static_cast<float>(MAX_VALUE_FOR_WEIGHTING);
}

// 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 sampledNormalizedSquaredLengthCache,
        std::vector<NearKeycodesSet> *sampledNearKeySets,
        std::vector<hash_map_compat<int, float> > *charProbabilities) {
    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 from MAX_SKIP_PROBABILITY.
        // Note that all values that are multiplied to this probability should be in [0.0, 1.0];
        float skipProbability = ProximityInfoParams::MAX_SKIP_PROBABILITY;

        const float currentAngle = getPointAngle(sampledInputXs, sampledInputYs, i);
        const float speedRate = (*sampledSpeedRates)[i];

        float nearestKeyDistance = static_cast<float>(MAX_VALUE_FOR_WEIGHTING);
        for (int j = 0; j < keyCount; ++j) {
            if ((*sampledNearKeySets)[i].test(j)) {
                const float distance = getPointToKeyByIdLength(
                        maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount, i, j);
                if (distance < nearestKeyDistance) {
                    nearestKeyDistance = distance;
                }
            }
        }

        if (i == 0) {
            skipProbability *= min(1.0f,
                    nearestKeyDistance * ProximityInfoParams::NEAREST_DISTANCE_WEIGHT
                            + ProximityInfoParams::NEAREST_DISTANCE_BIAS);
            // Promote the first point
            skipProbability *= ProximityInfoParams::SKIP_FIRST_POINT_PROBABILITY;
        } else if (i == sampledInputSize - 1) {
            skipProbability *= min(1.0f,
                    nearestKeyDistance * ProximityInfoParams::NEAREST_DISTANCE_WEIGHT_FOR_LAST
                            + ProximityInfoParams::NEAREST_DISTANCE_BIAS_FOR_LAST);
            // Promote the last point
            skipProbability *= ProximityInfoParams::SKIP_LAST_POINT_PROBABILITY;
        } else {
            // If the current speed is relatively slower than adjacent keys, we promote this point.
            if ((*sampledSpeedRates)[i - 1] - ProximityInfoParams::SPEED_MARGIN > speedRate
                    && speedRate
                            < (*sampledSpeedRates)[i + 1] - ProximityInfoParams::SPEED_MARGIN) {
                if (currentAngle < ProximityInfoParams::CORNER_ANGLE_THRESHOLD) {
                    skipProbability *= min(1.0f, speedRate
                            * ProximityInfoParams::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 * ProximityInfoParams::SPEED_WEIGHT_FOR_SKIP_PROBABILITY
                                    + ProximityInfoParams::MIN_SPEED_RATE_FOR_SKIP_PROBABILITY);
                }
            }

            skipProbability *= min(1.0f,
                    speedRate * nearestKeyDistance * ProximityInfoParams::NEAREST_DISTANCE_WEIGHT
                            + ProximityInfoParams::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 * ProximityInfoParams::ANGLE_WEIGHT
                    + (1.0f - ProximityInfoParams::ANGLE_WEIGHT);
            if (currentAngle > ProximityInfoParams::DEEP_CORNER_ANGLE_THRESHOLD) {
                skipProbability *= ProximityInfoParams::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 < ProximityInfoParams::STRAIGHT_ANGLE_THRESHOLD
                    && currentAngle > ProximityInfoParams::CORNER_ANGLE_THRESHOLD) {
                skipProbability *= ProximityInfoParams::SKIP_CORNER_PROBABILITY;
            }
        }

        // probabilities must be in [0.0, ProximityInfoParams::MAX_SKIP_PROBABILITY];
        ASSERT(skipProbability >= 0.0f);
        ASSERT(skipProbability <= ProximityInfoParams::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;

        const float speedxAngleRate = min(speedRate * currentAngle / M_PI_F
                * ProximityInfoParams::SPEEDxANGLE_WEIGHT_FOR_STANDARD_DIVIATION,
                        ProximityInfoParams::MAX_SPEEDxANGLE_RATE_FOR_STANDERD_DIVIATION);
        const float speedxNearestKeyDistanceRate = min(speedRate * nearestKeyDistance
                * ProximityInfoParams::SPEEDxNEAREST_WEIGHT_FOR_STANDARD_DIVIATION,
                        ProximityInfoParams::MAX_SPEEDxNEAREST_RATE_FOR_STANDERD_DIVIATION);
        const float sigma = speedxAngleRate + speedxNearestKeyDistanceRate
                + ProximityInfoParams::MIN_STANDERD_DIVIATION;

        ProximityInfoUtils::NormalDistribution
                distribution(ProximityInfoParams::CENTER_VALUE_OF_NORMALIZED_DISTRIBUTION, sigma);
        // 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);
            }
        }

        // 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 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()){
                (*sampledNearKeySets)[i].reset(j);
            } else if(it->second < ProximityInfoParams::MIN_PROBABILITY) {
                // Erases from near keys vector because it has very low probability.
                (*sampledNearKeySets)[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::updateSampledSearchKeySets(
        const ProximityInfo *const proximityInfo, const int sampledInputSize,
        const int lastSavedInputSize,
        const std::vector<int> *const sampledLengthCache,
        const std::vector<NearKeycodesSet> *const sampledNearKeySets,
        std::vector<NearKeycodesSet> *sampledSearchKeySets,
        std::vector<std::vector<int> > *sampledSearchKeyVectors) {
    sampledSearchKeySets->resize(sampledInputSize);
    sampledSearchKeyVectors->resize(sampledInputSize);
    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) {
            (*sampledSearchKeySets)[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;
            }
            (*sampledSearchKeySets)[i] |= (*sampledNearKeySets)[j];
        }
    }
    const int keyCount = proximityInfo->getKeyCount();
    for (int i = 0; i < sampledInputSize; ++i) {
        std::vector<int> *searchKeyVector = &(*sampledSearchKeyVectors)[i];
        searchKeyVector->clear();
        for (int j = 0; j < keyCount; ++j) {
            if ((*sampledSearchKeySets)[i].test(j)) {
                const int keyCodePoint = proximityInfo->getCodePointOf(j);
                if (std::find(searchKeyVector->begin(), searchKeyVector->end(), keyCodePoint)
                        == searchKeyVector->end()) {
                    searchKeyVector->push_back(keyCodePoint);
                }
            }
        }
    }
}

// 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);
    const float keyWidthFloat = static_cast<float>(mostCommonKeyWidth);
    const float diff = fabsf(static_cast<float>((*lengthCache)[index0] - (*lengthCache)[index1]));
    if (diff > keyWidthFloat * ProximityInfoParams::SUPPRESSION_LENGTH_WEIGHT) {
        return false;
    }
    const float suppressionRate = ProximityInfoParams::MIN_SUPPRESSION_RATE
            + diff / keyWidthFloat / ProximityInfoParams::SUPPRESSION_LENGTH_WEIGHT
                    * ProximityInfoParams::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
                    * ProximityInfoParams::SUPPRESSION_WEIGHT_FOR_PROBABILITY_GAIN,
                    (*charProbabilities)[index1][NOT_AN_INDEX]
                            * ProximityInfoParams::SKIP_PROBABALITY_WEIGHT_FOR_PROBABILITY_GAIN);
            it2->second += probabilityGain;
            (*charProbabilities)[index1][NOT_AN_INDEX] -= probabilityGain;
        }
    }
    return true;
}

/* static */ bool ProximityInfoStateUtils::checkAndReturnIsContinuousSuggestionPossible(
        const int inputSize, const int *const xCoordinates, const int *const yCoordinates,
        const int *const times, const int sampledInputSize,
        const std::vector<int> *const sampledInputXs, const std::vector<int> *const sampledInputYs,
        const std::vector<int> *const sampledTimes,
        const std::vector<int> *const sampledInputIndices) {
    if (inputSize < sampledInputSize) {
        return false;
    }
    for (int i = 0; i < sampledInputSize; ++i) {
        const int index = (*sampledInputIndices)[i];
        if (index >= inputSize) {
            return false;
        }
        if (xCoordinates[index] != (*sampledInputXs)[i]
                || yCoordinates[index] != (*sampledInputYs)[i]) {
            return false;
        }
        if (!times) {
            continue;
        }
        if (times[index] != (*sampledTimes)[i]) {
            return false;
        }
    }
    return true;
}

// Get a word that is detected by tracing the most probable string into codePointBuf and
// returns probability of generating the word.
/* static */ float ProximityInfoStateUtils::getMostProbableString(
        const ProximityInfo *const proximityInfo, const int sampledInputSize,
        const std::vector<hash_map_compat<int, float> > *const charProbabilities,
        int *const codePointBuf) {
    ASSERT(sampledInputSize >= 0);
    memset(codePointBuf, 0, sizeof(codePointBuf[0]) * MAX_WORD_LENGTH);
    int index = 0;
    float sumLogProbability = 0.0f;
    // TODO: Current implementation is greedy algorithm. DP would be efficient for many cases.
    for (int i = 0; i < sampledInputSize && index < MAX_WORD_LENGTH - 1; ++i) {
        float minLogProbability = static_cast<float>(MAX_VALUE_FOR_WEIGHTING);
        int character = NOT_AN_INDEX;
        for (hash_map_compat<int, float>::const_iterator it = (*charProbabilities)[i].begin();
                it != (*charProbabilities)[i].end(); ++it) {
            const float logProbability = (it->first != NOT_AN_INDEX)
                    ? it->second + ProximityInfoParams::DEMOTION_LOG_PROBABILITY : it->second;
            if (logProbability < minLogProbability) {
                minLogProbability = logProbability;
                character = it->first;
            }
        }
        if (character != NOT_AN_INDEX) {
            codePointBuf[index] = proximityInfo->getCodePointOf(character);
            index++;
        }
        sumLogProbability += minLogProbability;
    }
    codePointBuf[index] = '\0';
    return sumLogProbability;
}

/* 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