Commit Graph

34 Commits

Author SHA1 Message Date
Stephen Kelly 9644a2d11c cmAlgorithms: Add cmMakeReverseIterator. 2015-07-22 21:23:50 +02:00
Stephen Kelly 514a1dff5b cmAlgorithms: Add some convenient typedefs. 2015-07-22 20:25:47 +02:00
Stephen Kelly 1fe71e2ef0 cmAlgorithms: Move Range type out of private namespace. 2015-07-22 10:58:19 -04:00
Stephen Kelly 8ea0b81d20 cmAlgorithms: Rename cmRange to cmMakeRange. 2015-07-22 10:58:19 -04:00
Brad King 18e85253c3 Merge topic 'cmRemoveDuplicates-improvement'
8701a3f4 cmRemoveDuplicates: Partially specialize the API for pointer types.
eec7091d cmRemoveDuplicates: Type-parameterize all uniq-operations
7cbafa8c cmRemoveDuplicates: Store unique iterators instead of values.
2015-03-12 15:26:37 -04:00
Brad King 15b06bc012 Merge topic 'cmAlgorithms-cleanup'
95dd238f cmRemoveDuplicates: Fix iterator -> const_iterator.
4448f175 cmInstalledFile: Move Property implementation out of line.
7916d7ba Include cmAlgorithms where it is used.
2015-03-12 15:26:35 -04:00
Stephen Kelly 8701a3f468 cmRemoveDuplicates: Partially specialize the API for pointer types.
If de-duplicating a container of pointers, there is no need to
store iterators to them, as that is just more 'pointer chasing'.

Store the pointers themselves and use API which compares the pointers
in the specialization.
2015-03-11 00:17:55 +01:00
Stephen Kelly eec7091d76 cmRemoveDuplicates: Type-parameterize all uniq-operations 2015-03-11 00:17:55 +01:00
Stephen Kelly 7cbafa8c65 cmRemoveDuplicates: Store unique iterators instead of values.
There is no need to copy all of the values in the container in
order to determine uniqueness.  Iterators can be stored instead
and can be used with standard algorithms with custom comparison
methods.

This also means that we use less space in case the value_type size
is greater than sizeof(iterator).  That is common for std::string
which may require up to 32 bytes (libstdc++ 5.0 and MSVC at least).
With libstdc++ 4.9 and older, std::string is 8 bytes, so we likely
don't gain anything here.

Inspired-by: Daniel Pfeifer <daniel@pfeifer-mail.de>
2015-03-11 00:17:55 +01:00
Stephen Kelly 95dd238f5c cmRemoveDuplicates: Fix iterator -> const_iterator. 2015-03-11 00:17:30 +01:00
Stephen Kelly 3ff95f3b0b cmAlgorithms: Add early return in cmRemoveIndices.
Avoid derefencing the iterator and segfaulting if the range
is empty.
2015-03-10 21:20:58 +01:00
Stephen Kelly 47c2da6aa8 cmAlgorithms: Cache the end iterators in algorithms. 2015-02-24 09:16:02 -05:00
Stephen Kelly a5b10ae68a cmAlgorithms: Remove needless assignment. 2015-02-24 09:16:02 -05:00
Stephen Kelly 7fd8557f4c cmAlgorithms: Maintain the pivot iterator in cmRemoveIndices.
Avoid the algorithm of 'Schlemiel the painter' in the case of
iterators which are not RandomAccess.
2015-02-24 09:16:02 -05:00
Stephen Kelly 1f79679136 cmAlgorithms: Relax iterator requirement for cmRemoveIndices.
Require only forward iterators from the range.
2015-02-24 09:16:02 -05:00
Stephen Kelly ba959934a6 cmAlgorithms: Make cmRemoveDuplicates work with more containers.
Remove the accidental requirement that the input range must be a
std::vector.
2015-02-24 09:16:02 -05:00
Stephen Kelly cae45df772 cmAlgorithms: Rename template argument to RemoveN. 2015-02-24 09:16:01 -05:00
Stephen Kelly b917f4c003 cmAlgorithms: Relax cmRemoveN requirement to FwdIter.
cmRotate already requires only FwdIter.
2015-02-24 09:16:01 -05:00
Stephen Kelly bbc1a9788d cmAlgorithms: Add a size() to cmRange.
size() is already used by cmRemoveDuplicates, which is designed to
accept a cmRange.
2015-02-24 09:16:01 -05:00
Stephen Kelly 47a3e22ea5 cmAlgorithms: Rename template type in cmDeleteAll algorithm.
It may be any range, not only a container.
2015-02-23 20:19:35 +01:00
Stephen Kelly cb75eec0b4 cmAlgorithms: Add const to const objects. 2015-02-23 20:19:35 +01:00
Stephen Kelly 4afe6c26c6 cmAlgorithms: Add cmReverseRange adaptor.
Use it to implement list(REVERSE).
2015-02-20 21:36:58 +01:00
Stephen Kelly a3a0a8c222 cmAlgorithms: Add cmFindNot algorithm. 2015-02-20 21:36:58 +01:00
Stephen Kelly 61fe1919de cmAlgorithms: Update concept requirement to FowardIterator 2015-02-20 21:36:58 +01:00
Stephen Kelly 09d6125bfe cmAlgorithms: Move cmRotate out of 'implementation detail' namespace.
This should be generally usable in cmake.
2015-02-20 21:36:58 +01:00
Stephen Kelly 37b88d348a cmAlgorithms: Add cmWrap.
Port some existing cmJoin to use it.

