diff options
| -rw-r--r-- | sc/inc/queryiter.hxx | 6 | ||||
| -rw-r--r-- | sc/qa/unit/ucalc_sort.cxx | 80 | ||||
| -rw-r--r-- | sc/source/core/data/queryiter.cxx | 54 |
3 files changed, 121 insertions, 19 deletions
diff --git a/sc/inc/queryiter.hxx b/sc/inc/queryiter.hxx index e247a471db65..847241124a2e 100644 --- a/sc/inc/queryiter.hxx +++ b/sc/inc/queryiter.hxx @@ -140,9 +140,9 @@ protected: void PerformQuery(); /* Only works if no regular expression is involved, only searches for rows in one column, - and only the first query entry is considered with simple conditions SC_LESS_EQUAL - (sorted ascending) or SC_GREATER_EQUAL (sorted descending). Delivers a starting point, - continue with e.g. GetThis() and GetNext() afterwards. Introduced + and only the first query entry is considered with simple conditions SC_LESS,SC_LESS_EQUAL, + SC_EQUAL (sorted ascending) or SC_GREATER,SC_GREATER_EQUAL (sorted descending). Delivers + a starting point, continue with e.g. GetThis() and GetNext() afterwards. Introduced for FindEqualOrSortedLastInRange(). */ bool BinarySearch(); diff --git a/sc/qa/unit/ucalc_sort.cxx b/sc/qa/unit/ucalc_sort.cxx index 698cbb1bde97..e99b0a38cec3 100644 --- a/sc/qa/unit/ucalc_sort.cxx +++ b/sc/qa/unit/ucalc_sort.cxx @@ -2102,6 +2102,18 @@ void TestSort::testQueryBinarySearch() CPPUNIT_ASSERT(it.BinarySearch()); CPPUNIT_ASSERT_EQUAL(SCROW(8), it.GetRow()); } + { + ScQueryParam param = makeSearchParam( range, ascendingCol, SC_LESS, 5 ); + TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0, param, false ); + CPPUNIT_ASSERT(it.BinarySearch()); + CPPUNIT_ASSERT_EQUAL(SCROW(2), it.GetRow()); + } + { + ScQueryParam param = makeSearchParam( range, ascendingCol, SC_EQUAL, 5 ); + TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0, param, false ); + CPPUNIT_ASSERT(it.BinarySearch()); + CPPUNIT_ASSERT_EQUAL(SCROW(8), it.GetRow()); + } { // Descending, this should return the last 5. @@ -2114,6 +2126,12 @@ void TestSort::testQueryBinarySearch() CPPUNIT_ASSERT(it.BinarySearch()); CPPUNIT_ASSERT_EQUAL(SCROW(6), it.GetRow()); } + { + ScQueryParam param = makeSearchParam( range, descendingCol, SC_GREATER, 5 ); + TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0, param, false ); + CPPUNIT_ASSERT(it.BinarySearch()); + CPPUNIT_ASSERT_EQUAL(SCROW(1), it.GetRow()); + } { // There's no 6, so this should return the last 5. @@ -2126,6 +2144,18 @@ void TestSort::testQueryBinarySearch() CPPUNIT_ASSERT(it.BinarySearch()); CPPUNIT_ASSERT_EQUAL(SCROW(8), it.GetRow()); } + { + ScQueryParam param = makeSearchParam( range, ascendingCol, SC_LESS, 6 ); + TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0, param, false ); + CPPUNIT_ASSERT(it.BinarySearch()); + CPPUNIT_ASSERT_EQUAL(SCROW(8), it.GetRow()); + } + { + ScQueryParam param = makeSearchParam( range, ascendingCol, SC_EQUAL, 6 ); + TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0, param, false ); + CPPUNIT_ASSERT(it.BinarySearch()); + CPPUNIT_ASSERT_EQUAL(SCROW(8), it.GetRow()); + } { // Descending, there's no 6, so this should return the last 9. @@ -2138,6 +2168,12 @@ void TestSort::testQueryBinarySearch() CPPUNIT_ASSERT(it.BinarySearch()); CPPUNIT_ASSERT_EQUAL(SCROW(1), it.GetRow()); } + { + ScQueryParam param = makeSearchParam( range, descendingCol, SC_GREATER, 6 ); + TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0, param, false ); + CPPUNIT_ASSERT(it.BinarySearch()); + CPPUNIT_ASSERT_EQUAL(SCROW(1), it.GetRow()); + } { // All values are larger than 0, so this should be an error. @@ -2150,6 +2186,18 @@ void TestSort::testQueryBinarySearch() CPPUNIT_ASSERT(it.BinarySearch()); CPPUNIT_ASSERT_EQUAL(SCROW(0), it.GetRow()); } + { + ScQueryParam param = makeSearchParam( range, ascendingCol, SC_LESS, 0 ); + TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0, param, false ); + CPPUNIT_ASSERT(it.BinarySearch()); + CPPUNIT_ASSERT_EQUAL(SCROW(0), it.GetRow()); + } + { + ScQueryParam param = makeSearchParam( range, ascendingCol, SC_EQUAL, 0 ); + TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0, param, false ); + CPPUNIT_ASSERT(it.BinarySearch()); + CPPUNIT_ASSERT_EQUAL(SCROW(0), it.GetRow()); + } { // Descending, all values are larger than 0, so this should return the last item. @@ -2162,6 +2210,12 @@ void TestSort::testQueryBinarySearch() CPPUNIT_ASSERT(it.BinarySearch()); CPPUNIT_ASSERT_EQUAL(SCROW(10), it.GetRow()); } + { + ScQueryParam param = makeSearchParam( range, descendingCol, SC_GREATER, 0 ); + TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0, param, false ); + CPPUNIT_ASSERT(it.BinarySearch()); + CPPUNIT_ASSERT_EQUAL(SCROW(10), it.GetRow()); + } { // All values are smaller than 10, so this should return the last item. @@ -2174,6 +2228,18 @@ void TestSort::testQueryBinarySearch() CPPUNIT_ASSERT(it.BinarySearch()); CPPUNIT_ASSERT_EQUAL(SCROW(10), it.GetRow()); } + { + ScQueryParam param = makeSearchParam( range, ascendingCol, SC_LESS, 10 ); + TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0, param, false ); + CPPUNIT_ASSERT(it.BinarySearch()); + CPPUNIT_ASSERT_EQUAL(SCROW(10), it.GetRow()); + } + { + ScQueryParam param = makeSearchParam( range, ascendingCol, SC_EQUAL, 10 ); + TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0, param, false ); + CPPUNIT_ASSERT(it.BinarySearch()); + CPPUNIT_ASSERT_EQUAL(SCROW(10), it.GetRow()); + } { // Descending, all values are smaller than 10, so this should be an error. @@ -2186,6 +2252,12 @@ void TestSort::testQueryBinarySearch() CPPUNIT_ASSERT(it.BinarySearch()); CPPUNIT_ASSERT_EQUAL(SCROW(0), it.GetRow()); } + { + ScQueryParam param = makeSearchParam( range, descendingCol, SC_GREATER, 10 ); + TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0, param, false ); + CPPUNIT_ASSERT(it.BinarySearch()); + CPPUNIT_ASSERT_EQUAL(SCROW(0), it.GetRow()); + } { // Search as ascending but use descending range (=search will not work). @@ -2203,6 +2275,14 @@ void TestSort::testQueryBinarySearch() // CPPUNIT_ASSERT_EQUAL(SCROW(10), it.GetRow()); } + { + // SC_EQUAL with descending is considered an error. + ScQueryParam param = makeSearchParam( range, descendingCol, SC_EQUAL, 9 ); + TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0, param, false ); + CPPUNIT_ASSERT(it.BinarySearch()); + // CPPUNIT_ASSERT_EQUAL(SCROW(10), it.GetRow()); + } + m_pDoc->DeleteTab(0); } diff --git a/sc/source/core/data/queryiter.cxx b/sc/source/core/data/queryiter.cxx index 60d62ad2da60..73a700f108f8 100644 --- a/sc/source/core/data/queryiter.cxx +++ b/sc/source/core/data/queryiter.cxx @@ -283,7 +283,9 @@ bool ScQueryCellIteratorBase< accessType, queryType >::BinarySearch() assert(maParam.GetEntry(0).GetQueryItem().meType == ScQueryEntry::ByString || maParam.GetEntry(0).GetQueryItem().meType == ScQueryEntry::ByValue); assert(maParam.bByRow); - assert(maParam.GetEntry(0).eOp == SC_LESS_EQUAL || maParam.GetEntry(0).eOp == SC_GREATER_EQUAL); + assert(maParam.GetEntry(0).eOp == SC_LESS || maParam.GetEntry(0).eOp == SC_LESS_EQUAL + || maParam.GetEntry(0).eOp == SC_GREATER || maParam.GetEntry(0).eOp == SC_GREATER_EQUAL + || maParam.GetEntry(0).eOp == SC_EQUAL); // TODO: This will be extremely slow with mdds::multi_type_vector. @@ -301,7 +303,7 @@ bool ScQueryCellIteratorBase< accessType, queryType >::BinarySearch() SvNumberFormatter& rFormatter = *(mrContext.GetFormatTable()); const ScQueryEntry& rEntry = maParam.GetEntry(0); const ScQueryEntry::Item& rItem = rEntry.GetQueryItem(); - bool bLessEqual = rEntry.eOp == SC_LESS_EQUAL; + bool bAscending = rEntry.eOp == SC_LESS || rEntry.eOp == SC_LESS_EQUAL || rEntry.eOp == SC_EQUAL; bool bByString = rItem.meType == ScQueryEntry::ByString; bool bAllStringIgnore = bIgnoreMismatchOnLeadingStrings && !bByString; bool bFirstStringIgnore = bIgnoreMismatchOnLeadingStrings && @@ -323,7 +325,9 @@ bool ScQueryCellIteratorBase< accessType, queryType >::BinarySearch() sal_Int32 nTmp = rCollator.compareString(aCellStr, rEntry.GetQueryItem().maString.getString()); if ((rEntry.eOp == SC_LESS_EQUAL && nTmp > 0) || (rEntry.eOp == SC_GREATER_EQUAL && nTmp < 0) || - (rEntry.eOp == SC_EQUAL && nTmp != 0)) + (rEntry.eOp == SC_EQUAL && nTmp != 0) || + (rEntry.eOp == SC_LESS && nTmp >= 0) || + (rEntry.eOp == SC_GREATER && nTmp <= 0)) ++nRow; } } @@ -361,11 +365,11 @@ bool ScQueryCellIteratorBase< accessType, queryType >::BinarySearch() // range isn't strictly sorted. size_t nLastInRange = nLo; size_t nFirstLastInRange = nLastInRange; - double fLastInRangeValue = bLessEqual ? + double fLastInRangeValue = bAscending ? -(::std::numeric_limits<double>::max()) : ::std::numeric_limits<double>::max(); OUString aLastInRangeString; - if (!bLessEqual) + if (!bAscending) aLastInRangeString = OUString(u'\xFFFF'); aCellData = aIndexer.getCell(nLastInRange); @@ -424,7 +428,7 @@ bool ScQueryCellIteratorBase< accessType, queryType >::BinarySearch() nCellVal, rItem.mfVal)) { nRes = -1; - if (bLessEqual) + if (bAscending) { if (fLastInRangeValue <= nCellVal) { @@ -443,7 +447,7 @@ bool ScQueryCellIteratorBase< accessType, queryType >::BinarySearch() nCellVal, rItem.mfVal)) { nRes = 1; - if (!bLessEqual) + if (!bAscending) { if (fLastInRangeValue >= nCellVal) { @@ -465,7 +469,7 @@ bool ScQueryCellIteratorBase< accessType, queryType >::BinarySearch() OUString aCellStr = ScCellFormat::GetInputString(aCell, nFormat, rFormatter, rDoc); nRes = rCollator.compareString(aCellStr, rEntry.GetQueryItem().maString.getString()); - if (nRes < 0 && bLessEqual) + if (nRes < 0 && bAscending) { sal_Int32 nTmp = rCollator.compareString( aLastInRangeString, aCellStr); @@ -481,7 +485,7 @@ bool ScQueryCellIteratorBase< accessType, queryType >::BinarySearch() bDone = true; } } - else if (nRes > 0 && !bLessEqual) + else if (nRes > 0 && !bAscending) { sal_Int32 nTmp = rCollator.compareString( aLastInRangeString, aCellStr); @@ -501,18 +505,18 @@ bool ScQueryCellIteratorBase< accessType, queryType >::BinarySearch() else if (!bStr && bByString) { nRes = -1; // numeric < string - if (bLessEqual) + if (bAscending) nLastInRange = i; } else // if (bStr && !bByString) { nRes = 1; // string > numeric - if (!bLessEqual) + if (!bAscending) nLastInRange = i; } if (nRes < 0) { - if (bLessEqual) + if (bAscending) nLo = nMid + 1; else // assumed to be SC_GREATER_EQUAL { @@ -524,7 +528,7 @@ bool ScQueryCellIteratorBase< accessType, queryType >::BinarySearch() } else if (nRes > 0) { - if (bLessEqual) + if (bAscending) { if (nMid > 0) nHi = nMid - 1; @@ -536,9 +540,27 @@ bool ScQueryCellIteratorBase< accessType, queryType >::BinarySearch() } else { - found = i; - // But keep searching to find the last matching one. - nLo = nMid + 1; + if(rEntry.eOp == SC_LESS_EQUAL || rEntry.eOp == SC_GREATER_EQUAL || rEntry.eOp == SC_EQUAL) + { + found = i; + nLastInRange = i; + // But keep searching to find the last matching one. + nLo = nMid + 1; + } + else if (bAscending) + { + if (nMid > 0) + nHi = nMid - 1; + else + bDone = true; + } + else + { + if (nMid > 0) + nHi = nMid - 1; + else + bDone = true; + } } } |