Merge topic 'cmListCommand-algorithms'

116459d3 cmListCommand: Avoid needlessly erasing from vectors.
1c7c35c3 cmListCommand: Replace remove duplicates loop with algorithm.
cebeed24 cmAlgorithms: Add cmRemoveDuplicates algorithm.
3cfe7a4c cmListCommand: Implement REMOVE_ITEM in terms of cmRemoveMatching.
050958a3 cmAlgorithms: Add cmRemoveMatching algorithm.
a77af8f1 cmListCommand: Replace joining loop with cmJoin algorithm.
6a22e401 cmListCommand: Use cmRemoveIndices for REMOVE_AT subcommand.
0b5cf0da cmAlgorithms: Implement algorithm for removing indexes.
069f2440 cmListCommand: Convert loop to find algorithm.
67a26764 cmListCommand: Implement REVERSE subcommand with std::reverse.
1cecd3a5 cmListCommand: Use std::find algorithm for FIND subcommand.

2 files changed, 123 insertions, 88 deletions

diff --git a/Source/cmAlgorithms.h b/Source/cmAlgorithms.h
index ad2b9c1..a996088 100644
--- a/Source/cmAlgorithms.h
+++ b/Source/cmAlgorithms.h
@@ -138,6 +138,39 @@ private:
   const_iterator End;
 };
 
+template<typename BiDirIt>
+BiDirIt Rotate(BiDirIt first, BiDirIt middle, BiDirIt last)
+{
+  typename std::iterator_traits<BiDirIt>::difference_type dist =
+      std::distance(first, middle);
+  std::rotate(first, middle, last);
+  std::advance(last, -dist);
+  return last;
+}
+
+template<typename Iter>
+Iter RemoveN(Iter i1, Iter i2, size_t n)
+{
+  return ContainerAlgorithms::Rotate(i1, i1 + n, i2);
+}
+
+template<typename Range>
+struct BinarySearcher
+{
+  typedef typename Range::value_type argument_type;
+  BinarySearcher(Range const& r)
+    : m_range(r)
+  {
+  }
+
+  bool operator()(argument_type const& item)
+  {
+    return std::binary_search(m_range.begin(), m_range.end(), item);
+  }
+private:
+  Range const& m_range;
+};
+
 }
 
 template<typename Iter1, typename Iter2>
@@ -188,4 +221,62 @@ std::string cmJoin(Range const& r, std::string delimiter)
   return cmJoin(r, delimiter.c_str());
 };
 
+template<typename Range>
+typename Range::const_iterator cmRemoveN(Range& r, size_t n)
+{
+  return ContainerAlgorithms::RemoveN(r.begin(), r.end(), n);
+}
+
+template<typename Range, typename InputRange>
+typename Range::const_iterator cmRemoveIndices(Range& r, InputRange const& rem)
+{
+  typename InputRange::const_iterator remIt = rem.begin();
+
+  typename Range::iterator writer = r.begin() + *remIt;
+  ++remIt;
+  size_t count = 1;
+  for ( ; writer != r.end() && remIt != rem.end(); ++count, ++remIt)
+    {
+    writer = ContainerAlgorithms::RemoveN(writer, r.begin() + *remIt, count);
+    }
+  writer = ContainerAlgorithms::RemoveN(writer, r.end(), count);
+  return writer;
+}
+
+template<typename Range, typename MatchRange>
+typename Range::const_iterator cmRemoveMatching(Range &r, MatchRange const& m)
+{
+  return std::remove_if(r.begin(), r.end(),
+                        ContainerAlgorithms::BinarySearcher<MatchRange>(m));
+}
+
+template<typename Range>
+typename Range::const_iterator cmRemoveDuplicates(Range& r)
+{
+  std::vector<typename Range::value_type> unique;
+  unique.reserve(r.size());
+  std::vector<size_t> indices;
+  size_t count = 0;
+  for(typename Range::const_iterator it = r.begin();
+      it != r.end(); ++it, ++count)
+    {
+    typename Range::iterator low =
+        std::lower_bound(unique.begin(), unique.end(), *it);
+    if (low == unique.end() || *low != *it)
+      {
+      unique.insert(low, *it);
+      }
+    else
+      {
+      indices.push_back(count);
+      }
+    }
+  if (indices.empty())
+    {
+    return r.end();
+    }
+  std::sort(indices.begin(), indices.end());
+  return cmRemoveIndices(r, indices);
+}
+
 #endif
diff --git a/Source/cmListCommand.cxx b/Source/cmListCommand.cxx
index dd0cfa9..98dcef1 100644
--- a/Source/cmListCommand.cxx
+++ b/Source/cmListCommand.cxx
@@ -104,19 +104,8 @@ bool cmListCommand::GetList(std::vector<std::string>& list,
     }
   // expand the variable into a list
   cmSystemTools::ExpandListArgument(listString, list, true);
-  // check the list for empty values
-  bool hasEmpty = false;
-  for(std::vector<std::string>::iterator i = list.begin();
-      i != list.end(); ++i)
-    {
-    if(i->empty())
-      {
-      hasEmpty = true;
-      break;
-      }
-    }
   // if no empty elements then just return
