LookupTree for fast autocompletion lookups (by Nico Weyand).

LookupTree is a tree structure for fast autocompletion lookups.
Additionally the tree structure stores word probabilities, so each
autocompletion request returns a result with highest probability.
LatinLookupTree is an implementation which was designed to be even
faster and more efficient latin text, however it works with any kind
of unicode strings.

The tree structure was coded by Nico Weyand, Unicode strings support
and conversion to Libreoffice code structure was done by me.

Change-Id: I6549ee45d0952407b8a070f30ed0598fcb420aa7

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