diff options
| -rw-r--r-- | editeng/CppunitTest_editeng_lookuptree.mk | 71 | ||||
| -rw-r--r-- | editeng/Library_editeng.mk | 5 | ||||
| -rw-r--r-- | editeng/Module_editeng.mk | 3 | ||||
| -rw-r--r-- | editeng/Package_inc.mk | 7 | ||||
| -rw-r--r-- | editeng/inc/editeng/LatinLookupTree.hxx | 76 | ||||
| -rw-r--r-- | editeng/inc/editeng/LatinTreeNode.hxx | 48 | ||||
| -rw-r--r-- | editeng/inc/editeng/LookupTree.hxx | 95 | ||||
| -rw-r--r-- | editeng/inc/editeng/Node.hxx | 102 | ||||
| -rw-r--r-- | editeng/inc/editeng/TreeHead.hxx | 49 | ||||
| -rw-r--r-- | editeng/qa/lookuptree/lookuptree_test.cxx | 225 | ||||
| -rw-r--r-- | editeng/source/lookuptree/LatinLookupTree.cxx | 240 | ||||
| -rw-r--r-- | editeng/source/lookuptree/LatinTreeNode.cxx | 112 | ||||
| -rw-r--r-- | editeng/source/lookuptree/Node.cxx | 213 |
13 files changed, 1243 insertions, 3 deletions
diff --git a/editeng/CppunitTest_editeng_lookuptree.mk b/editeng/CppunitTest_editeng_lookuptree.mk new file mode 100644 index 000000000000..a69999ee235a --- /dev/null +++ b/editeng/CppunitTest_editeng_lookuptree.mk @@ -0,0 +1,71 @@ +# -*- Mode: makefile-gmake; tab-width: 4; indent-tabs-mode: t -*- +#************************************************************************* +# +# DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. +# +# Copyright 2000, 2011 Oracle and/or its affiliates. +# +# OpenOffice.org - a multi-platform office productivity suite +# +# This file is part of OpenOffice.org. +# +# OpenOffice.org is free software: you can redistribute it and/or modify +# it under the terms of the GNU Lesser General Public License version 3 +# only, as published by the Free Software Foundation. +# +# OpenOffice.org is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU Lesser General Public License version 3 for more details +# (a copy is included in the LICENSE file that accompanied this code). +# +# You should have received a copy of the GNU Lesser General Public License +# version 3 along with OpenOffice.org. If not, see +# <http://www.openoffice.org/license.html> +# for a copy of the LGPLv3 License. +# +#************************************************************************* + +$(eval $(call gb_CppunitTest_CppunitTest,editeng_lookuptree)) + +$(eval $(call gb_CppunitTest_add_exception_objects,editeng_lookuptree, \ + editeng/qa/lookuptree/lookuptree_test \ +)) + +$(eval $(call gb_CppunitTest_use_libraries,editeng_lookuptree, \ + xo \ + basegfx \ + editeng \ + lng \ + svt \ + tk \ + vcl \ + svl \ + sot \ + utl \ + tl \ + comphelper \ + ucbhelper \ + cppuhelper \ + cppu \ + sal \ + salhelper \ + i18nisolang1 \ + i18nutil \ + $(gb_STDLIBS) \ +)) + +$(eval $(call gb_CppunitTest_use_externals,editeng_lookuptree,\ + icuuc \ +)) + +$(eval $(call gb_CppunitTest_set_include,editeng_lookuptree,\ + $$(INCLUDE) \ +)) + +$(eval $(call gb_CppunitTest_use_api,editeng_lookuptree,\ + offapi \ + udkapi \ +)) + +# vim: set noet sw=4 ts=4: diff --git a/editeng/Library_editeng.mk b/editeng/Library_editeng.mk index 276e0625ad7c..81164b94c11c 100644 --- a/editeng/Library_editeng.mk +++ b/editeng/Library_editeng.mk @@ -2,7 +2,7 @@ #************************************************************************* # # DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. -# +# # Copyright 2000, 2011 Oracle and/or its affiliates. # # OpenOffice.org - a multi-platform office productivity suite @@ -125,6 +125,9 @@ $(eval $(call gb_Library_add_exception_objects,editeng,\ editeng/source/uno/unoviwou \ editeng/source/xml/xmltxtexp \ editeng/source/xml/xmltxtimp \ + editeng/source/lookuptree/LatinLookupTree \ + editeng/source/lookuptree/LatinTreeNode \ + editeng/source/lookuptree/Node \ )) # add libraries to be linked to editeng; again these names need to be given as diff --git a/editeng/Module_editeng.mk b/editeng/Module_editeng.mk index b7670989d4ba..eff4df4ce916 100644 --- a/editeng/Module_editeng.mk +++ b/editeng/Module_editeng.mk @@ -2,7 +2,7 @@ #************************************************************************* # # DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. -# +# # Copyright 2000, 2011 Oracle and/or its affiliates. # # OpenOffice.org - a multi-platform office productivity suite @@ -39,6 +39,7 @@ $(eval $(call gb_Module_add_targets,editeng,\ $(eval $(call gb_Module_add_check_targets,editeng,\ CppunitTest_editeng_core \ CppunitTest_editeng_borderline \ + CppunitTest_editeng_lookuptree \ )) # add any subsequent checks (e.g. complex tests) here diff --git a/editeng/Package_inc.mk b/editeng/Package_inc.mk index 300e2ae89c9f..653effb30333 100644 --- a/editeng/Package_inc.mk +++ b/editeng/Package_inc.mk @@ -2,7 +2,7 @@ #************************************************************************* # # DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. -# +# # Copyright 2000, 2011 Oracle and/or its affiliates. # # OpenOffice.org - a multi-platform office productivity suite @@ -153,5 +153,10 @@ $(eval $(call gb_Package_add_file,editeng_inc,inc/editeng/widwitem.hxx,editeng/w $(eval $(call gb_Package_add_file,editeng_inc,inc/editeng/writingmodeitem.hxx,editeng/writingmodeitem.hxx)) $(eval $(call gb_Package_add_file,editeng_inc,inc/editeng/wrlmitem.hxx,editeng/wrlmitem.hxx)) $(eval $(call gb_Package_add_file,editeng_inc,inc/editeng/xmlcnitm.hxx,editeng/xmlcnitm.hxx)) +$(eval $(call gb_Package_add_file,editeng_inc,inc/editeng/LookupTree.hxx,editeng/LookupTree.hxx)) +$(eval $(call gb_Package_add_file,editeng_inc,inc/editeng/Node.hxx,editeng/Node.hxx)) +$(eval $(call gb_Package_add_file,editeng_inc,inc/editeng/TreeHead.hxx,editeng/TreeHead.hxx)) +$(eval $(call gb_Package_add_file,editeng_inc,inc/editeng/LatinLookupTree.hxx,editeng/LatinLookupTree.hxx)) +$(eval $(call gb_Package_add_file,editeng_inc,inc/editeng/LatinTreeNode.hxx,editeng/LatinTreeNode.hxx)) # vim: set noet sw=4 ts=4: diff --git a/editeng/inc/editeng/LatinLookupTree.hxx b/editeng/inc/editeng/LatinLookupTree.hxx new file mode 100644 index 000000000000..373152c510c0 --- /dev/null +++ b/editeng/inc/editeng/LatinLookupTree.hxx @@ -0,0 +1,76 @@ +/* -*- 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/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you 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 . + */ + +#ifndef LATINLOOKUPTREE_HXX +#define LATINLOOKUPTREE_HXX + +#include <editeng/LookupTree.hxx> +#include <editeng/TreeHead.hxx> +#include <editeng/editengdllapi.h> + +using namespace rtl; + +/** + * LatinLookupTree implements a tree that is optimized for storing and looking + * up words that mainly consist of roman characters, although any other + * language can be handled, too. + */ +class EDITENG_DLLPUBLIC LatinLookupTree : public LookupTree, public TreeHead +{ +public: + + explicit LatinLookupTree(OUString sLanguage); + ~LatinLookupTree(); + + + /* =================== Implemented Virtuals From LookupTree =================== */ + void returnToRoot(); + void gotoNode(OUString sNode); + void advance(const sal_Unicode a); + void goBack(); + void insert(OUString sKey, const int nProbability = 1); + void insert(const int nProbability = 1); + void remove(OUString sKey); + OUString suggestAutoCompletion() const; + void clear(); + + /* =================== Implemented Virtuals From Node =================== */ + bool isSeparatedlyHandled(const sal_Unicode cKey) const; + Node*& getChildRef(const sal_Unicode cKey, bool bCreatePlaceholder = false); + void evaluateSeparateStorage(int& nSuggest, Node*& pSuggest) const; + void freeMemory(); + + + /* =================== Implemented Virtual From TreeHead =================== */ + Node* newNode(Node* pParent, const sal_Unicode cKey, const int nProbability = 0); + + /* =================== Member Variables =================== */ + // position of lower case letter 'a' within the selected char encoding. + static const unsigned int our_nLowerCaseA; + + // position of upper case letter 'A' within the selected char encoding. + static const unsigned int our_nUpperCaseA; + +private: + Node* m_pLeaves[52]; // handles [a-z] and [A-Z] +}; + +#endif // LATINLOOKUPTREE_HXX + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/editeng/inc/editeng/LatinTreeNode.hxx b/editeng/inc/editeng/LatinTreeNode.hxx new file mode 100644 index 000000000000..5e406858697c --- /dev/null +++ b/editeng/inc/editeng/LatinTreeNode.hxx @@ -0,0 +1,48 @@ +/* -*- 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/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you 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 . + */ + +#ifndef LATINTREENODE_HXX +#define LATINTREENODE_HXX + +#include <editeng/Node.hxx> + +/** + * LatinTreeNode represents a node within a LatinLookupTree. As en external + * caller, you should never have to do anything with this class directly. + * Use the class LatinLookupTree instead for constructing a new tree. + */ +class LatinTreeNode : public Node +{ +public: + explicit LatinTreeNode(TreeHead *pHead, Node* pParent, const sal_Unicode cKey, const int nProbability = 0); + ~LatinTreeNode(); + + /* =================== Implemented Virtuals From Node =================== */ + bool isSeparatedlyHandled(const sal_Unicode cKey) const; + Node*& getChildRef(const sal_Unicode cKey, bool bCreatePlaceholder = false); + void evaluateSeparateStorage(int& nSuggest, Node*& pSuggest) const; + void freeMemory(); + +private: + Node* m_pLeaves[26]; // handles [a-z] +}; + +#endif // LATINTREENODE_HXX + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/editeng/inc/editeng/LookupTree.hxx b/editeng/inc/editeng/LookupTree.hxx new file mode 100644 index 000000000000..95abcf25d6f8 --- /dev/null +++ b/editeng/inc/editeng/LookupTree.hxx @@ -0,0 +1,95 @@ +/* -*- 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/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you 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 . + */ + +#ifndef LOOKUPTREE_H +#define LOOKUPTREE_H + +#include <sal/types.h> +#include <rtl/ustring.hxx> +#include <editeng/editengdllapi.h> + +/** LookupTree is an interface class that allows for unified access to tree + * structures used for storing dictionnary words as well as their respective + * probabilities. + * It allows you to insert or remove words from the tree, navigate threw the + * tree along its branches and request for a suggestion for autocompletion + * according to the position within the tree. + * It also allows you to attribute a specific language to each tree so that + * it is possible to serve the correct auto completions even within a document + * that contains content in more than one language. + */ +class EDITENG_DLLPUBLIC LookupTree +{ +public: + explicit inline LookupTree(OUString sLanguage); + virtual ~LookupTree() {} + + inline OUString language() const; + + // Resets the current item to root. + virtual void returnToRoot() = 0; + + // Advances from the root position key by key towards the node keyed with + // the last char of sKey. + virtual void gotoNode(OUString sNode) = 0; + + // Advances from the current position towards the node keyed with cKey. + virtual void advance(const sal_Unicode cKey) = 0; + + // Sets the focus to the parent of the current node. Removes the current + // node if it is invalid. + virtual void goBack() = 0; + + // Inserts a complete keyword starting from the root node of the tree. + // Does not change the current position within the tree. + virtual void insert(OUString sKey, const int nProbability = 1) = 0; + + // Inserts a keyword with the given probability at the current position + // within the tree. Does not change the current position within the tree. + virtual void insert(const int nProbability = 1) = 0; + + // Removes a complete keyword starting from the root node of the tree. + // Does not change the current position within the tree. + virtual void remove(OUString sKey) = 0; + + // Returns the suggested autocompletion for the current location within + // the tree. + virtual OUString suggestAutoCompletion() const = 0; + + // Clears the tree and removes any information it contains. + virtual void clear() = 0; + + +private: + const OUString m_sLanguage; // language handled by this tree +}; + +LookupTree::LookupTree(OUString sLanguage) : + m_sLanguage( sLanguage ) +{ +} + +OUString LookupTree::language() const +{ + return m_sLanguage; +} + +#endif // LOOKUPTREE_H + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/editeng/inc/editeng/Node.hxx b/editeng/inc/editeng/Node.hxx new file mode 100644 index 000000000000..3159e48a99b7 --- /dev/null +++ b/editeng/inc/editeng/Node.hxx @@ -0,0 +1,102 @@ +/* -*- 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/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you 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 . + */ + +#ifndef NODE_HXX +#define NODE_HXX + +#include <sal/types.h> +#include <rtl/ustring.hxx> +#include <list> + +class TreeHead; + +/** + * Node represents a node within a LookupTree. As en external caller, you + * should never have to do anything with this class directly. + * Use any of the classes derived from LookupTree instead for constructing a + * new tree. + */ +class Node +{ +public: + //explicit Node(TreeHead* const pHead); + explicit Node(TreeHead* const pHead, Node* const pParent = NULL, + const sal_Unicode cKey = 0, const int nProbability = 0); + + virtual ~Node(); + + // Removes the specified child from this node. Make sure you may remove it + // before doing so. + void removeChild(Node*& pChild); + + // Inserts a complete keyword starting from this node of the tree. + void insertKey(OUString sKey, const int nProbability); + // Removes a complete keyword starting from this node of the tree. + void removeKey(OUString sKey); + + // Returns the child node keyed with cKey. + Node* advanceKey(const sal_Unicode cKey); + + // Use this to inform a parent about its child having changed. + // Call this only with nProbability = 0 if you have made sure the node can + // be removed. + void childHasChanged(Node* pChild, const int nProbability, bool bAllowRemoval = false); + + // Rechose the node that is suggested for auto-completion + void reevaluateSuggestion(bool& bNodeProbabilityChanged); + + + /* =================== Virtuals =================== */ + virtual bool isSeparatedlyHandled(const sal_Unicode cKey) const = 0; + + // Returns a reference to the pointer to the child node for the requested + // char. Returns NULL if no such child could be found. + // IMPORTANT: In the latter case, you may NOT overwrite the return value, + // if you did not set bCreatePlaceholder to true. + virtual Node*& getChildRef(const sal_Unicode cKey, bool bCreatePlaceholder = false) = 0; + + // Sets nSuggest to the highest probability within the subtree and pSuggest + // to point to the (first) node with this probability. + virtual void evaluateSeparateStorage(int& nSuggest, Node*& pSuggest) const = 0; + + // Removes all child nodes and clears all memory. + virtual void freeMemory() = 0; + + /* =================== Member Variables =================== */ + const sal_Unicode m_cKey; // the char represented by this node + int m_nKeyProbability; // the number of occurrences of this key + + // the highest KeyProbability in the tree sprouting from this node + int m_nHighestProbaInSubtree; + + Node* const m_pParent; // the parent of this node + Node* m_pSuggest; // next node in chain to the suggested autocompletion + + TreeHead* const m_pHead; // head of the tree + + unsigned short m_nChildren; // the number of children of the node + std::list<Node*> m_lChildren; // all chars not handled by array + + // Allows returning a reference to a valid Null pointer. May NOT be overwritten. + static Node* our_pNodeNullPointer; +}; + +#endif // NODE_HXX + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/editeng/inc/editeng/TreeHead.hxx b/editeng/inc/editeng/TreeHead.hxx new file mode 100644 index 000000000000..12c8b33c8d66 --- /dev/null +++ b/editeng/inc/editeng/TreeHead.hxx @@ -0,0 +1,49 @@ +/* -*- 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/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you 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 . + */ + +#ifndef TREEHEAD_HXX +#define TREEHEAD_HXX + +#include <editeng/Node.hxx> + +/** + * Represents the root node of a LookupTree. + */ +class TreeHead : public Node +{ +public: + explicit inline TreeHead(); + virtual ~TreeHead() {} + + /* =================== Virtuals =================== */ + virtual Node* newNode(Node* pParent, const sal_Unicode cKey, const int nProbability = 0) = 0; + + /* =================== Member Variables =================== */ + Node* m_pCurrent; // current location within the tree +}; + +TreeHead::TreeHead() : + Node( this ), + m_pCurrent( this ) +{ +} + +#endif // TREEHEAD_HXX + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/editeng/qa/lookuptree/lookuptree_test.cxx b/editeng/qa/lookuptree/lookuptree_test.cxx new file mode 100644 index 000000000000..9ca8bdcc38d9 --- /dev/null +++ b/editeng/qa/lookuptree/lookuptree_test.cxx @@ -0,0 +1,225 @@ +/* -*- 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/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you 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 . + */ + +#include <sal/types.h> +#include <cppunit/TestFixture.h> +#include <cppunit/extensions/HelperMacros.h> +#include <cppunit/plugin/TestPlugIn.h> + +#include <editeng/LookupTree.hxx> +#include <editeng/LatinLookupTree.hxx> + +namespace { + +class LookupTreeTest : public CppUnit::TestFixture +{ + public: + void test(); + + CPPUNIT_TEST_SUITE(LookupTreeTest); + CPPUNIT_TEST(test); + CPPUNIT_TEST_SUITE_END(); +}; + +CPPUNIT_TEST_SUITE_REGISTRATION(LookupTreeTest); + +void LookupTreeTest::test() +{ + LookupTree* a = new LatinLookupTree( "a" ); + + a->insert( OUString("vorschlagnummer1"), 2 ); + a->insert( OUString("vorschlagnummer12") ); + a->insert( OUString("vorschlagnummer2") ); + + CPPUNIT_ASSERT_EQUAL( OUString("vorschlagnummer1"), a->suggestAutoCompletion() ); + + a->insert( OUString("vorschlagnummer12") ); + CPPUNIT_ASSERT_EQUAL( OUString("vorschlagnummer12"), a->suggestAutoCompletion() ); + + a->insert( OUString("vorschlagnummer2") ); + a->insert( OUString("vorschlagnummer2") ); + CPPUNIT_ASSERT_EQUAL( OUString("vorschlagnummer2"), a->suggestAutoCompletion() ); + + a->insert( OUString("vorschlag"), 15 ); + CPPUNIT_ASSERT_EQUAL( OUString("vorschlag"), a->suggestAutoCompletion() ); + + a->insert( OUString("vorschlagnummer2"), 16 ); + CPPUNIT_ASSERT_EQUAL( OUString("vorschlagnummer2"), a->suggestAutoCompletion() ); + + a->remove( OUString("vorschlagnummer2") ); + CPPUNIT_ASSERT_EQUAL( OUString("vorschlag"), a->suggestAutoCompletion() ); + + a->insert( OUString("vorschlag20"), 20 ); + CPPUNIT_ASSERT_EQUAL( OUString("vorschlag20"), a->suggestAutoCompletion() ); + + a->remove( OUString("vorschlag20") ); + CPPUNIT_ASSERT_EQUAL( OUString("vorschlag"), a->suggestAutoCompletion() ); + + a->insert( OUString("vorschlagn"), 14 ); + CPPUNIT_ASSERT_EQUAL( OUString("vorschlag"), a->suggestAutoCompletion() ); + + a->remove( OUString("vorschlag") ); + CPPUNIT_ASSERT_EQUAL( OUString("vorschlagn"), a->suggestAutoCompletion() ); + + a->remove( OUString("vorschlagn") ); + CPPUNIT_ASSERT_EQUAL( OUString("vorschlagnummer12"), a->suggestAutoCompletion() ); + + a->insert( OUString("aber"), 1 ); + CPPUNIT_ASSERT_EQUAL( OUString("vorschlagnummer12"), a->suggestAutoCompletion() ); + + a->advance( 'a' ); + CPPUNIT_ASSERT_EQUAL( OUString("ber"), a->suggestAutoCompletion() ); + + a->goBack(); + CPPUNIT_ASSERT_EQUAL( OUString("vorschlagnummer12"), a->suggestAutoCompletion() ); + + a->insert( OUString("vorschlag"), 15 ); + CPPUNIT_ASSERT_EQUAL( OUString("vorschlag"), a->suggestAutoCompletion() ); + + a->insert( OUString("vorschlag13"), 13 ); + CPPUNIT_ASSERT_EQUAL( OUString("vorschlag"), a->suggestAutoCompletion() ); + + a->gotoNode( "vorsch" ); + CPPUNIT_ASSERT_EQUAL( OUString("lag"), a->suggestAutoCompletion() ); + + a->advance( 'l' ); + CPPUNIT_ASSERT_EQUAL( OUString("ag"), a->suggestAutoCompletion() ); + + a->advance( 'a' ); + CPPUNIT_ASSERT_EQUAL( OUString("g13"), a->suggestAutoCompletion() ); + + a->advance( 'g' ); + CPPUNIT_ASSERT_EQUAL( OUString("13"), a->suggestAutoCompletion() ); + + a->advance( '1' ); + CPPUNIT_ASSERT_EQUAL( OUString("3"), a->suggestAutoCompletion() ); + + a->advance( '3' ); + CPPUNIT_ASSERT ( a->suggestAutoCompletion().isEmpty() ); + + a->goBack(); + a->advance( 'z' ); + CPPUNIT_ASSERT ( a->suggestAutoCompletion().isEmpty() ); + + a->gotoNode( "vorschlag13" ); + CPPUNIT_ASSERT ( a->suggestAutoCompletion().isEmpty() ); + + a->advance( 'g' ); + a->advance( '1' ); + a->advance( '3' ); + a->remove( "vorschlag13" ); + CPPUNIT_ASSERT_EQUAL( OUString(""), a->suggestAutoCompletion() ); + + a->insert( "VeraHatMichL1eb.", 1000000 ); + a->returnToRoot(); + CPPUNIT_ASSERT_EQUAL( OUString("VeraHatMichL1eb."), a->suggestAutoCompletion() ); + + a->gotoNode( "VeraHatMich" ); + a->remove( "VeraHatMichL1eb." ); + CPPUNIT_ASSERT_EQUAL( OUString(""), a->suggestAutoCompletion() ); + + a->returnToRoot(); + CPPUNIT_ASSERT_EQUAL( OUString("vorschlag"), a->suggestAutoCompletion() ); + + a->gotoNode( "VeraLiebtMich" ); + a->insert( 600 ); + a->returnToRoot(); + CPPUNIT_ASSERT_EQUAL( OUString("VeraLiebtMich"), a->suggestAutoCompletion() ); + + a->insert( "VeraHatMichL1eb.", 1000000 ); + a->returnToRoot(); + CPPUNIT_ASSERT_EQUAL( OUString("VeraHatMichL1eb."), a->suggestAutoCompletion() ); + + a->gotoNode( "VeraHatMich" ); + a->remove( "VeraHatMichL1eb." ); + CPPUNIT_ASSERT ( a->suggestAutoCompletion().isEmpty() ); + + a->advance( 'L' ); + CPPUNIT_ASSERT ( a->suggestAutoCompletion().isEmpty() ); + + a->insert( "VeraHatMichL1eb.", 1000000 ); + a->returnToRoot(); + a->gotoNode( "VeraHatMich" ); + a->remove( "VeraHatMichL1eb." ); + CPPUNIT_ASSERT ( a->suggestAutoCompletion().isEmpty() ); + + a->goBack(); + CPPUNIT_ASSERT ( a->suggestAutoCompletion().isEmpty() ); + + a->insert( "VeraHatMichL1eb.", 1000000 ); + a->returnToRoot(); + a->gotoNode( "VeraHatMich" ); + a->remove( "VeraHatMichL1eb." ); + CPPUNIT_ASSERT ( a->suggestAutoCompletion().isEmpty() ); + + a->goBack(); + CPPUNIT_ASSERT ( a->suggestAutoCompletion().isEmpty() ); + + a->insert( "neu", 2000 ); + a->returnToRoot(); + CPPUNIT_ASSERT_EQUAL( OUString("neu"), a->suggestAutoCompletion() ); + + a->gotoNode( "ne" ); + CPPUNIT_ASSERT_EQUAL( OUString("u"), a->suggestAutoCompletion() ); + + a->advance( sal_Unicode('u') ); + a->advance( sal_Unicode('e') ); + a->advance( sal_Unicode('r') ); + a->insert(); + CPPUNIT_ASSERT ( a->suggestAutoCompletion().isEmpty() ); + + a->returnToRoot(); + CPPUNIT_ASSERT_EQUAL( OUString("neu"), a->suggestAutoCompletion() ); + + a->advance( 'n' ); + CPPUNIT_ASSERT_EQUAL( OUString("eu"), a->suggestAutoCompletion() ); + + a->advance( 'e' ); + CPPUNIT_ASSERT_EQUAL( OUString("uer"), a->suggestAutoCompletion() ); + + // Test unicode + OUString aQueryString = rtl::OStringToOUString( "H\xC3\xA4llo", RTL_TEXTENCODING_UTF8 ); + a->insert( aQueryString ); + a->returnToRoot(); + a->advance( sal_Unicode('H') ); + + OUString aAutocompletedString = a->suggestAutoCompletion(); + OUString aExpectedString = rtl::OStringToOUString( "\xC3\xA4llo", RTL_TEXTENCODING_UTF8 ); + + CPPUNIT_ASSERT_EQUAL( aExpectedString, aAutocompletedString ); + + OString aUtf8String( "\xe3\x81\x82\xe3\x81\x97\xe3\x81\x9f" ); + aQueryString = rtl::OStringToOUString( aUtf8String, RTL_TEXTENCODING_UTF8 ); + a->insert( aQueryString ); + + OUString aGotoString = rtl::OStringToOUString( "\xe3\x81\x82", RTL_TEXTENCODING_UTF8 ); + a->gotoNode( aGotoString ); + + aAutocompletedString = a->suggestAutoCompletion(); + aExpectedString = rtl::OStringToOUString( "\xe3\x81\x97\xe3\x81\x9f", RTL_TEXTENCODING_UTF8 ); + CPPUNIT_ASSERT_EQUAL( aExpectedString, aAutocompletedString ); + + delete a; +} + +} // namespace end + +CPPUNIT_PLUGIN_IMPLEMENT(); + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/editeng/source/lookuptree/LatinLookupTree.cxx b/editeng/source/lookuptree/LatinLookupTree.cxx new file mode 100644 index 000000000000..5d78724c33b8 --- /dev/null +++ b/editeng/source/lookuptree/LatinLookupTree.cxx @@ -0,0 +1,240 @@ +/* -*- 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/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you 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 . + */ + +#include <editeng/LatinLookupTree.hxx> +#include <editeng/LatinTreeNode.hxx> + +LatinLookupTree::LatinLookupTree(OUString sLanguage) : + LookupTree( sLanguage ) +{ + for ( sal_Unicode i = 0; i < 52; ++i ) + { + m_pLeaves[i] = NULL; + } +} + +LatinLookupTree::~LatinLookupTree() +{ + freeMemory(); +} + +void LatinLookupTree::returnToRoot() +{ + if ( m_pCurrent == m_pHead ) + return; + + // If there is no entry in this node or the tree that sprouts from it. + if ( m_pCurrent && + m_pCurrent->m_pParent && + !m_pCurrent->m_nChildren && + !m_pCurrent->m_nKeyProbability ) + { + m_pCurrent->m_pParent->childHasChanged( m_pCurrent, 0, true ); + } + + m_pCurrent = m_pHead; +} + +void LatinLookupTree::gotoNode(OUString sNode) +{ + returnToRoot(); + + // walk down the tree... + for ( int i = 0; i < sNode.getLength(); i++ ) + { + m_pCurrent = m_pCurrent->advanceKey( sNode[i] ); + } +} + +void LatinLookupTree::advance(const sal_Unicode cKey) +{ + m_pCurrent = m_pCurrent->advanceKey( cKey ); +} + +void LatinLookupTree::goBack() +{ + if ( m_pCurrent->m_pParent ) // if we're not at the root + { + const Node* const pChild = m_pCurrent; + m_pCurrent = m_pCurrent->m_pParent; // set focus to parent + + // if this is an unused tree leaf + if ( !pChild->m_nChildren && !pChild->m_nKeyProbability ) + { + m_pCurrent->removeChild( m_pCurrent->getChildRef( pChild->m_cKey ) ); + } + } +} + +void LatinLookupTree::insert(OUString sKey, const int nProbability) +{ + if ( !sKey.isEmpty() && nProbability > 0 ) + { + insertKey( sKey, nProbability ); + } +} + +void LatinLookupTree::insert(const int nProbability) +{ + if ( m_pCurrent == this ) + return; + + // change probability + int proba = m_pCurrent->m_nKeyProbability += nProbability; + + // inform his parent + m_pCurrent->m_pParent->childHasChanged( m_pCurrent, proba ); +} + +void LatinLookupTree::remove(OUString sKey) +{ + if ( !sKey.isEmpty() ) + { + removeKey( sKey ); + } +} + +OUString LatinLookupTree::suggestAutoCompletion() const +{ + if ( !m_pCurrent ) + return OUString(); + + Node* pWalker = m_pCurrent; + + int distance = 0, nTargetProbability = 0; + OUString sSuggestion; + + while ( pWalker->m_pSuggest && ( distance < 2 || + // Make sure the suggestion is at least 2 chars long. + nTargetProbability == pWalker->m_nHighestProbaInSubtree ) ) + { + if ( distance < 2 ) + nTargetProbability = pWalker->m_nHighestProbaInSubtree; + + // follow the tree along the suggested route + pWalker = pWalker->m_pSuggest; + ++distance; + sSuggestion += OUString(pWalker->m_cKey); + } + + return sSuggestion; +} + +void LatinLookupTree::clear() +{ + freeMemory(); +} + +bool LatinLookupTree::isSeparatedlyHandled(const sal_Unicode cKey) const +{ + return + ( cKey >= sal_Unicode('a') && cKey <= sal_Unicode('z') ) + || ( cKey >= sal_Unicode('A') && cKey <= sal_Unicode('Z') ); +} + +Node*& LatinLookupTree::getChildRef(const sal_Unicode cKey, bool bCreatePlaceholder) +{ + int pos = -1; + + // determine position in array if possible + if ( cKey >= sal_Unicode('a') && cKey <= sal_Unicode('z') ) + { + pos = cKey - our_nLowerCaseA; + } + else if ( cKey >= sal_Unicode('A') && cKey <= sal_Unicode('Z') ) + { + pos = cKey - our_nUpperCaseA + 26; + } + + if ( pos != -1 ) + { + return m_pLeaves[pos]; + } + else + { + for ( std::list<Node*>::iterator i = m_lChildren.begin(); i != m_lChildren.end(); ++i ) + { + if ( (*i)->m_cKey == cKey ) + { + return *i; + } + } + if ( bCreatePlaceholder ) + { + // Create new entry in case there isn't one. + m_lChildren.push_back( NULL ); + return *(--m_lChildren.end()); + } + else + { + return our_pNodeNullPointer; + } + } +} + +void LatinLookupTree::evaluateSeparateStorage(int& nSuggest, Node*& pSuggest) const +{ + for ( sal_Unicode i = 0; i < 52; ++i ) + { + if ( m_pLeaves[i] ) + { + if ( m_pLeaves[i]->m_nHighestProbaInSubtree > nSuggest ) + { + nSuggest = m_pLeaves[i]->m_nHighestProbaInSubtree; + pSuggest = m_pLeaves[i]; + } + if ( m_pLeaves[i]->m_nKeyProbability > nSuggest ) + { + nSuggest = m_pLeaves[i]->m_nKeyProbability; + pSuggest = m_pLeaves[i]; + } + } + } +} + +void LatinLookupTree::freeMemory() +{ + // remove nodes from array + for ( sal_Unicode i = 0; i < 52; ++i ) + { + if ( m_pLeaves[i] ) + { + m_pLeaves[i]->freeMemory(); + delete m_pLeaves[i]; + m_pLeaves[i] = NULL; + } + } + // clear list + while ( m_lChildren.size() ) + { + Node* pTmp = m_lChildren.front(); + m_lChildren.pop_front(); + delete pTmp; + } +} + +Node* LatinLookupTree::newNode(Node* pParent, const sal_Unicode cKey, const int nProbability) +{ + return new LatinTreeNode( this, pParent, cKey, nProbability ); +} + +const unsigned int LatinLookupTree::our_nLowerCaseA = 97; +const unsigned int LatinLookupTree::our_nUpperCaseA = 65; + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/editeng/source/lookuptree/LatinTreeNode.cxx b/editeng/source/lookuptree/LatinTreeNode.cxx new file mode 100644 index 000000000000..b68e039d1349 --- /dev/null +++ b/editeng/source/lookuptree/LatinTreeNode.cxx @@ -0,0 +1,112 @@ +/* -*- 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/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you 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 . + */ + +#include <editeng/LatinTreeNode.hxx> +#include <editeng/LatinLookupTree.hxx> + +LatinTreeNode::LatinTreeNode(TreeHead* pHead, Node* pParent, const sal_Unicode cKey, const int nProbability) : + Node( pHead, pParent, cKey, nProbability ) +{ + for ( sal_Unicode i = 0; i < 26; ++i ) + { + m_pLeaves[i] = NULL; + } +} + +LatinTreeNode::~LatinTreeNode() +{ + freeMemory(); +} + +bool LatinTreeNode::isSeparatedlyHandled(const sal_Unicode cKey) const +{ + return ( cKey >= sal_Unicode('a') && cKey <= sal_Unicode('z') ); +} + +Node*& LatinTreeNode::getChildRef(const sal_Unicode cKey, bool bCreatePlaceholder) +{ + // determine position in array if possible + if ( cKey >= sal_Unicode('a') && cKey <= sal_Unicode('z') ) + { + return m_pLeaves[cKey - LatinLookupTree::our_nLowerCaseA]; + } + else + { + for ( std::list<Node*>::iterator i = m_lChildren.begin(); i != m_lChildren.end(); ++i ) + { + if ( (*i)->m_cKey == cKey ) + { + return *i; + } + } + if ( bCreatePlaceholder ) + { + // Create new entry in case there isn't one. + m_lChildren.push_back( NULL ); + return *(--m_lChildren.end()); + } + else + { + return our_pNodeNullPointer; + } + } +} + +void LatinTreeNode::evaluateSeparateStorage(int& nSuggest, Node*& pSuggest) const +{ + for ( sal_Unicode i = 0; i < 26; ++i ) + { + if ( m_pLeaves[i] ) + { + if ( m_pLeaves[i]->m_nHighestProbaInSubtree > nSuggest ) + { + nSuggest = m_pLeaves[i]->m_nHighestProbaInSubtree; + pSuggest = m_pLeaves[i]; + } + if ( m_pLeaves[i]->m_nKeyProbability > nSuggest ) + { + nSuggest = m_pLeaves[i]->m_nKeyProbability; + pSuggest = m_pLeaves[i]; + } + } + } +} + +void LatinTreeNode::freeMemory() +{ + // remove nodes from array + for ( sal_Unicode i = 0; i < 26; ++i ) + { + if ( m_pLeaves[i] ) + { + m_pLeaves[i]->freeMemory(); + delete m_pLeaves[i]; + m_pLeaves[i] = NULL; + } + } + // clear list + while ( m_lChildren.size() ) + { + Node* pTmp = m_lChildren.front(); + m_lChildren.pop_front(); + delete pTmp; + } +} + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/editeng/source/lookuptree/Node.cxx b/editeng/source/lookuptree/Node.cxx new file mode 100644 index 000000000000..6d5e32050785 --- /dev/null +++ b/editeng/source/lookuptree/Node.cxx @@ -0,0 +1,213 @@ +/* -*- 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/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you 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 . + */ + +#include <editeng/TreeHead.hxx> +#include <editeng/Node.hxx> + +Node::Node(TreeHead* const pHead, Node* const pParent, + const sal_Unicode cKey, const int nProbability ) : + m_cKey( cKey ), + m_nKeyProbability( nProbability ), + m_nHighestProbaInSubtree( 0 ), + m_pParent( pParent ), + m_pSuggest( NULL ), + m_pHead( pHead ), + m_nChildren( 0 ) +{ +} + +Node::~Node() +{ +} + +void Node::removeChild(Node*& pChild) +{ + const sal_Unicode cKey = pChild->m_cKey; + + if ( pChild ) + { + delete pChild; + pChild = NULL; + --m_nChildren; + } + + if ( !isSeparatedlyHandled( cKey ) ) + { + std::list<Node*>::iterator i = m_lChildren.begin(); + while ( i != m_lChildren.end() ) + { + if ( !(*i) ) + { + i = m_lChildren.erase( i ); + } + ++i; + } + } +} + +void Node::insertKey(OUString sKey, const int nProbability) +{ + if ( !sKey.isEmpty() ) + { + const sal_Unicode cKey = sKey[0]; + sKey = sKey.copy( 1 ); + + Node*& pChild = getChildRef( cKey, true ); + + if ( !pChild ) + { + pChild = m_pHead->newNode( this, cKey ); + ++m_nChildren; + } + + pChild->insertKey( sKey, nProbability ); + } + else + { + m_nKeyProbability += nProbability; + if ( m_pParent ) + { + // inform parent about change + int probability = m_nHighestProbaInSubtree > m_nKeyProbability ? m_nHighestProbaInSubtree : m_nKeyProbability; + m_pParent->childHasChanged( this, probability); + } + } +} + +// Removes a complete keyword starting from this node of the tree. +void Node::removeKey(OUString sKey) +{ + if ( !sKey.isEmpty() ) + { + Node*& pChild = getChildRef( sKey[0] ); + + if ( pChild ) + { + // recursive call downwards + pChild->removeKey( sKey.copy( 1 ) ); + } + // Else: Keyword to be removed couldn't be found within the tree. + // No further changes are going to be made. + } + else // If we are the node to be removed... + { + // ... remove our entry from tree... + m_nKeyProbability = 0; + // ... and make sure our parent is updated. + m_pParent->childHasChanged( this, m_nHighestProbaInSubtree, this != m_pHead->m_pCurrent ); + } +} + +Node *Node::advanceKey(const sal_Unicode cKey) +{ + Node*& pChild = getChildRef( cKey, true ); + + if ( !pChild ) + { + pChild = m_pHead->newNode( this, cKey ); + } + + return pChild; +} + +void Node::childHasChanged(Node *pChild, const int nProbability, bool bAllowRemoval) +{ + if ( nProbability > m_nHighestProbaInSubtree ) + { + m_pSuggest = pChild; + m_nHighestProbaInSubtree = nProbability; + + if ( m_pParent ) // recursive call upwards + { + int probabilityChange = nProbability > m_nKeyProbability ? nProbability : m_nKeyProbability; + m_pParent->childHasChanged( this, probabilityChange ); + } + } + else if ( !nProbability || nProbability < m_nHighestProbaInSubtree ) + { + bool bNewEvaluationRequired = m_pSuggest == pChild; + + if ( !nProbability && bAllowRemoval ) + { + // Remove child. Caller needs to make sure we are allowed to. + removeChild( getChildRef( pChild->m_cKey ) ); + } + + if ( bNewEvaluationRequired ) + { + // This is used to store whether we need to inform our parent about + // the changes within this node. + bool bNodeProbabilityChanged; + + reevaluateSuggestion( bNodeProbabilityChanged ); + + // If necessary, inform our parent about change via recursive call + if ( bNodeProbabilityChanged && m_pParent ) + { + bAllowRemoval = bAllowRemoval && this != m_pHead->m_pCurrent; + int probabilityChange = m_nHighestProbaInSubtree > m_nKeyProbability ? m_nHighestProbaInSubtree : m_nKeyProbability; + m_pParent->childHasChanged( this, probabilityChange, bAllowRemoval ); + } + } + } +} + +void Node::reevaluateSuggestion(bool& bNodeProbabilityChanged) +{ + if ( m_nChildren ) // find child with highest probability + { + int nSuggest = 0; + Node* pSuggest = NULL; + + // find child with highest probability in array + evaluateSeparateStorage( nSuggest, pSuggest ); + + // do the same thing within list + for ( std::list<Node*>::iterator i = m_lChildren.begin(); i != m_lChildren.end(); ++i ) + { + if ( (*i)->m_nHighestProbaInSubtree > nSuggest ) + { + nSuggest = (*i)->m_nHighestProbaInSubtree; + pSuggest = (*i); + } + if ( (*i)->m_nKeyProbability > nSuggest ) + { + nSuggest = (*i)->m_nKeyProbability; + pSuggest = (*i); + } + } + + // determine whether we need to inform our parent + bNodeProbabilityChanged = m_nHighestProbaInSubtree != nSuggest; + + m_pSuggest = pSuggest; + m_nHighestProbaInSubtree = nSuggest; + } + else // there are no children + { + m_pSuggest = NULL; + m_nHighestProbaInSubtree = 0; + + bNodeProbabilityChanged = true; + } +} + +Node* Node::our_pNodeNullPointer = NULL; + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ |