tdf#126573 Add Excel2021 array function SORT to Calc

TODO/WIP: oasis proposal
More information about how this new function works:
https://support.microsoft.com/en-au/office/sort-function-22f63bd0-ccc8-492f-953d-c20e8e44b86c
https://exceljet.net/functions/sort-function

Note: Move ScSortInfoArray class to sortparam.hxx, which is a more
logical place.

Change-Id: I70e720e93ba0414d54cb3437de0bfa066508fe30
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/164778
Tested-by: Jenkins
Reviewed-by: Balazs Varga <balazs.varga.extern@allotropia.de>

4 files changed, 191 insertions, 1 deletions

diff --git a/sc/inc/helpids.h b/sc/inc/helpids.h
index 9e0b07fad10c..0d6d3303ba73 100644
--- a/sc/inc/helpids.h
+++ b/sc/inc/helpids.h
@@ -596,5 +596,6 @@ inline constexpr OUString HID_FUNC_RANDBETWEEN_NV = u"SC_HID_FUNC_RANDBETWEEN_NV
 inline constexpr OUString HID_FUNC_XLOOKUP_MS = u"SC_HID_FUNC_XLOOKUP_MS"_ustr;
 inline constexpr OUString HID_FUNC_XMATCH_MS = u"SC_HID_FUNC_XMATCH_MS"_ustr;
 inline constexpr OUString HID_FUNC_FILTER_MS = u"SC_HID_FUNC_FILTER_MS"_ustr;
+inline constexpr OUString HID_FUNC_SORT_MS = u"SC_HID_FUNC_SORT_MS"_ustr;
 
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/inc/scfuncs.hrc b/sc/inc/scfuncs.hrc
index 5fa1c12808c1..5f612b957ce9 100644
--- a/sc/inc/scfuncs.hrc
+++ b/sc/inc/scfuncs.hrc
@@ -4195,4 +4195,18 @@ const TranslateId SC_OPCODE_FILTER_ARY[] =
     NC_("SC_OPCODE_FILTER", "The value to return if all values in the included array are empty (filter returns nothing).")
 };
 
+// -=*# Resource for function SORT #*=-
+const TranslateId SC_OPCODE_SORT_ARY[] =
+{
+    NC_("SC_OPCODE_SORT", "Sorts the contents of a range or array."),
+    NC_("SC_OPCODE_SORT", "Range"),
+    NC_("SC_OPCODE_SORT", "The range, or array to sort."),
+    NC_("SC_OPCODE_SORT", "Sort index"),
+    NC_("SC_OPCODE_SORT", "A number indicating the row or column to sort by."),
+    NC_("SC_OPCODE_SORT", "Sort order"),
+    NC_("SC_OPCODE_SORT", "A number indicating the desired sort order; 1 for ascending order (default), -1 for descending order."),
+    NC_("SC_OPCODE_SORT", "By col"),
+    NC_("SC_OPCODE_SORT", "A logical value indicating the desired sort direction; FALSE to sort by row (default), TRUE to sort by column.")
+};
+
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/inc/sortparam.hxx b/sc/inc/sortparam.hxx
index 94817b862b3e..58e633d0bcda 100644
--- a/sc/inc/sortparam.hxx
+++ b/sc/inc/sortparam.hxx
@@ -27,9 +27,14 @@
 #include <editeng/colritem.hxx>
 #include <com/sun/star/lang/Locale.hpp>
 #include "scdllapi.h"
+#include "celltextattr.hxx"
+#include "cellvalue.hxx"
+#include "patattr.hxx"
 
 struct ScSubTotalParam;
 struct ScQueryParam;
+class SdrObject;
+class ScPostIt;
 
 enum class ScColorSortMode {
     None,
@@ -115,6 +120,7 @@ struct SC_DLLPUBLIC ScSortParam
     SCROW       nRow1;
     SCCOL       nCol2;
     SCROW       nRow2;
+    SCTAB       nSourceTab;
     ScDataAreaExtras aDataAreaExtras;
     sal_uInt16  nUserIndex;
     bool        bHasHeader;
@@ -148,6 +154,176 @@ struct SC_DLLPUBLIC ScSortParam
     sal_uInt16 GetSortKeyCount() const { return maKeyState.size(); }
 };
 
+struct ScSortInfo final
+{
+    ScRefCellValue maCell;
+    SCCOLROW       nOrg;
+};
+
+class ScSortInfoArray
+{
+public:
+
+    struct Cell
+    {
+        ScRefCellValue maCell;
+        const sc::CellTextAttr* mpAttr;
+        const ScPostIt* mpNote;
+        std::vector<SdrObject*> maDrawObjects;
+        CellAttributeHolder maPattern;
+
+        Cell() : mpAttr(nullptr), mpNote(nullptr),  maPattern() {}
+    };
+
+    struct Row
+    {
+        std::vector<Cell> maCells;
+
+        bool mbHidden:1;
+        bool mbFiltered:1;
+
+        explicit Row( size_t nColSize ) : maCells(nColSize, Cell()), mbHidden(false), mbFiltered(false) {}
+    };
+
+    typedef std::vector<Row> RowsType;
+
+private:
+    std::unique_ptr<RowsType> mpRows; /// row-wise data table for sort by row operation.
+
+    std::vector<std::unique_ptr<ScSortInfo[]>> mvppInfo;
+    SCCOLROW        nStart;
+    SCCOLROW        mnLastIndex; /// index of last non-empty cell position.
+
+    std::vector<SCCOLROW> maOrderIndices;
+    bool mbKeepQuery;
+    bool mbUpdateRefs;
+
+public:
+    ScSortInfoArray(const ScSortInfoArray&) = delete;
+    const ScSortInfoArray& operator=(const ScSortInfoArray&) = delete;
+
+    ScSortInfoArray( sal_uInt16 nSorts, SCCOLROW nInd1, SCCOLROW nInd2 ) :
+        mvppInfo(nSorts),
+        nStart( nInd1 ),
+        mnLastIndex(nInd2),
+        mbKeepQuery(false),
+        mbUpdateRefs(false)
+    {
+        SCSIZE nCount( nInd2 - nInd1 + 1 );
+        if (nSorts)
+        {
+            for ( sal_uInt16 nSort = 0; nSort < nSorts; nSort++ )
+            {
+                mvppInfo[nSort].reset(new ScSortInfo[nCount]);
+            }
+        }
+
+        for (size_t i = 0; i < nCount; ++i)
+            maOrderIndices.push_back(i+nStart);
+    }
+
+    void SetKeepQuery( bool b ) { mbKeepQuery = b; }
+
+    bool IsKeepQuery() const { return mbKeepQuery; }
+
+    void SetUpdateRefs( bool b ) { mbUpdateRefs = b; }
+
+    bool IsUpdateRefs() const { return mbUpdateRefs; }
+
+    /**
+     * Call this only during normal sorting, not from reordering.
+     */
+    std::unique_ptr<ScSortInfo[]> const & GetFirstArray() const
+    {
+        return mvppInfo[0];
+    }
+
+    /**
+     * Call this only during normal sorting, not from reordering.
+     */
+    ScSortInfo & Get( sal_uInt16 nSort, SCCOLROW nInd )
+    {
+        return mvppInfo[nSort][ nInd - nStart ];
+    }
+
+    /**
+     * Call this only during normal sorting, not from reordering.
+     */
+    void Swap( SCCOLROW nInd1, SCCOLROW nInd2 )
+    {
+        if (nInd1 == nInd2) // avoid self-move-assign
+            return;
+        SCSIZE n1 = static_cast<SCSIZE>(nInd1 - nStart);
+        SCSIZE n2 = static_cast<SCSIZE>(nInd2 - nStart);
+        for ( sal_uInt16 nSort = 0; nSort < static_cast<sal_uInt16>(mvppInfo.size()); nSort++ )
+        {
+            auto & ppInfo = mvppInfo[nSort];
+            std::swap(ppInfo[n1], ppInfo[n2]);
+        }
+
+        std::swap(maOrderIndices[n1], maOrderIndices[n2]);
+
+        if (mpRows)
+        {
+            // Swap rows in data table.
+            RowsType& rRows = *mpRows;
+            std::swap(rRows[n1], rRows[n2]);
+        }
+    }
+
+    void SetOrderIndices( std::vector<SCCOLROW>&& rIndices )
+    {
+        maOrderIndices = std::move(rIndices);
+    }
+
+    /**
+     * @param rIndices indices are actual row positions on the sheet, not an
+     *                 offset from the top row.
+     */
+    void ReorderByRow( const std::vector<SCCOLROW>& rIndices )
+    {
+        if (!mpRows)
+            return;
+
+        RowsType& rRows = *mpRows;
+
+        std::vector<SCCOLROW> aOrderIndices2;
+        aOrderIndices2.reserve(rIndices.size());
+
+        RowsType aRows2;
+        aRows2.reserve(rRows.size());
+
+        for (const auto& rIndex : rIndices)
+        {
+            size_t nPos = rIndex - nStart; // switch to an offset to top row.
+            aRows2.push_back(rRows[nPos]);
+            aOrderIndices2.push_back(maOrderIndices[nPos]);
+        }
+
+        rRows.swap(aRows2);
+        maOrderIndices.swap(aOrderIndices2);
+    }
+
+    sal_uInt16      GetUsedSorts() const { return mvppInfo.size(); }
+
+    SCCOLROW    GetStart() const { return nStart; }
+    SCCOLROW GetLast() const { return mnLastIndex; }
+
+    const std::vector<SCCOLROW>& GetOrderIndices() const { return maOrderIndices; }
+
+    RowsType& InitDataRows( size_t nRowSize, size_t nColSize )
+    {
+        mpRows.reset(new RowsType);
+        mpRows->resize(nRowSize, Row(nColSize));
+        return *mpRows;
+    }
+
+    RowsType* GetDataRows()
+    {
+        return mpRows.get();
+    }
+};
+
 namespace sc {
 
 struct ReorderParam
diff --git a/sc/inc/table.hxx b/sc/inc/table.hxx
index 846a9234b23d..f04b1fa0df7a 100644
--- a/sc/inc/table.hxx
+++ b/sc/inc/table.hxx
@@ -26,7 +26,6 @@
 #include "colcontainer.hxx"
 #include "sortparam.hxx"
 #include "types.hxx"
-#include "cellvalue.hxx"
 #include <formula/types.hxx>
 #include "calcmacros.hxx"
 #include <formula/errorcodes.hxx>