cmJoin is cumbersome to use in cases where the objective is to
somehow 'quote' each item and then join it with a separator.  In that
case, the joiner string is harder to read and reason about.  cmWrap
aims to solve that.

Provide an overload taking char wrappers to simplify the case
of surrounding every element in quotes without needing to escape
the quote character.
2015-02-20 21:35:58 +01:00
Stephen Kelly 10e53e2308 cmAlgorithms: Add missing const to functors. 2015-02-17 20:18:57 +01:00
Stephen Kelly 7490632258 cmAlgorithms: Remove sort of already-sorted container.
The indices is populated by an increasing number.
2015-02-17 20:18:57 +01:00
Stephen Kelly cebeed2486 cmAlgorithms: Add cmRemoveDuplicates algorithm.
Start by creating a vector to hold a unique values of the input range.  We
expect that in most cases, there will be relatively few duplicates, so
reserving enough memory for a complete copy is worthwhile.  Unlike a solution
involving a std::set, this algorithm allocates all the memory it needs
in one go and in one place, so it is more cache friendly.

Populate the unique copy with a lower_bound insert algorithm and record the
indices of duplicates.  This is the same complexity as the std::set insert
algorithm, but without the need to allocate memory on the heap and other
disadvantages of std::set.

Remove the duplicates with the cmRemoveIndices algorithm.
2015-02-15 20:46:25 +01:00
Stephen Kelly 050958a328 cmAlgorithms: Add cmRemoveMatching algorithm.
Implement it in terms of std::remove_if with a binary search through
a matching range.
2015-02-15 19:56:08 +01:00
Stephen Kelly 0b5cf0dabd cmAlgorithms: Implement algorithm for removing indexes.
Implement ContainerAlgorithms::RemoveN to remove N elements to the
end of a container by rotating.  The rotate is implemented in terms
of the efficient swap algorithm, optimized even more in the standard
library implementation when the compiler supports the rvalue-references
feature to move elements.  Implement cmRemoveN with a Range API
for completeness.

std::rotate in C++11 is specified to return an iterator, but
c++98 specifies it to return void.  libstdc++ 5.0 will be the first
version to have the correct return type.  Implement
ContainerAlgorithms::Rotate in terms of std::rotate and return the
correct iterator from it.  While std::rotate requires forward iterators,
 this workaround means cmRotate requires bidirectional iterators.  As
most of CMake uses random access iterators anyway, this should not
be a problem.

Implement cmRemoveIndices in terms of the RemoveN algorithm, such
that each element which is not removed is rotated only once.  This
can not use the cmRemoveN range-API algorithm because that would
require creating a new range, but the range must be taken by reference
and so it can't be a temporary.

These remove algorithms are not part of the STL and I couldn't find them
anywhere else either.
2015-02-15 19:04:31 +01:00
Stephen Kelly 0c12f1ea0d cmAlgorithms: Add a range adaptor and API for adjusting a range. 2015-02-11 22:57:55 +01:00
Stephen Kelly 4e78ebbdf9 cmAlgorithms: Add a Range container and adaptor method.
This can make a pair of iterators API compatible with the
cmJoin algorithm and other range-based algorithms.

Accept different iterator types in the cmRange adaptor so that
a const and non-const iterator are accepted.
2015-02-11 22:57:55 +01:00
Stephen Kelly ac26d4b343 Split cmAlgorithms into a separate header file. 2015-02-10 22:14:18 +01:00