Mercurial > hgweb.cgi > pecunia
changeset 168:0e701402324a
Fixed the invoking the previous iterator on the begining of a container when sorting.
Adds reversed order container test.
| author | John Schneiderman <JohnMS@member.fsf.org> |
|---|---|
| date | Wed, 20 Jan 2021 17:40:49 +0100 |
| parents | e00123157fa4 |
| children | ebdd75c8c300 |
| files | ChangeLog src/external/pecunia/Algorithm.hpp src/unit-tests/algorithm-unit-tests.cpp |
| diffstat | 3 files changed, 40 insertions(+), 10 deletions(-) [+] |
line wrap: on
line diff
--- a/ChangeLog Wed Jan 20 16:39:33 2021 +0100 +++ b/ChangeLog Wed Jan 20 17:40:49 2021 +0100 @@ -23,9 +23,11 @@ * Feature: The country/enity that uses a currency is available. * Feature: The name of a currency via its code. * Feature: Refactored the API to be clearer about intention. + * Bug Fix: Triggering potential undefined behaviour when when sorting. * Development: Uses the built-in CMake internal/external source code functionality. * Development: Ability to select building a static or shared library. * Development: Set of scripts to automate the generation of the currency codes. + * Development: Individual unit-tests now be debugged via Visual Studio by default. 2020-12-07 John Schneiderman <JohnMS_AT_member_DOT_fsf_DOT_org> 0.4.2 * Bug Fix: incorrect linkage declaration on Windows. 2020-12-07 John Schneiderman <JohnMS_AT_member_DOT_fsf_DOT_org> 0.4.1
--- a/src/external/pecunia/Algorithm.hpp Wed Jan 20 16:39:33 2021 +0100 +++ b/src/external/pecunia/Algorithm.hpp Wed Jan 20 17:40:49 2021 +0100 @@ -55,13 +55,15 @@ void quicksort( RandomIteratorType low, RandomIteratorType high, - const std::function<void(ContainerValueType&, ContainerValueType&)>& swaperator + const std::function<void(ContainerValueType&, ContainerValueType&)>& swaperator, + const bool isLowBegin ); template<typename RandomIteratorType, typename ContainerValueType> RandomIteratorType partition( RandomIteratorType low, RandomIteratorType high, - const std::function<void(ContainerValueType&, ContainerValueType&)>& swaperator + const std::function<void(ContainerValueType&, ContainerValueType&)>& swaperator, + const bool isLowBegin ); }} @@ -77,7 +79,7 @@ const auto size{container.size()}; if (size > 2) - internal::quicksort(container.begin(), std::prev(container.end()), swaperator); + internal::quicksort(container.begin(), std::prev(container.end()), swaperator, true); else if (size == 2) { auto lhs{container.begin()}; @@ -93,14 +95,15 @@ void pecunia::internal::quicksort( RandomIteratorType low, RandomIteratorType high, - const std::function<void(ContainerValueType&, ContainerValueType&)>& swaperator + const std::function<void(ContainerValueType&, ContainerValueType&)>& swaperator, + const bool isLowBegin ) { if (low < high) { - const auto pivot{partition(low, high, swaperator)}; - quicksort(low, pivot, swaperator); - quicksort(std::next(pivot), high, swaperator); + const auto pivot{partition(low, high, swaperator, isLowBegin)}; + quicksort(low, pivot, swaperator, isLowBegin); + quicksort(std::next(pivot), high, swaperator, false); } } @@ -108,17 +111,24 @@ RandomIteratorType pecunia::internal::partition( RandomIteratorType low, RandomIteratorType high, - const std::function<void(ContainerValueType&, ContainerValueType&)>& swaperator + const std::function<void(ContainerValueType&, ContainerValueType&)>& swaperator, + const bool isLowBegin ) { const auto pivotValue{*std::next(low, std::distance(low, high) / 2)}; - auto lowIndex{std::prev(low)}; + // N.B. Cannot use the previous iterator if it's the begining of the container. + auto lowIndex{isLowBegin ? low : std::prev(low)}; auto highIndex{std::next(high)}; + bool handledLowBegin{ ! isLowBegin}; do { do - std::advance(lowIndex, 1); + // Only advance when the we are not at the begining since it's not been evaluated yet. + if (handledLowBegin) + std::advance(lowIndex, 1); + else + handledLowBegin = true; while (*lowIndex < pivotValue); do
--- a/src/unit-tests/algorithm-unit-tests.cpp Wed Jan 20 16:39:33 2021 +0100 +++ b/src/unit-tests/algorithm-unit-tests.cpp Wed Jan 20 17:40:49 2021 +0100 @@ -204,6 +204,24 @@ QCOMPARE(monies.at(8), m5); } + void sort_sameCurrencyValuesUnsortedReversed_ShouldBeSorted() + { + const Money m0{60, 0u, Iso4217Codes::USD}; + const Money m1{50, 0u, Iso4217Codes::USD}; + const Money m2{40, 0u, Iso4217Codes::USD}; + const Money m3{30, 0u, Iso4217Codes::USD}; + const Money m4{20, 0u, Iso4217Codes::USD}; + const Money m5{10, 0u, Iso4217Codes::USD}; + vector<Money> monies{{m0, m1, m2, m3, m4, m5}}; + sort(monies); + QCOMPARE(monies.at(0), m5); + QCOMPARE(monies.at(1), m4); + QCOMPARE(monies.at(2), m3); + QCOMPARE(monies.at(3), m2); + QCOMPARE(monies.at(4), m1); + QCOMPARE(monies.at(5), m0); + } + void sort_mixedCurrencyValuesUnsorted_ShouldBeSortedAndKeepCurrency() { const Money m0{30, 0u, Iso4217Codes::USD};