From cb75eec0b45eda230996580043e00e38d35a1e5b Mon Sep 17 00:00:00 2001 From: Stephen Kelly Date: Fri, 20 Feb 2015 21:52:09 +0100 Subject: cmAlgorithms: Add const to const objects. --- Source/cmAlgorithms.h | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/Source/cmAlgorithms.h b/Source/cmAlgorithms.h index b9bd67b..56e7f17 100644 --- a/Source/cmAlgorithms.h +++ b/Source/cmAlgorithms.h @@ -84,7 +84,7 @@ private: template FwdIt cmRotate(FwdIt first, FwdIt middle, FwdIt last) { - typename std::iterator_traits::difference_type dist = + const typename std::iterator_traits::difference_type dist = std::distance(middle, last); std::rotate(first, middle, last); std::advance(first, dist); @@ -204,7 +204,7 @@ std::string cmJoin(Range const& r, const char* delimiter) std::ostringstream os; typedef typename Range::value_type ValueType; typedef typename Range::const_iterator InputIt; - InputIt first = r.begin(); + const InputIt first = r.begin(); InputIt last = r.end(); --last; std::copy(first, last, @@ -260,7 +260,7 @@ typename Range::const_iterator cmRemoveDuplicates(Range& r) for(typename Range::const_iterator it = r.begin(); it != r.end(); ++it, ++count) { - typename Range::iterator low = + const typename Range::iterator low = std::lower_bound(unique.begin(), unique.end(), *it); if (low == unique.end() || *low != *it) { -- cgit v0.12 From 47a3e22ea5aee971df1e04a6447bb916af81aa2c Mon Sep 17 00:00:00 2001 From: Stephen Kelly Date: Fri, 20 Feb 2015 21:52:36 +0100 Subject: cmAlgorithms: Rename template type in cmDeleteAll algorithm. It may be any range, not only a container. --- Source/cmAlgorithms.h | 20 ++++++++++---------- 1 file changed, 10 insertions(+), 10 deletions(-) diff --git a/Source/cmAlgorithms.h b/Source/cmAlgorithms.h index 56e7f17..4b03736 100644 --- a/Source/cmAlgorithms.h +++ b/Source/cmAlgorithms.h @@ -105,19 +105,19 @@ struct cmIsPair > enum { value = true }; }; -template::value> +template::value> struct DefaultDeleter { - void operator()(typename Container::value_type value) const { + void operator()(typename Range::value_type value) const { delete value; } }; -template -struct DefaultDeleter +template +struct DefaultDeleter { - void operator()(typename Container::value_type value) const { + void operator()(typename Range::value_type value) const { delete value.second; } }; @@ -187,11 +187,11 @@ cmRange(Range const& range) range.begin(), range.end()); } -template -void cmDeleteAll(Container const& c) +template +void cmDeleteAll(Range const& r) { - std::for_each(c.begin(), c.end(), - ContainerAlgorithms::DefaultDeleter()); + std::for_each(r.begin(), r.end(), + ContainerAlgorithms::DefaultDeleter()); } template -- cgit v0.12 From bbc1a9788d94ed9a6f710689611c63dcc52c8b09 Mon Sep 17 00:00:00 2001 From: Stephen Kelly Date: Fri, 20 Feb 2015 21:53:19 +0100 Subject: cmAlgorithms: Add a size() to cmRange. size() is already used by cmRemoveDuplicates, which is designed to accept a cmRange. --- Source/cmAlgorithms.h | 3 +++ 1 file changed, 3 insertions(+) diff --git a/Source/cmAlgorithms.h b/Source/cmAlgorithms.h index 4b03736..f90f105 100644 --- a/Source/cmAlgorithms.h +++ b/Source/cmAlgorithms.h @@ -127,11 +127,14 @@ struct Range { typedef const_iterator_ const_iterator; typedef typename std::iterator_traits::value_type value_type; + typedef typename std::iterator_traits::difference_type + difference_type; Range(const_iterator begin_, const_iterator end_) : Begin(begin_), End(end_) {} const_iterator begin() const { return Begin; } const_iterator end() const { return End; } bool empty() const { return std::distance(Begin, End) == 0; } + difference_type size() const { return std::distance(Begin, End); } Range& advance(cmIML_INT_intptr_t amount) { std::advance(Begin, amount); -- cgit v0.12 From b917f4c003cb192f461345b66a9af1a3436b86b1 Mon Sep 17 00:00:00 2001 From: Stephen Kelly Date: Fri, 20 Feb 2015 21:55:19 +0100 Subject: cmAlgorithms: Relax cmRemoveN requirement to FwdIter. cmRotate already requires only FwdIter. --- Source/cmAlgorithms.h | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/Source/cmAlgorithms.h b/Source/cmAlgorithms.h index f90f105..8790732 100644 --- a/Source/cmAlgorithms.h +++ b/Source/cmAlgorithms.h @@ -154,7 +154,9 @@ private: template Iter RemoveN(Iter i1, Iter i2, size_t n) { - return cmRotate(i1, i1 + n, i2); + Iter m = i1; + std::advance(m, n); + return cmRotate(i1, m, i2); } template -- cgit v0.12 From cae45df77235bf7314421f2520177f21179beb84 Mon Sep 17 00:00:00 2001 From: Stephen Kelly Date: Fri, 20 Feb 2015 21:56:45 +0100 Subject: cmAlgorithms: Rename template argument to RemoveN. --- Source/cmAlgorithms.h | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/Source/cmAlgorithms.h b/Source/cmAlgorithms.h index 8790732..ca4c1fd 100644 --- a/Source/cmAlgorithms.h +++ b/Source/cmAlgorithms.h @@ -151,10 +151,10 @@ private: const_iterator End; }; -template -Iter RemoveN(Iter i1, Iter i2, size_t n) +template +FwdIt RemoveN(FwdIt i1, FwdIt i2, size_t n) { - Iter m = i1; + FwdIt m = i1; std::advance(m, n); return cmRotate(i1, m, i2); } -- cgit v0.12 From ba959934a6a832e7d0a9f4bfc433e09aad1476f3 Mon Sep 17 00:00:00 2001 From: Stephen Kelly Date: Fri, 20 Feb 2015 22:00:01 +0100 Subject: cmAlgorithms: Make cmRemoveDuplicates work with more containers. Remove the accidental requirement that the input range must be a std::vector. --- Source/cmAlgorithms.h | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) diff --git a/Source/cmAlgorithms.h b/Source/cmAlgorithms.h index ca4c1fd..161a2cb 100644 --- a/Source/cmAlgorithms.h +++ b/Source/cmAlgorithms.h @@ -258,14 +258,15 @@ typename Range::const_iterator cmRemoveMatching(Range &r, MatchRange const& m) template typename Range::const_iterator cmRemoveDuplicates(Range& r) { - std::vector unique; + typedef std::vector UniqueVector; + UniqueVector unique; unique.reserve(r.size()); std::vector indices; size_t count = 0; for(typename Range::const_iterator it = r.begin(); it != r.end(); ++it, ++count) { - const typename Range::iterator low = + const typename UniqueVector::iterator low = std::lower_bound(unique.begin(), unique.end(), *it); if (low == unique.end() || *low != *it) { -- cgit v0.12 From 1f7967913662429adcc509528086d6525acff317 Mon Sep 17 00:00:00 2001 From: Stephen Kelly Date: Fri, 20 Feb 2015 22:07:28 +0100 Subject: cmAlgorithms: Relax iterator requirement for cmRemoveIndices. Require only forward iterators from the range. --- Source/cmAlgorithms.h | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-) diff --git a/Source/cmAlgorithms.h b/Source/cmAlgorithms.h index 161a2cb..3dd5f95 100644 --- a/Source/cmAlgorithms.h +++ b/Source/cmAlgorithms.h @@ -237,12 +237,15 @@ typename Range::const_iterator cmRemoveIndices(Range& r, InputRange const& rem) { typename InputRange::const_iterator remIt = rem.begin(); - typename Range::iterator writer = r.begin() + *remIt; + typename Range::iterator writer = r.begin(); + std::advance(writer, *remIt); ++remIt; size_t count = 1; for ( ; writer != r.end() && remIt != rem.end(); ++count, ++remIt) { - writer = ContainerAlgorithms::RemoveN(writer, r.begin() + *remIt, count); + typename Range::iterator pivot = r.begin(); + std::advance(pivot, *remIt); + writer = ContainerAlgorithms::RemoveN(writer, pivot, count); } writer = ContainerAlgorithms::RemoveN(writer, r.end(), count); return writer; -- cgit v0.12 From 7fd8557f4c3d761c8ec0e7c29c9fa74a3ff45295 Mon Sep 17 00:00:00 2001 From: Stephen Kelly Date: Fri, 20 Feb 2015 22:10:41 +0100 Subject: cmAlgorithms: Maintain the pivot iterator in cmRemoveIndices. Avoid the algorithm of 'Schlemiel the painter' in the case of iterators which are not RandomAccess. --- Source/cmAlgorithms.h | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/Source/cmAlgorithms.h b/Source/cmAlgorithms.h index 3dd5f95..f00e1c0 100644 --- a/Source/cmAlgorithms.h +++ b/Source/cmAlgorithms.h @@ -239,12 +239,14 @@ typename Range::const_iterator cmRemoveIndices(Range& r, InputRange const& rem) typename Range::iterator writer = r.begin(); std::advance(writer, *remIt); + typename Range::iterator pivot = writer; + typename InputRange::value_type prevRem = *remIt; ++remIt; size_t count = 1; for ( ; writer != r.end() && remIt != rem.end(); ++count, ++remIt) { - typename Range::iterator pivot = r.begin(); - std::advance(pivot, *remIt); + std::advance(pivot, *remIt - prevRem); + prevRem = *remIt; writer = ContainerAlgorithms::RemoveN(writer, pivot, count); } writer = ContainerAlgorithms::RemoveN(writer, r.end(), count); -- cgit v0.12 From a5b10ae68a4a84face73767f96189673015946be Mon Sep 17 00:00:00 2001 From: Stephen Kelly Date: Fri, 20 Feb 2015 22:15:47 +0100 Subject: cmAlgorithms: Remove needless assignment. --- Source/cmAlgorithms.h | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) diff --git a/Source/cmAlgorithms.h b/Source/cmAlgorithms.h index f00e1c0..43023db 100644 --- a/Source/cmAlgorithms.h +++ b/Source/cmAlgorithms.h @@ -249,8 +249,7 @@ typename Range::const_iterator cmRemoveIndices(Range& r, InputRange const& rem) prevRem = *remIt; writer = ContainerAlgorithms::RemoveN(writer, pivot, count); } - writer = ContainerAlgorithms::RemoveN(writer, r.end(), count); - return writer; + return ContainerAlgorithms::RemoveN(writer, r.end(), count); } template -- cgit v0.12 From 47c2da6aa8c8f77e8d01b68cd5de596da2b2c3d7 Mon Sep 17 00:00:00 2001 From: Stephen Kelly Date: Fri, 20 Feb 2015 22:19:14 +0100 Subject: cmAlgorithms: Cache the end iterators in algorithms. --- Source/cmAlgorithms.h | 11 +++++++---- 1 file changed, 7 insertions(+), 4 deletions(-) diff --git a/Source/cmAlgorithms.h b/Source/cmAlgorithms.h index 43023db..b9d7e78 100644 --- a/Source/cmAlgorithms.h +++ b/Source/cmAlgorithms.h @@ -236,6 +236,7 @@ template typename Range::const_iterator cmRemoveIndices(Range& r, InputRange const& rem) { typename InputRange::const_iterator remIt = rem.begin(); + typename InputRange::const_iterator remEnd = rem.end(); typename Range::iterator writer = r.begin(); std::advance(writer, *remIt); @@ -243,13 +244,14 @@ typename Range::const_iterator cmRemoveIndices(Range& r, InputRange const& rem) typename InputRange::value_type prevRem = *remIt; ++remIt; size_t count = 1; - for ( ; writer != r.end() && remIt != rem.end(); ++count, ++remIt) + const typename Range::iterator rangeEnd = r.end(); + for ( ; writer != rangeEnd && remIt != remEnd; ++count, ++remIt) { std::advance(pivot, *remIt - prevRem); prevRem = *remIt; writer = ContainerAlgorithms::RemoveN(writer, pivot, count); } - return ContainerAlgorithms::RemoveN(writer, r.end(), count); + return ContainerAlgorithms::RemoveN(writer, rangeEnd, count); } template @@ -267,8 +269,9 @@ typename Range::const_iterator cmRemoveDuplicates(Range& r) unique.reserve(r.size()); std::vector indices; size_t count = 0; + const typename Range::iterator end = r.end(); for(typename Range::const_iterator it = r.begin(); - it != r.end(); ++it, ++count) + it != end; ++it, ++count) { const typename UniqueVector::iterator low = std::lower_bound(unique.begin(), unique.end(), *it); @@ -283,7 +286,7 @@ typename Range::const_iterator cmRemoveDuplicates(Range& r) } if (indices.empty()) { - return r.end(); + return end; } return cmRemoveIndices(r, indices); } -- cgit v0.12