Add an insert() method to MapVector. Adds the first MapVector unit test.

[oota-llvm.git] / include / llvm / ADT / MapVector.h

diff --git a/include/llvm/ADT/MapVector.h b/include/llvm/ADT/MapVector.h
index bad207baa90db32f018dd99d7cfb6b3bbd3686e2..f29681f644e8d6c39639352b7ba1395ae563e631 100644 (file)
--- a/include/llvm/ADT/MapVector.h
+++ b/include/llvm/ADT/MapVector.h
@@ -19,6 +19,7 @@
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/STLExtras.h"
 #include <vector>
 
 namespace llvm {
@@ -26,10 +27,10 @@ namespace llvm {
 /// This class implements a map that also provides access to all stored values
 /// in a deterministic order. The values are kept in a std::vector and the
 /// mapping is done with DenseMap from Keys to indexes in that vector.
-template<typename KeyT, typename ValueT>
+template<typename KeyT, typename ValueT,
+         typename MapType = llvm::DenseMap<KeyT, unsigned>,
+         typename VectorType = std::vector<std::pair<KeyT, ValueT> > >
 class MapVector {
-  typedef llvm::DenseMap<KeyT, unsigned> MapType;
-  typedef std::vector<std::pair<KeyT, ValueT> > VectorType;
   typedef typename VectorType::size_type SizeType;
 
   MapType Map;
@@ -63,6 +64,11 @@ public:
     return Vector.empty();
   }
 
+  void clear() {
+    Map.clear();
+    Vector.clear();
+  }
+
   ValueT &operator[](const KeyT &Key) {
     std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0);
     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
@@ -73,6 +79,40 @@ public:
     }
     return Vector[I].second;
   }
+
+  ValueT lookup(const KeyT &Key) const {
+    typename MapType::const_iterator Pos = Map.find(Key);
+    return Pos == Map.end()? ValueT() : Vector[Pos->second].second;
+  }
+
+  std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
+    std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0);
+    std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
+    unsigned &I = Result.first->second;
+    if (Result.second) {
+      Vector.push_back(std::make_pair(KV.first, KV.second));
+      I = Vector.size() - 1;
+      return std::make_pair(llvm::prior(end()), true);
+    }
+    return std::make_pair(begin() + I, false);
+  }
+
+  unsigned count(const KeyT &Key) const {
+    typename MapType::const_iterator Pos = Map.find(Key);
+    return Pos == Map.end()? 0 : 1;
+  }
+
+  iterator find(const KeyT &Key) {
+    typename MapType::const_iterator Pos = Map.find(Key);
+    return Pos == Map.end()? Vector.end() :
+                            (Vector.begin() + Pos->second);
+  }
+
+  const_iterator find(const KeyT &Key) const {
+    typename MapType::const_iterator Pos = Map.find(Key);
+    return Pos == Map.end()? Vector.end() :
+                            (Vector.begin() + Pos->second);
+  }
 };
 
 }