tdf#108259 Enable autofilter with many different values

Backport from 511fb8e80d298d42f5c45e7410bf64f2a25b441e and
2a39dc74724d3648ff76aa900edfebe0dd19b296

When you create an autofilter on a column which contains many different
values, you will have problems.

First of all, if you exceed 65535 values, you will enter in an infinite
loop because a uint16 is incremented for each value, and after 65535,
you restart to 0.

Secondly, the algorithm executes a double loop in O(n2) to determine
checked values, it's too long. Instead of that, all checked values can be
determined before.

Patch by Linagora.

Change-Id: I5a6ed2b0520f46edbafac24a85c3020a0dcb51c0
Reviewed-on: https://gerrit.libreoffice.org/38489
Tested-by: Jenkins <ci@libreoffice.org>
Reviewed-by: Eike Rathke <erack@redhat.com>

2 files changed, 46 insertions, 4 deletions

diff --git a/sc/source/ui/cctrl/checklistmenu.cxx b/sc/source/ui/cctrl/checklistmenu.cxx
index d3ed848145da..8b43361e8ced 100644
--- a/sc/source/ui/cctrl/checklistmenu.cxx
+++ b/sc/source/ui/cctrl/checklistmenu.cxx
@@ -1141,8 +1141,8 @@ void ScCheckListMenuWindow::setAllMemberState(bool bSet)
     {
         if (!(*itr))
         {
-            sal_uInt16 nCount = maChecks->GetEntryCount();
-            for( sal_uInt16 i = 0; i < nCount; ++i)
+            sal_uInt32 nCount = maChecks->GetEntryCount();
+            for( sal_uInt32 i = 0; i < nCount; ++i)
             {
                 SvTreeListEntry* pEntry = maChecks->GetEntry(i);
                 if (!pEntry)
@@ -1620,7 +1620,7 @@ ScCheckListBox::ScCheckListBox( vcl::Window* pParent )
 
 SvTreeListEntry* ScCheckListBox::FindEntry( SvTreeListEntry* pParent, const OUString& sNode )
 {
-    sal_uInt16 nRootPos = 0;
+    sal_uInt32 nRootPos = 0;
     SvTreeListEntry* pEntry = pParent ? FirstChild( pParent ) : GetEntry( nRootPos );
     while ( pEntry )
     {
@@ -1639,6 +1639,41 @@ void ScCheckListBox::Init()
     SetNodeDefaultImages();
 }
 
+void ScCheckListBox::GetRecursiveChecked(SvTreeListEntry* pEntry, std::unordered_set<OUString, OUStringHash>& vOut, SvTreeListEntry* pParent)
+{
+    if (GetCheckButtonState(pEntry) == SvButtonState::Checked)
+    {
+        // we have to hash both parent and child together
+        OUString aName = GetEntryText(pEntry);
+        if (pParent) aName += GetEntryText(pParent);
+        vOut.insert(aName);
+    }
+
+    if (pEntry->HasChildren())
+    {
+        const SvTreeListEntries& rChildren = pEntry->GetChildEntries();
+        for (auto& rChild : rChildren)
+        {
+            GetRecursiveChecked(rChild.get(), vOut, pEntry);
+        }
+    }
+
+}
+
+std::unordered_set<OUString, OUStringHash> ScCheckListBox::GetAllChecked()
+{
+    std::unordered_set<OUString, OUStringHash> vResults(0);
+    sal_uInt32 nRootPos = 0;
+    SvTreeListEntry* pEntry = GetEntry(nRootPos);
+    while (pEntry)
+    {
+        GetRecursiveChecked(pEntry, vResults, nullptr);
+        pEntry = GetEntry(++nRootPos);
+    }
+
+    return vResults;
+}
+
 bool ScCheckListBox::IsChecked( const OUString& sName, SvTreeListEntry* pParent )
 {
     SvTreeListEntry* pEntry = FindEntry( pParent, sName );
@@ -1907,6 +1942,7 @@ bool ScCheckListMenuWindow::isAllSelected() const
 void ScCheckListMenuWindow::getResult(ResultType& rResult)
 {
     ResultType aResult;
+    std::unordered_set<OUString, OUStringHash> vCheckeds = maChecks->GetAllChecked();
     size_t n = maMembers.size();
     for (size_t i = 0; i < n; ++i)
     {
@@ -1915,7 +1951,10 @@ void ScCheckListMenuWindow::getResult(ResultType& rResult)
             OUString aLabel = maMembers[i].maName;
             if (aLabel.isEmpty())
                 aLabel = ScGlobal::GetRscString(STR_EMPTYDATA);
-            bool bState =  maChecks->IsChecked( aLabel,  maMembers[i].mpParent );
+
+            bool bState = vCheckeds.find(maMembers[i].mpParent ?
+                    aLabel.copy(0).concat(maChecks->GetEntryText(maMembers[i].mpParent)) :
+                    aLabel) != vCheckeds.end();
             ResultEntry aResultEntry;
             aResultEntry.bValid = bState;
             if ( maMembers[i].mbDate )
diff --git a/sc/source/ui/inc/checklistmenu.hxx b/sc/source/ui/inc/checklistmenu.hxx
index 9c1a1f3fd07f..6ac7c4879fc2 100644
--- a/sc/source/ui/inc/checklistmenu.hxx
+++ b/sc/source/ui/inc/checklistmenu.hxx
@@ -19,6 +19,7 @@
 #include <svx/checklbx.hxx>
 
 #include <memory>
+#include <unordered_set>
 #include <unordered_map>
 #include <map>
 
@@ -239,6 +240,8 @@ class ScCheckListBox : public SvTreeListBox
     void CheckEntry( const OUString& sName, SvTreeListEntry* pParent, bool bCheck );
     void CheckEntry( SvTreeListEntry* pEntry, bool bCheck );
     SvTreeListEntry* ShowCheckEntry( const OUString& sName, ScCheckListMember& rMember, bool bShow = true, bool bCheck = true );
+    void GetRecursiveChecked(SvTreeListEntry* pEntry, std::unordered_set<OUString, OUStringHash>& vOut, SvTreeListEntry* pParent);
+    std::unordered_set<OUString, OUStringHash> GetAllChecked();
     bool IsChecked( const OUString& sName, SvTreeListEntry* pParent );
     SvTreeListEntry* FindEntry( SvTreeListEntry* pParent, const OUString& sNode );
     sal_uInt16 GetCheckedEntryCount() const;