-  if(!hasEmpty)
+  if (std::find(list.begin(), list.end(), std::string()) == list.end())
     {
     return true;
     }
@@ -284,18 +273,14 @@ bool cmListCommand::HandleFindCommand(std::vector<std::string> const& args)
     return true;
     }
 
-  std::vector<std::string>::iterator it;
-  unsigned int index = 0;
-  for ( it = varArgsExpanded.begin(); it != varArgsExpanded.end(); ++ it )
+  std::vector<std::string>::iterator it =
+      std::find(varArgsExpanded.begin(), varArgsExpanded.end(), args[2]);
+  if (it != varArgsExpanded.end())
     {
-    if ( *it == args[2] )
-      {
-      char indexString[32];
-      sprintf(indexString, "%d", index);
-      this->Makefile->AddDefinition(variableName, indexString);
-      return true;
-      }
-    index++;
+    std::ostringstream indexStream;
+    indexStream << std::distance(varArgsExpanded.begin(), it);
+    this->Makefile->AddDefinition(variableName, indexStream.str().c_str());
+    return true;
     }
 
   this->Makefile->AddDefinition(variableName, "-1");
@@ -370,25 +355,16 @@ bool cmListCommand
     return false;
     }
 
-  size_t cc;
-  for ( cc = 2; cc < args.size(); ++ cc )
-    {
-    size_t kk = 0;
-    while ( kk < varArgsExpanded.size() )
-      {
-      if ( varArgsExpanded[kk] == args[cc] )
-        {
-        varArgsExpanded.erase(varArgsExpanded.begin()+kk);
-        }
-      else
-        {
-        kk ++;
-        }
-      }
-    }
+  std::vector<std::string> remove(args.begin() + 2, args.end());
+  std::sort(remove.begin(), remove.end());
+  std::vector<std::string>::const_iterator remEnd =
+      std::unique(remove.begin(), remove.end());
+  std::vector<std::string>::const_iterator remBegin = remove.begin();
 
-
-  std::string value = cmJoin(varArgsExpanded, ";");
+  std::vector<std::string>::const_iterator argsEnd =
+      cmRemoveMatching(varArgsExpanded, cmRange(remBegin, remEnd));
+  std::vector<std::string>::const_iterator argsBegin = varArgsExpanded.begin();
+  std::string value = cmJoin(cmRange(argsBegin, argsEnd), ";");
   this->Makefile->AddDefinition(listName, value.c_str());
   return true;
 }
@@ -414,15 +390,8 @@ bool cmListCommand
     return false;
     }
 
-  std::string value;
-  std::vector<std::string>::reverse_iterator it;
-  const char* sep = "";
-  for ( it = varArgsExpanded.rbegin(); it != varArgsExpanded.rend(); ++ it )
-    {
-    value += sep;
-    value += it->c_str();
-    sep = ";";
-    }
+  std::reverse(varArgsExpanded.begin(), varArgsExpanded.end());
+  std::string value = cmJoin(varArgsExpanded, ";");
 
   this->Makefile->AddDefinition(listName, value.c_str());
   return true;
@@ -450,24 +419,11 @@ bool cmListCommand
     return false;
     }
 
-  std::string value;
-
-
-  std::set<std::string> unique;
-  std::vector<std::string>::iterator it;
-  const char* sep = "";
-  for ( it = varArgsExpanded.begin(); it != varArgsExpanded.end(); ++ it )
-    {
-    if (unique.find(*it) != unique.end())
-      {
-      continue;
-      }
-    unique.insert(*it);
-    value += sep;
-    value += it->c_str();
-    sep = ";";
-    }
-
+  std::vector<std::string>::const_iterator argsEnd =
+      cmRemoveDuplicates(varArgsExpanded);
+  std::vector<std::string>::const_iterator argsBegin =
+      varArgsExpanded.begin();
+  std::string value = cmJoin(cmRange(argsBegin, argsEnd), ";");
 
   this->Makefile->AddDefinition(listName, value.c_str());
   return true;
@@ -549,27 +505,15 @@ bool cmListCommand::HandleRemoveAtCommand(
     removed.push_back(static_cast<size_t>(item));
     }
 
-  std::string value;
-  const char* sep = "";
-  for ( cc = 0; cc < varArgsExpanded.size(); ++ cc )
-    {
-    size_t kk;
-    bool found = false;
-    for ( kk = 0; kk < removed.size(); ++ kk )
-      {
-      if ( cc == removed[kk] )
-        {
-        found = true;
-        }
-      }
+  std::sort(removed.begin(), removed.end());
+  std::vector<size_t>::const_iterator remEnd =
+      std::unique(removed.begin(), removed.end());
+  std::vector<size_t>::const_iterator remBegin = removed.begin();
 
-    if ( !found )
-      {
-      value += sep;
-      value += varArgsExpanded[cc];
-      sep = ";";
-      }
-    }
+  std::vector<std::string>::const_iterator argsEnd =
+      cmRemoveIndices(varArgsExpanded, cmRange(remBegin, remEnd));
+  std::vector<std::string>::const_iterator argsBegin = varArgsExpanded.begin();
+  std::string value = cmJoin(cmRange(argsBegin, argsEnd), ";");
 
   this->Makefile->AddDefinition(listName, value.c_str());
   return true;