SetVector: Add front, pop_front and additional constructor.

[MatzeB]

Summary

front() and pop_front() allow convenient usage of a std::dequeue as the
underlying vector type.
The new constructor allows to pass in instances of the underlying set/vector.
This is useful when using a BitSet as the Set type to be able to initialized
it to a maximum element size.

[dblaikie]

Test cases?
Got use cases in mind? (specific new/incoming patches to LLVM projects that
will use this functionality)

& 'resize' seems like the wrong name for a set or map operation - perhaps
"reserve"? (I think there was a recent change for this rename in DenseMap,
right?)

[MatzeB]

Added unittests for the new methods and the missing tests for nearly all of the other methods.

[MatzeB]

In D18579#386552, @dblaikie wrote:

Test cases?
Got use cases in mind? (specific new/incoming patches to LLVM projects that
will use this functionality)

See http://reviews.llvm.org/D18427

& 'resize' seems like the wrong name for a set or map operation - perhaps
"reserve"? (I think there was a recent change for this rename in DenseMap,
right?)

It is still called resize() in DenseSet, SmallPtrSet and BitVector so I'd like to keep that name for consistency. Of course someone else can rename them all to reserve() in the future.

[MatzeB]

New version which does not introduce the resize() (or reserve()) operation anymore in favor of a constructor allowing to supply (empty) instances for the vector and set.

[dblaikie]

That seems like a somewhat strange API - calling reserve down into the
vector (& possibly the set, for things like DenseSet) seems more
appropriate, no?

[MatzeB]

In D18579#391254, @dblaikie wrote:

That seems like a somewhat strange API - calling reserve down into the
vector (& possibly the set, for things like DenseSet) seems more
appropriate, no?

After the discussions here I felt that reserve()/resize() are details of the underlying set not necessarily a common agreed interface supported by all sets, what if the next set implementation has additional methods for tuning? An alternative to that strange constructor would be to expose the set object so people can call reserve()/resize() on it directly though it breaks isolation.

[dblaikie]

Yeah, not sure - wouldn't mind some other voices here to see how people
feel.

Reserve isn't part of any STL concept so far as I can tell, so, yes, to
that degree it is an implementation detail.

[MatzeB]

Abandoning for lack of progress and use case. The motivating pass simply uses a combination of BitVector+Set instead of a SetVector now.

include/llvm/ADT/SetVector.h

public:
   typedef typename vector_type::const_iterator const_iterator;
   typedef typename vector_type::const_reverse_iterator reverse_iterator;
   typedef typename vector_type::const_reverse_iterator const_reverse_iterator;
   typedef typename vector_type::size_type size_type;
 
   /// \brief Construct an empty SetVector
   SetVector() {}
 
+  /// \brief Construct en empty SetVector given instances of the underlying
+  /// vector and set.
+  SetVector(Vector &&NewVector, Set &&NewSet)
+      : set_(std::move(NewSet)), vector_(std::move(NewVector)) {
+    assert(set_.empty() && vector_.empty() && "Expect empty set/vector.");
+  }
+
   /// \brief Initialize a SetVector with a range of elements
   template<typename It>
   SetVector(It Start, It End) {
     insert(Start, End);
   }
 
   ArrayRef<T> getArrayRef() const { return vector_; }
 
public:
   }
 
   /// \brief Return the last element of the SetVector.
   const T &back() const {
     assert(!empty() && "Cannot call back() on empty SetVector!");
     return vector_.back();
   }
 
+  /// Return the first element of the SetVector.
+  const T &front() const {
+    assert(!empty() && "Cannot call front() on empty SetVector!");
+    return vector_.front();
+  }
+
   /// \brief Index into the SetVector.
   const_reference operator[](size_type n) const {
     assert(n < vector_.size() && "SetVector access out of range!");
     return vector_[n];
   }
 
   /// \brief Insert a new element into the SetVector.
   /// \returns true iff the element was inserted into the SetVector.
public:
   }
 
   T LLVM_ATTRIBUTE_UNUSED_RESULT pop_back_val() {
     T Ret = back();
     pop_back();
     return Ret;
   }
 
+  /// \brief Remove the first element of the SetVector, only available if the
+  /// underlying vector type supports the pop_front() operation.
+  void pop_front() {
+    assert(!empty() && "Cannot remove an element from an empty SetVector!");
+    set_.erase(front());
+    vector_.pop_front();
+  }
+
+  T LLVM_ATTRIBUTE_UNUSED_RESULT pop_front_val() {
+    T Ret = front();
+    pop_front();
+    return Ret;
+  }
+
   bool operator==(const SetVector &that) const {
     return vector_ == that.vector_;
   }
 
   bool operator!=(const SetVector &that) const {
     return vector_ != that.vector_;
   }
 

unittests/ADT/SetVectorTest.cpp

 //===- llvm/unittest/ADT/SetVector.cpp ------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // SetVector unit tests.
 //
 //===----------------------------------------------------------------------===//
 
+#include <iterator>
+#include <deque>
 #include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/BitSet.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
