summaryrefslogtreecommitdiff
path: root/editeng
diff options
context:
space:
mode:
Diffstat (limited to 'editeng')
-rw-r--r--editeng/Library_editeng.mk1
-rw-r--r--editeng/qa/lookuptree/lookuptree_test.cxx95
-rw-r--r--editeng/source/lookuptree/Trie.cxx183
3 files changed, 275 insertions, 4 deletions
diff --git a/editeng/Library_editeng.mk b/editeng/Library_editeng.mk
index f352113c96ef..e9c5b4bea2d2 100644
--- a/editeng/Library_editeng.mk
+++ b/editeng/Library_editeng.mk
@@ -116,6 +116,7 @@ $(eval $(call gb_Library_add_exception_objects,editeng,\
editeng/source/lookuptree/LatinLookupTree \
editeng/source/lookuptree/LatinTreeNode \
editeng/source/lookuptree/Node \
+ editeng/source/lookuptree/Trie \
))
# add libraries to be linked to editeng; again these names need to be given as
diff --git a/editeng/qa/lookuptree/lookuptree_test.cxx b/editeng/qa/lookuptree/lookuptree_test.cxx
index c8ee1ab0e558..4722bb16d278 100644
--- a/editeng/qa/lookuptree/lookuptree_test.cxx
+++ b/editeng/qa/lookuptree/lookuptree_test.cxx
@@ -25,21 +25,25 @@
#include <editeng/LookupTree.hxx>
#include <editeng/LatinLookupTree.hxx>
+#include <editeng/Trie.hxx>
+
namespace {
class LookupTreeTest : public CppUnit::TestFixture
{
- public:
- void test();
+public:
+ void testLookupTree();
+ void testTrie();
CPPUNIT_TEST_SUITE(LookupTreeTest);
- CPPUNIT_TEST(test);
+ CPPUNIT_TEST(testLookupTree);
+ CPPUNIT_TEST(testTrie);
CPPUNIT_TEST_SUITE_END();
};
CPPUNIT_TEST_SUITE_REGISTRATION(LookupTreeTest);
-void LookupTreeTest::test()
+void LookupTreeTest::testLookupTree()
{
LookupTree* a = new LatinLookupTree( "a" );
@@ -218,6 +222,89 @@ void LookupTreeTest::test()
delete a;
}
+void LookupTreeTest::testTrie()
+{
+ editeng::Trie trie;
+ std::vector<OUString> suggestions;
+
+ trie.findSuggestions( OUString(""), suggestions);
+ CPPUNIT_ASSERT_EQUAL( (size_t) 0, suggestions.size() );
+
+ trie.insert( OUString("") );
+ trie.findSuggestions( OUString(""), suggestions);
+ CPPUNIT_ASSERT_EQUAL( (size_t) 0, suggestions.size() );
+
+ trie.findSuggestions( OUString("a"), suggestions);
+ CPPUNIT_ASSERT_EQUAL( (size_t) 0, suggestions.size() );
+
+ trie.insert( OUString("abc") );
+ trie.insert( OUString("abcdefghijklmnopqrstuvwxyz") );
+ trie.findSuggestions( OUString("a"), suggestions);
+ CPPUNIT_ASSERT_EQUAL( (size_t) 2, suggestions.size() );
+ CPPUNIT_ASSERT_EQUAL( OUString("abc"), suggestions[0] );
+ CPPUNIT_ASSERT_EQUAL( OUString("abcdefghijklmnopqrstuvwxyz"), suggestions[1] );
+ suggestions.clear();
+
+ trie.findSuggestions( OUString("abc"), suggestions);
+ CPPUNIT_ASSERT_EQUAL( (size_t) 1, suggestions.size() );
+ CPPUNIT_ASSERT_EQUAL( OUString("abcdefghijklmnopqrstuvwxyz"), suggestions[0] );
+ suggestions.clear();
+
+ trie.findSuggestions( OUString("abe"), suggestions);
+ CPPUNIT_ASSERT_EQUAL( (size_t) 0, suggestions.size() );
+ suggestions.clear();
+
+ trie.insert( OUString("abe") );
+ trie.findSuggestions( OUString(""), suggestions);
+ CPPUNIT_ASSERT_EQUAL( (size_t) 3, suggestions.size() );
+ CPPUNIT_ASSERT_EQUAL( OUString("abc"), suggestions[0] );
+ CPPUNIT_ASSERT_EQUAL( OUString("abcdefghijklmnopqrstuvwxyz"), suggestions[1] );
+ CPPUNIT_ASSERT_EQUAL( OUString("abe"), suggestions[2] );
+ suggestions.clear();
+
+ trie.insert( OUString("H31l0") );
+ trie.findSuggestions( OUString("H"), suggestions);
+
+ CPPUNIT_ASSERT_EQUAL( (size_t) 1, suggestions.size() );
+ CPPUNIT_ASSERT_EQUAL( OUString("H31l0"), suggestions[0] );
+ suggestions.clear();
+
+ trie.insert( OUString("H1") );
+ trie.findSuggestions( OUString("H"), suggestions);
+ CPPUNIT_ASSERT_EQUAL( (size_t) 2, suggestions.size() );
+ CPPUNIT_ASSERT_EQUAL( OUString("H31l0"), suggestions[0] );
+ CPPUNIT_ASSERT_EQUAL( OUString("H1"), suggestions[1] );
+ suggestions.clear();
+
+ trie.findSuggestions( OUString("H3"), suggestions);
+ CPPUNIT_ASSERT_EQUAL( (size_t) 1, suggestions.size() );
+ CPPUNIT_ASSERT_EQUAL( OUString("H31l0"), suggestions[0] );
+ suggestions.clear();
+
+ trie.insert( OStringToOUString( "H\xC3\xA4llo", RTL_TEXTENCODING_UTF8 ) );
+ trie.findSuggestions( OUString("H"), suggestions );
+ CPPUNIT_ASSERT_EQUAL( (size_t) 3, suggestions.size() );
+ CPPUNIT_ASSERT_EQUAL( OUString("H31l0"), suggestions[0] );
+ CPPUNIT_ASSERT_EQUAL( OUString("H1"), suggestions[1] );
+ CPPUNIT_ASSERT_EQUAL( OStringToOUString( "H\xC3\xA4llo", RTL_TEXTENCODING_UTF8 ), suggestions[2] );
+ suggestions.clear();
+
+ trie.findSuggestions( OUString("H3"), suggestions );
+ CPPUNIT_ASSERT_EQUAL( (size_t) 1, suggestions.size() );
+ CPPUNIT_ASSERT_EQUAL( OUString("H31l0"), suggestions[0] );
+ suggestions.clear();
+
+ trie.findSuggestions( OStringToOUString("H\xC3\xA4", RTL_TEXTENCODING_UTF8), suggestions );
+ CPPUNIT_ASSERT_EQUAL( (size_t) 1, suggestions.size() );
+ CPPUNIT_ASSERT_EQUAL( OStringToOUString("H\xC3\xA4llo", RTL_TEXTENCODING_UTF8), suggestions[0] );
+ suggestions.clear();
+
+ trie.findSuggestions( OUString(""), suggestions);
+ CPPUNIT_ASSERT_EQUAL( (size_t) 6, suggestions.size() );
+ suggestions.clear();
+
+}
+
} // namespace end
CPPUNIT_PLUGIN_IMPLEMENT();
diff --git a/editeng/source/lookuptree/Trie.cxx b/editeng/source/lookuptree/Trie.cxx
new file mode 100644
index 000000000000..30ee0be0769f
--- /dev/null
+++ b/editeng/source/lookuptree/Trie.cxx
@@ -0,0 +1,183 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ */
+
+#include <editeng/Trie.hxx>
+
+namespace editeng
+{
+
+using namespace std;
+
+/* TrieNode */
+
+TrieNode::TrieNode(sal_Unicode aCharacter) :
+ mCharacter(aCharacter),
+ mMarker(false)
+{
+ for (int i=0; i<LATIN_ARRAY_SIZE; i++)
+ {
+ mLatinArray[i] = NULL;
+ }
+}
+
+TrieNode::~TrieNode()
+{
+ vector<TrieNode*>::iterator iNode;
+ for(iNode = mChildren.begin(); iNode != mChildren.end(); iNode++)
+ {
+ delete *iNode;
+ }
+
+ for (int i=0; i<LATIN_ARRAY_SIZE; i++)
+ {
+ delete mLatinArray[i];
+ }
+}
+
+void TrieNode::markWord()
+{
+ mMarker = true;
+}
+
+void TrieNode::addNewChild(TrieNode* pChild)
+{
+ if (pChild->mCharacter >= sal_Unicode('a') &&
+ pChild->mCharacter <= sal_Unicode('z'))
+ {
+ mLatinArray[pChild->mCharacter - sal_Unicode('a')] = pChild;
+ }
+ else
+ {
+ mChildren.push_back(pChild);
+ }
+}
+
+TrieNode* TrieNode::findChild(sal_Unicode aInputCharacter)
+{
+ if (aInputCharacter >= sal_Unicode('a') &&
+ aInputCharacter <= sal_Unicode('z'))
+ {
+ return mLatinArray[aInputCharacter - sal_Unicode('a')];
+ }
+
+ vector<TrieNode*>::iterator iNode;
+
+ for(iNode = mChildren.begin(); iNode != mChildren.end(); iNode++)
+ {
+ TrieNode* pCurrent = *iNode;
+ if ( pCurrent->mCharacter == aInputCharacter )
+ return pCurrent;
+ }
+
+ return NULL;
+}
+
+void TrieNode::collectSuggestions(OUString sPath, vector<OUString>& rSuggestionList)
+{
+ // first traverse nodes for alphabet characters
+ for (int i=0; i<LATIN_ARRAY_SIZE; i++)
+ {
+ TrieNode* pCurrent = mLatinArray[i];
+ if (pCurrent != NULL)
+ {
+ OUString aStringPath = sPath + OUString(pCurrent->mCharacter);
+ if(pCurrent->mMarker)
+ rSuggestionList.push_back(aStringPath);
+ // recursivly traverse tree
+ pCurrent->collectSuggestions(aStringPath, rSuggestionList);
+ }
+ }
+
+ // traverse nodes for other characters
+ vector<TrieNode*>::iterator iNode;
+ for(iNode = mChildren.begin(); iNode != mChildren.end(); iNode++)
+ {
+ TrieNode* pCurrent = *iNode;
+ if (pCurrent != NULL)
+ {
+ OUString aStringPath = sPath + OUString(pCurrent->mCharacter);
+ if(pCurrent->mMarker)
+ rSuggestionList.push_back(aStringPath);
+ // recursivly traverse tree
+ pCurrent->collectSuggestions(aStringPath, rSuggestionList);
+ }
+ }
+}
+
+TrieNode* TrieNode::traversePath(OUString sPath)
+{
+ TrieNode* pCurrent = this;
+
+ for ( sal_Int32 i = 0; i < sPath.getLength(); i++ )
+ {
+ sal_Unicode aCurrentChar = sPath[i];
+ pCurrent = pCurrent->findChild(aCurrentChar);
+ if ( pCurrent == NULL )
+ return NULL;
+ }
+
+ return pCurrent;
+}
+
+/* TRIE */
+
+Trie::Trie()
+{
+ mRoot = new TrieNode();
+}
+
+Trie::~Trie()
+{
+ delete mRoot;
+}
+
+void Trie::insert(OUString sInputString) const
+{
+ // adding an empty word is not allowed
+ if ( sInputString.isEmpty() )
+ {
+ return;
+ }
+
+ // traverse the input string and modify the tree with new nodes / characters
+
+ TrieNode* pCurrent = mRoot;
+ sal_Unicode aCurrentChar;
+
+ for ( sal_Int32 i = 0; i < sInputString.getLength(); i++ )
+ {
+ aCurrentChar = sInputString[i];
+ TrieNode* pChild = pCurrent->findChild(aCurrentChar);
+ if ( pChild == NULL )
+ {
+ TrieNode* pNewNode = new TrieNode(aCurrentChar);
+ pCurrent->addNewChild(pNewNode);
+ pCurrent = pNewNode;
+ }
+ else
+ {
+ pCurrent = pChild;
+ }
+ }
+
+ pCurrent->markWord();
+}
+
+void Trie::findSuggestions(OUString sWordPart, vector<OUString>& rSuggesstionList) const
+{
+ TrieNode* pNode = mRoot->traversePath(sWordPart);
+
+ if (pNode != NULL)
+ {
+ pNode->collectSuggestions(sWordPart, rSuggesstionList);
+ }
+}
+
+}
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
generated by cgit (git 2.34.1) at 2025-02-15 01:48:47 +0000