Introduce patriciaTrie to abstract traversing version 2 dictionary.
Bug: 6669677
Change-Id: Ifef72f3d7a7ba67c5232b98c7835485d72d7322d
diff --git a/native/jni/Android.mk b/native/jni/Android.mk
index d5df6b6..f89eea7 100644
--- a/native/jni/Android.mk
+++ b/native/jni/Android.mk
@@ -70,6 +70,7 @@
proximity_info_state_utils.cpp) \
suggest/core/policy/weighting.cpp \
suggest/core/session/dic_traverse_session.cpp \
+ suggest/policyimpl/dictionary/patricia_trie_policy.cpp \
suggest/policyimpl/gesture/gesture_suggest_policy_factory.cpp \
$(addprefix suggest/policyimpl/typing/, \
scoring_params.cpp \
diff --git a/native/jni/src/suggest/core/dicnode/dic_node_utils.cpp b/native/jni/src/suggest/core/dicnode/dic_node_utils.cpp
index 2063c39..9bf7ece 100644
--- a/native/jni/src/suggest/core/dicnode/dic_node_utils.cpp
+++ b/native/jni/src/suggest/core/dicnode/dic_node_utils.cpp
@@ -26,6 +26,7 @@
#include "suggest/core/dictionary/probability_utils.h"
#include "suggest/core/layout/proximity_info.h"
#include "suggest/core/layout/proximity_info_state.h"
+#include "suggest/core/policy/dictionary_structure_policy.h"
#include "utils/char_utils.h"
namespace latinime {
@@ -36,14 +37,15 @@
/* static */ void DicNodeUtils::initAsRoot(const BinaryDictionaryInfo *const binaryDictionaryInfo,
const int prevWordNodePos, DicNode *const newRootNode) {
- newRootNode->initAsRoot(binaryDictionaryInfo->getRootPosition(), prevWordNodePos);
+ newRootNode->initAsRoot(binaryDictionaryInfo->getStructurePolicy()->getRootPosition(),
+ prevWordNodePos);
}
/*static */ void DicNodeUtils::initAsRootWithPreviousWord(
const BinaryDictionaryInfo *const binaryDictionaryInfo,
DicNode *const prevWordLastNode, DicNode *const newRootNode) {
newRootNode->initAsRootWithPreviousWord(
- prevWordLastNode, binaryDictionaryInfo->getRootPosition());
+ prevWordLastNode, binaryDictionaryInfo->getStructurePolicy()->getRootPosition());
}
/* static */ void DicNodeUtils::initByCopy(DicNode *srcNode, DicNode *destNode) {
diff --git a/native/jni/src/suggest/core/dictionary/bigram_dictionary.cpp b/native/jni/src/suggest/core/dictionary/bigram_dictionary.cpp
index 242a9bd..ff304d2 100644
--- a/native/jni/src/suggest/core/dictionary/bigram_dictionary.cpp
+++ b/native/jni/src/suggest/core/dictionary/bigram_dictionary.cpp
@@ -150,11 +150,10 @@
int BigramDictionary::getBigramListPositionForWord(const int *prevWord, const int prevWordLength,
const bool forceLowerCaseSearch) const {
if (0 >= prevWordLength) return 0;
- const uint8_t *const root = mBinaryDictionaryInfo->getDictRoot();
- int pos = BinaryFormat::getTerminalPosition(root, prevWord, prevWordLength,
- forceLowerCaseSearch);
-
+ int pos = mBinaryDictionaryInfo->getStructurePolicy()->getTerminalNodePositionOfWord(
+ mBinaryDictionaryInfo, prevWord, prevWordLength, forceLowerCaseSearch);
if (NOT_VALID_WORD == pos) return 0;
+ const uint8_t *const root = mBinaryDictionaryInfo->getDictRoot();
const uint8_t flags = BinaryFormat::getFlagsAndForwardPointer(root, &pos);
if (0 == (flags & BinaryFormat::FLAG_HAS_BIGRAMS)) return 0;
if (0 == (flags & BinaryFormat::FLAG_HAS_MULTIPLE_CHARS)) {
@@ -189,8 +188,8 @@
int pos = getBigramListPositionForWord(word0, length0, false /* forceLowerCaseSearch */);
// getBigramListPositionForWord returns 0 if this word isn't in the dictionary or has no bigrams
if (0 == pos) return false;
- int nextWordPos = BinaryFormat::getTerminalPosition(mBinaryDictionaryInfo->getDictRoot(),
- word1, length1, false /* forceLowerCaseSearch */);
+ int nextWordPos = mBinaryDictionaryInfo->getStructurePolicy()->getTerminalNodePositionOfWord(
+ mBinaryDictionaryInfo, word1, length1, false /* forceLowerCaseSearch */);
if (NOT_VALID_WORD == nextWordPos) return false;
for (BinaryDictionaryBigramsIterator bigramsIt(mBinaryDictionaryInfo, pos);
diff --git a/native/jni/src/suggest/core/dictionary/binary_dictionary_info.h b/native/jni/src/suggest/core/dictionary/binary_dictionary_info.h
index c921236..7cb3144 100644
--- a/native/jni/src/suggest/core/dictionary/binary_dictionary_info.h
+++ b/native/jni/src/suggest/core/dictionary/binary_dictionary_info.h
@@ -22,11 +22,10 @@
#include "defines.h"
#include "suggest/core/dictionary/binary_dictionary_format_utils.h"
#include "suggest/core/dictionary/binary_dictionary_header.h"
+#include "suggest/policyimpl/dictionary/dictionary_structure_policy_factory.h"
namespace latinime {
-class BinaryDictionaryHeader;
-
class BinaryDictionaryInfo {
public:
BinaryDictionaryInfo(const uint8_t *const dictBuf, const int dictSize, const int mmapFd,
@@ -35,7 +34,9 @@
mDictBufOffset(dictBufOffset), mIsUpdatable(isUpdatable),
mDictionaryFormat(BinaryDictionaryFormatUtils::detectFormatVersion(
mDictBuf, mDictSize)),
- mDictionaryHeader(this), mDictRoot(mDictBuf + mDictionaryHeader.getSize()) {}
+ mDictionaryHeader(this), mDictRoot(mDictBuf + mDictionaryHeader.getSize()),
+ mStructurePolicy(DictionaryStructurePolicyFactory::getDictionaryStructurePolicy(
+ mDictionaryFormat)) {}
AK_FORCE_INLINE const uint8_t *getDictBuf() const {
return mDictBuf;
@@ -61,10 +62,6 @@
return mDictionaryFormat;
}
- AK_FORCE_INLINE int getRootPosition() const {
- return 0;
- }
-
AK_FORCE_INLINE const BinaryDictionaryHeader *getHeader() const {
return &mDictionaryHeader;
}
@@ -75,6 +72,10 @@
return mIsUpdatable && isUpdatableDictionaryFormat;
}
+ AK_FORCE_INLINE const DictionaryStructurePolicy *getStructurePolicy() const {
+ return mStructurePolicy;
+ }
+
private:
DISALLOW_COPY_AND_ASSIGN(BinaryDictionaryInfo);
@@ -86,6 +87,7 @@
const BinaryDictionaryFormatUtils::FORMAT_VERSION mDictionaryFormat;
const BinaryDictionaryHeader mDictionaryHeader;
const uint8_t *const mDictRoot;
+ const DictionaryStructurePolicy *const mStructurePolicy;
};
}
#endif /* LATINIME_BINARY_DICTIONARY_INFO_H */
diff --git a/native/jni/src/suggest/core/dictionary/dictionary.cpp b/native/jni/src/suggest/core/dictionary/dictionary.cpp
index 51f23dc..675b549 100644
--- a/native/jni/src/suggest/core/dictionary/dictionary.cpp
+++ b/native/jni/src/suggest/core/dictionary/dictionary.cpp
@@ -83,27 +83,14 @@
}
int Dictionary::getProbability(const int *word, int length) const {
- const uint8_t *const root = mBinaryDictionaryInfo.getDictRoot();
- int pos = BinaryFormat::getTerminalPosition(root, word, length,
+ const DictionaryStructurePolicy *const structurePolicy =
+ mBinaryDictionaryInfo.getStructurePolicy();
+ int pos = structurePolicy->getTerminalNodePositionOfWord(&mBinaryDictionaryInfo, word, length,
false /* forceLowerCaseSearch */);
if (NOT_VALID_WORD == pos) {
return NOT_A_PROBABILITY;
}
- const uint8_t flags = BinaryFormat::getFlagsAndForwardPointer(root, &pos);
- if (flags & (BinaryFormat::FLAG_IS_BLACKLISTED | BinaryFormat::FLAG_IS_NOT_A_WORD)) {
- // If this is not a word, or if it's a blacklisted entry, it should behave as
- // having no probability outside of the suggestion process (where it should be used
- // for shortcuts).
- return NOT_A_PROBABILITY;
- }
- const bool hasMultipleChars = (0 != (BinaryFormat::FLAG_HAS_MULTIPLE_CHARS & flags));
- if (hasMultipleChars) {
- pos = BinaryFormat::skipOtherCharacters(root, pos);
- } else {
- BinaryFormat::getCodePointAndForwardPointer(root, &pos);
- }
- const int unigramProbability = BinaryFormat::readProbabilityWithoutMovingPointer(root, pos);
- return unigramProbability;
+ return structurePolicy->getUnigramProbability(&mBinaryDictionaryInfo, pos);
}
bool Dictionary::isValidBigram(const int *word0, int length0, const int *word1, int length1) const {
diff --git a/native/jni/src/suggest/policyimpl/dictionary/dictionary_structure_policy_factory.h b/native/jni/src/suggest/policyimpl/dictionary/dictionary_structure_policy_factory.h
new file mode 100644
index 0000000..5070651
--- /dev/null
+++ b/native/jni/src/suggest/policyimpl/dictionary/dictionary_structure_policy_factory.h
@@ -0,0 +1,47 @@
+/*
+ * 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.
+ */
+
+#ifndef LATINIME_DICTIONARY_STRUCTURE_POLICY_FACTORY_H
+#define LATINIME_DICTIONARY_STRUCTURE_POLICY_FACTORY_H
+
+#include "defines.h"
+#include "suggest/core/dictionary/binary_dictionary_format_utils.h"
+#include "suggest/policyimpl/dictionary/patricia_trie_policy.h"
+
+namespace latinime {
+
+class DictionaryStructurePolicy;
+
+class DictionaryStructurePolicyFactory {
+ public:
+ static const DictionaryStructurePolicy *getDictionaryStructurePolicy(
+ const BinaryDictionaryFormatUtils::FORMAT_VERSION dictionaryFormat) {
+ switch (dictionaryFormat) {
+ case BinaryDictionaryFormatUtils::VERSION_1:
+ // Fall through
+ case BinaryDictionaryFormatUtils::VERSION_2:
+ return PatriciaTriePolicy::getInstance();
+ default:
+ ASSERT(false);
+ return 0;
+ }
+ }
+
+ private:
+ DISALLOW_IMPLICIT_CONSTRUCTORS(DictionaryStructurePolicyFactory);
+};
+} // namespace latinime
+#endif // LATINIME_DICTIONARY_STRUCTURE_POLICY_FACTORY_H
diff --git a/native/jni/src/suggest/policyimpl/dictionary/patricia_trie_policy.cpp b/native/jni/src/suggest/policyimpl/dictionary/patricia_trie_policy.cpp
new file mode 100644
index 0000000..c995af9
--- /dev/null
+++ b/native/jni/src/suggest/policyimpl/dictionary/patricia_trie_policy.cpp
@@ -0,0 +1,70 @@
+/*
+ * 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 "suggest/policyimpl/dictionary/patricia_trie_policy.h"
+
+#include "defines.h"
+#include "suggest/core/dicnode/dic_node.h"
+#include "suggest/core/dicnode/dic_node_vector.h"
+#include "suggest/core/dictionary/binary_dictionary_info.h"
+#include "suggest/core/dictionary/binary_format.h"
+
+namespace latinime {
+
+const PatriciaTriePolicy PatriciaTriePolicy::sInstance;
+
+void PatriciaTriePolicy::createAndGetAllChildNodes(const DicNode *const dicNode,
+ const BinaryDictionaryInfo *const binaryDictionaryInfo,
+ const NodeFilter *const nodeFilter, DicNodeVector *const childDicNodes) const {
+ // TODO: Move children creating methods form DicNodeUtils.
+}
+
+void PatriciaTriePolicy::getWordAtPosition(const BinaryDictionaryInfo *const binaryDictionaryInfo,
+ const int terminalNodePos, const int maxDepth, int *const outWord,
+ int *const outUnigramProbability) const {
+ BinaryFormat::getWordAtAddress(binaryDictionaryInfo->getDictRoot(), terminalNodePos,
+ maxDepth, outWord, outUnigramProbability);
+}
+
+int PatriciaTriePolicy::getTerminalNodePositionOfWord(
+ const BinaryDictionaryInfo *const binaryDictionaryInfo, const int *const inWord,
+ const int length, const bool forceLowerCaseSearch) const {
+ return BinaryFormat::getTerminalPosition(binaryDictionaryInfo->getDictRoot(), inWord,
+ length, forceLowerCaseSearch);
+}
+
+int PatriciaTriePolicy::getUnigramProbability(
+ const BinaryDictionaryInfo *const binaryDictionaryInfo, const int nodePos) const {
+ const uint8_t *const root = binaryDictionaryInfo->getDictRoot();
+ int pos = nodePos;
+ const uint8_t flags = BinaryFormat::getFlagsAndForwardPointer(root, &pos);
+ if (flags & (BinaryFormat::FLAG_IS_BLACKLISTED | BinaryFormat::FLAG_IS_NOT_A_WORD)) {
+ // If this is not a word, or if it's a blacklisted entry, it should behave as
+ // having no probability outside of the suggestion process (where it should be used
+ // for shortcuts).
+ return NOT_A_PROBABILITY;
+ }
+ const bool hasMultipleChars = (0 != (BinaryFormat::FLAG_HAS_MULTIPLE_CHARS & flags));
+ if (hasMultipleChars) {
+ pos = BinaryFormat::skipOtherCharacters(root, pos);
+ } else {
+ BinaryFormat::getCodePointAndForwardPointer(root, &pos);
+ }
+ return BinaryFormat::readProbabilityWithoutMovingPointer(root, pos);
+}
+
+} // namespace latinime
diff --git a/native/jni/src/suggest/policyimpl/dictionary/patricia_trie_policy.h b/native/jni/src/suggest/policyimpl/dictionary/patricia_trie_policy.h
new file mode 100644
index 0000000..9b93381
--- /dev/null
+++ b/native/jni/src/suggest/policyimpl/dictionary/patricia_trie_policy.h
@@ -0,0 +1,58 @@
+/*
+ * 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.
+ */
+
+#ifndef LATINIME_PATRICIA_TRIE_POLICY_H
+#define LATINIME_PATRICIA_TRIE_POLICY_H
+
+#include "defines.h"
+#include "suggest/core/policy/dictionary_structure_policy.h"
+
+namespace latinime {
+
+class PatriciaTriePolicy : public DictionaryStructurePolicy {
+ public:
+ static AK_FORCE_INLINE const PatriciaTriePolicy *getInstance() {
+ return &sInstance;
+ }
+
+ AK_FORCE_INLINE int getRootPosition() const {
+ return 0;
+ }
+
+ void createAndGetAllChildNodes(const DicNode *const dicNode,
+ const BinaryDictionaryInfo *const binaryDictionaryInfo,
+ const NodeFilter *const nodeFilter, DicNodeVector *const childDicNodes) const;
+
+ void getWordAtPosition(const BinaryDictionaryInfo *const binaryDictionaryInfo,
+ const int terminalNodePos, const int maxDepth, int *const outWord,
+ int *const outUnigramProbability) const;
+
+ int getTerminalNodePositionOfWord(
+ const BinaryDictionaryInfo *const binaryDictionaryInfo, const int *const inWord,
+ const int length, const bool forceLowerCaseSearch) const;
+
+ int getUnigramProbability(const BinaryDictionaryInfo *const binaryDictionaryInfo,
+ const int nodePos) const;
+
+ private:
+ DISALLOW_COPY_AND_ASSIGN(PatriciaTriePolicy);
+ static const PatriciaTriePolicy sInstance;
+
+ PatriciaTriePolicy() {}
+ ~PatriciaTriePolicy() {}
+};
+} // namespace latinime
+#endif // LATINIME_PATRICIA_TRIE_POLICY_H