+template<typename T> void BasicTest(T &X) {
+  EXPECT_EQ(X.size(), 0u);
+  EXPECT_TRUE(X.empty());
+
+  EXPECT_TRUE(X.insert(8));
+  EXPECT_TRUE(X.insert(0));
+  EXPECT_TRUE(X.insert(7));
+  EXPECT_FALSE(X.insert(0));
+  EXPECT_FALSE(X.insert(8));
+  EXPECT_TRUE(X.insert(9));
+  EXPECT_FALSE(X.insert(7));
+
+  EXPECT_EQ(X.size(), 4u);
+  EXPECT_FALSE(X.empty());
+
+  EXPECT_EQ(X.count(7), 1u);
+  EXPECT_EQ(X.count(8), 1u);
+  EXPECT_EQ(X.count(0), 1u);
+  EXPECT_EQ(X.count(9), 1u);
+  EXPECT_EQ(X.count(3), 0u);
+  EXPECT_EQ(X.count(12), 0u);
+
+  static unsigned const NElements = 4;
+  static int long const Elements[NElements] = { 8, 0, 7, 9 };
+  typename T::iterator I = X.begin();
+  typename T::reverse_iterator R = X.rbegin();
+  for (unsigned E = 0; E < NElements; ++E) {
+    EXPECT_EQ(*I, Elements[E]);
+    EXPECT_EQ(*R, Elements[NElements - 1 - E]);
+    EXPECT_EQ(X[E], Elements[E]);
+    typename T::iterator P = I;
+    ++I;
+    EXPECT_EQ(std::next(P), I);
+    EXPECT_EQ(std::prev(I), P);
+
+    typename T::reverse_iterator RP = R;
+    ++R;
+    EXPECT_EQ(std::next(RP), R);
+    EXPECT_EQ(std::prev(R), RP);
+  }
+  EXPECT_EQ(I, X.end());
+  EXPECT_EQ(R, X.rend());
+
+  EXPECT_TRUE(X.front() == 8);
+  EXPECT_TRUE(X.back() == 9);
+
+  T Y = X;
+  T Z = X;
+  X.clear();
+
+  EXPECT_EQ(X.begin(), X.end());
+  EXPECT_EQ(X.rbegin(), X.rend());
+  EXPECT_TRUE(X.empty());
+  EXPECT_EQ(X.size(), 0u);
+
+  EXPECT_EQ(Y.size(), 4u);
+  EXPECT_FALSE(Y.empty());
+
+  for (unsigned E = 0; E < NElements; ++E) {
+    EXPECT_EQ(Y.back(), Elements[NElements - 1 - E]);
+    Y.pop_back();
+    EXPECT_EQ(Y.size(), NElements - E - 1);
+
+    EXPECT_EQ(Z.pop_back_val(), Elements[NElements - 1 - E]);
+    EXPECT_EQ(Z.size(), NElements - E - 1);
+  }
+  for (unsigned E = 0; E < NElements; ++E) {
+    EXPECT_EQ(Y.count(Elements[E]), 0u);
+    EXPECT_EQ(Z.count(Elements[E]), 0u);
+  }
+  EXPECT_TRUE(Y.empty());
+  EXPECT_TRUE(Z.empty());
+}
+
+TEST(SetVector, BasicTestLongLongDefault) {
+  SetVector<long long> X;
+  BasicTest(X);
+}
+
+TEST(SetVector, BasicTestDoubleEndedQueueBitSet) {
+  SetVector<unsigned, std::deque<unsigned>, BitSet> X(std::deque<unsigned>(),
+                                                      BitSet(13));
+  BasicTest(X);
+}
+
+TEST(SetVector, PopFront) {
+  SetVector<unsigned, std::deque<unsigned>, BitSet> X(std::deque<unsigned>(),
+                                                      BitSet(83));
+
+  static unsigned const NElements = 4;
+  static int long const Elements[NElements] = { 8, 0, 7, 9 };
+  for (unsigned E = 0; E < NElements; ++E)
+    X.insert(Elements[E]);
+
+  auto Y = X;
+  for (unsigned E = 0; E < NElements; ++E) {
+    EXPECT_EQ(X.front(), Elements[E]);
+    X.pop_front();
+    EXPECT_EQ(X.size(), NElements - E - 1);
+
+    EXPECT_EQ(Y.pop_front_val(), Elements[E]);
+    EXPECT_EQ(Y.size(), NElements - E - 1);
+  }
+  for (unsigned E = 0; E < NElements; ++E) {
+    EXPECT_EQ(X.count(Elements[E]), 0u);
+    EXPECT_EQ(Y.count(Elements[E]), 0u);
+  }
+  EXPECT_TRUE(X.empty());
+  EXPECT_TRUE(Y.empty());
+}
+
 TEST(SetVector, EraseTest) {
   SetVector<int> S;
   S.insert(0);
   S.insert(1);
   S.insert(2);
 
   auto I = S.erase(std::next(S.begin()));
 
   // Test that the returned iterator is the expected one-after-erase
   // and the size/contents is the expected sequence {0, 2}.
   EXPECT_EQ(std::next(S.begin()), I);
   EXPECT_EQ(2u, S.size());
   EXPECT_EQ(0, *S.begin());
   EXPECT_EQ(2, *std::next(S.begin()));
 }
-